THE DYNAMIC LOT-SIZING PROBLEM WITH STARTUP AND RESERVATION COSTS

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.