Solving linear cost dynamic lot-sizing problems in O(n log n) time
成果类型：
Article
署名作者：
Ahuja, Ravindra K.; Hochbaum, Dorit S.
署名单位：
State University System of Florida; University of Florida; University of California System; University of California Berkeley; University of California System; University of California Berkeley
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1070.0508
发表日期：
2008
页码：
255-261
关键词：
摘要：
In this paper, we study capacitated dynamic lot-sizing problems with or without backorders, under the assumption that production costs are linear, that is, there are no setup costs. These two dynamic lot-sizing problems ( with or without backorders) are minimum-cost flow problems on an underlying network that possess a special structure. We show how the well-known successive shortest-path algorithm for the minimum-cost flow problem can be used to solve these problems in O(n(2)) time, where n is the number of periods in the dynamic lot-sizing problems, and how, with the use of dynamic trees, we can solve these problems in O(nlog n) time. Our algorithm also extends to the dynamic lot-sizing problem with integer variables and convex production costs with running time O(n log n logU), where U is the largest demand value.