Minimizing mean flowtime and makespan on master-slave systems

Joseph Y.T. Leung, Hairong Zhao

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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, etc. In this model each job is associated with 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. In this paper, we consider scheduling problems on single-master master-slave systems. We first strengthen some previously known complexity results for makespan problems, by showing them to be strongly NP-hard. We then show that the problem of minimizing the mean flowtime is strongly NP-hard even under severe constraints. Finally, we propose some heuristics for the mean flowtime and makespan problems subject to some constraints, and we analyze the worst-case performance of these heuristics.

Original languageEnglish (US)
Pages (from-to)843-856
Number of pages14
JournalJournal of Parallel and Distributed Computing
Volume65
Issue number7
DOIs
StatePublished - Jul 2005

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Keywords

  • Heuristics
  • Makespan
  • Master-slave systems
  • Mean flowtime
  • NP-hard
  • Scheduling

Fingerprint

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

Cite this