Minimizing sum of completion times and makespan in master-slave systems

Joseph Y.T. Leung, Hairong Zhao

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We consider scheduling problems in the master-slave model. In this model, each job has to be processed sequentially in three stages. In the first stage, a preprocessing task runs on a master machine, in the second stage, a slave task runs on a dedicated slave machine, and, in the last stage, a postprocessing task again runs on a master machine, possibly different from the master machine in the first stage. It has been shown that the problem of minimizing the makespan or the sum of completion times is NP-hard in the strong sense even if preemption is allowed. In this paper, we design efficient approximation algorithms to minimize the sum of completion times in various settings. These are the first general results for the minsum problem in the master-slave model. We also show that these algorithms generate schedules with small makespan as well.

Original languageEnglish (US)
Pages (from-to)985-999
Number of pages15
JournalIEEE Transactions on Computers
Issue number8
StatePublished - Aug 2006

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Approximation algorithms
  • Linear programming
  • Makespan
  • Sequence and scheduling


Dive into the research topics of 'Minimizing sum of completion times and makespan in master-slave systems'. Together they form a unique fingerprint.

Cite this