Processor scheduling with improved heuristic algorithms

Abstract

Consideration is given to the problem of nonpreemptively scheduling a set of N independent tasks to a system of M identical processors, with the objective to minimize the overall finish time. Since this problem is known to be NP-Hard, and hence unlikely to permit an efficient solution procedure, heuristic algorithms are studied in an effort to provide near-optimal results. Worst-case analysis is used to gauge the worth of a scheduling procedure. For a particular algorithm, an upper bound is sought for the length of its schedule expressed relative to an optimal assignment of tasks to processors. Departing from more traditional schemes of only determining an algorithm's worst-case performance bound, the work contained herein focuses on modifying a scheduling heuristic for "bad" regions of the input space, thereby improving its worst-case bound. It is shown that rather simple alterations, having little effect on the run-time of an algorithm, may guarantee a significantly better behavior. The O/1-INTERCHANGE heuristic is improved so that, while its time complexity is still O(NlogM), its worst-case performance bound is reduced from 2 to 4/3 times optimal. The familiar LPT algorithm is altered so that, while its time complexity is still O(NlogN), its worst-case bound is reduced from 4/3 to 5/4 times optimal. The major effort of this research is devoted to proving that the MULTIFIT heuristic can be modified, without increasing its time complexity from O(NlogN), so that its worst-case performance bound is reduced from some value in the range {13/11, 6/5} to 72/61 times optimal, a better bound as of this writing than that yielded by any other known polynomial-time algorithm.