Assigning real-time tasks to heterogeneous processors by applying ant colony optimization

作者：Chen Hua; Cheng Albert Mo Kim^*; Kuo Ying Wei

来源：Journal of Parallel and Distributed Computing, 2011, 71(1): 132-142.

DOI：10.1016/j.jpdc.2010.09.011

• Scheduling
• Real-time systems
• Multiprocessors
• Heterogeneous processors
• Ant colony optimization
• Power-aware computing
• Periodic tasks

The problem of determining whether a set of periodic tasks can be assigned to a set of heterogeneous processors without deadline violations has been shown, in general, to be NP-hard. This paper presents a new algorithm based on ant colony optimization (ACO) metaheuristic for solving this problem. A local search heuristic that can be used by various metaheuristics to improve the assignment solution is proposed and its time and space complexity is analyzed. In addition to being able to search for a feasible assignment solution, our extended ACO algorithm can optimize the solution by lowering its energy consumption. Experimental results show that both the prototype and the extended version of our ACO algorithm outperform major existing methods; furthermore, the extended version achieves an average of 15.8% energy saving over its prototype.

• 出版日期2011-1