双阈值控制的遗传算法求解作业车间调度问题

Genetic algorithm controlled by two thresholds for Job Shop scheduling problem

针对作业车间调度问题自身的求解难点和遗传算法的特点,分析了目前遗传调度算子存在的问题,提出了一种双阈值控制的多父辈POX交叉算子,即用父辈相似度阈值调整变异的时间,收敛度阈值调整变异概率,在变异的同时提高交叉性能。利用这种方法求解作业车间调度问题,能防止父个体相似时交叉不能产生新个体,防止交叉产生的优秀个体再变异,并防止早熟现象。仿真实验表明,该算法可以显著提高解的质量和收敛速度。

Aiming at the difficulty of the Job Shop scheduling problem and the characteristics of the Genetic Algorithm （GA）, the problems existing in genetic operator were analyzed, and a Multi--parent Precedence Operation Crossover （MPOX） operator controlled by two thresholds was proposed. Mutation time was adjusted by parents similarity threshold, and mutant probability was adjusted by restrain degree threshold. In the mutation process, the performance of crossing was improved. Applying this method in solving Job Shop scheduling problem, phenomena were avoided such as new individuals could not be produced while parent individuals were similar, variation of the outstanding individual by crossing, and premature. Simulation experiment indicated that, this algorithm could significantly improve the solution quality and its convergence speed.