Citation
Homogeneously non-idling schedules of unit-time jobs on identical parallel machines. In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium, pages 39-54, 2013.
Paper
Abstract
In this paper, we study the basic homogeneous m-machine scheduling problem where weakly dependent unit-time jobs have to be scheduled within the time windows between their release dates and due dates so that, for any subset of machines, the set of the time units at which at least one machine is busy, is in interval. We ?rst introduce the notions of pyramidal structure, k-hole, m-matching, preschedule, k-schedule and schedule for this problem. Then we provide a feasibility criteria for a preschedule. The key result of the paper is then to provide a structural necessary and su?cient condition for an instance of the problem to be feasible. We conclude by giving the directions of ongoing works and by bringing open questions related to di?erent variants of the basic non-idling m-machine scheduling problem.
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-039-054-P, author = {A. Quilliot and P. Chretienne},
title = {Homogeneously non-idling schedules of unit-time jobs on identical parallel machines},
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 = {39--54},
note = {Paper},
abstract = { In this paper, we study the basic homogeneous m-machine scheduling problem where weakly dependent unit-time jobs have to be scheduled within the time windows between their release dates and due dates so that, for any subset of machines, the set of the time units at which at least one machine is busy, is in interval. We ?rst introduce the notions of pyramidal structure, k-hole, m-matching, preschedule, k-schedule and schedule for this problem. Then we provide a feasibility criteria for a preschedule. The key result of the paper is then to provide a structural necessary and su?cient condition for an instance of the problem to be feasible. We conclude by giving the directions of ongoing works and by bringing open questions related to di?erent variants of the basic non-idling m-machine scheduling problem.},
owner = {Graham},
timestamp = {2017.01.16},
webpdf = {2013-039-054-P.pdf} }