A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, and minimum order quantity (CLSP-MOQ). In this problem, a demand must be satisfied at each period t over a planning horizon of T periods. This demand can be satisfied from the stock or by a production at the same period. When a production is made at period t, the produced quantity must be greater to than a minimum order quantity (L) and lesser than the production capacity (U). To solve this problem optimally, a polynomial time algorithm in O(T5) is proposed and it is computationally tested on various instances.

► We propose a polynomial time algorithm for the single item lot sizing problem. ► The problem considers concave costs and the minimum order quantity constraint. ► Computational experiments proved that the algorithm, in O(T5), is efficient.