Scheduling problems with multiple due windows assignment and controllable processing times on a single machine

This paper deals with multiple due windows assignment scheduling problems and controllable processing times on a single machine. We assume that the actual processing time of a job can be controlled by the introduction of additional resource and any due window is not allowed to contain another due window as a proper subset. The objective is to determine the optimal due window positions and sizes, the set of jobs assigned to each due window, the optimal job compressions, and the optimal schedule to minimize a total cost function, which consists of the earliness, the tardiness, the processing time compressions, and the due windows related costs. We show that for the case when the number of jobs assigned to each due window is given in advance, the problem is polynomially solvable in O(n(3)) time, where n is the total number of jobs; while if the number of jobs assigned to each due window is unknown, the problem can be optimally solved in O(n(m + 2)) time, where m is the number of due windows. Furthermore, we extend the problem by incorporating with the aging effect and prove that it remains polynomially solvable. (C) 2013 Elsevier B.V. All rights reserved.