Solving Capacitated Flexible Job-Shop Scheduling Problems Based on Master-Slave Genetic Algorithm
A genetic algorithm with master-slave structure is proposed to solve the capacitated flexible job-shop scheduling problems based on the analysis of jobs, machines and their relationship. The master and slave chromosomes are broken into blocks according to jobs or machines respectively. The master chromosomes represent alternative processing route combinations, while the slave chromosomes stand for feasible scheduling schemes subjected to master chromosome. In order to minimize delay time of jobs, the genetic operators such as selection, multi-point crossover are designed for job-gene block. On the other hand, the selective operator, multi-point crossover operator and multi-point mutation operator are designed for machine-gene block in order to minimize idle time of machines. The reciprocal of makespan and capacity deficit is set as fitness value of one scheduling scheme from slave chromosomes. Then, the master chromosome gets its fitness value from the best fitness value of its constrained slave chromosomes. The simulation results validate the effectiveness of the proposed algorithm.
Genetic Algorithm Flexible Job-Shop Scheduling Optimization
Liu Zhansheng Gao Yingping Yang Zhendong Jiang Yuanyang
School of Management, Hebei University of Technology, Tianjin P.R.China, 300130
国际会议
天津
英文
2007-10-20（万方平台首次上网日期，不代表论文的发表时间）