by Janiak, A., Janiak, W., Kovalyov, M., Werner, F..
Series: 2007-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