考慮清理灰塵之最小化總延遲時間單機排程問題

Minimizing the tardiness on a single machine with dust accumulation consideration

鍾隆鑫(Lung-Hsin Chung)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201500206

摘要

本研究探討單一機台(Single-machine)在半導體晶圓製造上，為了避免晶圓在製造時遭受到汙染，需清理在作業時晶圓表面上所產生的灰塵，例如金屬、有機物與金屬離子...等，其主要方式是利用清洗劑來清結晶圓表面上的灰塵，灰塵會溶解於清洗劑之中，一旦清洗劑中累積的灰塵超過允許的數值，便會破壞晶圓表面，為了避免此情況發生必須更換清洗劑，才能繼續清洗晶圓之排程問題，本研究將更換清洗劑視為機台的維護活動。考慮N個工件在機台上加工，每個工件有各自的處理時間、交期及產生的灰塵量，且機台有其最大累積灰塵限制。本研究以最小化總延遲時間為目標，數學式表示為1|clean-up|∑_(i=1)^N▒T_i 。

本問題為NP-Hard問題，首先提出了2種不同架構整數規劃模式，求得最佳解，模式(1)中每次的維護與每個工件都會被安排一個位置，考慮該如何排序，才能得到最佳解。模型(2)中則以二元變數來決定何時要進行維護來求得最佳解。模式(2)的求解速度會較模型(1)快。本研究另提出啟發式演算法來求解大型問題。結果顯示與最佳解相比在p_i=∪[1,10]時平均誤差為5.38%，p_i=∪[1,100]平均誤差為5.99%，而在大型問題上啟發式演算法也比常用的EDD(Earliest Due Date)方法好，當p_i=∪[1,10]情況時本研究演算法較EDD方法好15.91%，在p_i=∪[1,100]則是優於EDD方法23.40%。

關鍵字

整數規劃 ； 單機 ； 最小化總延遲時間 ； 維護 ； 啟發式演算法

並列摘要

This paper considers wafer manufacturing of semiconductor where wafer cleaning should be taken to avoid pollution. The function of wafer cleaning is to clean up the dirt, i.e., particle, organic, and metal-lons on the surface of wafer. The main materials of wafer cleaning is cleaning agent which can take away the dirt on the wafer surface. The dirt is dissolved in the cleaning agent. Once the accumulation of substantial dirt is over a permitted value, the cleaning agent will damage the wafer surface and it is necessary to be changed. Thus, we deal with the problem of scheduling jobs and dirt clean-up based maintenance to avoid the loss of capacity. The objective is to minimize the total tardiness of the jobs. This problem is strongly NP-hard. Two mixed binary integer programming models are developed to optimally solve this problem. Furthermore, an efficient heuristic algorithm is proposed for solving large-sized problems.

In this study, we have two integer programming models for the following problem: 1|clean-up|∑_(i=1)^N▒T_i . Model (1) considers at most (N-1) numbers of clean-up dust activities for the machine in the planning horizon. Model (2) uses binary variables to control whether the maintenance is carried or not. The number numbers of maintenance will affect the solving speed. When the numbers of job more, model (2) is faster than models (1). The large size problem is solved by the heuristic algorithm.

並列關鍵字

Mixed binary integer programming ； Single machine ； Heuristic algorithm ； Maintenance ； Total tardiness

參考文獻

Ben-Daya, M., & Al-Fawzan, M. (1996). A simulated annealing approach for the one-machine mean tardiness scheduling problem. European Journal of Operational Research, 93(1), 61-67.

Biskup, D., Herrmann, J., & Gupta, J. N. (2008). Scheduling identical parallel machines to minimize total tardiness. International Journal of Production Economics, 115(1), 134-142.

Chen, J.-S. (2006). Optimization models for the machine scheduling problem with a single flexible maintenance activity. Engineering Optimization, 38(1), 53-71.

Chen, J.-S. (2008). Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan. European Journal of Operational Research, 190(1), 90-102.

Chen, J. (2006). Single-machine scheduling with flexible and periodic maintenance. Journal of the Operational Research Society, 57(6), 703-710.