Polynomial-time solvability of dynamic lot size problems

Abstract

There has been a lot of research on dynamic lot sizing problems with different nonlinear cost structures due to capacitated production, minimum order quantity requirements, availability of quantity discounts, etc. Developing optimal solutions efficiently for dynamic lot sizing models with nonlinear cost functions is a challenging topic. In this paper, we present a set of sufficient conditions such that if a single-item dynamic lot sizing problem satisfies these conditions, then the existence of a polynomial-time solution method for the problem is guaranteed. Several examples are presented to demonstrate the use of these sufficient conditions.