Hybrid Metaheuristic Algorithm for Real Time
Task Assignment Problem in Heterogeneous Multiprocessors
Poongothai Marimuthu,
Rajeswari Arumugam, and Jabar Ali
Department
of Electronics and Communication Engineering, Coimbatore Institute of
Technology, India
Abstract: The
assignments of real time tasks to heterogeneous multiprocessors in real time
applications are very difficult in scenarios that require high performance. The
main problem in the heterogeneous multiprocessor system is task assignment to the
processors because the execution time for each task varies from one processor
to another. Hence, the problem of finding a solution for task assignment to heterogeneous
processor without exceeding the processors capacity in general is an NP hard
problem. In order to meet the constraints in real time systems, a Hybrid
Max-Min Ant colony optimization algorithm (H-MMAS) is proposed in this paper.
Max-Min Ant System (MMAS) is extended with a local search heuristic to improve
task assignment solution. The Local Search has resulted in maximizing the
number of tasks assigned as well as minimizing the energy consumption. The
performance of the proposed algorithm H-MMAS is compared with the Modified
Binary Particle Swarm
Optimization algorithm (BPSO), Ant Colony Optimization (ACO), MMAS algorithms
in terms of the average number of task assigned, normalized energy consumption,
quality of solution and average Central Processing Unit (CPU) time. From the
experimental results, the proposed algorithm has outperformed MMAS, Modified
BPSO and ACO for consistency matrix. In case of inconsistency matrix H-MMAS
performed better than Modified BPSO, similar to ACO and MMAS, but there is an
improvement in the normalized energy consumption.
Keywords: Multiprocessors, task assignment, heterogeneous
processors, ant colony optimization, real time systems.
Received September 21, 2014; accepted December 21,
2015