考慮灰塵累積之最小化總延遲時間單機排程研究

Scheduling jobs with dirt cleaning consideration to minimize the total tardiness

林裕軒(Lin, YU-HSUAN)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201600839

摘要

本研究針對單一機台在晶圓的製造或加工過程中都會產生灰塵，為了避免晶圓遭到汙染，常會使用清潔劑來清潔晶圓表面上的灰塵，此時晶圓上的灰塵會溶解於清潔劑中，當清潔劑中灰塵累積量超過灰塵累積量上限時，就會使晶圓遭到汙染與破壞，所以要在清潔劑還沒超過灰塵累積量上限時更換清潔劑，才能有效的清潔晶圓並使晶圓避免遭受到破壞。本研究把更換清潔劑視為機台的維護活動。考慮1台機台上有 N 個獨立工件進行加工，機台一次只能加工一個工件，每個工件有各自的處理時間、交期及在機台上加工時產生之灰塵量，且機台有灰塵累積量上限的限制。本研究以最小化總延遲時間為目標。

針對本問題，首先提出整數規劃模式，求得最佳解，整數規劃模式中以二元變數與位置的灰塵累積量，來判斷何時需進行保養維護活動來求得最佳解。本研究也提出啟發式演算法來求解大規模問題。結果顯示在小規模問題中與最佳解相比，平均誤差率皆在6%以下，在大規模問題中啟發式演算法也比EDD方法來得好許多。

關鍵字

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

並列摘要

This thesis is about wafer manufacturing of semiconductor where wafer cleaning should be avoid the pollution. Wafer cleaning is to clean up the dirt on the surface of wafer. Cleaning agent is the main materials of wafer cleaning, which can take away the dirt on the wafer surface. The dirt will dissolved in the cleaning agent. When the accumulation of dirt over the threshold, the cleaning agent will damage the wafer’s surface and it is necessary to be changed the cleaning agent. Therefore, the problem of scheduling jobs and dirt clean-up based maintenance to avoid the loss of capacity attracts our interests to deal with. The main objective is to minimize the total tardiness of the scheduling jobs. This problem is NP-Hard problem. We developed mixed binary integer programming model to solving this problem optimally. Moreover, developed an heuristic algorithm to solving large-sized problems efficiently.

In this study, we have mixed binary integer programming model to solving this problem. It uses binary variables and the position of dirt cumulants to control whether the maintenance is started or not. And the large-sized problems are solved by the heuristic algorithm.

並列關鍵字

Minimized the total tardiness ； Single machine ； Mixed binary integer programming ； Heuristic algorithm ； Maintenance

參考文獻

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.

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. (2006). Single-machine scheduling with flexible and periodic maintenance. Journal of the Operational Research Society, 57(6), 703-710.

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

Du, J., & Leung, J. Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15(3), 483-495.