在平行機台下考慮反應室與機台限制求最小化最大完工時間之排程問題

Minimizing makespan on parallel machines with chamber and machine eligibility

高碩謙(Shuo-Chien Kao)

指導教授 ： 蘇玲慧

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2018年)

https://doi.org/10.6840/cycu201800238

摘要

本研究探討平行機台(Parallel Machine)上考慮機台限制(Machine Eligibility)與反應室限制(Chamber Constraints)的排程問題，針對半導體產業中的蝕刻製程技術的排程問題為探討方向。本研究有m個機台與n個工件，每一個工件只能在特定的機台上以及只能在特定的機台上的反應室上加工，工件的處理時間為已知，當工件開始作業時，不允許被搶斷，工件只能選擇一個機台加工，每一個機台裡都含有反應室(Chamber)3-4顆，當工件放入該機台的反應室(Chamber)上時，處理時間會平均分配到該機台的各個反應室上，且計算各個機台上的反應室之最後一個時間點為完工時間，目標為最小化最大完工時間。
由於本問題屬於NP-hard問題，本研究在小規模問題時提出一個整數規劃模型求出最佳解，在與啟發式演算法求出的近似解進行比較，結果顯示與最佳解相比，平均誤差為3.64%，也比數學規劃模式求解時間短，在探討大規模問題時，啟發式演算法與傳統派工法則LPT(Largest Processing Time)相比，啟發式演算法的解也比LPT的解好，平均改善率為4.61 %。

關鍵字

平行機台 ； 最小化最大完工時間 ； 機台限制 ； 反應室限制

並列摘要

This study investigates scheduling problem related to machine eligibility and chamber constraints on a parallel machine, and discusses the scheduling of etching process technology in the semiconductor industry. The number of machines and that of jobs under investigation are m and n respectively. Each job can only be processed on a specific machine and only on the chamber of the specific machine. The processing time of the job is known. When the job starts to work, it is not allowed to be intercepted. Each job is allocated to one machine. Each machine contains 3-4 chambers. When jobs are placed in the chamber of the machine, their processing time will be evenly distributed to each chamber of the machine .The job completion time of the chamber on each machine will be calculated. The goal is to minimize the makespan.
Because this problem is the NP-hard problem, for the small-scale problem, this study proposes an integer programming model to find the best solution. Compared with the approximate solution obtained by the heuristic algorithm, the results show that compared with the optimal solution, the average deviation is 3.64%, which is shorter than the solution time of the mathematical programming model. For large-scale problems, the heuristic algorithm has a solution better than the Largest Processing Time(LPT). The average improvement rate is 4.61%.

並列關鍵字

Parallel machine ； minimize the makespan ； machine eligibility ； chamber constraints

參考文獻

1.Afzalirad, M., & Rezaeian, J. (2016). Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions. Computers & Industrial Engineering, 98, 40-52.

2.Behnamian, J., Zandieh, M., & Ghomi, S. F. (2009). Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications, 36(6), 9637-9644.

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

4.Fanjul-Peyro, L., & Ruiz, R. (2012). Scheduling unrelated parallel machines with optional machines and jobs selection. Computers & Operations Research, 39(7), 1745-1753.

5.Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM journal on Applied Mathematics, 17(2), 416-429.