## Abstract

We consider the problem of scheduling a set of chains onm 〉 1 identical processors with the objectives of minimizing the makespan and the mean flow time. We show that finding a nonpreemptive schedule with the minimum makespan is strongly NP-hard for each fixedm 〉 1, answering the open question of whether this problem is strongly NP-hard for trees. We also show that finding a nonpreemptive schedule with the minimum mean flow time is strongly NP-hard for each fixedm 〉 1, improving the known strong NP-hardness results for in-trees and out-trees. Finally, we generalize the result of McNaughton, showing that preemption cannot reduce the mean weighted flow time for a set of chains. The last two results together imply that finding a preemptive schedule with the minimum mean flow time is also strongly NP-hard for each fixedm 〉 1, answering another open question on the complexity of this problem for trees.

Original language | English (US) |
---|---|

Pages (from-to) | 219-236 |

Number of pages | 18 |

Journal | Information and Computation |

Volume | 92 |

Issue number | 2 |

DOIs | |

State | Published - 1991 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics