Citation
Scheduling Algorithms for Master-Slave System. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 501-513, 2005.
Paper
Abstract
We consider scheduling problems in the master-slave model. In this model each job has to be processed sequentially in three stages. In the first stage, a preprocessing task runs on a master machine; in the second stage, a slave task runs on a dedicated slave machine; in the last stage, a postprocessing task again runs on a master machine, possibly different from the master machine in the first stage. It has been shown that the problem of minimizing makespan or total completion time is NP-hard in the strong sense even if preemption is allowed. In this paper we design efficient approximation algorithms to minimize the total completion time in various settings.These are the first general results for total completion time problem in the master-slave model.We also show that these algorithms generate schedules with small makespan as well.
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-501-513-P, author = {J. Y-T. Leung and H. Zhao},
title = {Scheduling Algorithms for Master-Slave System},
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 = {501--513},
note = {Paper},
abstract = {We consider scheduling problems in the master-slave model. In this model each job has to be processed sequentially in three stages. In the first stage, a preprocessing task runs on a master machine; in the second stage, a slave task runs on a dedicated slave machine; in the last stage, a postprocessing task again runs on a master machine, possibly different from the master machine in the first stage. It has been shown that the problem of minimizing makespan or total completion time is NP-hard in the strong sense even if preemption is allowed. In this paper we design efficient approximation algorithms to minimize the total completion time in various settings.These are the first general results for total completion time problem in the master-slave model.We also show that these algorithms generate schedules with small makespan as well.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-501-513-P.pdf} }