《平行機分組工件排序的多面體方法》是依託鄭州大學，由原晉江擔任項目負責人的面上項目。
基本介紹
- 中文名：平行機分組工件排序的多面體方法
- 項目類別：面上項目
- 項目負責人：原晉江
- 依託單位：鄭州大學
項目摘要,結題摘要,
項目摘要
為了突破國內排序研究中數學工具和理論深度不夠而導致學科發展受阻的局面，我們建議通過研究可行解域（即排序多面體）來處理排序問題。目的是在全新的理論工具的基礎上尋求有效的多項式時間算法、近似算法和線上算法。藉助線性規劃的對偶理論、整數規劃的線性規劃鬆弛、不等式系統的全對偶整性與整多面體的關係以及原設-對偶近似算法的原理，我們將對平行機分組工件系統的離線和線上排序進行系統的研究。我們構造完工時間向量的整線性約束，並以此為基礎研究鬆弛線性約束所定義的多面體與整線性約束之間的內在聯繫。在成果表現方面，不僅要對平行機分組工件排序模型有完整的研究結果，還要對一般排序問題的多面體組合研究方法建立基本的理論構架。
結題摘要
排序論是運籌學和組合最最佳化領域極為活躍的研究分支。平行機分組工件排序則包含了豐富的經典及新興排序模型，例如：線上排序、多目標排序、工件可拒絕可退化排序、集成送貨排序、工期可指派排序等。本項目研究平行機分組工件排序問題的線上算法以及離線情形的計算複雜性與近似算法。研究成果分類如下：線上算法研究發表論文10篇、多目標排序研究發表論文4篇；工件可拒絕可退化排序研究論文5篇；集成送貨排序研究論文2篇；工期可指派排序研究論文2篇。受本項目資助共發表學術論文23篇，其中22篇論文發表於SCI期刊上。本項目的代表性成果如下：（1）對無界平行批處理機最小化時間表長允許重啟線上排序給出了競爭比為1.382的最好可能線上算法；（2）對無界平行批處理機最小化所有工件送貨完成時間線上排序給出了一個競爭比為1.828的線上算法，改進了歷史文獻中競爭比為2的線上算法；（3）對無界平行批處理機上的兩個競爭代理在相容與不相容兩種情形分別給出了不同指標下的計算複雜性分類；（4）對分組工件無界平行批集成送貨排序給出了NP-困難性證明和3/2-因子近似算法。
