《線上和離線折衷排序研究》是依託鄭州大學，由原晉江擔任項目負責人的面上項目。
基本介紹
- 中文名：線上和離線折衷排序研究
- 項目類別：面上項目
- 項目負責人：原晉江
- 依託單位：鄭州大學
項目摘要,結題摘要,
項目摘要
折衷排序是排序領域的重要研究方向，近年來又有新的發展。針對多個排序指標，在離散情形，折衷排序要求刻畫所有Pareto最優點，而在連續的情形，折衷排序要求刻畫trade-off曲線。本項目研究多指標下的線上和離線折衷排序，包括經典折衷排序、多代理折衷排序以及折衷重新排序。目的是在全新的理論工具的基礎上尋求有效的多項式時間算法、近似算法和線上算法。對離線情形進行複雜性分析、並設計多項式時間算法及多項式時間近似算法生成問題的所有Pareto最優點或trade-off 曲線。對線上情形在分析時間位勢與最佳化指標之間的內在聯繫的基礎上設計具有良好trade-off競爭比的線上算法。在成果表現方面，對離線折衷排序給出完整的研究結果，並對線上折衷排序建立基本的理論構架。
結題摘要
折衷排序是排序領域的重要研究方向，發展新的研究方法並用來求解各種具有理論意義和套用前景的多指標排序模型是本項目的實施要點。本項目對摺衷排序進行了深入的研究，得到了較為系統的研究進展。對離線折衷排序我們在發展各種ε-約束變異方法的前提下對重新排序、雙代理排序、分批排序等模型中的多個典型的折衷排序問題給出了強多項式時間算法，部分結果突破了文獻中的弱多項式時間算法；在雙指標排序的計算複雜性研究中我們解決了多個歷史遺留問題並對以最大延遲作為基準目標的排序反問題以及具有工件最大允許錯位的重新排序模型進行了系統的研究；在折衷排序的線上算法和近似算法方面，我們研究了“時間表長與加權完工時間和的折衷”、“時間表長與最大延遲的折衷”、“總完工時間和與拒絕費用的正組合”、“加工與送貨兩階段排序”等排序問題，得到了性能良好的線上算法和近似算法。受本項目資助共發表SCI期刊學術論文40篇。代表性成果如下：（1）對最小化工件錯位總和與時間表長的 Pareto 最優重新排序，創建了跳躍式ε-約束變異方法，並由此得到求解全部 Pareto 最優點的強多項式時間算法；（2）對工件具有到達時間並可中斷最小化兩個代理的最大延遲的Pareto 最優排序問題，建立了Pareto 最優排序的EDD順序下的Pmtn-List排序結構，然後利用工件輪廓的構思確定出所有的Pareto 最優點，進而在多項式時間求解了所研究的問題；（3）證明了單機最小化總提前及延誤量問題以及GDD假設下單機最小化工件加權總誤工問題的強 NP-困難性，從而解決了兩個上世紀80年代遺留至今的計算複雜性問題；（4）提出並研究了折衷線上排序，並對單機同時最小化時間表長與加權完工時間和的折衷線上排序問題給出了具有最好可能的Trade-off競爭比的線上算法。
