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

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

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

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