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

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

吳振耀(Chen-Yao Wu)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201900495

摘要

本研究針對半導體中的晶圓製程為研究對象，考慮了一個具有多個不可用週期的單機總延後時間最小化之排程問題，其中必須關閉機台以清理製造過程中所產生的灰塵。在特定機台上處理晶片期間，晶片上累積的灰塵(包括顆粒、有機材料和金屬鹽等)必須將其清理後才能使機台繼續運作，一但灰塵超過上限值，就必須中斷機台運行並進行清理避免損壞晶片。
本研究使用傳統派工法則(Shortest Processing Time, SPT)進行研究並且另外發展出兩種演算法，分別為整數規劃模型與啟發式演算法，透過小規模問題將整數規劃模型求得之最佳解與啟發式演算法求得之解進行求解品質與求解效率之比較；透過大規模問題將傳統派工法則(SPT)求得之解與啟發式演算法求得之解進行求解品質與求解效率之比較。
整數規劃模型包含許多限制式，在眾多限制下求出最佳解；啟發式演算法則先將原有工件的處理時間加入灰塵比例做出調整，再將調整過後的處理時間依照SPT法則排序求出啟發式解，本研究經過多次試驗後，得出使用啟發式演算法在求解時間上相較於整數規劃模型快上許多，與最佳解相比在p_i=U[1,10]的區間裡平均誤差為3.71%、p_i=U[1,100]區間為5.31%，而在大數據問題中啟發式演算法也較常用的派工法則SPT Rule(Shortest Processing Time)來的佳，在p_i=U[1,10]的區間中啟發式演算法較SPT法則好4.80%，在p_i=U[1,100]的區間中則是比SPT法則好5.28%。

關鍵字

單機台 ； 總延後時間 ； 整數規劃 ； 啟發式演算法

並列摘要

This study aims at the wafer fabrication process in semiconductors. It considers the scheduling problem of minimizing the total lateness of a single machine with multiple unavailable cycles. The machine must be turned off in order to remove the dust generated during the manufacturing process. During the sequence of processing the wafer on a specific machine, the dust accumulated on the wafer (including particles, organic materials, metal salts, etc.) must be cleaned before the machine can continue to operate. In other words, once the dust exceeds the upper limit, the machine must be shut down for to clean the dust on the wafer.
This study applies traditional dispatching rules (Shortest Processing Time, SPT) to conduct research with two additional algorithms, namely integer programming model and heuristic algorithm. By using the small-scale questions to compare the best solution found in Integer Programming Model Algorithm with the Heuristic Algorithm. Furthermore, the study exercises the big data questions to compare the best solution found from SPT Rule with Heuristic Algorithm.
The optimal solution is obtained under many constraints which contain in the integer programming model. The heuristic algorithm first adjust the processing time of the original work-piece with the dust ratio to a new processing time, then based on the SPT rule conclude an optimal solution. After many experiments, this study shows that using heuristic algorithm is much faster in solving working-time than integer programming model The conclusion is based on comparing the best solution in the interval of p_i=U[1,10], the average error is 3.71%, and the p_i=U[1,100] interval is 5.31%. As for the big data problem, the heuristic algorithm is better than the commonly used SPT Rule (Shortest Processing Time). For p_i=U[1,10], the heuristic algorithm is 4.80% better than the SPT rule. Furthermore, the interval of p_i=U[1,100], it is 5.28% better than the SPT rule.

並列關鍵字

Single Machine ； Total Lateness ； Integer Programming Model Algorithm ； Heuristic Algorithms.

參考文獻

B.M.T Lin and A.A.K Jeng (2004). "Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs." International Journal of Production Economics 91(2):121-134.

B. Yang., J. Geunes., William J. O’Brien (2004). "A heuristic approach for minimizing weighted tardiness and overtime costs in single resource scheduling." Computers & Operations Research 31(8): 1273-1301.

Ü. Bilge., M. Kurtulan., F. Kırac (2007). "A tabu search algorithm for the single machine total weighted tardiness problem." European Journal of Operational Research 176(3): 2423-1435.

X.P. Wang. and L.X. Tang (2009). "A population-based variable neighborhood search for the single machine total weighted tardiness problem." Computers & Operations Research 36(6): 2105-2110.

Jorge, M.S. Valente. and Jeffrey, E. Schaller (2012). "Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem." Computers & Operations Research 39(9): 2223-2231.