Scheduling precedence graphs in systems with interprocessor communication times. (English) Zbl 0677.68026

Summary: The problem of nonpreemptively scheduling a set of m partially ordered tasks on n identical processors subject to interprocessor communication delays is studied in an effort to minimize the makespan. A new heuristic, called earliest task first (ETF), is defined and analyzed. It is shown that the makespan \(\omega_{ETF}\) generated by ETF always satisfies \(\omega_{ETF}\leq (2-1/n)\omega^{(i)}_{opt}+C\), where \(\omega^{(i)}_{opt}\) is the optimal makespan without considering communication delays and C is the communication requirements over some immediate predecessor-immediate successor pairs along one chain. An algorithm is also provided to calculate C. The time complexity of Algorithm ETF is \(0(nm^ 2)\).


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI Link