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

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of parallel and distributed computing 2011, Vol.71 (1), p.132-142
Main Authors: Chen, Hua, Cheng, Albert Mo Kim, Kuo, Ying-Wei
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Ant colony optimization
Applied sciences
Colonies
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Energy of solution
Energy use
Exact sciences and technology
Heterogeneous processors
Language processing and microprogramming
Mathematical models
Multiprocessors
Optimization
Periodic tasks
Power-aware computing
Processors
Prototypes
Real-time systems
Scheduling
Searching
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. ► Ant colony optimization (ACO) is used to solve the multiprocessor partitioned scheduling problem. ► A local search heuristic is employed by various metaheuristics to improve the assignment solution. ► Experimental results show that implementations of our ACO algorithm outperform major existing methods. ► The extended version achieves an average of 15.8% energy savings.
ISSN:0743-7315
1096-0848
DOI:10.1016/j.jpdc.2010.09.011