The discrete lot-sizing and scheduling problem

The discrete lot-sizing and scheduling problem consists in scheduling several products on a single machine so as to meet the known dynamic demand and to minimize the sum of inventory and setup cost. The planning interval is phased into many short periods, e.g. shifts or days, and setups may occur only at the beginning of a period. A branch-and-bound procedure is presented using Lagrangean relaxation for determining both lower bounds and feasible solutions. The relaxed problems are solved by dynamic programming. Computational results on a personal computer are reported for various examples from the literature with up to 12 products and 122 periods or 3 products and 250 periods. The procedure yields optimal solutions or at least feasible solutions with tight lower bounds in a few minutes. The results are compared with those obtained by solving the usual capacitated lot-sizing problem.