Improved heuristic methods for multiple stage production planning

Multiple stage production planning typifies any system in which the scheduling of some production stage may place demands on necessary predecessor stages, or constrain the schedules of successor stages. This paper considers detailed material planning, or lot sizing, in a multiple stage, dynamic demand environment. A new heuristic method for developing such production schedules is introduced, based on a structured neighborhood search approach to these problems. An efficient lower bounding technique is also presented, employing Lagrangian relaxation and an alternate approach to the mathematical formulation of a multiple stage planning problem. This technique was employed to find lower bounds on all numerical experiments. The scope of the investigation, with respect to the number of improved heuristic methods included for comparison, is among the broadest in the literature. The new heuristic performed consistently better than other methods, producing solutions which were within an average of 1% of optimal.