Aco and Ga based fault-tolerant scheduling of real-time tasks on multiprocessor systems — A comparative study
- Resource Type
- Conference
- Authors
- Kumar, Abhaya; Panda, Sunita; Pani, Subhendu Kumar; Baghel, Vikas; Panda, Ankita
- Source
- 2014 IEEE 8th International Conference on Intelligent Systems and Control (ISCO) Intelligent Systems and Control (ISCO), 2014 IEEE 8th International Conference on. :120-126 Jan, 2014
- Subject
- Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Engineered Materials, Dielectrics and Plasmas
Engineering Profession
Fields, Waves and Electromagnetics
General Topics for Engineers
Power, Energy and Industry Applications
Robotics and Control Systems
Signal Processing and Analysis
Transportation
Program processors
Schedules
Sociology
Statistics
Fault tolerance
Fault tolerant systems
Genetic algorithms
Real-time system
Primary-backup approach
Fault-tolerance
Genetic Algorithm
Ant Colony Optimization Algorithm
Heuristic based scheduling approach
- Language
Fault-tolerant scheduling of real-time (RT) tasks in multiprocessor environment is essentially a NP-hard problem. This basically involves allocating a set of tasks to a set of processors so as to minimize the makespan and ensure tasks to meet their timing constraints. Many traditional heuristic approaches, such as earliest deadline first (EDF) and least laxity first (LLF) have been adopted to find optimal solution to this scheduling problem. However, conventional approach to achieve fault-tolerance (FT) in scheduling RT tasks based on traditional heuristic approach suffers from poor performance and results in inefficient processor utilization. Nature-inspired heuristic algorithms are gaining increased acceptance among researcher for solving real world NP-hard combinatorial optimization problems. This paper presents a comparative study of the novel primary-backup (PB) based fault-tolerant scheduling (PBFTS) technique for RT tasks in multiprocessor environment using two popular nature-inspired heuristic algorithms: the Ant Colony Optimization (ACO) and the Genetic Algorithm (GA). Exhaustive simulation reveals that the PBFTS algorithm based on GA and ACO both outperform the traditional PBFTS schemes in terms of performance, system utilization and efficiency. However, the comparative study also shows that the ACO based scheme surpasses the GA based scheme in terms of speed of execution whereas GA based scheme displays superior convergence with respect to ACO counterpart.