相依整備時間考量下具等效平行機台之多階段流程型排程問題啟發式求解模式建構

Heuristic for Flowshop Scheduling with Identical Parallel Machine and Dependent Setup Times Consideration

葉玉玲(Yuk-Ling Yip) ； 許洲榮(Chou-Jung Hsu) ； 蔡碧芳(Pi-Fang Tsai)

《技術學刊》 20卷3期 (2005/09) Pp. 297-304

https://doi.org/10.29507/JT.200509.0009

摘要

在生產系統中，每一製程若由一台以上同種類型的機器設備所組成，則如何完成各製程中工件之指派以及各機台上工件加工順序之安排即所謂的等效平行機台排程問題。本研究即針對具相依整備時間之等效平行機台流程型排程問題，在以總流程時間最小化之目標下，建構以模擬退火法爲基之啟發式演算法SATS，以快速尋求到一近似解。爲了保持所建構演算法SATS求解之穩定性，本研究針對影響演算法之參數進行分析並建議其最佳之演算參數設定。而爲驗證SATS之正確性與適用性，本研究亦將SATS分別在數種小問題規模下與數學模式之最佳解進行比較分析；至於在中、大問題規模之求解上則與傳統模擬退火法及禁忌搜尋法進行求解績效差異之比較。研究結果顯示，本研究所提出之SATS演算法，能夠迅速獲得一近似解，具有不錯之求解品質與效率。

關鍵字

等效平行機台 ； 相依整備時間 ； 流程型排程 ； 總流程時間 ； 模擬退火法

並列摘要

In this study, an identical parallel machine flowshop scheduling problem, in which the dependent setup time is taken into account, is considered with minimization of total flowtime. The addressed flowshop scheduling problem, is more complex than traditional flowshop scheduling problems since, in the addressed flowshop scheduling problem both machine assignment and job sequencing problems are considered simultaneously. To solve the addressed problem, a hybrid heuristic, which is combined with simulated annealing and tabu search, is proposed to get a near optimal schedule in a reasonable computation time. During the study, the parameters used in the heuristics that affect the solution quality and efficiency are analyzed and designed; then for the constructed heuristic, a good parameter setting is suggested. The experimental results are reported, and provided as the reference for the further research.

並列關鍵字

identical parallel machine ； flowshop ； dependent setup time ； total flowtime ； simulated annealing