M. Desiraju and H.H. Ali (USA)
Fault Tolerant Scheduling, Augmented Graph, Predecessor, Successor, Primary task, Backup task.
While precedence constrained scheduling is NP-hard in general, it is known that optimal scheduling algorithms exist for special cases such as for trees, Interval Orders or when number of processors is limited to two. In this paper, we employ these optimal algorithms to address the important issue of fault tolerance for scheduling general graphs. The input precedence graphs are augmented into Interval Orders and then scheduled optimally while incorporating fault tolerance measures. It is proved that for the case where the graph is already an Interval Order, the fault tolerant schedule generated is optimal. For general precedence graphs, the obtained schedules are shown to be near optimal by comparing them with a standard list scheduling algorithm.
Important Links:
Go Back
