Combining the principles of variable neighborhood decomposition search and the fix&optimize heuristic to solve multi‐level lot‐sizing and scheduling problems

In this paper a new heuristic is proposed to solve general multi‐level lot‐sizing and scheduling problems. The idea is to cross‐fertilize the principles of the meta‐heuristic Variable Neighborhood Decomposition Search (VNDS) with those of the MIP‐based Fix&Optimize heuristic. This combination will make it possible to solve the kind of problems that typically arise in the consumer goods industry due to sequence‐dependent setups and shifting bottlenecks. In order to demonstrate the strength of this procedure, a GLSP variant for multiple production stages is chosen as a representative. With the help of artificial and real‐world instances, the quality of the solution as well as the computational performance of the new procedure is tested and compared to a standard MIP‐solver.