07-43
Soft Due Window Assignment and Scheduling of Unit-Time Jobs on Parallel Machines
by Janiak, A.; Janiak, W.; Kovalyov, M.; Werner, F.
Preprint series: 07-43, Preprints
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 incurs. 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 maximum 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 job, 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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.