Minimizing mean flow time for UET tasks

Yumei Huo, Joseph Leung

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We consider the problem of scheduling a set of n unit-execution-time (UET) tasks, with precedence constraints, on m ≥ 1 parallel and identical processors so as to minimize the mean flow time. For two processors, the Coffman-Graham algorithm gives a schedule that simultaneously minimizes the mean flow time and the makespan. The problem becomes strongly NP-hard for an arbitrary number of processors, although the complexity is not known for each fixed m ≥ 3. For arbitrary precedence constraints, we show that the Coffman-Graham algorithm gives a schedule with a worst-case bound no more than 2, and we give examples showing that the bound is tight. For intrees, the problem can be solved in polynomial time for each fixed m ≥ 1, although the complexity is not known for an arbitrary number of processors. We show that Hu's algorithm (which is optimal for the makespan objective) yields a schedule with a worst-case bound no more than 1.5, and we give examples showing that the ratio can approach 1.308999. " 2006 ACM.

Original languageEnglish (US)
Pages (from-to)244-262
Number of pages19
JournalACM Transactions on Algorithms
Volume2
Issue number2
DOIs
StatePublished - Aug 29 2006

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Approximation algorithms
  • Intrees
  • Mean flow time
  • Precedence constraints
  • Scheduling

Fingerprint Dive into the research topics of 'Minimizing mean flow time for UET tasks'. Together they form a unique fingerprint.

Cite this