Citation
Minimizing the number of late jobs on parallel machines with alpha time windows. In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium, pages 206-217, 2013.
Paper
Abstract
We consider the problem of minimization the number of late jobs on parallel machines in presence of ? time windows (di = ri + pi + ? for all jobs). We prove the NPcompletenessofthisproblemevenwhen m = 2 and di = d foralljobs.Wedevelopalower bound by solving a minimum cost ?ow problem associated to a relaxation of the problem. Asetofheuristicsarepresentedtominimizethenumberoflatejobsbasedonajob-focused andmachine-focusedapproach.Asimulationexperimentisrealizedtotesttheeffectiveness ofheuristicsregardingthelowerbound.Thissimulationhasbeencomputedfor1,2,5,10,15 and 20 machines and it shows that the best heuristic has an average deviation to the bound of 4.88%, 6.35%, 7.38%, 7.5%, 7.87% and 7.64% respectively. Keywords Parallel machines scheduling, number of late jobs, ? time windows, lower bound
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2013-206-217-P, author = {V. Jeauneau P. Chretienne},
title = {Minimizing the number of late jobs on parallel machines with alpha time windows},
booktitle = {In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium},
year = {2013},
editor = {G. Kendall and B. McCollum and G. {Venden Berghe}},
pages = {206--217},
note = {Paper},
abstract = { We consider the problem of minimization the number of late jobs on parallel machines in presence of ? time windows (di = ri + pi + ? for all jobs). We prove the NPcompletenessofthisproblemevenwhen m = 2 and di = d foralljobs.Wedevelopalower bound by solving a minimum cost ?ow problem associated to a relaxation of the problem. Asetofheuristicsarepresentedtominimizethenumberoflatejobsbasedonajob-focused andmachine-focusedapproach.Asimulationexperimentisrealizedtotesttheeffectiveness ofheuristicsregardingthelowerbound.Thissimulationhasbeencomputedfor1,2,5,10,15 and 20 machines and it shows that the best heuristic has an average deviation to the bound of 4.88%, 6.35%, 7.38%, 7.5%, 7.87% and 7.64% respectively. Keywords Parallel machines scheduling, number of late jobs, ? time windows, lower bound},
owner = {Graham},
timestamp = {2017.01.16},
webpdf = {2013-206-217-P.pdf} }