Nonpreemptive LP-Scheduling on Homogeneous Multiprocessor Systems

Abstract

Unequal execution time task systems are nonpreemptively scheduled on $m \geqq 2$ identical processors without additional resource constraints. Worst-case bounds for the ratio of the length of an LP-schedule (longest path) and an optimal schedule are given for two classes of dependency structures—chains and trees. Moreover, the asymptotic bounds, which are independent of the number of processors, are given for these classes and for anti-tree-systems.