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²).
No takes yet. Share an insight, caveat, or question.
Hwang et al. (1989) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: