具有串并行异类工序约束的多柔性车间联合调度

Joint scheduling of multiple flexible workshops with serial and parallel heterogeneous process constraints

为了减少具有串并行异类工序约束多车间联合调度的总延期时间,提出了基于知识牵引遗传算法的调度求解方法。首先,采用扩展工艺树描述串并行异类工序约束,并基于无向图描述机器在多车间的分布;针对染色体初始化和进化过程中的扩展工艺树约束,定义了紧前工序数和剩余紧前工序数的概念,基于剩余紧前工序数设计了染色体初始化和进化方法;为了提高遗传算法的进化能力,将种群进化能力和最优个体进化能力作为知识,用于牵引算法的进化方式和方向,从而提出了知识牵引遗传算法的求解方法。经实验验证,知识牵引遗传算法调度的总延期时间均值最小,为30.8 h,说明该算法在多车间调度中具有最好的优化性能;且总延期时间盒须图长度最小,说明知识牵引遗传算法的稳定性也较好。

In order to reduce the total delay time of multi workshop joint scheduling with serial parallel heterogeneous process con-straints,a scheduling solution method based on knowledge guided genetic algorithm was proposed.Firstly,an extended process tree was used to describe the constraints of serial parallel heterogeneous processes,and the distribution of machines in multiple workshops was described based on an undirected graph.To address the constraints of the extended process tree during chromo-some initialization and evolution,the concepts of the number of tight preceding steps and the number of remaining tight preceding steps were defined.Based on the number of remaining tight preceding steps,chromosome initialization and evolution methods were designed.In order to improve the evolutionary ability of genetic algorithms,the population evolutionary ability and the opti-mal individual evolutionary ability were used as knowledge to drive the evolutionary mode and direction of the algorithm,thus a solution method based on knowledge guided genetic algorithm was proposed.After experimental verification,the average total de-lay time of knowledge driven genetic algorithm scheduling is the smallest,at 30.8 hours,indicating that the algorithm has the best optimization performance in multi workshop scheduling.And the length of the total delay time box graph is the smallest,in-dicating that the stability of knowledge driven genetic algorithm is also good.