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

Genetic algorithm with forward-backward scheduling for job-shop problems

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

     

    Abstract: When the standard genetic algorithm is applied into job-shop scheduling problems,it has the common defects of early convergence and easily falling into local minimization.A dynamic double-population genetic algorithm based on domain knowledge is applied into job-shop scheduling problems.Since the optimal schedule is active,the active scheduling technique is used to reduce the search space.Moreover,the forward and backward scheduling strategies are adopted to improve the population diversity by the two subpopulations,respectively.A new chromosome encoding is used to represent the active schedule.With this coding scheme,the initialization strategy,the genetic operations of every subpopulation and the crossover operator between the two subpopulations are proposed.Experimental results of the Benchmark instances taken from literatures indicate that it outperforms current approaches in computational time and quality of the solutions.

     

/

返回文章
返回