In this paper we study a new class of capacitated economic lot-sizing problems. We
show that the problem is NP-hard in general and derive a fully polynomial-time approximation
algorithm under mild conditions on the cost functions. Furthermore, we
develop a polynomial-time dynamic programming algorithm for the case where all cost
functions are concave. Finally, we extend our results to allow for backlogging.