A polynomial time algorithm for the single-item lot sizing problem with capacities, minimum order quantities and dynamic time windows

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, considering minimum order quantity and dynamic time windows. The frequency constraints on the production lots are modeled by dynamic time windows. Between two consecutive production lots, there are at least QQ periods and at most RR periods. This paper presents an optimal algorithm in O((T−Q)2(R−Q)T4Q3), which is bounded byO(T7)O(T7).