查看文章

In this paper, the classical single-item, uncapacitated dynamic lot-sizing model is extended by introducing the notion of time windows. This notion arises when demands from customers are quantities that can only be processed within certain time frames. Two cases are studied: customer-specific and non-customer-specific time windows. Customer specific means that demand that becomes available at a given period and is to be processed before the end of a later period can only be processed to satisfy that specific demand, ie, customers need to be differentiated. The special case of non-customer-specific time windows, where customers are not differentiated, is relevant when considering for example cumulative capacity constraints due to time-phased arrival of raw materials. When production costs are time independent, an extension of the well-known Wagner-Within algorithm is proposed. A general dynamic programming pseudo-polynomial algorithm is presented for the customer-specific problem. We show that this algorithm runs in polynomial time (O (T4)) in the non-customer-specific case.