Abstract: Aiming at the problem of non-delay delivery of customer orders through joint optimization of outsourcing and internal job scheduling in job shop environment,a no-tardiness job shop scheduling model with outsourcing option was constructed.By taking the minimum makespan and total outsourcing cost as the optimization objective,a multi-objective differential evolution-variable neighborhood search algorithm was designed to solve the model.In the algorithm,a two-stage decoding scheme considering virtual machines based on a double-layer real number encoding scheme was proposed,the differential evolution operators were adaptively improved,and a variable neighborhood search method based on four different neighborhood structures was designed.The effectiveness of the improved items and the superiority of the proposed algorithm were verified by comparison experiments on modified job shop scheduling problem benchmarks.

Key words: outsourcing, job shop, no-tardiness, differential evolution, variable neighborhood search

摘要： 针对作业车间环境下通过外协加工与内部作业调度联合优化实现客户订单无拖期交付的问题,构建了考虑外协的作业车间无拖期调度模型,以最小化最大完工时间和总外协成本为优化目标,设计了一种多目标差分进化变邻域搜索算法对模型进行求解。在算法中,基于双层实数编码方案,提出了考虑虚拟机器的两阶段解码方案;对差分进化算子进行了适应性改进;设计了基于4种不同邻域结构的变邻域搜索方法。以作业车间调度问题基准算例为实验对象进行了仿真对比实验,验证了适应性改进项的有效性和所提算法的优越性。

关键词: 外协, 作业车间, 无拖期, 差分进化, 变邻域搜索