An Efficient Procedure for Dynamic Lot-sizing Model with Demand Time Windows

We consider a dynamic lot-sizing model with demand time windows where n demands need to be scheduled in T production periods. For the case of backlogging allowed, an O(T3) algorithm exists under the non-speculative cost structure. For the same model with somewhat general cost structure, we propose an efficient algorithm with O(max {T2, nT}) time complexity.