多階段IC封裝排程問題--以演算法為基礎之解決方案

Abstract

IC封裝排程問題是一種變化型的彈性流線型製程系統，涉及了流線型工作站以及等效平行機台等問題。在具有多階段製成特性之IC封裝廠中，各工作將依據各產品別進行加工，每個工作通常包含數個加工程序，必須在限定的交期之內完成所有必須步驟並出貨。此外，各工作在每一階段的加工時間長短，根據產品別的不同有所差異。而機台上各工作間的設置時間，則具有序列相依的特性。由於IC封裝排程問題涉及了產品族差異、產品族相關之加工時間、交期限制、機台產能、序列相依之設置時間與加工順序，在求解問題上，將會遭遇更多的困難。在此研究中，我們提出了四個多階段的策略，根據負荷分配的概念，期能最小化IC封裝排程問題中的機台工作負荷。我們將節約演算法整合至排程策略中，這些演算法將會幫助我們在合理的排程中，最小化機台設置時間—亦即最小化工作負荷的基礎。我們將應用文獻上著名的節約演算法，並針對現有的演算法進行改善，期能在多階段製程特性下獲得較佳的的解。為了驗證排程策略的合理性，我們設計了一組測試問題，包含產品族比例、交期緊迫度、關鍵製程設置時間差異與總加工時間之差異等具有影像性的因子。測試結果說明了四個排程策略都是合理可行的。而我們發展的新演算法，也比文獻上現有的演算法，在減少機台設置時間方面有著更佳的表現。

The integrated circuit packaging scheduling problem (ICPSP) is a variation of the flexible flow shop scheduling problem, which represents a generalization of the traditional flow shop and the identical parallel machine problem. In the multi-stage integrated circuit (IC) packaging factories, the jobs are clustered by their product types and carry with multiple operations, which must be processed on a series of identical parallel machines according to the processing sequences and be completed before due dates. Further, the job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Since the ICPSP involves constraints on job product types, product-type dependent processing time, due date restrictions, machine capacity, sequentially dependent setup time, and manufacturing sequences, it is more difficult to solve than the classical flexible flow shop problem. In this research, we consider the ICPSP and propose four strategies to solve multi-stage processing with feasible planning for the objective of minimizing the total machine workload. We integrate saving-based algorithms into our strategies in order to minimize the total setup time of machines, which is the essential of minimizing total machine workload, and reduce the total numbers of setup at each stage with feasible solutions. We apply well-known saving-based algorithms and develop new savings function for modifications for obtaining better solution in the ICPSP. To demonstrate the feasibility of strategies, a set of test problems is designed, which involves the following four factors, the product family ratio at critical stage, the tightness of due dates, the setup time level at critical stage, and the level of total processing time. Computational results from running the designed test problems demonstrate that the feasibility of strategies and the performance of the three proposed modified savings algorithms significantly outperform the original savings algorithm.