带工艺约束并行机调度问题的一种新的遗传算法

以最小化拖期任务数为目标,研究了解决一类带工艺约束并行机调度问题的新的遗传算法.基于向量组的染色体编码方法简单、译码快速,并能自动满足工艺约束;扩展的顺序交叉算子EOX能自动满足工艺约束并尽量保留父代遗传信息,在较大程度上优于传统的交叉算子;位变异和交换变异相结合的变异方法有利于更好保持种群的多样性.大量模拟数据与生产线应用实例表明本文所提的基于向量组编码的遗传算法是相当有效的.

A New Genetic Algorithm for Parallel Machine Scheduling with Process Constraint

A new genetic algorithm is studied for solving parallel machine scheduling problems with process constraint to minimize the total number of tardy jobs.A so-called vector-group coding method is presented,which shows the quality of coding simply,decoding fast and satisfying process constraints automatically.A new crossover operator named Extended Order Crossover (EOX) is then proposed,which has the merits of automatically satisfying procedure constraints and preserving much genetic information.Mutation,the other genetic operator,is implemented with the combination of bit-mutation and swap-mutation to keep the population diverse.The algorithm behaves more efficiently than others experimentally using various random data and application instance from practical production line.