The Joint Replenishment Problem with Time-Varying Costs and Demands: Efficient, Asymptotic and ε-Optimal Solutions

We address the Joint Replenishment Problem (JRP) where, in the presence of joint setup costs, dynamic lot sizing schedules need to be determined for m items over a planning horizon of N periods, with general time-varying cost and demand parameters. We develop a new, so-called, partitioning heuristic for this problem, which partitions the complete horizon of N periods into several relatively small intervals, specifies an associated joint replenishment problem for each of these, and solves them via a new, efficient branch-and-bound method. The efficiency of the branch-and-bound method is due to the use of a new, tight lower bound to evaluate the nodes of the tree, a new branching rule, and a new upper bound for the cost of the entire problem. The partitioning heuristic can be implemented with complexity O(mN²log log N). It can be designed to guarantee an ε-optimal solution for any ε > 0, provided that some of the model parameters are uniformly bounded from above or below. In particular, the heuristic is asymptotically optimal as N → ∞ for any fixed number of items m, and it remains asymptotically optimal when both m and N are simultaneously increased to infinity. Most importantly, a numerical study shows that the partitioning heuristic performs exceptionally well. Even for small problems, the average optimality gap is only 0.38% and in none of the problem categories is it larger than 0.78%.