Optimal Power-of-Two Replenishment Strategies in Capacitated General Production/Distribution Networks

In this paper we develop a model for a capacitated production/distribution network of general (but acyclic) topology with a general bill of materials, as considered in MRP (Material Requirement Planning) or DRP (Distribution Requirement Planning) systems. This model assumes stationary, deterministic demand rates and a standard stationary cost structure; it is a generalization of the uncapacitated model treated in the seminal papers of Maxwell and Muckstadt (1985) and Roundy (1986). The capacity constraints consist of bounds on the frequency with which individual items can or need to be replenished. We derive a pair of simple and efficient algorithms capable of determining an optimal power-of-two policy. These algorithms consist of a limited number of maximum flow computations in networks closely related to the production/distribution network. The complexity of these algorithms, even when applied to the uncapacitated model, compares favorably with that of the existing alternative solution methods.