EFFICIENT ALGORITHMS FOR FINDING OPTIMAL POWER-OF-2 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 ''pr oduct'' at a given location and/or production stage. An arc (i, j) ind icates 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 g iven proportions. The cost structure consists of inventory carrying, v ariable, and fixed production/distribution costs. The latter depend, a t any given replenishment epoch, on the specific set of items being re plenished, 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 low er bound for the minimum cost. In this paper, we derive efficient algo rithms for the computation of an optimal power-of-two policy, possibly in combination with this lower bound. These consist of a limited numb er of polymatroidal maximum flow calculations in networks closely asso ciated with the original production/distribution network.