Material allocation in MRP with tardiness penalties

In this paper, we address some flaws in the material allocation function of Materials Requirements Planning (MRP). The problem formulation differs from standard MRP logic in certain important ways: start and finish times for orders are forced to be realistic and material allocations are made to minimize the total tardiness penalty associated with late completion. We show that the resulting MRP material allocation problem is NP-hard in the strong sense. A lower bound and a heuristic are developed from a mixed integer linear formulation and its Lagrangean relaxation. The lower bound and the heuristics are closer to the optimum in cases where there is either abundant material or considerable competition for material; in intermediate cases, small perturbations in material allocation can have a significant effect. A group of heuristics based on the MRP approach and its modifications is examined; they are optimal under certain conditions. An improvement method that preserves priorities inherent in any given starting solution is also presented. The Lagrangean heuristic performs better than the MRP based heuristics for a set of 3900 small problems, yielding solutions that are about 5% to 10% over the optimal. The best MRP based heuristic does about as well as the Lagrangean heuristic on a set of 120 larger problems, and is 25% to 40% better than the standard MRP approach, on the data sets tested.