Premium
Due‐window assignment with unit processing‐time jobs
Author(s) -
Mosheiov Gur,
Oron Daniel
Publication year - 2004
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20039
Subject(s) - window (computing) , computer science , interval (graph theory) , schedule , constant (computer programming) , bounded function , mathematical optimization , assignment problem , due date , unit of time , scheduling (production processes) , unit (ring theory) , simple (philosophy) , real time computing , mathematics , combinatorics , mathematical analysis , physics , mathematics education , quantum mechanics , programming language , operating system , philosophy , epistemology
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. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004