基于关键路径疫苗的免疫遗传算法求解JSP问题

Immune Genetic Algorithms for Job-shop Scheduling Based on Critical Path Vaccine

车间作业调度是决定工件加工顺序以及分配相应设备的过程,合理的调度方案能提高设备利用率。针对单件车间调度问题,采用免疫遗传算法进行调度方案求解。基于关键路径的思想,提出一种新的疫苗提取和接种方法。疫苗提取时,取种群中最优个体的关键路径信息作为疫苗,接种时,依据该疫苗信息修改待接种个体各机器上的工件安排顺序,从而继承最优个体关键路径上的信息,提高个体适应度,加速算法寻优过程。通过对标准测试案例的求解,以及与其他算法的比较,结果表明关键路径疫苗技术是有效的。

This paper proposes a new method of extracting and injecting vaccine based on the idea of critical path.Taking the critical path information of best individual as vaccine when extracting vaccine.Modifing the order of the workpiece on machine of individuals to be vaccinated according to the information of vaccine when injecting vaccine.Thus improve individual fitness and accelerate algorithm optimization process by inheriting the best individual＇s information on the critical path.