- 學位論文
使用模擬退火演算法求解混合型 機台之排程問題
Problems of scheduling on mixed machinery using simulated annealing heuristic
摘要
本研究為探討混合型機台排程問題，混合型機台包含多組雙機流程型機台及平行機台。每個工件皆可從兩種機型選擇一種機型之一組機器進行加工。雙機流程型第一台機器與第二台機器之間設有Limited buffer，若第一機工件加工完畢預備至第二機加工時，第二機尚有工件進行加工，則第一機加工完畢之工件必須等待，待第二機工件加工完畢；若工件等待時間超出緩衝限制，則此工件在第一機的開始時間必須延遲。 本研究求解目標為最小化最大完成時間，已被證明為NP-hard問題。本研究提出一個混合整數規劃模型及兩種模擬退火法SA1與SA2。在小工件數問題計算SA1與SA2 的誤差率進行比較，大工件數則計算SA2對SA1的差距比例進行比較及分析。SA1與SA2差異處在於，SA1利用啟發式演算法之Makespan做為SA1的起始值，同時，Johnson's rule排序的工件指派順序作為起始解，透過隨機兩兩順序位置上工件交換產生鄰解，藉以達到調整工件指派順序求得近似最佳解；SA2則透過啟發式演算法所求得之解進行隨機機台上工件交換的方式求得近似最佳解。 實驗數據結果顯示影響SA1及SA2在大小工件數實驗的求解表現最主要因素為工件數與機台數比例(n/m)，而Limited buffer影響SA1及SA2求解表現不顯著，此外ANOVA分析結果也顯示Limited buffer之P-value >α(0.05)，表示Limited buffer因子不顯著，因此兩種方法在不同的Buffer size下，求解能力不受影響。
並列摘要
This research addresses the problem of scheduling jobs on hybrid machine types. There are multiple sets of old two-machine flowshop as the first type and parallel machines as the second type. A job is either processed on an old two-machine flowshop or on a new single machine. When the job is processed on the two-machine flowshop, there is limited intermediate time between the two machines. The objective is to determine a production schedule for all jobs so as to minimize the Makespan. The problem is denoted to which is NP-hard since the two parallel machines problem was proved to be NP-hard. A Mixed Integer Programming model is developed to solve the problem optimally and two simulated annealing approaches, SA1 and SA2, are proposed to obtain a near optimal solution. Computational results indicate that the performance of the Simulated Annealing is robust. Furthermore, the impact of number of machines and Jobs are explored in detail are reported.