This paper addresses certain types of scheduling problems that arise when a parallel computation is to be executed on a multiprocessor. We define a model that allows for communication delays between precedence-related tasks, and propose a classification of various submodels. We also review complexity results and optimization and approximation algorithms that have been presented in the literature.
Key Words & Phrases: scheduling, parallel processors, communication delays, lgorithms, complexity.
|ISSN van geprinte versie||0926-4493|