Hindsight helps: deterministic task scheduling with backtracking Conference Paper uri icon


  • This paper considers the problem of scheduling a set of precedence-related tasks on a nonpreemptive homogeneous message-passing multiprocessor system in order to minimize the makespan, that is, the completion time of the last task relative to start time of the first task. We propose a family of scheduling algorithms, called IPR for immediate predecessor rescheduling, which utilize one level of backtracking. We also develop a unifying framework to facilitate the comparison between our results and the various models and algorithms that have been previously studied. We show, both theoretically and experimentally, that the IPR algorithms outperform previous algorithms in terms of both time complexity and the makespans of the resulting schedules. Moreover, our simulation results indicate that the relative advantage of the IPR algorithms increases as the communication constraint is relaxed.

name of conference

  • 1997 International Conference on Parallel Processing (Cat. No.97TB100162)

published proceedings

  • Proceedings of the 1997 International Conference on Parallel Processing (Cat. No.97TB100162)

author list (cited authors)

  • Yueh-O Wang, .., Amato, N. M., & Friesen, D. K.

citation count

  • 0

complete list of authors

  • Amato, NM||Friesen, DK

publication date

  • January 1997