Heuristics for Multilevel Lot-Sizing with a Bottleneck

In this paper we present a heuristic method, based on Lagrangian relaxation, for multilevel lot-sizing when there is a single bottleneck facility. A series of Lagrangian relaxations (one for each item in the product structure) is imbedded in a branch and bound procedure. The objective is to find a production schedule that fits within available capacity at minimum cost. The method has two solution phases, dual and primal. In the dual phase of the procedure, implied costs of setups and production are determined based on a tentative schedule. The primal phase is repeated with these new prices and we iterate to reach a good solution. The solution procedure is first tested on two special cases: uncapacitated multilevel lot-sizing and the capacitated, single-level multi-item lot sizing problem. The results show that the solution procedure can provide better solutions than some heuristics designed especially for those problems. Test results on the bottleneck problem indicate that good feasible solutions are found for problems too difficult to solve with exact methods.