半導體製造系統之多目標排程

Multiobjective Scheduling in Semiconductor Manufacturing Systems

蔣宗哲(Tsung-Che Chiang)

指導教授 ： 傅立成

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2008年)

https://doi.org/10.6342/NTU.2008.00937

摘要

這是一本研究如何對半導體製造廠中之生產設備進行排程的論文。為了因應接單生產 (make-to-order) 的市場趨勢，我們的研究特別專注於如何排程以最佳化多個與客戶交期 (due date) 相關的效能指標。本文中，對於廠內循序 (serial) 機台與批次 (batch) 機台的即時派工 (dispatching) 問題，我們分別提出兩條新的派工法則 (dispatching rule)，其主要特色為計算工件優先值時，會考慮總緊急度，並會視需要作交期延長的動作。論文中，我們也針對傳統使用派工法則的方式指出其缺點，並將派工決策視為一個二維指派問題，透過求解此指派問題的方式來彌補傳統方式之不足。除此之外，我們提出一個多目標演化式演算法 (multiobjective evolutionary algorithm)，它可以依據製造廠內的現有狀況與廠方設定的效能指標，來產生一群具有Pareto最佳性 (Pareto optimal) 的派工法則與參數組合。生管人員毋須事前訂定多個效能指標間的偏好關係，就可直接從這群Pareto最佳解組合中，挑選最適當的組合來作即時派工之用途。對於多目標演化式演算法中的關鍵程序，包括適合度計算 (fitness assignment)、親代選擇 (mating selection)、環境選擇 (environmental selection) 與區域搜尋 (local search)，我們都提出了創新的設計。在實驗中，我們使用一套公開且具有代表性的測試資料來驗證所提方法之效能。這套測試資料包含了七個不同半導體製造廠的資料，配合不同的廠負載度 (load level) 與交期鬆緊度 (due date tightness) 設定，產生數十種不同的測試環境。實驗結果顯示，所提方法之效能，顯著優於多種既有之方法。因此，我們相信本論文所提之方法，將可應用於半導體製造廠之多目標排程，使產品之生產時程更為滿足客戶訂單之交期。

關鍵字

半導體製造 ； 排程 ； 派工 ； 批次 ； 多目標 ； 演化式演算法

並列摘要

In this dissertation, we address the scheduling problem in the semiconductor manufacturing industry, one of the most complicated and capital-intensive industries in the world. Due date delivery performance is of our particular concern to cater to the make-to-order market environment nowadays. We propose a real-time scheduling approach to resolve the main decisions including serial dispatching and batch dispatching. The real-time scheduling approach is based on two newly proposed dispatching rules, whose features include total urgency estimation and due date extension. To apply the dispatching rules, the weakness of traditional paradigm is discussed, and a 2-D assignment-based paradigm is proposed. In addition, a performance optimizer based on the evolutionary algorithm is developed with the consideration of multiple objectives simultaneously. The critical components of the multiobjective evolutionary algorithm (MOEA) including fitness assignment, mating selection, environmental selection, and local search procedure are designed elaborately to balance between exploration and exploitation. By using the proposed MOEA-based optimizer, it is easy for production managers to obtain a set of rules and parameter values which is fit to their own manufacturing systems and is able to produce schedules to their satisfaction. Experiments are conducted on a representative test bed consisting of seven wafer fabrication facilities under different levels of fab load and due date tightness. Considering performance measures including on-time delivery rate, mean tardiness, and maximum tardiness simultaneously, the proposed serial and batch dispatching rules significantly outperform 16 existing serial rules and 6 batch rules, respectively. The proposed MOEA also shows superiority over a representative approach in the literature. According to these promising results, we can conclude that the proposed real-time scheduler and performance optimizer are useful tools to do multiobjective scheduling in the semiconductor manufacturing industry.

並列關鍵字

semiconductor manufacturing ； scheduling ； dispatching ； batch ； multiobjective ； evolutionary algorithms

參考文獻

Adams, J., Balas, E., and Zawack, D., 1988, The shifting bottleneck procedure for job-shop scheduling, Management Science, 34, 391 – 401.

Anderson, E.J. and Nyirenda, J.C., 1990, Two new rules to minimize tardiness in a job shop. International Journal of Production Research, 28, 2277 – 2292.

Appleton-Day, K. and Shao, L., 1997, Real-time dispatch gets real-time results in AMD’s Fab 25, Proceedings of the IEEE/SEMI Advanced Semiconductor Manufacturing Conference, 444 – 447.

Arroyo, J.E.C. and Armentano, V.A., 2005, Genetic local search for multi-objective flowshop scheduling problems, European Journal of Operational Research, 167 (3), 717 – 738.

Arzi, Y. and Raviv, D., 1998, Dispatching in a workstation belonging to a re-entrant production line under sequence-dependent set-up times, Production Planning & Control, 9 (7), 690 – 699.