Report Number: CS-TR-80-832
Institution: Stanford University, Department of Computer Science
Title: Scheduling wide graphs
Author: Dolev, Danny
Date: December 1980
Abstract: The problem of scheduling a partially ordered set of unit length tasks on m identical processors is known to be NP-complete. There are efficient algorithms for only a few special cases of this problem. In this paper we explore the relations between the structure of the precedence graph (the partial order) and optimal schedules. We prove that in finding an optimal schedule for certain systems it suffices to consider at each step high roots which belong to at most the m-1 highest components of the precedence graph. This result reduces the number of cases we have to check during the construction of an optimal schedule. Our method may lead to the development of linear scheduling algorithms for many practical cases and to better bounds for complex algorithms. In particular, in the case the precedence graph contains only inforest and outforest components, this result leads to efficient algorithms for obtaining an optimal schedule on two or three processors.
http://i.stanford.edu/pub/cstr/reports/cs/tr/80/832/CS-TR-80-832.pdf