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, we develop several optimal/near-optimal procedures for the Capacitated Lot-Sizing and Scheduling Problem (CLSP) with setup times, limited regular time and limited overtime. We formulate a mixed-integer linear programming model of the problem and solve it by Lagrangean relaxation. We 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. Our results show that large problems can be solved in reasonable computer times and within one-percent accuracy of the optimal solutions. We 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. Our procedures are general enough to be applied directly or with slight modifications in real-life production settings.