考慮清理灰塵之最小化最大完工時間單機排程問題

Scheduling jobs on a single machine with dirt cleaning consideration to minimize makespan

陳重穎(Chong-Ying Chen)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201900491

摘要

本研究目標為考慮清理灰塵之最小化最大完工時間單機排程問題，針對半導體晶圓生產的排程問題為研究對象，為了避免製造的過程中因為機台或機械設備間的開關摩擦以及化學品的抽氣管路的使用而產生灰塵汙染，導致機台損壞，考慮n個工件，機台有可容忍灰塵上限值，當生產過程中灰塵累積量達到機台可容忍灰塵上限值時需要進行清理灰塵，且工件在進行製程時不允許中途停止或是搶占的情況發生。

此問題屬於NP-Hard問題，本研究發展出兩種演算法，分別為整數規劃模型與啟發式演算法，並結合兩種傳統派工法則進行分析，分別為LPT(Longest Process Time)和LDF(Largest Dirt First)，透過小規模問題將整數規劃模型求得之最佳解與啟發式演算法求得之解進行求解品質與求解時間之比較，透過大規模問題將派工手法則LPT與LDF求得之解與啟發式演算法求得之解進行求解品質與求解時間之比較。

研究成果顯示LDF手法的求解結果會優於LPT手法，而啟發式演算法則優於LPT手法與LDF手法，從小規模問題得知使用整數規劃模型與啟發式演算法的誤差率在工件數30以下皆低於5%，而從大規模問題可得知使用LDF改善率皆小於LPT改善率，且改善率會隨著工件數的增加而上升，在工件數少於300個情況下，LDF改善率平均不超過20%，而LPT改善率平均則超過20%，並從實驗結果得知工件生成的灰塵量(t_i)與機台可容忍灰塵上限值(T)為最主要影響總工時長短的關鍵，因此派工順序應該由工件灰塵量的值做為優先考慮因素。

關鍵字

清理灰塵 ； 單一機台 ； 最小化最大完工時間 ； 啟發式演算法 ； 整數規劃

並列摘要

The goal of this study is to consider the scheduling jobs on a single machine with dirt cleaning consideration to minimize makespan. The scheduling problem for semiconductor wafer production is the research object. The objective is to avoid damaging the machine or mechanical equipment cause by switch friction and chemical exhaust pipe in the manufacturing process. Considering N number of jobs with the machine having an upper limited tolerance of dirt capacity. When the dirt accumulation in the production process reaches the upper dirt limit of the machine, it needs to be carried out, and jobs is not allowed to stop or preempt during the process.

This problem is classified NP-Hard problem. This study developed two algorithms, namely the integer programming model and the heuristic algorithm, and combined with two traditional scheduling method, respectively, LPT (Longest Processing Time) method and LDF (Largest Dirt First) method. By using the small-scale problem to compare between the optimal solution obtained by the integer programming model and the heuristic algorithm on the solution quality and the solution time Furthermore, through the large-scale problem to compare the solutions obtained by the LPT method and the LDF method with the heuristic algorithm on the solution quality and the solution time.

The research results show that the LDF method is better than the LPT method, and the heuristic algorithm is better than the LPT method and the LDF method. From the small-scale problem, if job number less than thirty, the quality of solution both the integer programming model and the heuristic algorithm are less than 5% . As for the large-scale problem, the results shows that the LDF quality of solution is less than the LPT method, and the quality of solution will increase as the number of jobs increases. While number of jobs less than 300, average of LDF quality no more than 20%, and average of LPT quality more than 20%. The In addition, according to the experiment results, the amount of dirt generated by the job and the upper dirt limit of the machine are the two main factors which affects the makespan. As a result, the order of dispatch should be prioritized by the value of the amount of dirt created by jobs.

並列關鍵字

Dirt cleaning ； Single machine ； Minimize Makespan ； Heuristic Algorithm ； Integer Programming Algorithm

參考文獻

Agnetis, A., Mirchandani, P.B., Pacciarelli, D. & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52(2), 229-242.

Carrasco, R.A., Iyengar, G. & Stein, C. (2018). Resource cost aware scheduling. European Journal of Operational Research, 269(2), 621-632.

Cui, W.W., Lu, Z.Q. & Pan, E.S. (2014). Integrated production scheduling and maintenance policy for robustness in a single machine. Computers & Operations Research, 47, 81-91.

Espinouse, M.L., Pawlak, G. & Sterna, M. (2017). Complexity of Scheduling Problem in Single-Machine Flexible Manufacturing System with Cyclic Transportation and Unlimited Buffers. Journal of Optimization Theory and Applications, 173(3), 1042-1054.

Ji, M., He, Y. & Cheng, T.C.E. (2007). Single-machine scheduling with periodic maintenance to minimize makespan. Computers & Operations Research, 34(6), 1764-1770.