Computing Nested Reorder Intervals for Multi-Item Distribution Systems

We consider a multistage, multi-item distribution system in which each of a number of items is stocked at each of a number of locations. The cost of placing an order at a location depends on the set of items ordered there. Demand for the items is constant, and there is a linear holding cost for each item at each location. Only nested policies are considered. A known heuristic is guaranteed to find a policy that is within 2% of optimal. However, if there are M items and L locations the running time of the heuristic is O(M⁴L⁴). We improve the running time to O(MLD log(ML)) where D is at most the maximum of the depth of the location and family arborescences.