A Continous Bound on the Performance of Critial-Path Schedules

Abstract.  In the paper the scheduling problem for unit execution time jobs with precedence constraints on m >= 3 processors is investigated, especially the performance of a well-known class of schedules: the critical-path schedules. It is known that their completion time differs from optimum at most by factor 2-(1/(m+1)). In this paper, a parameter is defined which allows to give a subtler performance guarantee, covering the interval [2-(2/m), 2-(1/(m-1))] in a continous fashion. More precisely: given the precedence constraints in form of a directed acyclic graph G, the probability z(G) that a certain substructure, called zigzag, occurs on a randomly chosen level of G is considered. It is shown that the completion time of critical-path schedules differs from optimum at most by factor 2-(2/m)+(z(G)/m).