Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

This paper studies the problem of scheduling a set of n independent tasks on m identical processors so as to minimize mean weighted flow-time. The problem is known to be NP-complete for m 2 and to be NP-complete in the strong sense for m arbitrary. The worst case behavior of a heuristic algorithm which requires time O(nlog n) is investigated, and it is shown that the mean weighted flow-time obtained by the algorithm does not exceed (√ 2 + 1) / 2 1.0207 times that of an optimal schedule. Moreover the bound (√ 2 + 1) / 2 is best possible.