A Fault-Tolerant Scheduling Algorithm Based on a Multi-Objective Genetic Algorithm for Precedence-Constrained Tasks in Real-Time Heterogeneous Distributed Systems

作者：Chen Yuanlong^*; Ma Peijun; Li Dong

来源：Journal of Computational and Theoretical Nanoscience, 2013, 10(5): 1091-1096.

DOI：10.1166/jctn.2013.2811

• Heterogeneous Distributed System
• Dynamical Distance
• Fault Tolerant Scheduling
• Multi-Objective Genetic Algorithm

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.

• 出版日期2013-5
• 单位哈尔滨工业大学