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

Awi Federgruen and Michal Tzur
Additional contact information
Awi Federgruen: Columbia University, New York, New York
Michal Tzur: Tel Aviv University, Tel Aviv, Israel

Operations Research, 1994, vol. 42, issue 6, 1067-1086

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 O ( mN 2 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%.

Keywords: inventory/production: joint replenishment problems; inventory/production; approximations: asymptotically-optimal heuristics (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.6.1067 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:6:p:1067-1086

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().