《基於實例空間壓縮的minsum目標的平行機線上排序研究》是依託廈門大學，由陶繼平擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於實例空間壓縮的minsum目標的平行機線上排序研究
- 項目類別：青年科學基金項目
- 項目負責人：陶繼平
- 依託單位：廈門大學
項目摘要,結題摘要,
項目摘要
線上排序作為一種信息匱缺情況下的組合最佳化問題，廣泛存在於生產製造、並行計算及公共服務等領域。本項目針對多個 minsum 目標的平行機時間線上排序模型，分析這類問題對應的線上算法由於缺乏完整信息而所面臨的困境，挖掘相應算法所對應最差實例的特點與共性，展開以最差實例為中心的算法設計與分析。在分析問題競爭比下界時，用對手策略構造一系列特殊實例以導出較緊的下界；在設計算法時，構造基於工件優先權的線上等待策略,以保證其能兼顧到各類最差實例；在競爭分析時，通過調整任意實例的某些參數使其向最差實例可能的結構靠近，逐步將最差實例的搜尋空間從整個實例空間壓縮到更小的子集，以導出期望的競爭比。本項目不僅旨在為最小化總加權完工時間的各類平行機線上排序,以及加工時間有界的相應半線上問題,提出具有更好競爭性能的線上或半線上算法，還意在發展一種更具一般性與系統性的基於實例空間壓縮的競爭分析方法。
結題摘要
線上排序作為一種信息匱缺情況下的組合最佳化問題，廣泛存在於生產製造、並行計算及公共服務等領域。本項目針對多個 minsum 目標的平行機時間線上排序模型，分析這類問題對應的線上算法由於缺乏完整信息而所面臨的困境，挖掘相應算法所對應最差實例的特點與共性，展開以最差實例為中心的算法設計與分析。主要研究內容及相應成果包括： 1、提出並完善了一種新穎的基於實例空間壓縮的競爭比分析方法，並將該方法套用於多個 minsum 目標的平行機時間線上排序模型，設計了更好的線上算法。 2、研究了最小化總加權完工時間的同速並行機線上調度，通過擴展相應單機及非加權情況下的線上算法，提出了基於平均剩餘時間延時的AD-SWPT算法，並採用基於實例空間壓縮的分析方法，證明了該算法的競爭比為2.5-1/2m.相應成果發表在計算機與運籌學方面的優秀國際期刊《Computers & Operations Research》。 3、針對上述的2.5-1/2m算法，進一步設計了一個以機器數m為參數的算法，該算法將競爭比提高到了2.28，相應結果發表在《Journal of Industrial Management Optimization》。 4、針對加工時間有界的最小化總加權流通時間的單機半線上調度及同速並行機半線上調度，採用基於實例空間壓縮的方法分別分析了SWPT規則的競爭性能，證明了SWPT針對單機情形為最優的半線上算法，針對並行機情形其競爭比不超過P+1.5-1/2m，其中P為實例中最大加工時間與最小加工時間的比值。成果發表在《Mathematical Problems in Engineering》。 5、將基於實例空間壓縮方法套用到一個加工時間具有惡化效益的單機調度，得到了一個最優的線上算法，成果發表在《Applied Mathematics and Computation》。 本項目不僅為最小化總加權完工時間的各類平行機線上排序提出了具有更好競爭性能的線上或半線上算法，還發展了一種更具一般性與系統性的基於實例空間壓縮的競爭分析方法，該方法可以套用於其它具有類似結構的排序問題的線上算法分析。 經過三年的研究，受到該項目的資助，已發表12篇學術論文，其中5篇被SCI收錄，在項目研究進行中，培養或協助培養了多名研究生。
