Synthesis of robust task schedules for minimum disruption repair

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.