Synthesis of Robust Task Schedules for Minimum Disruption Repair

TitleSynthesis of Robust Task Schedules for Minimum Disruption Repair
Publication TypeConference Paper
Year of Publication2004
AuthorsKandasamy, N., D. Hanak, C. van Buskirk, H. Neema, and G. Karsai
Refereed DesignationRefereed
Conference NameIEEE International Conference on Systems, Man and Cybernetics
Date Published10/2004
ISBN Number0-7803-8566-7
Accession Number8393579
Other NumbersISSN: 1062-922X

An off-line scheduling algorithm considers resource, precedence, and synchronization requirements of a task graph, and generates a schedule guaranteeing its timing requirements. This schedule must, however, be executed in a dynamic and unpredictable operating environment where resources may fail and tasks may execute longer than expected. To accommodate such execution uncertainties, this paper addresses the synthesis of robust task schedules using a slack-based approach and proposes a solution using integer linear programming (ILP). An ILP model, whose solution maximizes the temporal flexibility of the overall task schedule, is formulated. Two different ILP solvers are used to solve this model and their performance compared. For large task graphs, an efficient approximate method is presented and its performance evaluated.

RobustTaskSchedules.pdf370.75 KB