《分散決策模式下的排序問題研究》是依託浙江大學，由談之奕擔任項目負責人的面上項目。
基本介紹
- 中文名：分散決策模式下的排序問題研究
- 依託單位：浙江大學
- 項目負責人：談之奕
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
排序是運籌學組合最最佳化領域中研究最為活躍的分支之一，分散決策模式下的排序問題是近年來受到廣泛重視的排序新課題。它與經典排序的主要區別是工件可自由選擇加工機器，而非由某個決策者統一安排。這一變化反映了網路經濟和信息通訊等排序新套用領域高度自發性和利益多樣化等新特徵對排序研究的客觀要求。本項目將深入研究若干分散決策排序新模型和新問題，核心內容是算法設計和最壞情況分析。具體包括局部排序規則的設計與分析，半分散決策模式問題，以及以工件為主體的排序性能分析等。我們還將研究套用領域一些涉及競爭和合作的具體排序問題。這些問題國際上的研究剛剛起步或起步不久，有較大難度，本項目將對它們進行前瞻性研究，獲得創新性成果。
結題摘要
排序是運籌學組合最最佳化領域中研究最為活躍的分支之一，分散決策模式下的排序問題是近年來受到廣泛重視的排序新課題。它與經典排序的主要區別是工件可自由選擇加工機器，而非由某個決策者統一安排。這一變化反映了網路經濟和信息通訊等排序新套用領域高度自發性和利益多樣化等新特徵對排序研究的客觀要求。本項目深入研究了若干分散決策排序新模型和新問題，核心內容是算法設計和最壞情況分析。主要成果包括：給出了不同類機SPT局部規則以極小化makespan為目標的問題的最壞情況界的下界，並證明了其在一定意義下的最優性；研究了以每台機器總完工時間最大值為社會費用的排序問題，給出了SPT算法的最壞情況界和改進算法；給出了SPT算法求解以總完工時間為目標函式的帶機器維護時段平行機排序問題的最壞情況界，當兩台機器均有維護時段且維護時段不重疊時SPT是最好可能的多項式時間近似算法；給出了同型機以極小化makespan和極大化機器最小負載為社會費用的排序博弈PoA以工件最大加工時間與最小加工時間比值為參數的參數緊界；對帶機器激活費用的排序博弈問題的Nash均衡有效性進行了分析，給出了PoA和PoS的參數上界和下界；討論了雙社會費用問題算法性能的評價指標等。
