Multi-Objective Genetic Algorithm for Tasks Allocation in Cloud Computing

Multi-Objective Genetic Algorithm for Tasks Allocation in Cloud Computing

Youssef Harrath (University of Bahrain, Kingdom of Bahrain) and Rashed Bahlool (University of Bahrain, Kingdom of Bahrain)
Copyright: © 2019 |Pages: 21
DOI: 10.4018/IJCAC.2019070103

Abstract

The problem of allocating real-time tasks to cloud computing resources minimizing the makespan is defined as a NP-hard problem. This work studies the same problem with two realistic multi-objective criteria; the makespan and the total cost of execution and communication between tasks. A mathematical model including objective functions and constraints is proposed. In addition, a theoretical lower bound for the makespan which served later as a baseline to benchmark the experimental results is theoretically determined and proven. To solve the studied problem, a multi-objective genetic algorithm is proposed in which new crossover and mutation operators are proposed. Pareto-optimal solutions are retrieved using the genetic algorithm. The experimental results show that genetic algorithm provides efficient solutions in term of makespan for different-size problem instances with reference to the lower bound. Moreover, the proposed genetic algorithm produces many Pareto optimal solutions that dominate the solution given by greedy algorithm for both criteria.
Article Preview
Top

Introduction

Since the 1960s, researchers have been proving that the cost of having super computers can be reduced with the help of the concept of load balancing. This implies that the power of those super computers could be divided, forming smaller and distributed computing units, ensuring the concept of parallelism in which tasks can be executed simultaneously (Thain, Tannenbaum, & Livny, 2005). Ultimately, these smaller computing units can be shared among service requesters. It is worth mentioning that cloud computing descends from the distributed computing family (Voorsluys, Broberg, & Buyya, 2011). Hence, the concept of having shared and distributed resources is not newly introduced in cloud computing, as Wang, et al. (2010) states, however, its concept has been evolving since the invention of time-sharing systems.

Having said that, it is also noticed that the problem of allocating tasks to distributed resources has been extensively studied in distributed systems, such as grids and clusters in the works of Hwang (1993), Bharadwaj (1996), and Kesselman and Foster (1999). Consequently, many heuristics were proposed by researchers to deal with the problems of task allocation sharing the same objective, i.e. to efficiently distribute the load among distributed computing units. Thus, it is observed that some of these heuristics developed for predecessors have been adopted in cloud computing. These methods include: Min-Min, Max-Min, Round-Robbin, Genetic Algorithm, and Particle-Swarm Optimization (Braun, et al., 2001; Teo & Ayani, 2001; Wolski, Plank, Brevik, & Bryan, 2001; Ritchie & Levine, 2004).

Cloud computing, on the other hand, is an efficient utilization of a pool of virtualized resources given in an on-demand and a pay-per-use manner (Vaquero, Rodero-Merino, Caceres, & Linder, 2008). These virtual resources provided by the cloud are to be provided in the emulated form of hardware which acts in a similar manner as physical machines, thus ensuring a high level of abstraction and better resource utilization (Furht & Escalante, 2010). This leads to a better capital investment for businesses, as cloud eliminates the need for hosting and maintaining hardware and software resources in any organization, as highlighted in the work of Wu et al. (June, 2010) and Ma et al. (2014). Services in a cloud environment are given in three different forms: Software-as-a-Service (SaaS), Platform-as-a-Service (PaaS), and Infrastructure-as-a-Service (IaaS). SaaS is the providence of applications to end-users in which all processes contributing in executing the applications are hosted in the cloud. PaaS on the other hand, is the providence of software development kits (SDK) that are necessary for developers and programmers, whereas IaaS is the delivery of virtual and scalable hardware resources such as computing power and storage. It is worth mentioning that all three services are provided in an on-demand and pay-per-use manner.

Cloud computing enables computing devices, with less regard to their capacities and sizes, to continue accessing different types of services over the internet. Not to forget that these services are to be provided while ensuring a high level of satisfaction for both customers and cloud providers, while also meeting certain quality of service (QoS) objectives. These QoS objectives include executing tasks before their deadlines in time-sensitive applications discussed in the works of Nastar and Mitschke (1998), Datta et al. (2008), and Kim et al. (2009). Nonetheless, according to Kumar et al. (2011), and as the usage of cloud starts to evolve, studies in the field of cloud computing which are concerned with the real-time aspect is limited.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2019)
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing