Computational Sciences and Engineering

Current Issue

By Issue

By Author

By Subject

Author Index

Keyword Index

About Journal

Aims and Scope

Editorial Board

Publication Ethics

Indexing and Abstracting

Related Links

FAQ

Peer Review Process

Journal Metrics

News

An Enhanced Genetic Algorithm for Task Scheduling in Heterogeneous Systems

Document Type : Original Article

Authors

1 Department of Electrical and Computer Engineering, University of Science and Technology of Mazandaran, Behshahr, Iran

2 Department of Computer Science, Iran University of Science and Technology, Tehran, Iran

Abstract

Generally, jobs are divided into smaller portions, in parallel and according to distributed processing, and each portion is called a task. Each task can execute dependently or independently. When introducing heterogeneous systems, it is desirable that tasks can run on these systems. Since it is advantageous that tasks running on heterogeneous systems are completed faster, the optimization of task scheduling is of great importance. Actually, task scheduling problems in heterogeneous systems are NP-hard and it is a crucial issue. In such problems, Directed Acyclic Graphs (DAGs) can be used as task graphs to be scheduled on heterogeneous systems. The proposed method presents a genetic algorithm with new operators and final scheduler to be scheduled on heterogeneous systems. The practicality and convergence of the algorithm are proved by Markov’s chain theory. The findings reveal that the currently proposed algorithm is more efficient in comparison to previously presented ones and also has a better make span. Moreover, it is concluded that the Enhanced Genetic Algorithm (EGA) achieves the solution faster in early generations.

Keywords

References
[1] Xu, Y., Li, K., Hu, J., & Li, K. (2014). A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 270, 255-287.
[2] Arabnejad, H., & Barbosa, J. G. (2013). List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE transactions on parallel and distributed systems, 25(3), 682-694.
[3] Panwar, P., Sachdeva, S., & Rana, S. (2016). A genetic algorithm based scheduling algorithm for grid computing environments. In Proceedings of Fifth International Conference on Soft Computing for Problem Solving: SocProS 2015,1,165-173 Springer Singapore.
[4] Coffman, E. G., & Bruno, J. L. (1976). Computer and job-shop scheduling theory. John Wiley & Sons.
[5] Gary, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness.
[6] Ullman, J. D. (1975). NP-complete scheduling problems. Journal of Computer and System sciences, 10(3), 384-393.
[7] Zomaya, A. Y., Ward, C., & Macey, B. (1999). Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Transactions on Parallel and Distributed systems, 10(8), 795-812.
[8] Kwok, Y.K., Ahmad, I. (1999). Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv. (CSUR) 31(4).
[9] Topcuoglu, H., Hariri, S., & Wu, M. (2002). Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. IEEE Trans. Parallel and Distributed Systems, 13(3), 260-274.
[10] Canon, L.C., Jeannot, E., Sakellariou, R., & Zheng, W. (2008), Comparative Evaluation of the Robustness of Dag Scheduling Heuristics. Grid Computing: Achievements and Prospects, S.Gorlatch, P. Fragopoulou, and T. Priol, eds., Springer, 73-84.
[11] Boeres, C., Filho, J.V., & Rebello, V. E. F. (2004). A Cluster-Based Strategy for Scheduling Task on Heterogeneous Processors. 16th Symp. Computer Architecture and High Performance Computing, 214-221.
[12] Cirou, B., & Jeannot, E. (2001). Triplet: A Clustering Scheduling Algorithm for Heterogeneous Systems.  Int’l Conf. Parallel Processing Workshops, 231-236.
[13] Jiang, Y. S., & Chen, W. M. (2015). Task scheduling for grid computing systems using a genetic algorithm. The Journal of Supercomputing, 71(4), 1357-1377.
[14] Holland, J. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, USA.
[15] Agustı, L. E., Salcedo-Sanz, S., Jiménez-Fernández, S., Carro-Calvo, L., Del Ser, J., & Portilla-Figueras, J. A. (2012). A new grouping genetic algorithm for clustering problems. Expert Systems with Applications, 39(10), 9695-9703.
[16] Mitchell, (1999). An Introduction to Genetic Algorithms. Cambridge, Massachusetts London, England: Massachusetts Institute of Technolog.
[17] Li, F., Da Xu, L., Jin, C., & Wang, H. (2012). Random assignment method based on genetic algorithms and its application in resource allocation. Expert Systems with Applications, 39(15), 12213-12219.
[18] Gebali, F. (2015). Analysis of Computer Networks. Cham Heidelberg New York Dordrecht London: Springer.
[19] Panwar, P., Lal, A.K., & Singh, J. (2012).  A Genetic algorithm based technique for efficient scheduling of tasks on multiprocessor system.  In: Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011), 911–919. Springer India.
Computational Sciences and Engineering
Volume 3, Issue 2
September 2023
Pages 177-188
Files
Share
How to cite
Statistics