考慮機台與反應室限制之平行機台總延遲時間最小化之排程問題

Minimizing the total tardiness of parallel machine with machine and chamber eligibilities

蔡宗廷(Tsung-Ting Tsai)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201800237

摘要

本研究針對半導體中的蝕刻製程為研究對象，目標為考慮機台與反應室限制之平行機台總延遲時間最小化之排程問題，此問題屬於NP-Hard問題。

考慮有n個工件、m台機台、每一台機台上有3~4顆反應室(chamber)，且工件具有獨立之處理時間與到期日，每一個工件只能使用某些機台與某些機台上的某些反應室進行加工，每一個工件只能在某些機台中選擇一台機台加工，工件選定機台後就要使用該工件在該機台上所有特定之反應室進行加工，且將工件之處理時間平均分配到該機台上特定之反應室中。

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

關鍵字

平行機台 ； 機台限制 ； 反應室限制 ； 總延遲時間

並列摘要

This study is aimed to investigate the etch process in semiconductors. The goal is to consider the scheduling problem of minimizing the total tardiness of machine eligibility and chamber eligibility of parallel machine. This problem belongs to the NP-hard problem.

Suppose that there are N number of work pieces, and M number of machines. A work piece has independent processing time and the due date. 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.

There are three kinds of algorithms implemented in this study, including Integer Programming Model Algorithm, EDD 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 EDD and Heuristic Algorithm.

並列關鍵字

Parallel machine ； Machine eligibility ； Chamber eligibility ； Total Tardiness

參考文獻

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.

Anghinolfi, D., & Paolucci, M. (2007). Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Computers & Operations Research, 34(11), 3471-3490.

Cao, D., Chen, M., & Wan, G. (2005). Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Computers & Operations Research, 32(8), 1995-2012.

Cheng, C.-Y., & Huang, L.-W. (2017). Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control. Journal of manufacturing systems, 42, 1-10.

Hulett, M., Damodaran, P., & Amouie, M. (2017). Scheduling non-identical parallel batch processing machines to minimize total weighted tardiness using particle swarm optimization. Computers & Industrial Engineering, 113, 425-436.