We consider a dynamic lot-sizing model with production time windows where each of n demands has earliest and latest production due dates and it must be satisfied during the given time window. For the case of nonspeculative cost structure, an O(n log n) time procedure is developed and it is shown to run in O(n) when demands come in the order of latest production due dates. When the cost structure is somewhat general fixed plus linear that allows speculative motive, an optimal procedure with O(T 4) is proposed where T is the length of a planning horizon. Finally, for the most general concave production cost structure, an optimal procedure with O(T 5) is designed.
