Minimizing mean flowtime on master-slave machines

Joseph Y.T. Leung, Hairong Zhao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
EditorsH.R. Arabnia, J. Ni
Pages939-945
Number of pages7
StatePublished - 2004
EventProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04 - Las Vegas, NV, United States
Duration: Jun 21 2004Jun 24 2004

Publication series

NameProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
Volume2

Other

OtherProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
Country/TerritoryUnited States
CityLas Vegas, NV
Period6/21/046/24/04

All Science Journal Classification (ASJC) codes

  • General Engineering

Keywords

  • Heuristic
  • Master-slave
  • Mean flowtime
  • NP-hard
  • Scheduling

Fingerprint

Dive into the research topics of 'Minimizing mean flowtime on master-slave machines'. Together they form a unique fingerprint.

Cite this