A decomposition approach for the General Lotsizing and Scheduling Problem for Parallel production Lines

• A novel solution heuristic for the General Lotsizing and Scheduling Problem for Parallel production Lines is presented.
• The idea is to iteratively decompose the parallel-line problem into a series of single-line problems.
• The new heuristic improves already existing approaches.
• Large practical applications can now be solved.

This paper presents a novel solution heuristic to the General Lotsizing and Scheduling Problem for Parallel production Lines (GLSPPL). The GLSPPL addresses the problem of simultaneously deciding about the sizes and schedules of production lots on parallel, heterogeneous production lines with respect to scarce capacity, sequence-dependent setup times and deterministic, dynamic demand of multiple products. Its objective is to minimize inventory holding, sequence-dependent setup and production costs. The new heuristic iteratively decomposes the multi-line problem into a series of single-line problems, which are easier to solve. Different approaches for decomposition and for the iteration between a modified multi-line master problem and the single-line subproblems are proposed. They are compared with an existing solution method for the GLSPPL by means of medium-sized and large practical problem instances from different types of industries. The new methods prove to be superior with respect to both solution quality and computation time.