基于混合遗传算法的柔性车间调度问题研究

Research on Flexible Shop Scheduling Based on Improved Hybrid Genetic Algorithm

以最大完工时间最短为目标研究柔性作业车间静态调度问题,提出一种改进的基于模拟退火的混合遗传算法。为贴近实际车间环境,根据是否考虑工件运输时间构建了两种并行的约束规则。对遗传算法的交叉算子进行改进,提高后代种群个体的多样性,通过引入黄金分隔法,将算法迭代过程划分成前中后三个阶段,并制定不同阶段的模拟退火算法融入规则,以提高种群的收敛速度并防止种群陷入局部最优。利用标准车间实例对算法进行对比测试,所提出的改进混合遗传算法明显优于传统的混合算法。

Taking the shortest maximum completion time as the goal to study the static scheduling problem of flexible job shop,an improved hybrid genetic algorithm based on simulated annealing was proposed.In order to be close to the actual workshop environment,two parallel constraint rules were constructed based on whether to consider the workpiece transportation time.The crossover operator of the genetic algorithm was improved to increase the diversity of the population individual of the offspring.By introducing the golden separation method,the iterative process of the algorithm was divided into three stages,the first,the middle and the last.The simulated annealing algorithm of different stages was formulated to integrate the rules to improve the convergence rate of the population and prevent the population from falling into local optimum.Using standard workshop examples to compare and test the algorithm,the proposed improved hybrid genetic algorithm was obviously superior to the traditional hybrid algorithm.