A fault-tolerant scheduling algorithm based on a multi-objective genetic algorithm for precedence-constrained tasks in real-time heterogeneous distributed systems

摘要

In this paper, we investigate an efficient off-line fault-tolerant scheduling algorithm that generates schedules in which real-time tasks with precedence constraints can tolerate more than one fault at a time in a heterogeneous system with a fully connected network. We assume tasks to be non-preemptable, and each task has two copies scheduled on different processors and mutually excluded. Our fault-tolerant scheduling algorithm based on non-domination sort genetic algorithm (NSGA) employs performance improving techniques, including (1) a dynamic distance concept that decides the relative position of two task copies in the task graph, (2) a multi objectives genetic algorithm to optimise multiple targets. We performed experiments using synthetic workloads and a real-world application. Simulation results show that compared with existing scheduling algorithms, our scheduling algorithm improves guarantee ratio, reliability and overhead.