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.

References

[1] Babaeizadeh S., Banitalebi A., Ahmad R., and Aziz M., Solving Optimal Control Problem Hybrid Metaheuristic Algorithm for Real Time Task Assignment ... 453 Using Max-Min Ant System, IOSR Journal of Mathematics, vol. 1, no. 3, pp. 47-51, 2012.

[2] Baruah S., Partitioning Real-Time Tasks Among Heterogeneous Multiprocessors, in Proceedings of the IEEE International Conference on Parallel Processing, Montreal, pp. 467-474, 2004.

[3] Braun T., Siegel H., Beck N., B l ni L., Maheswaran M., Reuther A., Robertsong J., Theys M., Yao B., Hensgen D., and Freund R., A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing System, Journal of Parallel and Distributed Computing, vol. 61, no. 6, pp. 810-837, 2001.

[4] Chen H., Cheng A., and Kuo Y., Assigning Real-Time Tasks to Heterogeneous Processors by Applying Ant Colony Optimization, Journal of Parallel and Distributed Computing, vol. 71, no. 1, pp.132-142, 2011.

[5] Dorigo M. and St tzle T., Ant Colony Optimization, MIT Press, 2004.

[6] Garey M. and Johnson D., Computers and Intractability: A Guide to the Theory of NP- Completeness, W. H. Freeman and Co, 1979.

[7] Jin H., Wang H., Wang H., and Dai G., An ACO-Based Approach for Task Assignment and Scheduling of Multiprocessor Control Systems, in Proceedings of International Conference on Theory and Applications of Models of Computation, Beijing, pp. 138-147, 2006.

[8] Krishna C. and Shink K., Real-Time System, McGraw-Hill, 1997.

[9] Narayan V. and Subbarayan G., An Optimal Feature Subset Selection Using GA for Leaf Classification, The International Arab Journal of Information Technology, vol. 11, no. 5, pp. 447-451, 2014.

[10] Poongothai M., ARM Embedded Web Server Based on DAC System, in Proceedings of the International Conference on Process Automation, Control and Computing, Coimbatore, pp. 1-5, 2011.

[11] Poongothai M., Rajeswari A., and Kanishkan V., A Heuristic Based Real Time Task Assignment Algorithm for the Heterogeneous Multiprocessors, IEICE Electronic Express, vol. 11, no. 3, pp. 1-9, 2014.

[12] Prescilla K. and Selvakumar A., Modified Binary Particle Swarm Optimization Algorithm Application to Real-Time Task Assignment in Heterogeneous Multiprocessor, Microprocessors and Microsystems, vol. 37, no. 6-7, pp. 583-589, 2013.

[13] Srikanth G., Maheswari V., Shanthi P., and Siromoney A., Tasks Scheduling Using Ant Colony Optimization, Journal of Computer Science, vol. 8 , no. 8, pp. 1314-1320, 2012.

[14] Stutzle T. and Hoos H., MAX-MIN Ant System and Local Search for the Traveling Salesman Problem, in Proceedings of the IEEE International Conference on Evolutionary Computation, Indianapolis, pp. 309-314,1997.

[15] Wu J., Liu X., Shu J., Li Y., and Liu K., Independent Task Assignment of Space Warfare Based on MAS and ACO, Journal of Information and Computational Science, vol. 10, no. 12, pp. 3861-3867, 2013. Poongothai Marimuthu is currently an Assistant Professor (Senior Grade) in the Department of Electronics and Communication Engineering, Coimbatore Institute of Technology, Coimbatore 641014 India. Her research areas includes Scheduling in Real-time systems, energy efficient computing systems, low power design and power management of energy harvesting real-time embedded system. Rajeswari Arumugam is currently a Professor and Head of Department of Electronics and Communication Engineering, Coimbatore Institute of Technology, Coimbatore 641014 India. Her areas of interest include wireless communication, signal processing. Jabar Ali is currently doing his M.E. (Communication Engineering) in Department of Electronics and Communication Engineering, Coimbatore Institute of Technology, Coimbatore 641014, India. He completed his B.E. in Electronics and Communication Engineering in Mepco Schlenk Engineering College, Sivakasi, India. His areas of interest include Scheduling in real-time embedded systems and computer networks.