《加工時間可控排序問題及依賴資源指派問題研究》是依託瀋陽航空航天大學，由王吉波擔任項目負責人的面上項目。
基本介紹
- 中文名：加工時間可控排序問題及依賴資源指派問題研究
- 項目類別：面上項目
- 項目負責人：王吉波
- 依託單位：瀋陽航空航天大學
項目摘要,結題摘要,
項目摘要
運用運籌學方法、計算機算法分析和數值仿真來研究工件加工時間可控的排序問題與依賴資源指派問題模型，並對這些複雜模型進行理論分析和仿真研究，以求深刻理解這些問題的本質。1.研究完工時間費用為加權完工時間平方和、加權總延遲時間、一些非正則等更複雜實用的目標函式及資源凸函式有界條件下極小化加權總完工時間等若干未解決的問題；2. 對於NP-難問題，主要基於列生成的分支定界法研究小規模問題的最優算法，大規模問題的啟發式算法和基於軟計算的搜尋算法等來設計高速有效的近似算法及啟發式算法；3.依賴資源指派問題中，指派費用函式為線性函式和凸函式的情況下，研究總指派成本和總資源消耗成本的各種組合下，這些問題的計算複雜性和提出最佳化算法。工件加工時間可控的排序問題與依賴資源指派問題更為實用，也更為複雜，絕大多數都是NP-難的，通過探討可行排序或最優排序的局部及整體性質和數量關係，建立系統有效的計算方法和基本理論。
結題摘要
工件加工時間可控的排序問題與依賴資源指派問題在鋼鐵製造業及醫療救助業等方面有著廣泛的套用，是當今國際研究的熱點問題之一。本項目的研究成果主要包括三方面內容：(1)工件的加工時間與開工時間有關的可控排序。考慮單機成組可控排序問題， 對凸資源分配模型，在總資源有限的基礎上極小化最大完工時間問題，證明了一種特殊情況是多項式時間可解的。此外對於一般情況，給出了一個啟發式算法和分支定界算法。(2)工件加工時間與所排位置有關的可控排序問題。研究了單機情況下具有截斷學習效應的可控排序問題。對一系列正則排序目標和資源的費用目標的四種組合情況分別給出了求解算法。對成組情況的單機可控排序問題，對凸資源分配模型，在總資源有限下的最大完工時間極小化問題，給出了求解算法。(3) 工件加工時間同時與所排位置（學習效應）、開工時間（惡化效應）和資源有關的可控排序問題。提出了工件加工時間與開工時間、所排位置和所用資源都有關係的可控排序問題。在單機和不相關平行機情況下，對一些排序目標和資源目標下的各種組合分別進行了分析，證明了一系列問題都存在多項式時間最優算法，對找不到多項式時間算法的問題給出了啟發式算法和分支定界算法。
