Multiprocessor scheduling with communication delays

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