基于正逆序策略求解Job Shop的遗传调度算法

• 作 者: 王伟玲 李铁克 苏志雄
• 机 构: 北京科技大学经济管理学院,
• 出 处: 北京科技大学学报
• 发表日期: 2010年06期
• 关键词: 遗传算法 调度算法 车间作业调度 Job Shop 染色体编码 Benchmark 双种群 求解质量 局部极值点 调度问题

针对标准遗传算法在求解车间作业调度问题中易陷入局部极值点的缺点,提出了一种基于领域知识的动态双种群遗传算法.由于最优调度必定是活动调度,算法利用活动调度技术来进行空间缩减;两个子种群分别采用正、逆序调度策略来提高种群的多样性.算法采用一种新的染色体编码来表示活动调度方案,并给出了相应子种群的初始化策略、遗传操作,以及子种群之间的交叉方式.Benchmark算例的仿真实验与分析表明,该算法在计算时间和求解质量上均具有较好的效果.

Aimed at the shortcomings of standard genetic algorithm in solving job shop scheduling problem easily, this paper proposes a dynamic two-species genetic algorithm based on domain knowledge.As the optimal scheduling must be activity scheduling, the algorithm uses activity scheduling technology And the space is reduced.The two sub-populations adopt positive and reverse scheduling strategies respectively to improve the diversity of the population.The algorithm uses a new chromosome coding to represent the activity scheduling scheme and gives the corresponding strategy of subpopulation initialization, genetic operation, The crossover between populations.Benchmark example simulation and analysis show that the algorithm has good effect on the calculation time and quality of solution.