基因演算法於印刷電路板鑽孔排程之應用

Application of genetic algorithm to the production scheduling of drilling operation in a PCB factory

李勝隆(Sheng-Lung Li)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(2003年)

摘要

本研究主要探討隨機選取交配與突變運算元之基因演算法(Genetic Algorithm)，在印刷電路板產業的應用，並以鑽孔排程為例。鑽孔排程在印刷電路板產業中為一典型的非等效平行機台(Unrelated Parallel Machine)排程問題，此生產型態隨著訂單派工法則的不同，對客戶交期有一定的影響，本研究採取訂單不可分割原則，並考慮機器產能將訂單排入機台，並以總延遲時間最小化為評估準則。
在以往的文獻中，以基因演算法求解非等效平行機台之問題，皆採取固定選取交配與突變運算元，但是，經過許多世代的演算，會造成母體相似度太高，而無法突破區域最佳解，因此如何使基因演算法之求解品質提高乃是一重點所在，本研究則導入交配與突變運算元12種組合進行隨機選取，不論問題組合多寡與其他啟發式法則比較皆能夠得到近似最佳解，其最小改善率也達到45.8%，因此，本研究所提出之演算法具有實際應用價值，可協助管理者在排程作業之決策。

關鍵字

基因演算法 ； 非等效平行機台排程 ； 塔布搜尋法 ； 印刷電路板

並列摘要

This research applies the genetic algorithm with random chosen crossover and mutation operations to printed circuit board industry and takes drilling operation process as an example. Scheduling of in printed circuit board industry belongs to unrelated parallel machine scheduling problem. Due-date is affected by different dispatching rules. This research assumes that orders are undivided and are assigned to machines according machines’ capacities is to distribute it onto the unrelated parallel machines for meeting the due-date. The objective is the minimization of the sum of the tardiness.
The past literatures about application of genetic algorithm to the unrelated parallel scheduling machine problems apply fixed crossover and mutation operations. But, it will make homogeneity of population too high after many generations and is unable to skip the local optimal solution. Therefore how to raise the solution quality of genetic algorithm is the key issue in this research. In this research, we propose the genetic algorithm with random chosen crossover and mutation operations to reduce the sum of the tardiness. The results of genetic algorithm with random chosen operation are superior to those of other approaches and the lowest percentage of improvement is around 45.8%. It shows this algorithm is worth considered for application on real world case.

並列關鍵字

Genetic Algorithm ； Unrelated Parallel Machines Scheduling ； Tabu Search ； Printed Circuit Board

參考文獻

1. Allahverdi, A. and J., Mittenthal, “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time,” Naval Research Logistics, 41, pp.677-682, 1994.

2. Chang, P. C. and J. C. Hsieh, “A comprehensive review of genetic algorithms applied to the production scheduling problems,”submitted to Applied Soft Computing, 2002.

3. Chang, P. C., J. C. Hsieh and S. G. Lin,“The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem,” International Journal of Production Economics, 79, pp.171-183, 2002.

4. Cheng, R. and M. Gen,“Parallel machine scheduling problems using memetic algorithms” Computers & Industrial Engineering, 33, 3, pp.761-764, 1997.

6. Davis, L., Handbook of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1987.