Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
Jing‐Jang Hwang, Yuan-Chieh Chow, Frank D. Anger et al. · SIAM Journal on Computing · 1989
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. It is shown that the makespan $\omega _{{\text{ETF}}} $ generated by ETF always satisfies $\omega _{{\text{ETF}}} \leqq ({{2 - 1} / n})\omega _{{\text{opt}}}^{(i)} + C$, where $\omega _{{\text{opt}}}^{(i)} $ 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 $O(nm^2 )$.
Cited by 566 works. doi:10.1137/0218016
Authors
References
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Bounds on Multiprocessing Timing Anomalies
- Computer and job-shop scheduling theory
- Recent Developments in Deterministic Sequencing and Scheduling: A Survey
- Parallel processing of robot-arm control computation on a multimicroprocessor system
- Deterministic scheduling in systems with interprocessor communication times