基于主-从遗传算法求解柔性调度问题  

Solving flexible Job-Shop scheduling problems based on master-slave genetic algorithm

作　　者：张维存[1] 郑丕谔[1] 吴晓丹[2] 

机构地区：[1]天津大学管理学院,天津300072 [2]河北工业大学管理学院,天津300130

出　　处：《计算机集成制造系统》2006年第8期1241-1245,共5页Computer Integrated Manufacturing Systems

基　　金：河北省教育厅博士基金资助项目(B2004405)~~

摘　　要：通过分析柔性作业车间调度问题中工件与设备的特征及两者间的关系,提出了一种主-从遗传算法的调度方案。在该算法中,主、从染色体分别采用工件基因块和设备基因块的分块编码。主染色体代表可行加工路径组合,从染色体代表主染色体约束下的可行调度方案。然后,以最小化工件延迟时间为目标,为主染色体设计选择和多点变异两类遗传操作;以最小化设备空闲时间为目标,为从染色体设计选择、多点交叉和多点变异3类遗传操作。从染色体适应值取其代表的调度方案中工件流通时间的倒数,主染色体适应值取其对应从染色体种群的最优适应值。这种双层多点遗传操作避免了非可行解的产生,并可采用类似旅行商问题的遗传操作。最后,通过仿真和比较实验,验证了该算法的有效性。A genetic algorithm with master-slave structure was proposed to solve the flexible Job-Shop scheduling problems based on the analysis of jobs, machines and their relationships. The master and slave chromosomes were broken into blocks according to jobs or machines respectively. The master chromosomes represented feasible processing route combinations, while the slave chromosomes represented feasible scheduling schemes subjected to master chromosome. In order to minimize delay time of jobs, the genetic operators such as selection, multi-point crossover were designed for job-gene block. At the same time, the selection operator, multi-point crossover operator and multi-point mutation operator were designed for machine-gene block in order to minimize idle time of machines. The reciprocal of make-span was obtained as fitness value of one scheduling scheme from slave chromosomes. Then, the master chromosome got its fitness value from the best fitness value of its constrained slave chromosomes. Furthermore, illegal schemes could be avoided and some genetic operators designed for Traveling Salesman Problems （TSP） could be adopted because of our proposed double levels structure and multi-points operators. The simulation results and comparison with others＇ verified the effectiveness of the proposed algorithm.

关 键 词：遗传算法 柔性作业车间调度 优化 

分 类 号：F406.2[经济管理—产业经济]