基于最優解下限的單工序平行機排序啟發式算法

作者：樸惠淑,賈春玉,常留賢

摘要：針對單工序平行機排序LPT方法計算步驟多等問題,提出了一種適用于中小企業現場排序的最優解下限截取啟發式算法。傳統平行機排序最優解下限表達式存在因偏離最優解過大而難以引導排序走向最優的缺陷,改進后的下限表達式更加接近于最優解。從計算步驟多少和偏離最優解下限的最大偏差率兩個角度,比較分析了最優解下限截取法與LPT法的特點。經實驗數據驗證,得出零件數與平行機數之比非整除且滿足一定條件時,簡單易行的截取法更優于LPT法的結論。

發文機構：大連海事大學交通運輸管理學院 寧波工程學院經濟與管理學院 電子科技大學中山學院

關鍵詞：平行機排序最優解下限LPT法截取法parallel machine schedulinglower bound of optimum solutionLPT methodintercept method

分類號： F224.3[經濟管理—國民經濟]