帶有限等待的動態HFS調度的拉格朗日松弛算法

作者：軒華

摘要：作為基于最優化的近似算法,分析了拉格朗日松弛算法的分解策略,設計了算法的實現優化過程。針對從鋼鐵生產提煉出的帶有限等待時間要求的動態HFS調度,采用基于工件解耦的分解策略,應用拉格朗日松弛算法進行求解,以最小化總加權完成時間和工件等待懲罰之和。該算法將工件耦合約束松弛到目標函數中,將形成的松弛問題分解成多個更易求解的工件級子問題,進而利用動態規劃求解這些子問題,通過拉格朗日乘子的更新迭代過程獲得原問題的近優解。對不同問題規模的測試結果表明,該算法能在較短的計算時間內得到較好的近優解,說明了拉格朗日松弛算法求解等待時間受限的HFS調度的可行性和有效性。

發文機構：鄭州大學管理工程系

關鍵詞：動態HFS調度有限等待約束運輸時間工件分解拉格朗日松弛dynamic hybrid flowshop schedulinglimited-wait constaintstransportationtimejob decompositionLagrangian relaxation

分類號： TB49[一般工業技術]