使用模擬退火演算法求解Just-in-time工作權重個數最大化之排程問題

本研究主旨在探討無相關平行機台（unrelated parallel machines）上工作不允許佔先（preemption）之排程問題研究，而研究目標為完成時間剛好為該工作交期之工作權重數量最大化。每個工作具有不同的抵達時間，每個工作還須考量機台限制的條件，也就是工作必須由指定的機台集合中的任一機台上進行加工，機台具有可利用時間限制的條件，以及工作具有順序相依性的整備時間（sequence-dependent set-up time），每個工作會因為排入機台上的前一個工作不同，而需要不同的整備時間。本研究目的為針對此問題擬提出啟發式演算法H1，並將所得啟發解作為模擬退火法（simulated annealing）之起始解，近而求得滿意的近似最佳解，並將此結果與陳科甫（2009）使用網路流量（network flow）進行求解之最佳解進行比較，並透過模擬實驗來分析此啟發解之求解品質。模擬退火法在工作數為20時，經實驗設計分析測試，參數因子具有顯著效果，但當工作數為40時，經實驗設計分析測試，參數因子皆無顯著效果，因此本研究中直接使用啟發式演算法H1與數學規劃模式比較求解誤差，經由實驗結果得知，平均求解誤差為3.39 %，求解效率實驗結果得知啟發式演算法H1的平均求解時間約8.99秒，陳科甫（2009）之平均求解時間為662.611秒。

關鍵字

模擬退火；排程；無相關平行機台； Just-in-time

並列摘要

We consider the unrelated parallel machines with sequence-dependent setup times problem. The objective is using Simulated Annealing to maximize the weighted number of jobs that are completed exactly at their due date. Each job has different arrival time and can only be processed on specified machines. Each machine is not continuously available at all times. Setup magnitude of a job depends on its immediately preceding job on the same machine. And we compared with Chen （2009） to find the deviation . And the computation result will be report.

並列關鍵字

Unrelated parallel machine ； Simulated Annealing ； Just-in-time

參考文獻

陳科甫 (2009), “平行機台下Just-in-time工作權重個數最大化之排程問題”.

Andresen M., Brasel H., Morig M., Tusch J., Werner F., Willenius P., (2008), “Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop,” Mathematical and Computer Modelling, 48, 1279–1293.

Baker K.R., (1974), “Introduction to Sequencing and Scheduling,” Wiley, New York.

Breit J., Schmidt G., Strusevich V. A., (2001), “Two-machine open shop scheduling with an availability constraint,” Operations Research Letters 29, 65–77.

Centeno G., Armacost R.L., (1997), “Parallel machine scheduling with release time and machine eligibility restrictions.” Computers & Industrial Engineering, 33（1-2）,273-276.

國際替代計量

使用模擬退火演算法求解Just-in-time工作權重個數最大化之排程問題

全文下載

主題瀏覽