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

通过分析柔性作业车间调度问题中工件与设备的特征及两者间的关系,提出了一种主-从遗传算法的调度方案。在该算法中,主、从染色体分别采用工件基因块和设备基因块的分块编码。主染色体代表可行加工路径组合,从染色体代表主染色体约束下的可行调度方案。然后,以最小化工件延迟时间为目标,为主染色体设计选择和多点变异两类遗传操作;以最小化设备空闲时间为目标,为从染色体设计选择、多点交叉和多点变异3类遗传操作。从染色体适应值取其代表的调度方案中工件流通时间的倒数,主染色体适应值取其对应从染色体种群的最优适应值。这种双层多点遗传操作避免了非可行解的产生,并可采用类似旅行商问题的遗传操作。最后,通过仿真和比较实验,验证了该算法的有效性。