Capacitated Lot-Sizing and Scheduling by Lagrangean relaxation

Development of new models and solution procedures for production planning has been of research interest for several decades. Implementation of these models has resulted in lower production costs by reducing inventories, number of setups and labor costs. In this paper, the authors develop several optimal/near-optimal procedures for the Capacitated Lot-Sizing and Scheduling Problem with setup times, limited regular time and limited overtime. They formulate a mixed-integer linear programming model of the problem and solve it by Lagrangean relaxation. The authors experiment with alternative Lagrangean relaxations and develop new procedures to solve these relaxations. Overall, the capacity constraints relaxation seems to be superior to the demand constraints relaxation. The present results show that large problems can be solved in reasonable computer times and within one-percent accuracy of the optimal solutions. They solved 99×8 (i.e., 99 items and 8 periods), 50×12 and 50×8 problems in 30.61, 36.25 and 12.65 seconds of CDC Cyber 730 computer time, respectively. The present procedures are general enough to be applied directly or with slight modifications in real-life production settings.