C.P.M. Scheduling with Small Communication Delays and Task Duplication

Operations Research · 1991 · Volume 39 · Issue 4

Abstract

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.

Keywords

computers: task allocation on distributed memory processors, production/scheduling: scheduling with interprocessor communication delays

Enable JavaScript for citation tools and additional paper interactions.