Scheduling problems in master-slave model

Joseph Y.T. Leung, Hairong Zhao

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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
Volume159
Issue number1
DOIs
StatePublished - Mar 2008

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Management Science and Operations Research

Keywords

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

Fingerprint

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

Cite this