Friday , April 19 2024

Genetic Algorithms for Job Scheduling in
Cloud Computing*

Mohammed-Albarra HASSAN1,2, Imed KACEM1*,
Sébastien MARTIN1, Izzeldin M. OSMAN3
1 Université de Lorraine,
LCOMS EA 7306, Metz, 57000, France
imed.kacem@univ-lorraine.fr (Corresponding author)
2 University of Gezira,
Wadmedani, Sudan
barra.hassan@univ-lorraine.fr
3 University of Sciences and Technology,
Khartoum, Sudan
izzeldin@acm.org

Abstract: Efficient job scheduling algorithms needed to improve the resource utilization in cloud computing, the role of a good scheduling algorithm on cloud computing is to minimize the total completion time for last job on the system. In this paper, we present a genetic-based task scheduling algorithms in order to minimize Maximum Completion Time Makespan. These algorithms combines different techniques such as list scheduling and earliest completion time (ECT) with genetic algorithm. We reviewed, evaluated and compared the proposed algorithms against one of the well-known Genetic Algorithms available in the literature, which has been proposed for task scheduling problem on heterogeneous computing systems. After an exhaustive computational analysis we identify that the proposed Genetic algorithms show a good performance overcoming the evaluated method in different problem sizes and complexity for a large benchmark set of instances.

Keywords: Task scheduling, Genetic Algorithm, Cloud Computing, Unrelated Parallel machines with precedence Constraints.

>>Full text<<
CITE THIS PAPER AS:
Mohammed-Albarra HASSAN, Imed KACEM, Sébastien MARTIN, Izzeldin M. OSMAN, Genetic Algorithms for Job Scheduling inCloud Computing, Studies in Informatics and Control, ISSN 1220-1766, vol. 24 (4), pp. 387-400, 2015. https://doi.org/10.24846/v24i4y201503

Introduction

In Cloud environments a task scheduling is a process that manages and maps the execution of inter-dependent tasks on the data centers (resources) [6]. It allocates appropriate tasks to the virtual resources which is virtual machines (VMs) so the execution is often completed to satisfy objective functions imposed by customers. Efficient task scheduling algorithm will have important impact on the performance of the system. The scheduling problem in cloud computing can be generalized as an unrelated parallel machine with different speeds and precedence constraints. We consider VMs as an unrelated parallel machine because the cloud computing providers offer their services virtually by sharing their physical resources through a large number of virtual machines in parallel. These virtual machines, allocated with different CPU capacities, so it can be considered as unrelated parallel machines.

In cloud computing users may face hundreds of thousands of virtualized resources to utilize. It is hard to allocate user’s tasks on the available resources. Due to the virtualization properties, cloud computing leaves task scheduling complexity to the virtual machine layer through resource virtualization.

Hence, to allocate the resources to each task efficiently, scheduling plays more important role in cloud computing [3]. It is quite difficult to achieve an optimal solution with traditional optimization methods. Mathematical optimization techniques can give an optimal solution for a reasonably sized problem, however, in the case of a large scale problem, their application is limited [13]. Dispatching rules (LPT, SPT, EDD,…) are suitable only for small scale problems and no single dispatching rule guarantees good result in various problems [5]. Research efforts in scheduling are concentrated on heuristic approaches. Many heuristics and meta-heuristics have been proposed such as simulated annealing (SA), tabu search, branch and bound (B&B) and genetic algorithm (GA) [3]. Among these various approaches to different scheduling problems, there has been an increasing interest in applying GA in view of its adaptability. The important difference between GA and other heuristics is that GA maintains a set of solutions (population) rather than a unique solution, which leads to a better diversity.

This paper considers the problem of task scheduling in cloud computing as the problem of unrelated parallel machines with precedence constraints in order to minimize makespan (Cmax). In scheduling problems, Cmax is equivalent to the completion time of the last task leaving the system.

The small Cmax usually implies a high utilization. Therefore, reducing the Cmax should also lead to a higher throughput rate [5]. Three genetic algorithms have been applied to solve this problem. The rest of the paper is organized as follows. Section 2 reports the literature review. In Section 3, we formulate the problem.

Our genetic algorithms are represented in Section 4. In Section 5 we discussed the results, and Section 6 concludes the paper.

REFERENCES

  1. GRAHAM, R. L., E. L. LAWLER, J. K. LENSTRA, A. R. KAN, Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, Annals of Discrete Mathematics, vol. 5, 1979, pp. 287-326.
  2. RAHMANI, A. M., M. REZVANI, A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems, Intl J. of Computer Theory and Engineering, vol. 1, no. 1, 2009, pp. 1793-8201.
  3. SHENAI, S., Survey on Scheduling Issues in Cloud Computing, Procedia Engineering, vol. 38, 2012, pp. 2881-2888.
  4. HALL, N. G., E. MARC, Generating Experimental Data for Computational Testing with Machine Scheduling Applications, Operations Research, vol. 49, no. 7, 2001, pp. 854-865.
  5. CHENG, W., L. MIN, A Genetic Algorithm for Minimizing the Makespan in the Case of Scheduling Identical Parallel Machines, Artificial Intelligence in Eng., vol. 13, no. 4, 1999, pp. 399-403.
  6. BALA, A., I. CHANA, A Survey of Various Task Scheduling Algorithms in Cloud Environment, IJCA, 2011, pp. 26-30.
  7. HUANG, Q., X. HUANG, J. LI, K. SHUANG, S. SU, J. WANG, Cost-efficient Task Scheduling for Executing Large Programs in the Cloud, Parallel Computing, vol. 39(4), 2013, pp. 177-188.
  8. GUO, L., C. JIANG, S. ZHAO, S. SHEN, Task Scheduling Optimization in Cloud Computing based on Heuristic Algorithm, Journal of Networks, vol. 7, no. 3, 2012, pp. 547-553.
  9. TIAN, S., Y. XU, H. ZHAO, G. ZHOU, A Genetic-based Task scheduling Algorithms on Heterogeneous Computing Systems to Minimize Makespan, Journal of Convergence Information Technology( JCIT), vol. 8, no. 5, 2013, pp. 547-555.
  10. BILGAIYAN, S., M. DAS, S. SAGNIKA, An Analysis of Task Scheduling in Cloud Computing using Evolutionary and Swarm-based Algorithms, International Journal of Computer Applications, vol. 89, no. 2, 2014, pp. 11-18.
  11. LIU, C., YANG, S., A Heuristic Serial Schedule Algorithm for Unrelated Parallel Machine Scheduling with Precedence Constraints, Journal of Software, vol. 6(6), 2011, pp. 1146-1153.
  12. HE, J., Y. KANG, H. LU, A PSO-based Genetic Algorithm for Scheduling of Tasks in a Heterogeneous Distributed System, Journal of software, vol. 8, no. 6, 2013, pp. 1443-1450.
  13. BALIN, S., Non-Identical Parallel Machine Scheduling using Genetic Algorithm, Expert Sys. with Applications, vol. 38(6), 2011, pp. 6814-6821.
  14. BAZZAZI, M., M. IZADI, F. SASSANI, F. TAHERI, R. TAVAKKOLI-MOGHADDAM, Design of a Genetic Algorithm for Bi-objective Unrelated Parallel Machines Scheduling with Sequence-dependent Setup Times and Precedence Constraints, Computers & Operations Research, vol. 36, no. 12, 2009, pp. 3224-3230.
  15. RUIZ, R., E. VALLADA, A Genetic Algorithm for the Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, European Journal of Operational Research, 211(3), 2011, pp. 612-622.
  16. BENZIANI, Y., I. KACEM, P. LAROCHE, A. NAGIH, Exact and Heuristic Methods for Minimizing the Total Completion Time in Job-shops, Studies in Informatics and Control, ISSN 1220-1766, vol. 23(1), 2014, pp. 31-40.
  17. ARYAN, Y., A. G. DELAVAR, HSGA: A Hybrid Heuristic Algorithm for Workflow Scheduling in Cloud Systems. Cluster Computing, vol. 17, no. 1, 2014, pp. 129-137.
  18. AHMAD, I., Y. K. KWOK, Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors, ACM Computing Surveys, vol. 31, no. 4, 1999, pp. 406-471.
  19. DEEPA, S. N., S. N. SIVANANDAM, Introduction to Genetic Algorithm, Springer Berlin Heidelberg, 2008.
  20. HASSAN, M.-A., I. KACEM, S. MARTIN, Unrelated Parallel Machines with Precedence Constraints: Application to Cloud Computing, Cloudnet 2014, pp. 438-442.

* This paper recalls the Task Scheduling Genetic Algorithm (GATS), published in [20]. In the current paper, we improve GATS and we propose an advanced version GATS+. Moreover, we propose two new algorithms: Genetic Algorithm Based on Cut-point (GACP) and Genetic Algorithm Based on The List of Available Jobs (GAAV), as well as its improved version (GAAV+). We also tested and compared different versions of these genetic algorithms (GAAV -> GATS, GAAV+ -> GATS, GATS -> GAAV, GATS -> GAAV+).

Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved