《兩類複雜機器環境的現代排序研究》是依託杭州電子科技大學，由張安擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：兩類複雜機器環境的現代排序研究
- 項目類別：青年科學基金項目
- 項目負責人：張安
- 依託單位：杭州電子科技大學
項目摘要,結題摘要,
項目摘要
現代排序的發展趨勢是機器的環境趨於複雜化，其中機器有禁用區間和機器帶加工許可權是兩類典型情形，本項目主要研究這兩類複雜機器環境的現代排序，核心內容是近似算法、線上算法的設計與分析．對有禁用區間的排序問題，重點研究機器環境為平行機或者目標函式為極小化（賦權）總完工時間的情形，研究禁用區間周期性出現、禁用區間可移動和隨機禁用區間等模型，並分析工件可恢復、工件可跨越對算法設計和算法性能的影響．對帶加工許可權的排序問題，研究問題的計算複雜性和可近似性，研究線上算法的設計和競爭比的分析，特別是預知部分信息的（半）線上模型和工件實時到達的線上模型，考慮設計問題的最優算法．我們還將開展帶加工許可權排序的套用研究．對這些問題的研究一方面有益於排序理論的發展，另一方面也為排序到實際套用中的轉化和推廣提供技術支撐．因此本項目的研究既有理論價值，又有實際意義，是一項有創造性和前瞻性的研究工作．
結題摘要
基於現代排序研究複雜機器環境的趨勢，本項目重點考慮了兩類典型情形：機器有禁用區間的排序和機器帶加工許可權的排序，項目從問題的計算複雜性、算法設計與分析等方面對這兩大類問題進行了深入研究。當兩台平行機上有禁用區間、加工不可恢復、目標為極小化總完工時間時，分析了不同禁用區間分布下SPT算法的最壞情況性能比；當單台機上有一個操作禁用區間，即允許工件跨越禁用區間加工時，證明了極小化總完工時間的問題是一般NP-hard的，設計了不同於SPT的近似算法，並給出了算法最壞情況性能分析；當機器帶有等級型加工許可權、目標為極小化最大完工時間時，設計了工件可分割情形的線上算法，並基於線性規劃對偶原理證明了算法的最優性；對三台機兩個等級的可中斷排序，分別設計了允許引入空閒和不允許引入空閒的線上算法，並證明了算法的競爭比；對兩台機、工件加工時長落在區間[p, rp]的半線上排序，設計了對任意r都是最優的線上算法並給出了算法的參數競爭比。此外，項目還研究了混合車間作業排序、加工與運輸協作排序等其他複雜機器環境的排序問題，取得了許多算法和複雜性方面的理論結果。本項目的這些研究都是當前國際上排序研究的熱點問題，通過本項目研究不僅豐富了排序理論的研究內容，而且發展了近似算法、線上算法的設計方法和分析技巧，達到了項目的預期目標。
