Article ID: | iaor20052548 |
Country: | United States |
Volume: | 51 |
Issue: | 7 |
Start Page Number: | 1005 |
End Page Number: | 1017 |
Publication Date: | Oct 2004 |
Journal: | Naval Research Logistics |
Authors: | Mosheiov Gur, Oron Daniel |
In due-window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due-window, as well as the job schedule. We address a common due-window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due-window starting time and for the optimal due-window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant-time solution for the problem.