@inproceedings{d3bb8f56220d47b3b88c74940498d1e9,
title = "Minimizing mean flowtime on master-slave machines",
abstract = "The master-slave scheduling model is a new model recently introduced by Sahni. It has many important applications in parallel computer scheduling and industrial settings such as semiconductor testing, machine scheduling, transportation maintenance, etc. In this model, each job has a preprocessing task, a slave task and a postprocessing task that must be executed in this order. While the preprocessing and postprocessing tasks are scheduled on the master machine, the slave tasks are scheduled on the slave machines. We consider the problem of minimizing mean flowtime in the single-master master-slave model. We prove that the problem is strongly NP-hard even if all the preprocessing and postprocessing tasks have unit execution time. We then give a polynomial-time optimal algorithm for a special case. Finally, we give some heuristics for other special cases and we analyze their worst-case performance.",
keywords = "Heuristic, Master-slave, Mean flowtime, NP-hard, Scheduling",
author = "Leung, {Joseph Y.T.} and Hairong Zhao",
year = "2004",
language = "English (US)",
isbn = "1932415262",
series = "Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04",
pages = "939--945",
editor = "H.R. Arabnia and J. Ni",
booktitle = "Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04",
note = "Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04 ; Conference date: 21-06-2004 Through 24-06-2004",
}