使用基因演算法配合其他啟發式演算法解決炙燒爐指派問題

Abstract

炙燒製程常常是IC封裝後的首道測試步驟，它既是IC測試的第一道製程，也是耗時最長的。而炙燒爐又具有成批測試的特性，且須兼顧到炙燒板（Burn-In Board）數量這個次資源因素，所以在排程上並不是只有一般的排序問題而已，還要同時考慮各種資源的指派問題；當貨物與炙燒爐的數量不多的時候，人工排程尚能應付，但兩者數量增加的時候，以人工去排程便會變得沒有效率。 為此本研究針對不同的問題需求，為炙燒爐指派問題建立2個問題模型，並嘗試使用基因演算法來求解。由於兩個問題模型皆屬整數規劃問題，且限制條件繁多，導致一般的基因演算法的效率不佳；故本研究再針對不同的模型共發展出6個啟發式演算法來提供基因演算法較佳的起始解，以期大幅提升基因演算法在炙燒爐指派問題上的求解能力。 本研究並以專業IC測試公司76日的資料做為模擬數據，以驗證論文所提的方法確實有其可行之處，並與作業研究方法及典型的基因演算法做一比較。

Burn-in is usually the first and critical process in IC testing. Because of the concern of batch processing property of burn-in ovens and the number of burn-in boards, it's not only a sequencing but also an assignment problem while scheduling. Although it is affordable for people to schedule when there are only a few jobs and ovens, it is not efficient by people scheduling when jobs and ovens amounts grow larger. Two Burn-In problem models are developed for dealing with different situations and solved by using genetic algorithms. Current studies are shown that general genetic algorithms can not give efficient solutions for these two models because of their integer programming nature with a lot of constraints. In this study, six heuristic algorithms are developed in this research for providing genetic algorithms with better initial solutions. Experiments conclude that the searching processes by using genetic algorithms actually benefit from these high quality starting points. Data of 76 days were collected from an IC testing company for simulation to show the effectiveness of the proposed methods. The results are also compared with those obtained by using integer programming and typical genetic algorithms.