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

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

10.29977/JCIIE.200505.0004

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

混合式基因演算法 ； 初始族群 ； 最小化最大完工時間 ； 順序相依設置時間 ； 交期 ； hybrid genetic algorithms ； initial population ； minimum make span ； sequence dependent setup time ； due dates

工業工程學刊

22卷3期（2005 / 05 / 01）

218 - 225

英文

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

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.

1. 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.
   連結：
2. 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
   連結：
3. Azizoglu, M.,O. Kirca(1998).Tradiness minimization on parallel machines.International Journal of Production Economics,55,163-168.
4. Cheng, R.,M. Gen(1997).Parallel Machine Scheduling Problems Using Memetic Algorithms.Computers & Industrial Engineering,33(3),761-764.
5. 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.
6. Cochran, J. K.,S. M. Horng,J. W. Fowler(2003).A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines.Computers & Operations Research,30,1087-1102.
7. Garey, M. R.,D. S. Johnson(1979).Computer And Intractability: A Guide to the Theory of NP-Completeness.San Francisco:W H Freeman.
8. Gupta, J. N. D.,J. Ruiz-Torres(2001).A listtit heuristic for minimizing makespan on identical parallel machines.Production Planning & Control,12(1),28-36.
9. Herrmann, J. W.(1999).A Genetic Algorithm for Minimax Optimization Problems.Proceedings of the Congress of Evolutionary Computation,1099-1103.
10. Lee, Y. H.,M. Pinedo(1997).Scheduling jobs on parallel machines with sequence-dependent setup times.European Journal of Operational Research,100,464-474.
11. Lin, C. C.(2001).A Genetic Algorithm for Unrelated Parallel-Machine Scheduling Problems.Taichung:Chaoyang University of Technology.
12. Min, L.,W. Cheng(1999).A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines.Artificial Intelligence in Engineering,13,399-403.
13. Park, Y. G.,S. Y. Kim,Y. H. Lee(2000).Scheduling jobs on parallel machines applying neural network and heuristic rules.Computers & Industrial Engineering,38,189-202.
14. Pearn, W. L.,S. H. Chung,M. H. Yang(2002).The wafer probing scheduling problem (WPSP).Journal of the Operational Research Society,53,864-874.
15. Pearn, W. L.,S. H. Chung,M. H. Yang(2002).Minimizing the total machine work load for the wafer probing scheduling problem (WPSP).IIE transactions,34,211-220.
16. Serifoglu, F. S.,G. Ulusoy(1999).Parallel machine scheduling with earliness and tardiness penalties.Computers & Operations Research,26,773-787.
17. Sethi, R.(1977).On the complexity of mean flow time scheduling.Mathematics of Operations Research,2(4),320-330.
18. Tamaki, H.,E. Nishino,S. Abe(1999).A Genetic Algorithm Approach to Multi-Objective Scheduling Problems with Earliness and Tardiness Penalties.Proceedings of the Congress of Evolutionary Computation,46-52.
19. Viginer, A.,B. Sonntag,M. C. Portmann(1999).A hybrid method for a parallel-machine scheduling problem.International Conference on Emerging Technologies and Factory Automation,671-678.
20. Zomaya, A. Y.,Y. H. The(2001).Observation on Using Genetic Algorithms for Dynamic Load-Balancing.IEEE,12(9),899-911.

1. Ali Allahverdi(2008).THREE-MACHINE FLOWSHOP SCHEDULING PROBLEM TO MINIMIZE MAKESPAN WITH BOUNDED SETUP AND PROCESSING TIMES.工業工程學刊,25(1),52-61.