基于差分进化与块结构邻域的作业车间调度优化

Differential Evolution Algorithm Based on Blocks on Critical Path for Job Shop Scheduling Problems

作业车间调度问题是一类非常重要的生产调度问题,具有广泛的工程应用背景。针对优化最大完成时间指标,研究通过交换或插入关键路径块结构中的工序产生可行解的方法,提出基于块结构的交换邻域和插入邻域。结合问题的结构特点和基本差分进化算法的原理,提出一种解决作业车间调度问题的离散差分进化算法。该算法采用基于操作的编码方式,设计了离散的变异算子和交叉算子,能够直接产生可行调度解。进而提出一种自适应的多邻域局部搜索算法,并将其嵌入离散差分进化算法中来改善优化质量;基于典型算例的仿真试验验证了所提算法的有效性和优越性。

Among all kinds of production scheduling problems,job shop scheduling problem（JSSP） is a key one with extensive engineering application background.The minimization of maximum completion time or makespan for JSSP is addressed.Based on some properties associated with the blocks of jobs on the critical path in the direct graph of JSSP,the way to generate feasible solution by an interchange or insertion operator is presented,and two specific search neighborhoods are obtained.Then a discrete differential evolution（DDE） algorithm with operation-based representation is developed for solving JSSP.The proposed DDE algorithm adopts a newly designed mutation and crossover operators and it can directly generate feasible solutions in the search space.An effective local search based on the newly obtained neighborhoods is presented and imbedded in the DDE algorithm to enhance the local search ability.Computational simulations and comparisons demonstrate the effectiveness and superiority of the proposed DDE algorithm.