線上排序問題研究中的位勢理論

《線上排序問題研究中的位勢理論》是依託中國礦業大學，由付乳燕擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：線上排序問題研究中的位勢理論
• 項目類別：青年科學基金項目
• 項目負責人：付乳燕
• 依託單位：中國礦業大學

項目摘要

為了促進國內外線上排序問題方面的研究，對於文獻中已有的關於時間線上排序模型，我們將進行深入的探討和分析，建立一套完整的位勢理論。藉助於位勢理論，我們將主要對批允許重啟的線上排序、帶有分組工件的多台平行批處理機線上排序以及一致機上的平行批線上排序等問題進行研究。在成果表現方面，我們不僅要建立一套套用性較強的位勢理論，還要在線上算法競爭比下界的實例構造和線上算法的設計兩方面尋求突破，力求在上述三種線上排序模型的研究過程中取得創新性的成果。

結題摘要

對於一個線上排序問題，我們一般通過線上算法給出排序方案，所謂最好可能的線上算法，指的是該算法的競爭比與該排序問題任意線上算法競爭比的下界相等。本項目“線上排序問題研究中的位勢理論”旨在，針對一些排序問題，給出一套完善的理論體系，用來設計線上算法並分析該算法的競爭比。通過對一些已經給出最好可能線上算法的排序問題的研究，我們得出以下結論：線上算法設計的關鍵點在於確定工件或批的開工時刻，而最好可能的線上算法中，工件或批的開工時刻與該排序問題的競爭比下界的證明過程又有著緊密的聯繫。 我們按照如下方式來定義位勢函式： 根據排序問題的目標函式，位勢函式的變數可能由工件的到達時間、加工時間、運輸時間、當前最大的開工時間等部分組成的，該函式的函式值代表的是每個等待加工的工件或批的較為理想的開工時刻。 根據位勢函式的這一特點， 結合前期的一些研究工作，我們得到了一些創新性的研究成果，主要體現在以下幾點： 　 (1) 對於工件屬於個不同工件組的單台平行機最小化最大完工時間的線上排序問題，給出了一個最好可能的線上算法，其競爭比是與工件組個數有關的，從而徹底解決了該線上排序問題。 　 (2) 對具有個不相容工件組的台平行機線上排序模型，證明了該問題所有線上算法競爭比的下界約為1.618，並且給出了一個線上算法。當m=2或者同一組工件具有相同加工時間時，該算法是一個最好可能的線上算法；當m＞2時，該算法的競爭比約為1.707。該結果將具有不相容工件族的平行批處理機最小化最大完工時間的線上排序模型推進到的情形，對該問題的一般情形下的徹底解決具有很好的借鑑意義。 (3) 對於帶有運輸時間的單台平行批處理機，目標函式是最小化最大運輸時間的線上排序模型，給出了一個競爭比約為1.828的線上算法。該結果第一次給出了一般情形下一個競爭比小於2的線上算法，對進一步徹底解決該問題有很重要的借鑑意義。 另外，對批容量不等的多台平行批處理機上的線上排序問題以及多目標排序問題，我們也給出了創新的研究結果。