Hindsight helps: Deterministic task scheduling with backtracking

Yueh O. Wang, Nancy M. Amato, D. K. Friesen

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)170-173
Number of pages4
JournalProceedings of the International Conference on Parallel Processing
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA
Duration: Sep 11 1997Sep 15 1997

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Hindsight helps: Deterministic task scheduling with backtracking'. Together they form a unique fingerprint.

Cite this