Citation
Scheduling UET-UCT task systems under the out-forest precedence constraints. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 445-452, 2005.
Paper
Abstract
This paper is concerned with two problems of scheduling unit execution time task systems on parallel identical processors with unit communication delays and precedence constraints in the form of an out-forest.One problem is the maximum lateness problem with different release times.To the authors knowledge, the presented worst-case analysis of an approximation algorithm, generalizing the idea of the classical Garey-Johnson algorithm, is the first result of this type for models with communication delays and different release times, and provides the best currently known performance guarantee for problems with communication delays and precedence constraints in the form of an out-forest.The paper also presents an iterative algorithm, constructing an optimal schedule, for a two-processor system, for the criterion of total completion time, among optimal schedules for the criterion of maximum lateness.
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-445-452-P, author = {C. Hanen and Y. Zinder},
title = {Scheduling UET-UCT task systems under the out-forest precedence constraints},
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 = {445--452},
note = {Paper},
abstract = {This paper is concerned with two problems of scheduling unit execution time task systems on parallel identical processors with unit communication delays and precedence constraints in the form of an out-forest.One problem is the maximum lateness problem with different release times.To the authors knowledge, the presented worst-case analysis of an approximation algorithm, generalizing the idea of the classical Garey-Johnson algorithm, is the first result of this type for models with communication delays and different release times, and provides the best currently known performance guarantee for problems with communication delays and precedence constraints in the form of an out-forest.The paper also presents an iterative algorithm, constructing an optimal schedule, for a two-processor system, for the criterion of total completion time, among optimal schedules for the criterion of maximum lateness.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-445-452-P.pdf} }