Template-Type: ReDIF-Paper 1.0 Author-Name: Shaw, D.X. Author-Name-Last: Shaw Author-Name: Wagelmans, A.P.M. Author-Name-Last: Wagelmans Author-Name-First: Albert Title: An Algorithm for Single-item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs Abstract: 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 [TeX: $O(n^2 \\bar{c} \\bar{d} )$] algorithm, where [TeX: $n$] is the number of periods, and [TeX: $\\bar d$ and $\\bar c$] are the average demand and the average production capacity over the $n$ periods, respectively. However, we present a dynamic programming procedure with complexity [TeX: $O(n^2 \\bar{q} \\bar{d} )$], where [TeX: $\\bar q$] is the average number of pieces of 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 [TeX: $O(n^2 \\bar{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 start-up 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 function and average demand of 100 units, is approximately 40 seconds on a SUN SPARC 5 workstation. Creation-Date: 1995-01-01 File-URL: https://repub.eur.nl/pub/1353/1353.pdf File-Format: application/pdf Series: RePEc:ems:eureir Number: EI 9526-/A Keywords: computational complexity, dynamic programming, economic lot sizing Handle: RePEc:ems:eureir:1353