Hybrid Genetic Algorithms for Minimizing the Maximum Completion Time for the Wafer Probing Scheduling Problem

以混合式基因演算法求解晶圓針測排程問題最大完工時間最小化問題

楊明賢(Ming-Hsien Yang) ； 羅乾鐘(Chien-Chung Lo) ； 陳新民(Hsin-Min Chen) ； 黃浩良(Hau-Lieng Huang)

《工業工程學刊》 22卷3期 (2005/05) Pp. 218-225

https://doi.org/10.29977/JCIIE.200505.0004

摘要

晶圓針測排程問題為平行機台排程問題的一種，且排程的目標在最小化所有機台的工作負荷以提高機台利用率。然而求解晶圓針測排程問題最大完工時間的最小化以均勻的利用平行機台的產能是非常重要的，該問題尚考慮以下的問題特性：產品別與產品族、順序相依設置時間、決定於產品別的工作處理時間、工作交期與機台產能限制等。為有效率地求解問題且提高求解品質，本研究採用混合式基因演算法，該方法先以求解晶圓針測排程問題的節約型與插入型等演算法以產生一組可行解當作初始族群，並藉由本研究提出的交配運算元產生新的子代以進一步降低所有機台的最大完工時間。考慮工作交期可能帶來的干擾，所設計的運算元在產生子代的過程中，將保持最關鍵的一段子排程。此混合式基因演算法的績效將透過兩個實務的問題的求解加以測試，並且根據五種突變機率與四種世代數進行分析。結果顯示，混合式基因演算法可有效的求解測試問題，最大完工時間的降低和突變機率與世代數相關。

關鍵字

混合式基因演算法 ； 初始族群 ； 最小化最大完工時間 ； 順序相依設置時間 ； 交期

並列摘要

The wafer probing scheduling problem (WPSP) is a variation of the parallel-machine problem, which carries with the objective to minimize the total workload to enhance the utilization rate of machine capacity. However, to minimize the maximum completion time for the wafer probing scheduling problem (WPSP) is very important for equally utilizing the capacity of parallel-machine, while satisfying the requirements of product types, product family, sequence dependent setup time, product-type dependent processing time, due dates of jobs, and capacities of machines. To solve such a complicated problem efficiently and effectively, we adopt the hybrid genetic algorithm approach, which generates initial population with the insertion and savings algorithms for WPSP and provide a new crossover operator to generate better solutions. Considering the disturbance of due dates of jobs in scheduling, we design a new crossover which makes each machine keep the critical sub-schedule in the generation of offspring. The performance of the proposed hybrid genetic algorithm is evaluated by two real-world problems and the solution quality of the proposed approach is analyzed under five levels of mutation rates and four levels of number of generations. Computational results reveal that the hybrid genetic algorithm can efficiently solve the considered problem and the reduction of makespan is related to the mutation rates and the number of generations.

並列關鍵字

hybrid genetic algorithms ； initial population ； minimum make span ； sequence dependent setup time ； due dates

參考文獻

Tsai, Y. L.(2004).Improving heuristics and genetic algorithms for minimizing the maximum completion time for the wafer probing scheduling problem (WPSP).Hsinchu:Master. Thesis. National Chiao Tung University.

Yang, M. H.,W. L. Pearn S. H. Chung,J.Y. Huang(2005).Minimizing the maximum completion time for the wafer probing scheduling problem.The 2003 Annual Meeting and Conference of Chinese Institute of Industrial Engineers.

Azizoglu, M.,O. Kirca(1998).Tradiness minimization on parallel machines.International Journal of Production Economics.55,163-168.

Cheng, R.,M. Gen(1997).Parallel Machine Scheduling Problems Using Memetic Algorithms.Computers & Industrial Engineering.33(3),761-764.

Cheng, R.,M. Gen,T. Tosawa(1995).Minmax Earliness/Tardiness Scheduling In Identical Parallel Machine System Using Genetic Algorithms.Computers & Industrial Engineering.29(1),513-517.