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 linear production costs and general holding costs, which is an NP-hard problem but solvable in pseudo-polynomial time. A straightforward dynamic programming approach to this problem results in an O(n²cd) algorithm, where n is the number of periods, and d and c are the average demand and the average production capacity over the n periods, respectively. However, we present a dynamic programming procedure with complexity O(n²qd), where q 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²d) 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.