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.
All Science Journal Classification (ASJC) codes
- Mathematics (miscellaneous)
- Approximation algorithms
- Mean flow time
- Precedence constraints