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

Abstract

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 \geqq 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(n\log n)$ is investigated, and it is shown that the mean weighted flow-time obtained by the algorithm does not exceed ${{(\sqrt 2 + 1)} / 2} \cong 1.0207$ times that of an optimal schedule. Moreover the bound ${{(\sqrt 2 + 1)} / 2}$ is best possible.