A collaborative variable neighborhood descent algorithm for the hybrid flowshop scheduling problem with consistent sublots

Lot streaming is the most widely used technique of supporting the overlap of consecutive operations. Inspired by the real-world scenarios, this paper introduces this issue into the hybrid flowshop scheduling problem with consistent sublots (HFSP_CS). The innovations of this paper lie in developing a mixed integer linear programming (MILP) model, and in developing a collaborative variable neighborhood descent algorithm (CVND). The CVND evolves with a primary solution and an archive set comprising of promising solutions found in the progress, and contains four processes including the VND process, collaborative process, archive set and primary solution restart processes. Accordingly, the primary solution conducts the VND process with the defined neighborhood structures to implement the local exploitation. The archive set executes the collaborative process to learn from the historical information to implement the global search. The archive set restart is triggered when it is stuck into the local optima. The primary solution restart aims to conduct a large perturbation on the primary solution for the following loop of VND process. Regarding the problem-specific characteristics, the solution encoding and decoding are designed and an improvement strategy is developed to further improve the solution quality. To validate the CVND, two sets of instances are collected. Through comparing with the CPLEX solver, a heuristic and five state-of-the-art metaheuristics on small instances, the CVND shows the most suitable performance in terms of the objective values and algorithm efficiency. Through comparing with the heuristic and metaheuristics on medium-large instances, the CVND performs statistically better in terms of the relative percentage deviation values. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper introduces the issue of consistent sublots into the hybrid flowshop scheduling problem and develops a mixed integer linear programming (MILP) model and a collaborative variable neighborhood descent algorithm (CVND). The CVND shows excellent performance in local exploitation and global search, with high algorithm efficiency. Results indicate that the CVND has significant advantages in solution quality and relative percentage deviation values.