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

Minimize the total weighted completion time on parallel machines subject to machine and chamber eligibilities

凃宥安(Yu-An Tu)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201800356

摘要

本研究探討平行機台上考慮機台限制與反應室限制之排程問題，目標為求最小化加權總完工時間，主要研究半導體製程中蝕刻技術的排程問題。本研究考慮共有 n 個工作 m 個機台，每個機台上有三或四顆反應室(Chamber)，每個工作的處理時間(P_j)以及權重(L_j)為已知，工作可以使用的機台與反應室也皆為已知，每個工作只能使用特定機台上的特定反應室進行作業，工作只能選擇一個機台進行處理，而工作選擇了機台後，便只能使用該機台上的反應室加工，且中途不允許被搶斷，並將處理時間平均分配到該機台上的特定反應室中。
由於此類排程問題屬於NP-Hard問題，因此本研究提出三種演算法，分別為整數規劃模式、啟發式演算法，以及傳統派工法則WSPT(Weighted Shortest Processing Time)，在小規模問題時，透過整數規劃模式所求得之最佳解與啟發式演算法所得到的解相比，進行求解誤差與求解時間上的比較；大規模問題的部分，則是將傳統派工法則WSPT法則求得的解與啟發式演算法所求之解作比較，同樣進行求解誤差與求解時間上的分析。

關鍵字

加權總完工時間 ； 平行機台 ； 機台限制 ； 反應室限制

並列摘要

This study investigates the scheduling issue of etch techniques in semiconductor processes, in which with machine eligibility and chamber eligibility are considered. The objective is to minimize the total weighted completion time on parallel machines. Each machine contains 3-4 chambers. Each job can only be processed on the certain chambers of the specific machine. After selecting the machine, it can only be processed by the chamber on the machine, and no interruption is allowed.
The problem is NP-Hard, this study proposes three algorithms to solve the problem: Integer Programming model, heuristic algorithm, and WSPT rule. In the case of small-scale problems, the optimal solution obtained by Integer Programming model is compared with the solution of the heuristic algorithm. On the other hand, in the case of large-scale problems, the solution for WSPT rule is compared with the solution of the heuristic algorithm.

並列關鍵字

total weighted completion time ； Parallel machines ； machine eligibility ； chamber eligibility

參考文獻

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.

Centeno, G., & Armacost, R. L. (2004). Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research, 42(6), 1243-1256.

Cheng, B., Yang, S., Hu, X., & Chen, B. (2012). Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes. Applied Mathematical Modelling, 36(7), 3161-3167.

Eastman, W. L., Even, S., & Isaacs, I. M. (1964). Bounds for the optimal scheduling of n jobs on m processors. Management science, 11(2), 268-279.

Huo, Y., & Zhao, H. (2018). Two machine scheduling subject to arbitrary machine availability constraint. Omega, 76, 128-136.