Improved heuristic methods for multiple stage production planning

The multiple stage production planning problem addresses any system of inventoriable stocks related by precedence requirements. Such a system could involve fabrication of finished goods from component parts, transportation of assemblies between facilities, or both, as growing interest in supply chain management suggests there may no longer be a useful distinction between the production planning and distribution planning problem. Yet most previous efforts to develop effective planning algorithms have relied on the direct or adapted application of known single item lot sizing techniques, implicitly framing any multiple stage system as a direct extension of the single item lot sizing problem. Considering the latter is better described as a special case of the former, the purpose of this paper is to propose and evaluate a highly adaptable production planning heuristic developed explicitly for the multiple stage problem. 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.