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, viable, 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.

Awi Federgruen and Yu-Sheng Zheng
Journal Article
Publication Date
Operations Research

Full Citation

Federgruen, Awi and Yu-Sheng Zheng
. “Efficient algorithms for finding optimal power-of-two policies for production/distribution systems with general joint setup costs.”
Operations Research
, (January 01, 1995):