AN ALGORITHM FOR SINGLE-ITEM CAPACITATED ECONOMIC LOT-SIZING WITH PIECEWISE-LINEAR PRODUCTION COSTS AND GENERAL HOLDING COSTS

We consider the Capacitated Economic Lot Size Problem with piecewise l inear production costs and general holding costs, which is an NP-hard problem but solvable in pseudopolynomial time. A straightforward dynam ic programming approach to this problem results in an O(n(2)(c) over b ar (d) over bar) algorithm, where n is the number of periods, and (d) over bar and care the average demand and the average production capaci ty over the n periods, respectively. However, we present a dynamic pro gramming procedure with complexity O(n(2)(q) over bar (d) over bar), w here (q) over bar is the average number of pieces required to represen t the production cost functions. In particular, this means that proble ms in which the production functions consist of a fixed set-up cost pl us a linear variable cost are solved in O(n(2)(d) over bar) time. Henc e, the running time of our algorithm is only linearly dependent on the magnitude of the data. This result also holds if extensions such as b acklogging and startup costs are considered. Moreover, computational e xperiments indicate that the algorithm is capable of solving quite lar ge problem instances within a reasonable amount of time. For example, the average time needed to solve test instances with 96 periods, 8 pie ces in every production cost function, and average demand of 100 units is approximately 40 seconds on a SUN SPARC 5 workstation.