蚁群遗传算法求解能力约束的柔性作业车间调度问题

Solution to flexible Job Shop scheduling problems with capacitated constraints based on ant colony & genetic algorithms

提出一种主、从递阶结构的蚁群遗传求解算法。算法中,主级为蚁群算法,完成工件组合和加工路径选择;从级为遗传算法,完成主级约束下的设备排产。分别以工件延迟时间和设备可用能力为启发式信息,设计蚂蚁工件间和设备间的转移概率;以设备空闲时间最小为目标,设计从级染色体选择、多点交叉和多点变异3类遗传操作。从级染色体适应值取其代表调度方案中工件流通时间的倒数,从蚂蚁游历值取其对应从级染色体种群的最优适应值。最后,通过仿真和比较实验,验证了该算法的有效性。

A hybrid algorithm of ant colony ＆ genetic algorithms was proposed to solve the flexible Job Shop scheduling problem capacitated constraints. The hybrid algorithm was formulated in a form of master--slave hierarchical structure. The ant colony algorithm performed as the master level to fulfill job combinations and select job-- processing route, while the genetic algorithm carried out at the slave level to match jobs with machines without violating the result from the master level. The transfer probabilities of ants between jobs and between machines were designed by using heuristic information of parts＇ time delay and devices＂ available capacity respectively. Genetic operations of the selection, multi-- point crossover and multi-- point mutation were well designed to minimize idle time of machines. The fitness value of slave chromosomes was regarded as the reciprocal of makespan in Job Shop scheduling, and the best fitness value in a population of corresponding slave chromosomes was considered as traveling value of the ant. Finally, the simulation and results from comparison with other algorithms demonstrated the effectiveness of the proposed algorithm.