排序問題的博弈分析和多目標排序

《排序問題的博弈分析和多目標排序》是依託浙江大學，由談之奕擔任項目負責人的面上項目。

基本介紹

• 中文名：排序問題的博弈分析和多目標排序
• 依託單位：浙江大學
• 項目負責人：談之奕
• 項目類別：面上項目

項目摘要

排序理論是運籌學組合最最佳化領域中研究最為活躍的分支之一，本項目將深入研究排序的兩個新課題：排序問題的博弈分析和多目標排序問題，核心內容是算法設計和最壞情況分析。對排序博弈，研究均衡排序的存在性及其性質，設計符合要求的排序機制。對多目標排序問題，考慮算法的雙目標最壞情況界，以及多組競爭工件、工件或機器可選擇等模型。我們還將研究套用領域的一些具體排序問題。對以上這些問題，我們將探討它們的計算複雜性、多項式時間近似方案的存在性或難近似性，以及快速近似算法的設計。這些問題國際上的研究剛剛起步或起步不久，有較大難度，本項目將對它們進行前瞻性研究，獲得創新性成果。

結題摘要

排序理論是運籌學組合最最佳化領域中研究最為活躍的分支之一，本項目主要研究排序問題的博弈分析和多目標排序問題，核心內容是算法設計和最壞情況分析。三年來，項目組在排序博弈的均衡有效性分析、多目標排序以及相關排序問題的研究中取得了一系列成果。對同類機整體目標為最小機器完工時間，工件費用為所在機器的完工時間的排序博弈，我們給出了兩台機時以機器速度比為參數的PoA，SPoA，PoS和SPoS的參數緊界，三台機一種特殊情況下的PoA值。對兩台同類機，局部機制為並行加工，分別給出了整體目標為makespan和最小機器完工時間時PoA的參數緊界。我們研究了以機器數和makespan之和為目標函式的平行機線上排序問題，改進了問題的下界，並設計了新的算法。對極小化每台機器上加工工件總完工時間的最大值的平行機排序問題，我們研究了問題的複雜性，給出了SPT算法最壞情況界新的上界與下界，並設計了最壞情況界為2的新算法，且該算法同時可使總完工時間達到最小。我們還考慮了目標為極小化總完工時間的有機器維護時段的排序問題，給出了不同維護時段設定下平行機排序問題SPT算法最壞情況界的估計。當機器台數為2且每台機器上只有一個維護時段時，證明了SPT算法是最壞情況界最小的多項式時間近似算法。對單台機，機器上有一個不可操作時段，目標為極小化總完工時間問題，設計了最壞情況界較小的近似算法。對單台機，半可恢復維護時段問題，我們討論了不同目標函式下問題的複雜性和近似算法。