## 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 - Aug 29 2006 |

## All Science Journal Classification (ASJC) codes

- Mathematics (miscellaneous)

## Keywords

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