考慮清理灰塵之最小化完成時間絕對差單機排程問題

Minimizing the total absolute deviation of completion time on a single machine with dust accumulation consideration

張存智(CUN-ZHI ZHANG)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201500872

摘要

本研究探討單一機台(Single machine)在半導體晶圓生產時為了避免在製造的過程中因為機台或機械設備間的開關摩擦以及化學品與抽氣管路的使用而產生灰塵汙染，例如金屬、有機物與金屬離子...等，因灰塵累積超過最大上限值時，導致機台損壞並停止運作的問題。因此，在灰塵累積仍未到達此上限值時，機器必須先停止運作以清理所累積的灰塵。本研究將清洗作業視為機台的維護活動。考慮n個工件在機台上加工，每個工件有各自的處理時間、位置權重及產生的灰塵量，且機台有其最大累積灰塵限制。本研究以最小化總完工時間的絕對標準差為目標，數學式表示為1│clean-up│TADC。

本問題為NP-hard問題，首先提出整數規劃模式，求得最佳解。接著提出啟發式演算法來求解大型問題。結果顯示與最佳解相比在p_i=∪[1,10]時平均誤差為4.35%，p_i=∪[1,100]平均誤差為4.99%，而在大型問題上啟發式演算法也比常用的TADC(Total absolute deviation of completion time)方法好，當p_i=∪[1,10]情況時本研究演算法較TADC方法好19.25%，在p_i=∪[1,100]則是優於TADC方法19.80%。

關鍵字

單機；維護；最小化總完工時間的絕對標準差；整數規劃；啟發式演算法

並列摘要

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. Thus, we deal with the problem of scheduling jobs and dirt clean-up based maintenance to avoid the loss of capacity. The machine has to be stopped to clean up the dirt once the accumulation of dirt on the machine is over a limited value.The objective is to minimize the total absolute deviation of completion time. This problem is strongly NP-hard. A mixed binary integer programming model is developed to optimally solve this problem. Furthermore, an efficient heuristic algorithm is proposed for solving large-sized problems.

In this study, we have an integer programming model for the following problem:1│clean-up│TADC.Model uses binary variables to control whether the maintenance is carried or not. The large size problem is solved by the heuristic algorithm.

The results showed that optimal solution is better than heuristic algorithm when p_i=∪[1,10] the average error is 4.35%；p_i=∪[1,100]the average error is 4.99% .

並列關鍵字

TADC；Mixed binary integer programming；Single machine；Heuristic algorithm；Maintenance

參考文獻

Cai X.(1996).V-shape property for job sequences that minimize the expected completion time variance. European Journal of Operational Research;91:118-123.

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

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

Huang X, Wang,M.Z.(2011).Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Applied Mathematical Modelling; 35:1349-1353.

Kanet J.(1981).Minimizing variation of flow time in single machine systems. Management Science;27:1453-1459.