A forward algorithm for capacitated lot sizing problem with lost sales

This paper addresses a single item dynamic lot sizing problem where the inventory capacity is limited and shortages are allowed. Unsatisfied demand cannot be backlogged, which means lost sales. Costs are assumed to be time-varying. Some new properties are obtained in an optimal solution and a dynamic programming algorithm is developed to solve the problem in strongly polynomial with O(T3logT) time.