《具有可分離準備時間和無等待約束的流水調度最佳化算法》是依託東南大學，由朱夏擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：具有可分離準備時間和無等待約束的流水調度最佳化算法
- 項目類別：青年科學基金項目
- 項目負責人：朱夏
- 依託單位：東南大學
中文摘要,結題摘要,
中文摘要
廣泛存在於冶金、製藥、食品加工等套用中的具有可分離準備時間和無等待約束流水調度最佳化是NP難問題。無等待流水調度中任務加工路線確定且一致，要求任務一旦開始加工便不能中斷。分析可分離準備時間獨立於調度順序(SIST)的無等待調度問題的任務間距離，推導算法基本操作的獨立變化性質；構造任務間全局/局部支配關係，設計基於此類關係的局部重排等最佳化策略。比較SIST問題與可分離準備時間依賴於調度順序(SDST) 無等待調度問題，建立後者的數學模型；構造基於機器空閒時間和準備時間的加權代價函式和緊鄰任務矩陣，提出結合緊鄰關係判斷機制的鄰域搜尋方法，設計基於多元因子性能評估的啟發式算法搜尋策略，提高算法性能；提出包含初始解、鄰域搜尋和局部解改善等三階段的全局最佳化複合啟發式算法和元啟發式算法，為兩類調度問題提供快速、有效的求解方法。本項目可推廣到實際工程套用，具有重要的科學意義和套用價值。
結題摘要
分析具有順序獨立可分離準備時間（SIST）和順序依賴可分離準備時間（SDST）的無等待調度問題性質，推導任務間距離與加工時間和準備時間等參數之間的函式關係，構造任務完工時間計算模型，並給出基於插入、刪除、移位、對換等基本運算元的多種操作的性質定理，設計m-機SIST問題任務間支配規則； 結合設計出的支配規則、最佳化策略和具有SDST/SIST約束的最小化總完工時間/最大完工時間無等待調度問題等目標函式的特點，提出多項式複雜度初始解生成算法；試驗分析高效的構造解方法；試驗分析不同插入或對換方法組合對提高解的效果，得到高效的提高解方法；試驗分析多種搜尋運算元及其組合方式，構建合理的最佳化機制，設計高效的元啟發式方法。
