Multiprocessor Scheduling with Communication Delays

摘要

Scheduling problems that arise when a parallel computation is executed on a multiprocessor are addressed. A model that allows for communication delays between precedence related tasks is defined, and a classification of various submodels is proposed. Complexity results and optimization and approximation algorithms that are presented in the literature are reviewed.