Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs

We consider a production/distribution network represented by a general directed acyclic network. Each node is associated with a specific “product” or item 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, and 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.

We show that a simply structured, so-called power-of-two policy is guaranteed to come within 2% of a lower bound for the minimum cost. Under a power-of-two policy, all items are replenished at constant intervals and only when their inventory drops to zero; moreover, these replenishment intervals are all power-of-two multiples of a common base planning period. The above results generalize those of Roundy (1986).