Multi-duplication fault tolerant scheduling algorithm based on genetic algorithm in heterogeneous systems - Zhong-zheng HE; Chao-guang MEN; Yong-jun CHEN; Xiang LI (Tongxin xuebao)
The fault-tolerant task scheduling mechanisms based on multi-duplication didn’t consider the scheduling makespan,the dependencies between tasks,the failures of the links and the longer scheduling makespan caused by the strict scheduling method in the heterogeneous distributed system.So the reliability calculation method that can involve the processor failures and the link failures was proposed firstly.Then the 0-1 integer linear program was proposed for the general scheduling problem.At last,the RAMD_TGS(reliability-aware multi-duplication task general scheduling) algorithm was proposed to solve the 0-1 integer linear program.The algorithm searched the mapped processor and the start execution time on the mapped processor for the task duplication by the evolution of the genetic algorithm.The experiments show that the RAMD_TGS algorithm can meet the reliability requirements and outperforms the existing scheduling algorithms based on the strict scheduling method in terms of scheduling makespan.The resource usages of the algorithm are also acceptable.