Efficient Algorithms for Finding Optimal Power-of-Two Policies for Production/Distribution Systems with General Joint Setup Costs

We consider a production/distribution system represented by a general directed acyclic network. Each node is associated with a specific “product” at a given location and/or production stage. An arc ( i , j ) indicates that item i is used to “produce” item j . External demands may occur at any of the network's nodes. These demands occur continuously at item-specific constant rates. Components may be assembled in any given proportions. The cost structure consists of inventory carrying, variable, and fixed production/distribution costs. The latter depend, at any given replenishment epoch, on the specific set of items being replenished, according to an arbitrary set function merely assumed to be monotone and submodular. It has been shown that a simply structured, so-called power-of-two policy is guaranteed to come within 2% of a lower bound for the minimum cost. In this paper, we derive efficient algorithms for the computation of an optimal power-of-two policy, possibly in combination with this lower bound. These consist of a limited number of polymatroidal maximum flow calculations in networks closely associated with the original production/distribution network.