Based on Improved Genetic Algorithm for Task Scheduling of Heterogeneous Multi-Core Processor

Abstract:

This paper puts forward an improved genetic scheduling algorithm in order to improve the execution efficiency of task scheduling of the heterogeneous multi-core processor system and give full play to its performance. The attribute values and the high value of tasks were introduced to structure the initial population, randomly selected a method with the 50% probability to sort for task of individuals of the population, thus to get high quality initial population and ensured the diversity of the population. The experimental results have shown that the performance of the improved algorithm was better than that of the traditional genetic algorithm and the HEFT algorithm. The execution time of tasks was reduced.

• Periodical: Advanced Materials Research (Volumes 1030-1032)
• Pages: 1671-1675
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1030-1032.1671
• Online since: September 2014
• Authors: Yue Qiu*, Jing Feng Zang
• Keywords: Crossover Probability, Genetic Algorithm (GA), Heterogeneous Multi-Core Processor, Mutation Probability, Task Scheduling

References

[1] T.D. Braun, H.S. Siegel, N. Beck: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing Vol. 61(6) (2001), pp.810-837.

DOI: 10.1006/jpdc.2000.1714

[2] B. Naderi, M.R. Tavakkoli, M. Khalili: Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowledge-Based Systems Vol. 23(2) (2010), pp.77-85.

DOI: 10.1016/j.knosys.2009.06.002

[3] E.S.H. Hou, N. Ansari, H. Ren: A genetic algorithm for multiprocessor scheduling. Parallel and Distributed Systems, IEEE Transactions on Vol. 5(2) (1994), pp.113-120.

DOI: 10.1109/71.265940

[4] Y. Wen, H. Xu, J. Yang: A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system. Information Sciences Vol. 181(3) (2011), pp.567-581.

DOI: 10.1016/j.ins.2010.10.001

[5] M.I. Daoud, N. Kharma. A hybrid heuristic–genetic algorithm for task scheduling in heterogeneous processor networks. Journal of Parallel and Distributed Computing Vol. 71(11) (2011), pp.1518-1531.

DOI: 10.1016/j.jpdc.2011.05.005

[6] A.S. Wu, S.Y. Jin: An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling. IEEE Transactions on Parallel and Distributed Systems Vol. 15(9) (2004), pp.824-834.

DOI: 10.1109/tpds.2004.38

[7] H. Topcuoglu, S. Hariri: Performance effective and Low complexity Task Scheduling for Heterogeneous Computing. IEEE Transactions on Parallel and Distributed Systems Vol. 13(3) (2002), pp.260-274.

DOI: 10.1109/71.993206

[8] Z. Bingul: Adaptive genetic algorithms applied to dynamic multi-objective problems. Applied Soft Computing Vol. 7 (2007), pp.791-799.

DOI: 10.1016/j.asoc.2006.03.001

[9] J. Carretero, F. Xhafa, A. Abraham: Genetic algorithm based schedulers for grid computing systems. International Journal of Innovative Computing, Information and Control Vol. 3(6) (2007), pp.1-19.