A Comparison of Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing in Real-Time Task Scheduling on CMP


Article Preview

Real-time task schedule problem in Chip-Multiprocessor (CMP) receives wide attention in recent years. It is partly because the increasing demand for CMP solutions call for better schedule algorithm to exploit the full potential of hardware, and partly because of the complexity of schedule problem, which itself is an NP-hard problem. To address this task schedule problem, various of heuristics have been studied, among which, Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Simulated Annealing (SA) are the most popular ones. In this paper, we implement these 3 schedule heuristics, and compare their performance under the context of real-time tasks scheduling on CMP. According to the results of our intensive simulations, PSO has the best fitness optimization of these 3 algorithms, and SA is the most efficient algorithm.



Edited by:

Ming Ma




S. Chai et al., "A Comparison of Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing in Real-Time Task Scheduling on CMP", Advanced Materials Research, Vol. 679, pp. 77-81, 2013

Online since:

April 2013




[1] Lee, W.Y., Energy-Saving DVFS Scheduling of Multiple Periodic Real-Time Tasks on Multi-core Processors, in: Proceedings of the 2009 13th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications, 2009, IEEE Computer Society. pp.216-223.

DOI: https://doi.org/10.1109/ds-rt.2009.12

[2] E. Azketa, J. P. Uribe, M. Marcos, L. Almeida and J. J. Gutierrez, Permutational Genetic Algorithm for the Optimized Assignment of Priorities to Tasks and Messages in Distributed Real-Time Systems, in: Trust, Security and Privacy in Computing and Communications (TrustCom), 2011 IEEE 10th International Conference on, 2011, pp.958-965.

DOI: https://doi.org/10.1109/trustcom.2011.132

[3] O. L. Sathappan, P. Chitra, P. Venkatesh and M. Prabhu, Modified genetic algorithm for multiobjective task scheduling on heterogeneous computing system, in: International Journal of Information Technology, Communications and Convergence, vol. 1, pp.146-158, (2011).

DOI: https://doi.org/10.1504/ijitcc.2011.039282

[4] L. Zhang, Y. Chen, R. Sun, S. Jing and B. Yang, A task scheduling algorithm based on pso for grid computing, in: International Journal of Computational Intelligence Research, vol. 4, pp.37-43, (2008).

[5] H. Izakian, B. T. Ladani, A. Abraham and V. Snasel, A discrete particle swarm optimization approach for grid job scheduling, in: International Journal of Innovative Computing, Information and Control, vol. 6, pp.4219-4233, (2010).

[6] H. Lin, Y. Feng and X. Qiang, On Task Allocation and Scheduling for Lifetime Extension of Platform-Based MPSoC Designs, in: Parallel and Distributed Systems, IEEE Transactions on, vol. 22, pp.2088-2099, (2011).

DOI: https://doi.org/10.1109/tpds.2011.132

[7] J. Hua, B. Yun, Z. Liping and L. Yanxiu, A hybrid algorithm of Harmony Search and Simulated Annealing for multiprocessor task scheduling, in: Systems and Informatics (ICSAI), 2012 International Conference on, 2012, pp.718-720.

DOI: https://doi.org/10.1109/icsai.2012.6223111

[8] J. Kennedy, Swarm intelligence, in: Handbook of nature-inspired and innovative computing, pp.187-219, (2006).

DOI: https://doi.org/10.1007/0-387-27705-6_6

[9] H. Orsila, E. Salminen and T. D. Hämäläinen, Best practices for simulated annealing in multiprocessor task distribution problems, in: Simulated Annealing, pp.321-342, (2008).

DOI: https://doi.org/10.5772/5559