Synthesising robust schedules for minimum disruption repair using linear programming
Dávid Hanák, Nagarajan Kandasamy · 2007
Abstract. An off-line scheduling algorithm considers resource, prece-dence, and synchronisation 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 envi-ronment where resources may fail and tasks may execute longer than expected. To accommodate such execution uncertainties, this paper ad-dresses the synthesis of robust task schedules using a slack-based ap-proach and proposes a solution using integer linear programming (ILP). Earlier we formulated a time slot based ILP model whose solutions max-imise the temporal flexibility of the overall task schedule. In this paper, we propose an improved, interval based model, compare it to the former, and evaluate both on a set of random scenarios using two public domain ILP solvers and a proprietary SAT/ILP mixed solver. 1