AbstractIn this paper, we develop two new efficient heuristic procedures for the joint replenishment problem. Each of the two heuristic procedures generates iteratively a near-optimal replenishment policy starting with ordering frequencies that are derived from the solution to a relaxed version of the joint replenishment problem. Both heuristic procedures are illustrated with an example problem involving five jointly ordered items. Seven more illustrative problems, taken from the joint replenishment problem literature, are also solved to assess the cost performance of the two heuristic procedures. They both provide the global optimal replenishment policies for all the illustrative problems.