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

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