多階段再回流晶圓針測排程問題之整合性解法

Abstract

多階段再回流晶圓針測排程問題（M-WPSP）是一種平行機台排程問題之實務類型。由於M-WPSP牽涉了涵蓋不同交期的多產品族、到臨時間、再回流、序列與批次處理，以及序列相依設置時間等等特性，使的這樣的問題比典型的平行機台排程問題更為難解。在本論文中，吾人以最小化總機台工作負荷為目標，提出了兩種策略。『順序策略』主要為依據產品製造的順序來進行分段規劃；『同步策略』則是設計來有效解決具有再回流特性之排程問題。除此之外，吾人探討五種現存而用以實行策略之插入程序，並據此發展三種改善之程序。為評量策略的效益，包含四種主要因子（產品族的凝聚程度、溫度改變的考量，交期的緊縮程度以及不同之產品到臨時間）的問題將被測試於兩種不同之工作負荷環境。為比較現存與改善之插入程序，同樣包含數個關鍵因子的測試問題將被提出討論與分析。

The multi-stage wafer probing scheduling problem (M-WPSP) with reentry, is a practical variation of the parallel-machine scheduling problem. Since the M-WPSP involves multiple product families with various job due dates, ready times, reentry, serial and batch operations, sequential dependent setup time, it is more difficult to solve than the classical parallel machine scheduling problems. In this thesis, we consider two strategies to solve the M-WPSP, where the total machine workload must be minimized. The sequential strategy schedules the jobs at the required stages according to the sequence of manufacturing operations. The parallel strategy is designed specifically for the reentrant characteristic. In additional to this, we investigate five existing insertion procedures and develop three modified insertion procedures, which are used to implement the proposed strategies and solve the M-WPSP. To evaluate the efficiency of the proposed strategies, a set of test problems involving four critical factors: the product family ratio, the temperature-change consideration, tightness of due dates, and ready time are designed to test the quality of solutions under two different workload environments. To test the performance of five existing insertion procedures and three modified insertion procedures, another set of test problems, which also involve the critical factors, are provided and analyzed under a single stage environment.