Task scheduling with interprocessor communication delays. (English) Zbl 0761.90057

Summary: Distributed memory architectures raise new and complex scheduling problems. We first define a basis distributed memory computer scheduling problem issued from an ideal architecture. By proving that the corresponding decision problem is NP-complete, we show that unlike shared memory computer scheduling problems, these new problems do not become easy when the processor limitation constraint is removed. Finally, we improve the knowledge of the borderline between the easy and difficult subproblems of the basic one by giving some polynomial special cases.


90B35 Deterministic scheduling theory in operations research
90B18 Communication networks in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI


[1] Carlier, J.; Chrétienne, P., Problèmes d’Ordonnancement: Modèlisation, Complexité, Algorithmes (1988), Masson: Masson Paris
[2] Coffman, E. G., Computer and Job-Shop Scheduling Problems (1974), Prentice-Hall: Prentice-Hall New York
[3] Lenstra, J. K., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0353.68067
[4] Rinnooy Kan, A. H.G., Machine Scheduling Problems: Classification, Complexity and Computations (1976), Nijhoff: Nijhoff The Hague · Zbl 0366.90092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.