Login Register Cart 0
Generic placeholder image

Recent Patents on Engineering

Editor-in-Chief

ISSN (Print): 1872-2121
ISSN (Online): 2212-4047

Back
Journal Home About Journal Editorial Board Journal Insight Current Issue Volumes/Issues
Subscribe
Research Article

An Improved Genetic Algorithm on Hybrid Information Scheduling

Author(s): Jingmei Li, Qiao Tian, Fangyuan Zheng* and Weifei Wu

Volume 13, Issue 4, 2019

Page: [416 - 423] Pages: 8

DOI: 10.2174/1872212112666180817130152

Price: $65

Abstract

Background: Patents suggest that efficient hybrid information scheduling algorithm is critical to achieve high performance for heterogeneous multi-core processors. Because the commonly used list scheduling algorithm obtains the approximate optimal solution, and the genetic algorithm is easy to converge to the local optimal solution and the convergence rate is slow.

Methods: To solve the above two problems, the thesis proposes a hybrid algorithm integrating list scheduling and genetic algorithm. Firstly, in the task priority calculation phase of the list scheduling algorithm, the total cost of the current task node to the exit node and the differences of its execution cost on different processor cores are taken into account when constructing the task scheduling list, then the task insertion method is used in the task allocation phase, thus obtaining a better scheduling sequence. Secondly, the pre-acquired scheduling sequence is added to the initial population of the genetic algorithm, and then a dynamic selection strategy based on fitness value is adopted in the phase of evolution. Finally, the cross and mutation probability in the genetic algorithm is improved to avoid premature phenomenon.

Results: With a series of simulation experiments, the proposed algorithm is proved to have a faster convergence rate and a higher optimal solution quality.

Conclusion: The experimental results show that the ICLGA has the highest quality of the optimal solution than CPOP and GA, and the convergence rate of ICLGA is faster than that of GA.

Keywords: Hybrid information scheduling, genetic algorithm, optimal solution, high performance, convergence rate, ICLGA.

Graphical Abstract

[1]
H.F. Sheikh, I. Ahmad, and D. Fan, "An Evolutionary Technique for Performance-Energy-Temperature Optimized Scheduling of Parallel Tasks on Multi-Core Processors", IEEE Transactions on Parallel & Distributed Systems,, vol. 27, pp. 668-681, 2016.
[2]
B. Keshanchi, A. Souri, and N.J. Navimipour, "An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: Formal verification, simulation, and statistical testing", J. Syst. Softw., vol. 124, pp. 1-21, 2016.
[3]
D. Yun, C.Q. Wu, and Y. Gu, "An Integrated Approach to Workflow Mapping and Task Scheduling for Delay Minimization in Distributed Environments", J. Parallel Distrib. Comput., vol. 84, pp. 51-64, 2015.
[4]
L.T. Peterson, and J.A. Mccombe, Scheduling heterogenous computation on multithreaded processors.. U.S. Patent 20120324458 A1, 2012.
[5]
F. Lotfifar, and H.S. Shahhoseini, "A Low-Complexity Task Scheduling Algorithm for Heterogeneous Computing Systems", Asia International Conference on Modelling & Simulation. IEEE, 2009pp. 596-601
[6]
A. Akkasi, "“Genetic algorithm for task scheduling in heterogeneous distributed computing system”", Inter. J. Sci. Eng. Res.. Vol. 6, pp. 1338-1345, 2015.
[7]
V. David, Method for executing tasks in a critical real-time system.. WO Patent /2014/167197, 2014.
[8]
Y. Zhong, Research on Intelligent Optimization Method and Its Application., Zhejiang University, 2005, pp. 19-30.
[9]
H. Topcuoglu, S. Hariri, and M.Y. Wu, "Task scheduling algorithms for heterogeneous processors ", Heterogeneous Computing Workshop. IEEE, 1999pp. 3-14
[10]
M.I. Daoud, and N. Kharma, "A hybrid heuristic–genetic algorithm for task scheduling in heterogeneous processor networks", J. Parallel Distrib. Comput., vol. 71, pp. 1518-1531, 2011.
[11]
M. Abdullahi, M.A. Ngadi, and S.M. Abdulhamid, "Symbiotic Organism Search optimization based task scheduling in cloud computing environment", Future Gener. Comput. Syst., vol. 56, pp. 640-650, 2016.
[12]
X. Wang, Y. Wang, and H. Zhu, "Energy-efficient Task Scheduling Model based on MapReduce for Cloud Computing using Genetic Algorithm", J. Comp., vol. 7, no. 12, 2012.
[13]
S.G. Ahmad, C.S. Liew, and E.U. Munir, "A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems", J. Parallel Distrib. Comput., vol. 87, pp. 80-90, 2015.
[14]
S.G. Ahmad, E.U. Munir, and W. Nisar, "“PEGA: A Performance Effective Genetic Algorithm for Task Scheduling in Heterogeneous Systems”", IEEE, International Conference on High Performance Computing and Communication & 2012 IEEE, International Conference on Embedded Software and Systems. IEEE,, 2012pp. 1082-1087
[15]
R. Singh, "“An optimized task duplication based scheduling in parallel system”", Int. J. Intell. Syst. Appl., Vol , vol. 8, pp. 26-37, 2016.
[16]
Y. Xu, K. Li, and L. He, "A Hybrid Chemical Reaction Optimization Scheme for Task Scheduling on Heterogeneous Computing Systems", IEEE Trans. Parallel Distrib. Syst., vol. 26, pp. 3208-3222, 2015.
[17]
R. Aron, I. Chana, and A.A. Abraham, "Hyper-heuristic approach for resource provisioning-based scheduling in grid environment", J. Supercomput., vol. 71, pp. 1427-1450, 2015.
[18]
W. Wang, K. Zhu, and L. Ying, "MapTask Scheduling in MapReduce With Data Locality: Throughput and Heavy-Traffic Optimality", IEEE/ACM Transactions on Networking , vol. 24, pp. 190-203, 2016.

Rights & Permissions Print Cite
Article Metrics
17
2
1
1
© 2024 Bentham Science Publishers | Privacy Policy