A dynamic lot-sizing model with demand time windows

One of the basic assumptions of the classical dynamic lot-sizing model is t hat the aggregate demand of a given period must be satisfied in that period . Under this assumption, if backlogging is not allowed, then the demand of a given period cannot be delivered earlier or later than the period. If bac klogging is allowed, the demand of a given period cannot be delivered earli er than the period, but it can be delivered later at the expense of a backo rdering cost. Like most mathematical models, the classical dynamic lot-sizi ng model is a simplified paraphrase of what might actually happen in real l ife. In most real-life applications, the customer offers a grace period-we call it a demand time window-during which a particular demand can be satisf ied with no penalty. That is, in association with each demand, the customer specifies an acceptable earliest and a latest delivery time. The time inte rval characterized by the earliest and latest delivery dates of a demand re presents the corresponding time window. This paper studies the dynamic lot-sizing problem with demand time windows and provides polynomial time algorithms for computing its solution. If back logging is not allowed, the complexity of the proposed algorithm is O(T-2) where T is the length of the planning horizon. When backlogging is allowed, the complexity of the proposed algorithm is O(T-3).