Multilevel capacitated lotsizing complexity and LP-based heuristics

This paper presents the first heuristics capable of solving multilevel lotsizing problems with capacity constraints on more than one level. Moreover, the form of the heuristics is quite general so that they can easily be extended to solve a variety of problems. If one wants to solve these problems on a routine basis in a real environment one needs to find fast and easy algorithms. However, the authors show that for certain problem classes this is a very difficult task, far more difficult than has been suggested in the literature. For problems with setup times they show that finding a feasible solution is NP-complete. Even without setup times testing for feasibility can be very difficult. Just how time consuming such heuristics must be is demonstrated. This leaves little chance to build fast and easy heuristics except for the most simple cases. The present exploration of the complexity issues points to mathematical programming as a potential source of heuristics for these problems. This paper presents a new and general approach based on rounding an LP solution for the problem without setup times. The methods use different information and patterns evident in the LP solution are explored. The approach is tested on a large set of problems. The main contributions of this paper are the way in which the authors distinguish between the easy and hard lotsizing problems, the LP-based heuristics and the test set of capacitated multilevel lotsizing problems.