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 language | English (US) |
---|---|
Pages (from-to) | 244-262 |
Number of pages | 19 |
Journal | ACM Transactions on Algorithms |
Volume | 2 |
Issue number | 2 |
DOIs | |
State | Published - 2006 |
All Science Journal Classification (ASJC) codes
- Mathematics (miscellaneous)
Keywords
- Approximation algorithms
- Intrees
- Mean flow time
- Precedence constraints
- Scheduling