Zurück zu den Preprints des Jahres 2007


2007-43

Soft Due Window Assignment and Scheduling of Unit-Time Jobs on Parallel Machines

by Janiak, A., Janiak, W., Kovalyov, M., Werner, F..


Series: 2007-43, Preprints

MSC:
90B35 Scheduling theory, deterministic

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