《具有層次結構的多目標排序的可解性研究》是何程為項目負責人，河南工業大學為依託單位的青年科學基金項目。
基本介紹
- 中文名：具有層次結構的多目標排序的可解性研究
- 項目類別：青年科學基金項目
- 項目負責人：何程
- 依託單位：河南工業大學
項目摘要,結題摘要,
項目摘要
受信息科學與系統科學的有力推動，組合最最佳化學科呈現蓬勃發展的態勢。作為時序性組合最最佳化問題，排序理論始終處於活躍的前沿領域。隨著排序理論向深度和廣度推進，工件集表現出結構化的趨勢，如出現多批次（分批）、多代理（分族）、多階段（重新）排序等；同時，最佳化指標從單目標發展為多目標。這樣就提出一類多層次的多目標排序問題。本項目針對這類新模型，系統地研究其可解性。這裡可解性包括建立多項式時間算法（如構造同時最最佳化的全部Pareto最優解）、證明問題的難解性（如某種約束問題的NP-困難性）以及設計近似算法。在已有的研究工作中，多目標排序與多層次排序各自均有較深入的成果；而二者的結合將提出一系列富有特色的課題，拓廣多目標排序的研究領域。特別對多層次問題尋求全部Pareto最優解的劃分構造方法具有顯著創新意義。
結題摘要
受信息科學與系統科學的有力推動，組合最最佳化學科呈現蓬勃發展的態勢。作為時序性組合最最佳化問題，排序理論始終處於活躍的前沿領域。隨著排序理論向深度和廣度推進，工件集表現出結構化的趨勢，如出現多批次（分批）、多代理（分族）、多階段（重新）排序等；同時，最佳化指標從單目標發展為多目標。在已有的研究工作中，多目標排序與多層次排序各自均有較深入的成果。然而將這兩個方面結合起來的研究卻非常少見。因此二者的結合將提出一系列富有特色的課題，拓廣多目標排序的研究領域。基於此種原因，我們對具有層次結構的多目標排序的可解性進行了一系列的研究。這裡“可解性”包括建立多項式時間算法（如構造同時最最佳化的全部Pareto最優解）、證明問題的難解性（如某種約束問題的NP-困難性）以及設計近似算法。我們的研究得到了一系列的成果，得到了平行分批、序列分批的幾個多項式時間算法，設計了幾個多代理排序問題的近似算法以及與之相關的幾個結果。這些問題的解決為後續進行更難的工作奠定了堅實的基礎，提供了豐富的解決問題的經驗，特別對多層次問題尋求全部Pareto最優解的劃分構造方法具有顯著創新意義。
