Article ID: | iaor2003956 |
Country: | United Kingdom |
Volume: | 4 |
Issue: | 3 |
Start Page Number: | 139 |
End Page Number: | 156 |
Publication Date: | May 2001 |
Journal: | Journal of Scheduling |
Authors: | Righter Rhonda, Liu Zhen |
Keywords: | graphs |
We consider scheduling of tasks of parallel programs on multiprocessor systems where tasks have precedence relations and synchronization points. The task graph structures are random variables in the sense that successors to a task do not become known until the task is executed. Thus, as is often the case with parallel processing, scheduling must occur at run time rather than compile time. We prove that a simple scheduling policy stochastically minimizes the processes of task completions and job (i.e. set of parallel tasks) completions for several classes of task graph structures.