《基於無衝突集的約束Job Shop調度最佳化算法》是依託東南大學，由李小平擔任項目負責人的面上項目。
基本介紹
- 中文名：基於無衝突集的約束Job Shop調度最佳化算法
- 項目類別：面上項目
- 項目負責人：李小平
- 依託單位：東南大學
中文摘要,結題摘要,
中文摘要
無等待或阻塞的約束Job Shop調度是NP難問題，廣泛存在於冶金、製藥、食品加工等套用中。無等待Job Shop中任務加工路線確定但不一致，要求任務一旦開始加工便不能間斷；阻塞Job Shop中任務加工路線確定且不一致，任務加工過程中如果某一操作所需機器不可達則造成阻塞。基於無等待和阻塞Job Shop調度問題的結構特點，分析任務間可行開始時間所形成無衝突集的性質；提出無衝突集的多項式計算方法，大大減少基於無衝突集時間表算法的計算時間，提高算法效率；提出分組-重構時間表安排策略，設計任務的移動代價評估機制，確定任務的移動方向（前向或後向）和範圍，壓縮機器空閒時間，提高算法性能；提出包含初始解、鄰域搜尋和局部解改善等三階段的全局最佳化複合啟發式算法，為無等待和阻塞Job Shop調度問題提供快速、有效的求解方法。本項目可推廣到捷運調度等實際工程套用中，具有重要的科學意義和套用價值。
結題摘要
針對最小化最大完工時間的無等待Job Shop和阻塞Job Shop調度問題，提出有效的求解方法。將問題分解為時間表問題和排列問題，分析無等待和阻塞Job Shop的結構特點和無衝突集性質，主要目的是從以下幾方面提高算法效率：（1）研究任務間距離的特點，基於任務間的可行開始時間形成無衝突集，採用分治法在多項式時間內求解給定排列的最優時間表，大大減少算法的計算時間；（2）建立基於可行時間差集的問題模型，提出基於移動懲罰的時間表方法，對時間表壓縮以進一步最佳化時間表；（3）研究有效的鄰域構造方法，提出包含初始解、鄰域搜尋和局部解提高等三階段的全局最佳化複合啟發式算法。
