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

关键词：作业车间调度问题 差分进化算法 最大完成时间 局部搜索 

单位：华中科技大学数字制造装备与技术国家重点实验室 武汉430074 聊城大学计算机学院 聊城252059 清华大学信息科学与技术国家实验室 北京100084