98%-effective lot-sizing for assembly inventory systems with backlogging
成果类型：
Article
署名作者：
Sun, DN; Atkins, D
署名单位：
University of British Columbia
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.6.940
发表日期：
1997
页码：
940-951
关键词：
摘要：
In the previous work, we have shown that for a production/inventory system arranged in series with backlogging at its final product, the total cost of the best power-of-two frequency lot-size heuristic is within 6% of the optimal (or 2% if the base period is allowed to vary). In this paper, we extend our results to an assembly production/inventory system with constant external demand at its final product with backlogging allowed. By using a submodular property, we show that the total cost of any feasible policy is bounded below by finding the minimum of a set of series systems. In this way, we can get a best power-of-two frequency policy that is within 2% of the optimal: However, the number of series systems to be considered fan be proportional to, in the worst case, the factorial of n (the number of nodes in the assembly system). As a consequence, this reduction cannot give us a polynomial algorithm and we have to use a different approach. By using a series of transformations, we reduce our problem to a special case of a polymatroidal network flow problem. The lower bound and the optimal power-of-two frequency policy for assembly systems with backlogging can then be found in O(n(6)) time.