Scheduling problems in master-slave model

Joseph Y.T. Leung, Hairong Zhao

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We consider scheduling problems in the master slave model, which was introduced by Sahni in 1996. The goal is to minimize the makespan and the total completion time. It has been shown that the problem of minimizing makespan is NP-hard. Sahni and Vairaktarakis developed some approximation algorithms to generate schedules whose makespan is at most constant times the optimal. In this paper, we show that the problem of minimizing total completion time is NP-hard in the strong sense. Then we develop algorithms to generate schedules whose total completion time and makespan are both bounded by some constants times their optimal values.

Original languageEnglish (US)
Pages (from-to)215-231
Number of pages17
JournalAnnals of Operations Research
Issue number1
StatePublished - Mar 2008

All Science Journal Classification (ASJC) codes

  • General Decision Sciences
  • Management Science and Operations Research


  • Approximation algorithms
  • Makespan
  • Master slave model
  • NP-hard
  • Total completion time


Dive into the research topics of 'Scheduling problems in master-slave model'. Together they form a unique fingerprint.

Cite this