考慮清理灰塵之最小化延遲工作數量單機排程問題

本研究探討單一機台(Single-machine)在半導體晶圓製造上，為了避免晶圓在製造時遭受到汙染，需清理在作業時晶圓表面上所產生的灰塵，例如金屬、有機物與金屬離子...等，其主要方式是利用清洗劑來清結晶圓表面上的灰塵，灰塵會溶解於清洗劑之中，一旦清洗劑中累積的灰塵超過允許的數值，便會破壞晶圓表面，為了避免此情況發生必須更換清洗劑，才能繼續清洗晶圓之排程問題，本研究將更換清洗劑視為機台的維護活動。考慮N個工件在機台上加工，每個工件有各自的處理時間、交期及產生的灰塵量，且機台有其最大累積灰塵限制。本研究以最小化總延遲工件數為目標，數學式表示為1|clean﹣up| ∑_(i=1)^N▒〖NT〗_i 。本問題為NP-Hard問題，首先提出了2種不同架構整數規劃模式，求得最佳解，模式(1)中每次的維護與每個工件都會被安排一個位置，考慮該如何排序，才能得到最佳解。模型(2)中則以二元變數來決定何時要進行維護來求得最佳解。模式(2)的求解速度比模型(1)更迅速。本研究另提出兩個啟發式演算法來求解大型問題。

關鍵字

最小化延遲工作數量；單機；整數規劃；啟發式演算法；維護

並列摘要

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-ions 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 number of tardy 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▒〖NT〗_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.

並列關鍵字

Number of tardy jobs ； Mixed binary integer programming ； Single machine ； Heuristic algorithm ； Maintenance

參考文獻

Adiri, I., Frostig, E., Rinnooy Kan, A. H. G. (1991), Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs. Naval Research Logistics 38:261-71.

Chen, WJ. (2006), Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. Journal of Operational Research Society 57:410–5.

Chen, W. (2007), Scheduling of jobs and maintenance in a textile company. The International Journal of Advanced Manufacturing Technology, 31(7-8): 737-742.

Chen, WY., Sheen, GJ. (2007), Single-machine scheduling with multiple performance measures: Minimizing job-dependent earliness and tardiness subject to the number of tardy jobs. Int. J. Production Economics 109:214-229.

Chen, JS. (2008), Optimization models for the tool change scheduling problem. Omega 36:888-94.

國際替代計量

考慮清理灰塵之最小化延遲工作數量單機排程問題

全文下載

主題瀏覽