The joint replenishment problem: New heuristics and worst case performance bounds

The joint replenishment problem involves the lot sizing of several items with nonstationary demand in discrete time. The items have individual ordering costs and linear inventory holding costs. In addition, a joint ordering cost is incurred whenever one or more items is ordered together. This problem often arises when economies can be affected by coordinated ordering or setup of the items, both in distribution and in manufacturing environments. This problem is known to be NP-complete. In this paper, the worst case performance of an existing multipass heuristic for the problem is analyzed. Then a new single pass forward heuristic is proposed, and it is proved that it has a uniformly bounded worst case performance. Furthermore, a lower bound on the cost of the optimal solution is obtained once the heuristic has been used. The paper then discusses a number of related heuristic algorithms and their worst case performance. The behavior of the present heuristics for a randomly generated set of problems is also studied.