Soft due window assignment and scheduling of unit-time jobs on parallel machinesReportar como inadecuado

Soft due window assignment and scheduling of unit-time jobs on parallel machines - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.


, Volume 10, Issue 4, pp 347–360

First Online: 13 May 2012Received: 22 October 2011Revised: 02 April 2012


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 job completion times, the due window location and the size are integer valued 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 On-m and Onlogn-m time, respectively. More efficient solution procedures are given for the case in which the due window size cost does not exceed the due window start time cost, the single machine case, the case of proportional earliness and tardiness costs and the case of equal earliness and tardiness costs.

KeywordsScheduling Parallel machines Earliness-tardiness Due window Unit-time jobs MSC classification68M20  Download to read the full article text

Autor: Adam Janiak - Wladyslaw Janiak - Mikhail Y. Kovalyov - Frank Werner


Documentos relacionados