An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs

被引:67
作者
Shaw, DX [1 ]
Wagelmans, APM
机构
[1] Purdue Univ, Sch Ind Engn, W Lafayette, IN 47907 USA
[2] Erasmus Univ, Inst Econometr, NL-3000 DR Rotterdam, Netherlands
关键词
economic lot sizing; dynamic programming; computational complexity;
D O I
10.1287/mnsc.44.6.831
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We consider the Capacitated Economic Lot Size Problem with piecewise linear production costs and general holding costs, which is an NP-hard problem but solvable in pseudopolynomial time. A straightforward dynamic programming approach to this problem results in an O(n(2)(c) over bar (d) over bar) algorithm, where n is the number of periods, and (d) over bar and care the average demand and the average production capacity over the n periods, respectively. However, we present a dynamic programming procedure with complexity O(n(2)(q) over bar (d) over bar), where (q) over bar is the average number of pieces required to represent the production cost functions. In particular, this means that problems in which the production functions consist of a fixed set-up cost plus a linear variable cost are solved in O(n(2)(d) over bar) time. Hence, the running time of our algorithm is only linearly dependent on the magnitude of the data. This result also holds if extensions such as backlogging and startup costs are considered. Moreover, computational experiments indicate that the algorithm is capable of solving quite large problem instances within a reasonable amount of time. For example, the average time needed to solve test instances with 96 periods, 8 pieces in every production cost function, and average demand of 100 units is approximately 40 seconds on a SUN SPARC 5 workstation.
引用
收藏
页码:831 / 838
页数:8
相关论文
共 7 条
[1]  
Aho A. V., 1983, DATA STRUCTURES ALGO
[2]   COMPUTATIONAL-COMPLEXITY OF THE CAPACITATED LOT SIZE PROBLEM [J].
BITRAN, GR ;
YANASSE, HH .
MANAGEMENT SCIENCE, 1982, 28 (10) :1174-1186
[3]   A DYNAMIC-PROGRAMMING ALGORITHM FOR DYNAMIC LOT-SIZE MODELS WITH PIECEWISE-LINEAR COSTS [J].
CHEN, HD ;
HEARN, DW ;
LEE, CY .
JOURNAL OF GLOBAL OPTIMIZATION, 1994, 4 (04) :397-413
[4]   DETERMINISTIC PRODUCTION PLANNING - ALGORITHMS AND COMPLEXITY [J].
FLORIAN, M ;
LENSTRA, JK ;
RINNOOYKAN, AHG .
MANAGEMENT SCIENCE, 1980, 26 (07) :669-679
[5]   FACETS AND ALGORITHMS FOR CAPACITATED LOT SIZING [J].
LEUNG, JMY ;
MAGNANTI, TL ;
VACHANI, R .
MATHEMATICAL PROGRAMMING, 1989, 45 (02) :331-359
[6]   VALID INEQUALITIES AND SEPARATION FOR CAPACITATED ECONOMIC LOT SIZING [J].
POCHET, Y .
OPERATIONS RESEARCH LETTERS, 1988, 7 (03) :109-115
[7]  
SHAW DX, 95167 TI ER U ROTT T