THE JOINT REPLENISHMENT PROBLEM WITH TIME-VARYING COSTS AND DEMANDS - EFFICIENT, ASYMPTOTIC AND EPSILON-OPTIMAL SOLUTIONS

• 成果类型: Article
• 署名作者: FEDERGRUEN, A; TZUR, M
• 署名单位: Tel Aviv University; University of Pennsylvania
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.42.6.1067
• 发表日期: 1994
• 页码: 1067-1086

摘要

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(mN2loglogN). It can be designed to guarantee an epsilon-optimal solution for any epsilon > 0, provided that some of the model parameters are uniformly bounded from above or below. In particular, the heuristic is asymptotically optimal as N --> 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 is larger than 0.78%.