Preprint series: 07-43, Preprints

MSC:

90B35 Scheduling theory, See also {68M20}

Abstract: We study problems of scheduling n unit-time jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then no scheduling cost in curs. Otherwise, a job-dependent earliness or tardiness cost incurs. The due window location and the size are decision variables. The objective is to find a job schedule as well as the location and the size of the due window such that a weighted sum or ma ximum of costs associated with job earliness, job tardiness and due window location and size is minimized. We establish properties of optimal solutions of these min-sum and min-max problems and reduce them to min-sum (traditional) or min-max (bottleneck) assignment problems solvable in $O(n^5/m^2)$ time. The single machine case and the case of proportional earliness and tardiness costs admit $O(n^3)$ and $O(n^3/m^2)$ solution procedures, respectively. If earliness and tardiness costs are equal for each jo b, the time requirement can be further reduced to $O(n^2\log n/m)$.

Keywords: Scheduling, Parallel machines, Earliness-tardiness, Due window assignment, Unit-time jobs, Due window negotiation

Upload: 2007-11-23-11-23

Update: 2008