## Awi Federgruen

*The joint replenishment problem with time-varying costs and demands: Efficient, asymptotic and ε-optimal solutions*

Coauthor(s): Michal Tzur.

#### Download:

Adobe Acrobat PDF

**Abstract:**

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 *0*(*mN*^{2}loglog*N*). It can be designed to guarantee an *e*-optimal solution for any *e* > 0, provided that some of the model parameters are uniformly bounded from above or below. In particular, the heuristic is asymptotically optimal as *N* approaches infinity 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%.

**Source:** *Operations Research*

**Exact Citation:**

Federgruen, Awi, and Michal Tzur. "The joint replenishment problem with time-varying costs and demands: Efficient, asymptotic and ε-optimal solutions." *Operations Research* 42, no. 6 (1994): 1067-1086.

**Volume:** 42

**Number:** 6

**Pages:** 1067-1086

**Date:**
1994