考慮清理灰塵之最小化延遲工件數非等效平行機台問題

Minimizing number of tardy jobs on unrelated parallel machines with dirt cleaning activities

黃家成(Huang-Chia Cheng)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201700133

摘要

本研究探討在機台中有多個不可用性的週期非等效平行機台(unrelated parallel machines)排程問題在半導體晶圓製造上，為了避免晶圓在製造時遭受到汙染，需清理在作業時晶圓表面上所產生的灰塵。例如金屬、有機物與金屬離子...等，其主要方式是利用清洗劑來清結晶圓表面上的灰塵，灰塵會溶解於清洗劑之中，一旦清洗劑中累積的灰塵超過允許的數值，便會破壞晶圓表面，為了避免此情況發生必須更換清洗劑，才能繼續清洗晶圓之排程問題，本研究將更換清洗劑視為機台的維護活動。
本問題整合生產排程與維護活動為NP-Hard問題，首先提出了混合二進位制整數規劃模式，求得最佳解，以及啟發式演算法與模擬退火法求近似最佳解。

關鍵字

晶圓清理維護 ； 延遲工件數 ； 二元整數規劃 ； 模擬退火演算法 ； 非等效平行機台

並列摘要

This thesis considers a unrelated parallel machines scheduling problem with several unavailability periods on each machine, where the machine has to be stopped in order to change the cleaning agent. The problem appears in the process in wafer manufacturing company. Each job leaves dirt i.e., particle, organic materials and metal-ions, on the surface of the wafer while processing. The dirt is moved by dissolving in a cleaning agent. Once the accumulation of dirt is over a permitted value, it is necessary to interrupt the processing and change the cleaning agent. The objective is to minimize the number of tardy jobs. The problem integrate production scheduling and cleaning activities and is strongly NP-hard. A mixed binary integer programming model is developed to find the optimal solution and a simulated annealing heuristic is proposed to find the near optimal solution. Computational results indicate that the performance of the heuristic is ….Furthermore, the efficiency of the mixed binary integer programming model and the impact of the dirt accumulation as well as cleaning time are explored in detail.
Keywords: Scheduling; Wafer cleaning; number of tardy jobs; BIP; Simulated Ennealing; unrelated parallel machines.

並列關鍵字

Scheduling ； Wafer cleaning ； number of tardy jobs ； BIP ； Simulated Ennealing ； unrelated parallel machines.

參考文獻

Ardakan, M. A., Hakimian, A., & Rezvan, M. T. (2014). A branch-and-bound algorithm for minimising the number of tardy jobs in a two-machine flow-shop problem with release dates. International Journal of Computer Integrated Manufacturing, 27(6), 519-528.

Chen, W. J. (2006). Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. Journal of the Operational Research Society, 57(4), 410-415.

Chen, J. F. (2006). Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups. International Journal of Advanced Manufacturing Technology, 29(5), 557-563.

Chen, W. J. (2009). Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega-International Journal of Management Science, 37(3), 591-599.

Chen, W. Y., & Sheen, G. J. (2007). Single-machine scheduling with multiple performance measures: Minimizing job-dependent earliness and tardiness subject to the number of tardy jobs. International Journal of Production Economics, 109(1-2), 214-229.