Scheduling Precedence Graphs in Systems with Interprocessor Communication Times

Abstract

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 designed and analyzed. An algorithm is also provided to calculate the communication requirements over some immediate predecessor-immediate successor pairs along one chain. The time complexity of Algorithm ETF is O(nm²).