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

Minimizing the total completion time of parallel machines with machine and chamber eligibilities

張斯閔(SSU-MIN CHANG)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201800573

摘要

本研究目標為考慮機台與反應室限制之平行機台總完工時間最小化之排程問題，針對半導體中的蝕刻製程為研究對象，考慮n個工件、m台機台、每一台機台上有三至四顆反應室(chamber)，每一個工件只能使用某些機台與某些機台上的某些反應室進行加工，每一個工件只能在某些機台中選擇一台機台加工，工件選定機台後就要使用該工件在該機台上所有特定之反應室進行加工，且將工件之處理時間平均分配到該機台上特定之反應室中，不允許搶佔的情況。

本研究屬於NP-Hard問題，並發展出三種演算法，分別為整數規劃模型、傳統派工法則(SPT)與啟發式演算法，透過小規模問題將整數規劃模型求得之最佳解與啟發式演算法求得之解進行求解品質與求解時間之比較，透過大規模問題將傳統派工法則(SPT)求得之解與啟發式演算法求得之解進行求解品質與求解時間之比較。

關鍵字

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

並列摘要

The goal of this study is to consider the scheduling problem of minimizing the total completion time of machine eligibility and chamber eligibility of parallel machine. This study is aimed to investigate the etch process in semiconductors.Suppose that there are N number of work pieces, and M number of machines. A certain work piece can only be used in a specific machine and specific chambers. Furthermore, it can only select one certain machine in a specific machine. A certain machine has 3 or 4 chambers. After the selection, this certain work piece would be processed in all the specific chambers in the certain machine, and the processing time would be evenly distributed into the specific chamber in this certain machine.
This problem belongs to the NP-hard problem.There are three kinds of algorithms implemented in this study, including Integer Programming Model Algorithm, SPT Rule and Heuristic Algorithm. The study used the small-scale questions to compare the best solution found in Integer Programming Model Algorithm with the one in Heuristic Algorithm. On the other hand, the study used the big-scale questions to compare the best solution in SPT and Heuristic Algorithm.

並列關鍵字

Parallel machine ； Machine eligibility ； Chamber eligibility ； Total Completion Time

參考文獻

Afzalirad, M. and J. Rezaeian (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. and R. L. Armacost (2004). "Minimizing makespan on parallel machines with release time and machine eligibility restrictions." International Journal of Production Research 42(6): 1243-1256.

Chung, T.-P., et al. (2010). "Scheduling on identical machines with batch arrivals." International Journal of Production Economics 123(1): 179-186.

Conway, R. W., et al. (2003). Theory of scheduling, Courier Corporation.

Costa, A., et al. (2016). "Minimizing the total completion time on a parallel machine system with tool changes." Computers & Industrial Engineering 91: 290-301.