An Approximate Dynamic-Programming Approach to the Joint Replenishment Problem

• 成果类型: Article
• 署名作者: Segev, Danny
• 署名单位: University of Haifa
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0611
• 发表日期: 2014
• 页码: 432-444
• 关键词: lot-size model; systems; COSTS

摘要

The main contribution of this paper is to propose a new dynamic-programming approach that epsilon-approximates the joint replenishment problem, with stationary demands and holding costs, in its discrete-time finite-horizon setting. Our first and foremost objective is to show that the computation time of classical dynamic-programming algorithms can be improved on by orders of magnitude when one is willing to lose an epsilon-factor in optimality. Based on synthesizing ideas such as commodity aggregation, approximate dynamic programming, and a few guessing tricks, we show that one can attain any required degree of accuracy in near-polynomial time.