We consider the problem of preemptively scheduling a set of n independent tasks with release times on m identical processors with the objective of minimizing the mean flow time. For one processor, Baker gives an O(n log n) time algorithm to find an optimal schedule. Lawler asks the question whether the problem can be shown to be solvable in polynomial time or shown to be NP-hard for m≥2. In this paper we answer this question by showing that it is NP-hard for each fixed m≥2.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)