《帶等級約束的半線上調度問題模型與算法研究》是依託大連理工大學,由陳鑫擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：帶等級約束的半線上調度問題模型與算法研究
- 依託單位：大連理工大學
- 項目類別：青年科學基金項目
- 項目負責人：陳鑫
項目摘要,結題摘要,
項目摘要
平行機線上調度問題（又稱排序問題）是組合最佳化領域和理論計算機科學領域的熱點問題之一。帶等級約束的調度問題，由於能很好的反映現實中的約束關係，已引起國內外學者的廣泛關注。現有文獻已給出大量關於該問題很好的結果，但考慮到實際生產環境的複雜性與半線上形式的多樣性，仍有一系列複雜的問題亟待解決。本項目考慮兩類帶等級約束的半線上調度模型：緩衝區模型和允許任務重排模型。將分析模型的競爭比下界、設計競爭比接近以至匹配該下界的半線上算法，進而討論兩個模型相關結果之間的關聯。研究過程由簡入繁，先從兩等級兩台同類機的情況入手，進而研究兩等級多台機器的情況，最終考慮多等級多台機器這種最複雜、卻又最接近於實際生產環境的情況。課題的成功實施，能夠補充帶等級約束調度問題的現有成果，拓展平行機調度問題的研究範疇，為調度模型的實際套用打下更為堅實的理論基礎。
結題摘要
調度問題（又稱排序問題）是運籌學、管理科學、計算機科學等領域的經典問題之一，其研究內容為如何將有限的資源、在滿足一定約束條件的情況下、分配給一系列的任務，以追求某個或者多個最最佳化目標。三年來，項目組對項目《帶等級約束的半線上調度問題模型與算法研究》進行了持續研究，共發表文章14篇，其中SCI檢索5篇、EI檢索6篇、核心期刊3篇。主要取得如下成果： 1、研究了在等級約束下、帶緩衝區的半線上調度模型和允許任務重排的半線上調度模型，分別給出上下界一致的半線上算法； 2、研究了在等級約束下、允許有限個任務隨時重新調整的半線上調度模型，並給出最優算法； 3、研究了在等級約束下、獲知任務部分信息的半線上調度模型，分析模型下界並給出匹配下界的最優算法； 4、改進了帶緩衝區的半線上調度問題的某些算法，獲得了比前人性能更好的算法。 除了上述計畫內的研究內容，在基金的支持下，項目組還獲得了其他一系列好的成果。 1、調度問題雖然具有不同的最最佳化目標，但由於其問題本身的相似性，研究方法上具有一定的借鑑性。因此，項目組首次研究了最小化任務損失的線上模型，獲得了最好可能算法； 2、除了理論分析之外，項目組還設計了平行機調度問題、DAG調度問題的（元）啟發式算法，並通過實驗對比驗證了算法的優勢。 總之，項目組很好的完成了立項中的問題，拓展了調度問題的研究範疇，並為調度問題的進一步研究打下了基礎。
