IC預燒測試廠生產排程問題之研究

Abstract

在半導體產業中，設備投資是非常昂貴的, 所以如何充分利用產能及滿足顧客交期來增加競爭力及獲利，為一重要之研究課題；在半導體製造的最終測試階段中，IC預燒作業為保證IC出廠品質之重要製程，由於預燒作業時間冗長，往往成為生產過程中的瓶頸，其排程結果將影響整個測試廠的生產績效，因此，本論文將針對此瓶頸作業所衍生的機台排程問題進行探討。IC預燒測試的排程必須考慮各批測試工件抵達時間，工件批量的大小，有限的機台產能，不同產品群組先後測試的相依設置時間以及混合產品群組同機測試的加工時間，是一個多維度的排程問題。再者，由於購置設備之機種的不同，不同機台的批次產能亦有所差別，因此，發展IC預燒測試排程的求解程序在IC測試廠也是一個重要的課題。 本論文探討兩種預燒機台排程問題(burn-in test problem; BTSP)；首先為同質性IC預燒機台排程問題(identical machines, burn-in test problem; iBTSP)，此為順序相依性設置時間之平行機台排程問題，工件在此問題中分屬不同的產品族 (product family)，設置時間與預燒時間不同，但相同的產品線(product group) 之產品其測試之條件相同，可合併機台預燒測試，預燒時間則以同批次產品族之最長預燒時間為準。另外則是針對非同質性機台混合預燒測試排程問題(non-identical machine, burn-in test problem; nBTSP)，此二種排程問題皆以最小化機台負荷為目標。 於本論文中，我們針對iBTSP與nBTSP兩個排程問題分別建立其混合整數規劃模式(MILP)，求取最佳解。同時，將iBTSP的子問題轉換為考量時間窗限制下之車輛路線問題(vehicle routing problem with time window；VRPTW)，並修改既有之網路演算法，提出兩個啟發式解法以解決此問題，由運算結果及績效比較中得知，啟發式法則有很好的求解效果。對於nBTSP，本文針對MILP問題之規模及計算時間進行分析，發現影響計算時間之因子中，總工件數的影響最大以外，機台數量亦有很大的影響。

To be competitive, the semiconductor industry companies need to utilize their capacity and to satisfy customers’ due dates in order to increase their profitability. In the final stage of IC testing process, the burn-in test is the key process to ensure the reliability of out-going ICs; the burn-in process usually causes bottleneck in production because the burn-in time is long, and its schedule mainly affect the system performance of IC test factories. Therefore, an essential scheduling problem is tackled for the bottleneck operation. The burn-in test scheduling problem (BTSP) is complicated because it is a multi-dimensional problem, involves the constraints of different product group, unequal ready times, non-identical job sizes, limited machine capacity, and batch dependent processing times. Therefore, the development of efficient algorithms is critical to form appropriate batches and to arrange a suitable schedule for those jobs which have been processed by the IC testing operation. For the BTSP, jobs are clustered by their product groups, while the test time of jobs in same group may different according to their product family. Jobs in different product family of same product group could be processed in a batch and the process time will be the longest process time of product family of the batch. In addition, the capacity of burn-in machines may different due to different machine brand or models. Furthermore, setup times for two consecutive jobs between different product types on the same machines are sequence-dependent. The burn-in test is a high energy consuming operation, how to use minimal machine time to complete all jobs is the key to manage the cost. Consequently, the objective of BTSP is minimal workload. In this dissertation, we considered identical parallel machine and non-identical parallel machine scheduling, called iBTSP and nBTSP. We formulated iBTSP and nBTSP as two mixed integer linear programming models (MILP). For the iBTSP, it can be viewed as a multi-level optimization problem, the sub-problem can be transformed into the vehicle routing problem with time window (VRPTW), a well-known network routing problem which has been investigated extensively. We present two compound algorithms based on the network algorithms with some modifications to accommodate the iBTSP and the computational results and performance comparisons show that the proposed algorithms are efficient and near-optimal. We analyzed the problem size and the computation time of the nBTSP, and found the total job number and machine number impacts the computation time most.