The Dynamic Lot-Sizing Problem with Startup and Reservation Costs

Dynamic lot-sizing models often assume that a production system incurs a fixed cost in each period that production is positive. In this paper, we consider a model with a startup cost incurred for switching on the production facility and a separate reservation cost charged for keeping the facility on whether or not it is used for production. Computationally, this problem is as hard as the usual model; the general capacitated case is NP-hard. We present a dynamic programming algorithm for the uncapacitated case, and a branch-and-bound approach using Lagrangian relaxation for the capacitated problem. We report computational experience on both the quality of the bounds employed and the effectiveness of the algorithm.