An evolutionary approach for real-time fault-tolerant multiprocessor scheduling

Recently, the number of applications demanding real-time performance from their multiprocessor systems has been significantly increasing. At the same time, due to the possible catastrophic consequences from missing deadlines, fault-tolerance has become a critical issue in real-time systems. However, only a few heuristic algorithms have been proposed to solve fault-tolerant scheduling problems in multiprocessor systems. As an alternative to traditional heuristic algorithms, several optimization methods such as simulated annealing, tabu search, and genetic algorithms have been adapted to solve various NP-complete problems and proven their effectiveness. Nonetheless, almost none of these methods have been used for fault-tolerant scheduling problems. In this paper, we present a genetic algorithm and take a new approach to address real-time fault-tolerant scheduling. We also modified the existing branch-and-bound (B&B) algorithm to fit into our problem and compare these two algorithms. The simulation results show that the genetic algorithm outperforms the B&B algorithm in almost all cases.