A column generation approach for discrete lotsizing and scheduling problem on identical parallel machines

In this paper the Discrete Lotsizing and Scheduling Problem (DLSP) on identical parallel machines with setup times is considered. The problem is determining the sequence and size of production batches for multiple items. The objective is to find a minimal cost production schedule such that deterministic, dynamic demand is fulfilled with backlogging. The problem is formulated as an integer programming problem and reformulated as a Generalized Set Partitioning Problem (GSPP). We show that a problem which checks optimality of LP relaxation problem of GSPP is equivalent to a single item, namely, a discrete lotsizing scheduling problem on parallel machines. It means that GSPP is decomposed to subproblems, and each one is solvable with dynamic programming. We obtain the lower bound of the reformulated problem by solving a LP relaxation problem of GSPP optimally and present a column generation heuristic to solve GSPP, which optimizes the restricted GSSP composed with columns generated at that time. The quality of the solutions can be measured, since the heuristic generates both lower and upper bounds. We compare our algorithm and a heuristic based on Lagrangian relaxation proposed by Campbell. Computational results on a personal computer show that our heuristic is rather effective in terms of quality of the solutions. One of the advantages of the column generation method is that the setting of parameters is not required in contrast to Lagrange relaxation.