考慮灰塵條件之最小化延遲工件數非等效平行機台問題

Minimizing the number of tardy jobs on unrelated parallel machines with contaminant consideration

蕭明誌(Ming-Chih Hsiao)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201900331

摘要

本論文探討非等效平行機台且機台具有多個不可用週期(several unavailability periods)限制之排程問題。在半導體晶圓製造製程中，晶圓洗淨之技術及潔淨度，是影響晶圓製程良率、品質及可靠度，重要的因素之一，因為之後所成長氧化層品質與晶圓表面潔淨度有關。為避免晶圓遭受污染物的汙染，在生產過程時，需透過清洗機構清洗晶圓表面上的污染物，污染物包含：微塵顆粒(Particle)、金屬(Metal)、有機物(Organic)與金屬離子(Metal-Ions)...等。晶圓清洗的方式，是以整個批次或單一晶圓，藉由清洗劑來去除髒污並清除晶片表面的污染物。在清潔過程中，污染物會溶解於清洗劑之中，一旦清洗劑中累積的污染物超過允許的數值，便會破壞晶圓表面。在此限制條件下，一定時間就必須更換清洗劑，才能繼續清洗晶圓。在研究中，將更換清洗劑視為機台的維護活動，目標是求解最小延遲工件數。本論文整合平行機台排程與機台維護活動，該問題為NP-Hard問題。我們提出混整數規劃模式來找尋最佳解，進而發展出一種複合演算法模型來求解大數量工件問題。複合演算法模型包含一個三階段之啟發式演算法及一個整合兩種解表示之粒子群演算法。首先，啟發式演算法將工件指派到合適的機台，然後延伸Moore演算法尋找各機台上的工件排程。第三階段再透過壓縮非延遲工件(non-tardy jobs)時間改善各機台的排程。為了改善三階段啟發式演算法之結果，在粒子群演算法中，運用兩種不一樣的編碼方式：最小位置值規則及絕對位置值規則，整合成一個兩階段的粒子群演算法。在模擬實驗中，分別探討本研究所提出複合演算法模型、ModLK模型與混整數規劃之執行結果。

關鍵字

排程 ； 延遲工件 ； 非等效平行機台 ； 汙染物累積 ； 啟發式演算法 ； 粒子群演算法

並列摘要

This dissertation focuses on the process of wafer manufacturing and considers the unrelated parallel machine scheduling problem in which there are several unavailability periods on each machine where some machines must be stopped to change a cleaning agent to remove the contaminants. The objective of the problem considered is to minimize the number of tardy jobs. During the manufacturing process of a wafer, contaminants on the surface of the wafer must be removed by a cleaning agent. Once the accumulation of contaminant exceeds a threshold value, it is necessary to interrupt the machine process and replace the cleaning agent in order to avoid damaging the wafer. The optimization problem, which integrates production scheduling and cleaning activities, is strongly NP-hard. A mixed binary integer programming (MBIP) model is developed to determine the optimal solution and a hybrid algorithm model (HAM) is proposed to solve the problem. The HAM includes a three-phase heuristic (3P-Heu) and an integrated representation particle swarm optimization (IRPSO). The heuristic first tries to assign each job to the most efficient machine. Subsequently, an intention of Moore’s algorithm is used to minimize the number of tardy jobs on each machine. Finally, the solution is improved by compacting the schedule of non-tardy jobs and inserting tardy jobs into the current sequence. In order to improve the solution quality from 3P-Heu, IRPSO is employed. In IRPSO, the smallest position value rule (SPVR) and the absolute position value rule (APVR) are integrated as a new two-phase meta-heuristic algorithm. An extensive simulation experiment shows that HAM outperformed ModLK for both small and large problems.

並列關鍵字

Scheduling ； Tardy jobs ； Unrelated Parallel Machines ； Contaminant Accumulation ； Heuristic ； Particle Swarm Optimization (PSO)

參考文獻

Adiri, I., Bruno, J., Frostig, E., and Kan, A. R. (1989). Single machine flow-time scheduling with a single breakdown. Acta Informatica, 26(7), 679-696.

Bornstein, C. T., Alcoforado, L. F., and Maculan, N. (2005). A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem. European Journal of Operational Research, 165(3), 649-656.

Chen, Y., Su, L.-H., Tsai, Y.-C., Huang, S., and Chou, F.-D. (2019). Scheduling Jobs on a Single Machine With Dirt Cleaning Consideration to Minimize Total Completion Time. IEEE Access, 7, 22290-22300.

Cheng, T. E., Hsu, C.-J., and Yang, D.-L. (2011). Unrelated parallel-machine scheduling with deteriorating maintenance activities. Computers & Industrial Engineering, 60(4), 602-605.

Chou, F.-D. (2013). Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks. International Journal of Production Economics, 141(1), 137-145.