Abstract: Aiming at the two-machine flow shop outsourcing and scheduling integrated optimization problem of minimizing the sum of in-house makespan and total outsourcing cost,a Hybrid Variable Neighborhood Search (HVNS) algorithm was proposed.In this algorithm,the initial joint decision solutions were obtained by performing problem-specific job removal-related heuristic approach.Based on three novel neighborhood structures,a best-improvement local- search procedure was designed to improve the resulted solutions through shaking.Besides,the probabilistic moving criterion was introduced to decide the target neighborhood in the next iteration.The appropriate selections for the changing sequence of neighborhoods and the way of calculating temperature parameter were achieved via extensive calibration experiments.The comparison results with CPLEX optimizer and the Implicit Enumeration Testing Procedure (IETP) showed that the calibrated HVNS was capable of finding the optimal solutions to the instances with n≤30 and much less computation time.In comparison with three algorithms by respectively using the genetic algorithm,simulated annealing and harmony search techniques,the calibrated HVNS showed significant superiority over three compared ones in terms of both solution quality and robustness.

Key words: scheduling, two-machine flow shop, outsourcing, variable neighborhood search algorithm

摘要： 针对最小化内部完工期与总外包费用的双机流水车间外包与调度联合优化问题,开发了一种混合变邻域搜索算法。在该算法中,采用工件剔除型启发式方法产生初始联合决策解;基于3种新型邻域结构提出了最佳改进式局部搜索规程;引入概率式准则来决定下轮迭代的目标搜索邻域。通过算法校准实验分析,探索出合适的邻域变更次序和温度参数的计算方式。通过与CPLEX软件、隐枚举测试程序对比显示,对于工件数不超过30的算例,校准后所提算法求得最优解的耗用时间更少。通过与遗传算法、模拟退火算法、和声搜索3种对比算法在工件数不少于100的算例上进行对比发现,所提算法经校准后,在求解质量和解的鲁棒性上均具有显著优势。

关键词: 调度, 双机流水车间, 外包, 混合变邻域搜索算法