EFFICIENT ALGORITHMS FOR FINDING OPTIMAL POWER-OF-2 POLICIES FOR PRODUCTION/DISTRIBUTION SYSTEMS WITH GENERAL JOINT SETUP COSTS
成果类型：
Article
署名作者：
FEDERGRUEN, A; ZHENG, YS
署名单位：
University of Pennsylvania
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.3.458
发表日期：
1995
页码：
458-470
关键词：
摘要：
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.