Online scheduling of equal-processing-time task systems

Yumei Huo, Joseph Y.T. Leung, Xin Wang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We consider the problem of online scheduling a set of equal-processing-time tasks with precedence constraints so as to minimize the makespan. For arbitrary precedence constraints, it is known that any list scheduling algorithm has a competitive ratio of 2 - 1 / m, where m is the number of machines. We show that for intree precedence constraints, Hu's algorithm yields an asymptotic competitive ratio of 3/2.

Original languageEnglish (US)
Pages (from-to)85-95
Number of pages11
JournalTheoretical Computer Science
Volume401
Issue number1-3
DOIs
StatePublished - Jul 23 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Competitive ratio
  • Equal-processing-time tasks
  • Intree precedence constraints
  • Makespan
  • Online scheduling
  • Parallel and identical machines

Fingerprint Dive into the research topics of 'Online scheduling of equal-processing-time task systems'. Together they form a unique fingerprint.

Cite this