98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems

A warehouse supplies N retailers. Constant external demand occurs at each retailer, and shortages are not allowed. There are linear holding costs and fixed costs for ordering at the warehouse and at each retailer. The goal is to minimize the long-run average cost over an infinite time horizon. We define a new class of policies for this problem whose simple structure facilitates both computation and implementation. The cost of a policy that is optimal within this class is shown to be within 2% of the cost of an optimal policy for the original problem, in the worst case. Such a policy can be computed in O(N log N) time.