98%-effective lot-sizing for assembly inventory systems with backlogging

In the previous work, we have shown that for a production/inventory system arranged in series with back-logging 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 can 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⁶) time.