zbMATH — the first resource for mathematics

C. P. M. scheduling with small communication delays and task duplication. (English) Zbl 0793.68012
Summary: This paper addresses a machine scheduling problem that arises in the case of scheduling tasks over an idealized distributed multiprocessor. Precedence constraints with small communication delays have to be taken into account and task duplication is allowed. A critical path-like algorithm is presented, which is shown to construct an optimal schedule in polynomial time.

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
Full Text: DOI