Citation
Online Scheduling Of Precedence Constrained Tasks. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 573-584, 2005.
Paper
Abstract
A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on m >= 1 identical and parallel processors so as to minimize the makespan (schedule length). In the past, research has focussed on the setting where all tasks are available for processing at the beginning (i.e., at time t=0). In this article we consider the setting where all tasks are available for processing at the beginning (i.e, at time t=0). In this article we consider the situation where tasks, along with their precedence constraints, are released at different times, and the scheduler has to make scheduling decisions without knowledge of future releases. In other words, the scheduler has to schedule tasks in an online fashion. We consider both preemptive and nonpreemptive schedules. We show that optimal online algorithms exist for some cases, while for others it is impossible to have one. Our results give a sharp boundary delineating the possible and the impossible cases.
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{2005-573-584-P, author = {Y. Huo and J. Y-T. Leung},
title = {Online Scheduling Of Precedence Constrained Tasks},
booktitle = {In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA},
year = {2005},
editor = {G. Kendall and L. Lei and M. Pinedo},
pages = {573--584},
note = {Paper},
abstract = {A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on m >= 1 identical and parallel processors so as to minimize the makespan (schedule length). In the past, research has focussed on the setting where all tasks are available for processing at the beginning (i.e., at time t=0). In this article we consider the setting where all tasks are available for processing at the beginning (i.e, at time t=0). In this article we consider the situation where tasks, along with their precedence constraints, are released at different times, and the scheduler has to make scheduling decisions without knowledge of future releases. In other words, the scheduler has to schedule tasks in an online fashion. We consider both preemptive and nonpreemptive schedules. We show that optimal online algorithms exist for some cases, while for others it is impossible to have one. Our results give a sharp boundary delineating the possible and the impossible cases.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-573-584-P.pdf} }