多資源限制之智慧型排程-以半導體測試作業為例

Intelligent scheduling for multi-resource constrained problems

胡朝鈞(Chao-Chun Hu)

指導教授 ： 王孔政

中原大學/工學院/工業工程研究所/碩士(2001年)

https://doi.org/10.6840/cycu200100286

摘要

半導體測試作業中，測試機使用率之提升與交期之滿足是測試作業控制與管理的兩項重點。然而，半導體測試作業的進行除測試機外，另需四種設備的搭配作業才可進行，因此測試作業擁有多資源作業之特性。本研究主要是藉由排序的方法，欲達到測試機使用率提升以及交期滿足之目標，將半導體測試作業的排序問題，建構成多資源排序之問題，並建立數學模式以定義多資源排序問題之特性，研究中並由數學模式之分析說明了問題的複雜度，以及數學規劃實行上之困難，因此發展智慧型之排序方法，解決此排序問題。研究過程中共發展出共同暫存區和獨立暫存區等兩大架構之智慧排序方法，其中並以進化式演算法和遺傳基因演算法作為排序方法之核心。在論文中除詳述數學模式及兩大架構之內容外，並對兩架構之智慧型排序方法進行運作速率和運作品質的分析，最後提出兩架構對於多資源排序問題的求解比較，以及核心演算法之綜合比較等。並在實驗結果中發現，獨立暫存區架構對於多資源之支配比共同暫存區架構好，在演算法方面，進化式演算法及遺傳基因演算法之運作皆比隨機搜尋結果佳。

關鍵字

半導體測試作業 ； 多資源排序遺 ； 遺傳基因演算法

並列摘要

The improvement of tester utilization and the fulfillment of delivery date are critical to testing operation control and management of semiconductor industry. Semiconductor testing is characterized by multi-resource constraints. In addition to tester facilities, the progress of semiconductor testing operation has to work with other equipment. This research aims at constructing a model for semiconductor testing operation to minimize task makespan and lateness as well. Due to the inherent exponentially computational complex of the problem, we developed a set of intelligent algorithms to sequencing testing tasks. The Intelligent sequencing algorithms fall into two categories, common buffer and individual buffer. The performance of the proposed algorithms are evaluated in term of solution quality and computation efficiency using a simulation model. Computational experiments show that the proposed intelligent sequencing algorithms perform well with respect to solution quality and efficiency.

並列關鍵字

Semiconductor testing operation ； Intelligent sequencing algorithms ； Multi-resource sequencing

參考文獻

Balogun, O., O. and Popplewell, K., 1999, “Towards the integration of flexible manufacturing system scheduling,” International Journal of Production Research, 37(15), 3399-3428.

Belhe, U. and Kusiak, A., 1995, “Resource constrained scheduling of hierarchically structured design activity networks,” IEEE Transactions Engineering Management, 42(2), 150 – 158.

Brown, D. E. and Scherer, W. T., Intelligent Scheduling Systems, Boston : Kluwer Academic Publishers, 1995.

Chen, T.R., Chang, T.S., Chen, C.W. and Kao, J.,1995, “Scheduling for IC sort test with preemptiveness via lagrangian relaxation,” IEEE transactions on systems, man and cybernetics, 25(8), 1249-1256.

Cheng, R. and Gen, M., 1995, “Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithm,” International Journal of Computers and Industrial Engineering, 29(1-4), 513-517.