Pa ge 1 Pa ge 10 American Journal of Smart Technology and Solutions (AJSTS) Genetic Algorithm of Independent Task Meta-Scheduling Centralized in the Cloud Computing Stéphane Fouakeu Tatieze1*, Jean Claude Kamgang2, Marcellin Julius Nkenlifack3 Volume 2 Issue 2, Year 2023 ISSN: 2837-0295 (Online) DOI: https://doi.org/10.54536/ajsts.v2i2.1804 https://journals.e-palli.com/home/index.php/ajsts Article Information ABSTRACT Received: June 30, 2023 Accepted: July 24, 2023 Published: July 30, 2023 A group of networked, virtualized computers make up the distributed, parallel cloud computing technology. The power for these machines is dynamic, and they are displayed as one or more computing resources. These are compiled based on service level agreements (SLAs) that have been negotiated between the service provider and the customers. Enterprise applications have migrated in large numbers to cloud computing during the past few years. One of the most important challenges of Cloud Computing is the scheduling of tasks; which should satisfy Cloud users in terms of Quality of Service and increase the profit of cloud providers. Bio-inspired algorithms (genetics) represent a heuristic research technique that produces effective solutions. In this article, we propose a genetic meta-scheduling algorithm that optimizes the execution time and makespan of tasks submitted by users. To achieve this, this algorithm is based on the requirements of user requests and the availability of resources (Virtual Machines) of Cloud Computing to obtain a better combination as an optimal solution. This effort makes the meta-scheduling genetic algorithm superior than others in the literature like the Min-Min algorithm and the regular genetic algorithm. Customer satisfaction is higher, and more particularly, the execution time and makespan are better. Keywords Cloud Computing, Genetic Algorithm, Meta-Scheduling 1 Department of Electrical Engineering and Industrial Automation, ENSAI, University of Ngaoundéré, Cameroon 2 Department of Mathematics and Computer, ENSAI, University of Ngaoundéré, Cameroon 3 Department of Mathematics and Computer, Faculty of Sciences, University of Dschang, Cameroon * Corresponding author’s e-mail: fouakeustephane@gmail.com INTRODUCTION Cloud computing (CC) is a new paradigm for utility virtualized resources, designed for end users in a dynamic computing environment to provide reliable and guaranteed services (Dillon et al., 2010). Cloud Computing has service models and deployment models. As service models, we have Software as a Service (SaaS), Platform as a Service (PaaS), Infrastructure as a Service (IaaS). Software as a Service (SaaS) provides users with applications in the form of online services already deployed in the cloud. This layer is managed by the SaaS provider in a way that is transparent to users. Platform as a Service (PaaS) is more oriented to serve application developers. It offers a fully configured and managed plat- form on which the user can develop, test and run their applications. Infrastructure as a Service (IaaS) allows infrastructure resources such as computing capacity, storage, network as utilities. As deployment models, we have private cloud, community cloud, public cloud, hybrid cloud. In the private cloud, all of its resources are made available exclusively to a single company or organization. The private cloud can be managed by the company itself (internal private cloud) or by a third party (external private cloud). In the community cloud, the infrastructure is shared by several independent organizations with com- mon interests. The infrastructure can be managed by the member organizations or by a third party. In the public cloud, the infrastructure is accessible to a wide public and is owned by a service provider. The latter charges users ac- cording to consumption and guarantees the availability of services through SLA contracts and for the hybrid cloud, the infrastructure is a composition of several clouds (private, community or public) (Dillon et al., 2010). Cloud environment allows users to use applications without installation and access their personal files at any computer with Internet access, end users access cloud based applications through a web browser or a light weight desktop (Durga et al., 2016). CC, applies distributed computing techniques to deliver an on-demand access to a shared virtual computing resources (ex. Net- works, Servers, Storage, Applications and Services) over the Internet (Zhang et al., 2010; Singh et al., 2017). Virtualization is an emerging technology for efficient utilization of cloud resources. It is used to split a single physical machine into multiple Virtual Machines (VM) (Malhotra et al., 2010). VM also can provide resource sharing, high utilization of pooled resources, rapid provisioning and workload isolation (Ahmad et al., 2015b). Usually, a Cloud Service Provider (CSP), like Google, presents these facilities using the pay per use model (Arya et al., 2014). By the help of cloud computing technology, users such as the individuals, researchers and large businesses can access their data, applications, on different platforms via the internet without the need for buying costly computing resources. The main goal of Cloud computing is to satisfy cloud users with the agreed QoS and improve profits of cloud providers (Buyya et al., 2009). To provide ensured proficient performance to users, it is necessary that tasks should be mapped efficiently to available resources. Task Scheduling (TS) is one of the core challenges in CC environment. The task Scheduling problem in Cloud, which is known to be NP-hard, is as- signing different tasks to corresponding resource node under the Quality of Services (QoS) constraints (Aarts et al., 2005). TS can be classified into Pa ge 11 https://journals.e-palli.com/home/index.php/ajsts Am. J. Smart. Technol. Solutions 2(2) 10-20, 2023 independent scheduling and de- pendent scheduling. In independent scheduling tasks are independent of each other and can be scheduled in any sequence, however in dependent scheduling, tasks are represented by a Directed Acyclic Graph (DAG) (i.e., workflow scheduling). DAG is a directed graph that comprises group of edges and vertices. Where each vertex signifies the task and every edge signifies the affiliation between two nodes or vertices connected through that edge (Singh et al., 2015). TS can also be classified into static and dynamic task scheduling. In static scheduling, all tasks or VMs are known a priori to scheduling. These tasks are independent of the virtual machine’s states and their availability. So, it imposes less runtime overhead. On the other hand, in dynamic scheduling, the information about the tasks is unknown in advance. So, the execution time of task may not be known and the information about VMs is not obtained until it comes into the scheduling stage (Nagadevi et al., 2013). TS is an optimization problem belonging to the class of NP-hard problems. Some traditional task scheduling algorithms have been applied in heterogeneous computing environments such as Min-Min (He et al., 2003), Max-Min (Mao et al., 2014), etc. So in cloud computing, there are various type of meta heuristic algorithms for scheduling problem in cloud computing such as ant colony optimization (ACO), particle swarm optimization (PSO) genetic algorithm (GA), etc, (Xu et al., 2009) can be applied to achieve near optimal solution. Genetic algorithm, based on natural selection and inheritance theory, has been widely and successfully applied in scheduling problems. In this paper, genetic algorithm is implemented using CloudSim simulator and compared to the traditional heuristic methods to solve the independent static TS problem in CC environment. In static environment, the specifications of the VMs are fixed. When users submit jobs to the resources for execution, meta-scheduler acquire information about resources from CIS (Cloud Information Service) and then divide the job into various tasks or subtasks if needed. Then map the to best resources distributed geographically same according to user’s requirements and availability of resources. CIS are responsible for providing information about status of available resources which helps the meta-scheduler for scheduling, monitoring and further communication if required. After execution of all tasks, result is combined and sends back to user via meta- scheduler. The main features of competent TS in this paper are minimizing deadline, and budget. The remainder of the paper is organized as follows. Section II gives an overview of related work on TS in cloud computing. Section III presents the task scheduling problem. Section IV presents the genetic algorithm. In Section V we have the system model. Experimental results and discussions are given in Section VI. Section VII concludes this paper. Related Work Tasks scheduling is a hot and major research area in the distributed environment like cloud computing. It is a challenging issue in which a lot of research works have been carried out. Many meta-heuristic techniques like Genetic Algorithm (GA) were proposed to solve the Tasks scheduling problems using various strategies: (Jang et al., 2012) proposed task scheduling model where the task scheduler calls the GA scheduling function to make task schedules based on information of tasks and virtual machines. The GA scheduling function creates a population, a set of task schedules, and evaluates the population by using the fitness function considering user satisfaction and virtual machine availability. The function iterates reproducing populations to output the best task schedule. Experimental results show effectiveness and efficiency of the genetic algorithm- based task scheduling model in comparison with existing task scheduling models, which are the round-robin task scheduling model, the load index-based task scheduling model, and the ABC based task scheduling model. (Kaur et al., 2012) have developed a task scheduling algorithm for cloud computing environment. The author used Shortest Cloudlet to Fastest Processor (SCFP) and Longest Cloudlet to Fastest Processor (LCFA) algorithm to initialize the population of GA. Their algorithm takes variable power processors and variable length tasks to represent a real-time scenario but considers single user job. In this research they have proposed a modified genetic algorithm for single user jobs in which the fitness is developed to encourage the formation of solutions to achieve the time minimization and compared it with existing heuristics. Experimental results show that, under the heavy loads, the proposed algorithm exhibits a good performance. In (Dasgupta et al., 2013) proposed GA as a load balancing technique for cloud computing to find a global optimum processor for job in a cloud. They have presented an approach that handles the load on processors as well as reduces the makespan, but takes equal priority tasks. Analysis of the results, indicates that the proposed strategy for load balancing not only outperforms a few existing techniques but also guarantees the QoS requirement of customer job. In (Kaur et al., 2014) genetic algorithm is enhanced using new fitness function based on mean and grand mean values. This optimization can be implemented on both ends, for job scheduling and resource scheduling. It reduces the execution time of all the tasks but considered limited number of tasks. (Atul et al., 2015) propose a multi-objective task scheduling algorithm for mapping tasks to a Vms in or-der to improve the throughput of the datacenter and reduce the cost without violating the SLA (Service Level Agreement) for an application in cloud SaaS environment. The pro- posed algorithm provides an optimal scheduling method. Most of the algorithms schedule tasks based on single criteria (i.e execution time). But in cloud environment it is required to consider various criteria like execution time, cost, bandwidth of user etc. This algorithm is simulated and the result shows better performance and improved throughput. (Juntao et al., 2016) proposes a novel dynamic task scheduling algorithm based on improved genetic algorithm (IGATS). This paper introduces the concept of load priority. First, select average queue-run Pa ge 12 https://journals.e-palli.com/home/index.php/ajsts Am. J. Smart. Technol. Solutions 2(2) 10-20, 2023 length to as a high-priority load parameter, which reflects the average number of processes running in the queue within the specified time interval; Second, select the CPU utilization and memory utilization as a priority load parameters, which reflects the currently running task size of system resources; experimental results demonstrate that the pro- posed algorithm can effectively improve the throughput of cloud computing systems, and can significantly reduce the execution time of task scheduling. (Amjad et al., 2017) presented an efficient greedy algorithm and a genetic algorithm with adaptive selection of crossover and mutation from a pool of crossover and mutation types to allocate and schedule real-time tasks with precedence constraint on heterogamous virtual machines. The selection of crossover and mutation is based on the previous performance of the operators. The adaptive GA uses population diversity to determine the fitness of each type of crossover while the fitness of mutation is determined in terms of its ability to find a better quality solution (i.e., intensification). (Rasha et al., 2018) proposed HTSCC ( Hybrid Task Scheduling in Cloud Computing) algorithm to improves the local search by using the GA mutation operator and expected to work with the different size of tasks. The proposed HTSCC algorithm makes use of the advantages of the GA and PSO algorithms in order to maximize resource utilization and minimize makespan. These features of the proposed algorithm re- duce the makespan and increase the resources utilization. To optimize large-scale task scheduling problem in Cloud environment with less makespan and computation time, (Kairong et al., 2018) proposed an adaptive incremental Genetic algorithm. Their method based on genetic algorithm which has adaptive probability of mutation rate and crossover rate can provide feasible solutions for the allocation of large numbers of tasks with less computation time. The simulation results show that algorithm outperforms the greedy algorithm and non-adaptive genetic algorithm in terms of solution quality. (Nagwan et al., 2019) have implemented TS using two metaheuristic algorithms (PSO, GA) and compared their performance with two traditional techniques (FCFS, SJF). They generate the chromosomes randomly with a list of tasks and a list of VMs to form the initial population in GA. After, evaluate the performance of each chromo- some using fitness function. It is calculated using a set of metrics such as makespan, flow time, response time, resource utilization, throughput time and degree of imbalance. Based on fitness value retrieved from each metric, chromosomes are selected and then are feed to a crossover and mutation operations. After, they update the population and decode the procuration chromosome (feasible solution) then, the best chromosome is the final solution for tasks allocation on VMS. The algorithms have been implemented as part of the cloud broker in symmetric and asymmetric environment. GA algorithm only fulfilled the optimal degree of imbalance in symmetric environment with real workload traces. Otherwise, it gave sufficient performance in obtaining the optimal response time in asymmetric environment in both of synthetic traces and real workload traces. Task Scheduling Problem Cloud consists of a number of resources that are different with one other via some means and cost of performing tasks in cloud using resources of cloud is different so scheduling of tasks in cloud is different from the traditional methods of scheduling and so scheduling of tasks in cloud need better attention to be paid because services of cloud depends on them. Task scheduling plays a key role to improve flexibility and reliability of systems in cloud. The main reason behind scheduling tasks to the resources in accordance with the given time bound, which involves finding out a complete and best sequence in which various tasks can be executed to give the best and satisfactory result to the user. In cloud computing, resources in any form i.e. cups, firewall, network are always dynamically allocated according to the sequence and requirements of the task, subtasks. So, this leads task scheduling in cloud to be a dynamic problem means no earlier defined sequence may be useful during processing of task. The reason behind the scheduling to be dynamic is that because flow of task is uncertain, execution paths are also uncertain and at the same time resources avail- able are also uncertain because there is a number of tasks are present that are sharing them simultaneously at the same time (Singh et al., 2014). The scheduling of tasks in cloud means choose the best suitable resource available for execution of tasks or to allocate computer machines to tasks in such a manner that the completion time is minimized as possible. In scheduling algorithms list of tasks is created by giving priority to each and every tasks where setting of priority to different tasks can be based on various parameters. Tasks are then chooses according to their priorities and assigned to available processors and computer ma- chines which satisfy a predefined objective function (Radulescu et al., 2000). Meta-scheduling is defined (Christodoulopoulos et al., 2009) as a software technique for optimizing workloads of grid clusters, by choosing and combining the resources of their different managers into a single aggregated view, so that jobs can be directed batch users to the best execution locations, in a manner transparent to them. For example, meta- scheduling is about assigning user jobs to nodes in a grid, such as clusters, which in turn have their own local schedulers. Cloud computing uses virtualization technique for mapping the resources of cloud to the virtual machine layer, implement the user’s task, so the task scheduling of cloud computing environment achieve at the applications layer and the virtual layer of resources. Scheduling is nothing but the mapping of tasks and resources in accordance with some certain principles for achieving the desired goal. Cloud computing paradigm simplifies the mapping of tasks to resources; the required resources together form to be virtual machines (VMs), the process of search the desired resource package is Pa ge 13 https://journals.e-palli.com/home/index.php/ajsts Am. J. Smart. Technol. Solutions 2(2) 10-20, 2023 same as the process of searching the various VMs. Genetic Algorithm Genetic Algorithm (GA) is based on the biological concept of generating the population. GA is considered a rapidly growing area of Artificial Intelligence (Jang et al., 2012). By Darwin’s theory of evolution was inspired the Genetic Algorithms (GAs). According to Darwin’s theory, term “Survival of the fittest” is used as the method of scheduling in which the tasks are assigned to resources according to the value of fitness function for each parameter of the task scheduling process (Buyya et al., 2009) (see Figure. 1). solution for the next generation based on the Darwin’s law of survival. This operation is the guiding channel for the GA based on the performance. There are various selection strategies to select the best chromosomes such as roulette wheel, Boltzmann strategy, tournament selection, selection based on rank and elitist selection. Crossover Crossover operation can be achieved by selecting two parent individuals and then creating a new individual tree by alternating and reforming the parts of those parents. Hybridization operation is a guiding process in the GA and it boosts the searching mechanism. There are some crossover strategies such as single-point crossover, two-point crossover, uniform crossover and so on. An example of single-point crossover is shown in this figure: Figure 1: Genetic Algorithm (Raj et al., 2013) Figure 2: Single-point crossover [23] Figure 3: Mutation operator [23]. The main principles of the GA are described as follows (Jang et al., 2012): Initial Population The initial population is the set of all individuals that are used in the GA to find out the optimal solution. Every solution in the population is called as an individual. Every individual is represented as a chromosome for making it suitable for the genetic operations. From the initial population, the individuals are selected, and some operations are applied on them to form the next generation. The mating chromosomes are selected based on some specific criteria. Fitness Function The productivity of any individual depends on the fit- ness value. It is the measure of the superiority of an individual in the population. The fitness value shows the performance of an individual in the population. There- fore, the individuals survive or die out according to the fitness or function value. Hence, the fitness function is the motivating factor in the GA. Selection The selection mechanism is used to select an intermediate Mutation After crossover, mutation takes place. It is the operator that introduces genetic diversity in the population. The mutation takes place whenever the population tends to become homogeneous due to repeated use of reproduction and crossover operators. It occurs during evolution according to a user-defined mutation probability, usually set to fairly low. Mutation alters one or more gene values in the chromosome from its initial state. This can produce the entirely new gene values being added to the gene pool. With this new gene values, the genetic algorithm may be able to produce a better solution than was previously. Keep Best Solution There is a solution that might satisfy good fitness function, but it is not selected during the crossover process. Overview of Proposed System System Model Our work based on the IaaS (infrastructure as a service) model of the system is illustrated in Figure 2: customers submit requests through an interface via their endpoints; cloud service providers provide customers with a virtual machine as a unit of required computing resources. Cloud customers rent these resources and pay the provider based on the amount of resources occupied and the length of Pa ge 14 https://journals.e-palli.com/home/index.php/ajsts Am. J. Smart. Technol. Solutions 2(2) 10-20, 2023 time they occupy them. The IaaS provides the hardware equipment and other basic resources as a service to users or customers in the cloud. The biggest advantage of IaaS is that it allows users to dynamically apply or release nodes, charging based on usage. The number of servers operating in IaaS reaches hundreds of thousands, so the resources that users can request are almost unlimited. At the same time, the IaaS is shared by the public, which allows for greater efficiency in the use of resources. This architecture works as follows: - Upon receipt of service requests submitted by the broker, the RM (Request Manager) evaluates them and ranks them in descending order of execution priority in the list of requests and makes them available to the Central Scheduler (CS). - The Central Scheduler (CS) sends a request for avail- ability of resources or virtual machines (VMs) to the Local Scheduler (LS) in the Cloud. - The Central Scheduler (CS) will have on one side a list of tasks grouped by order of execution priority and on the other side a list of resources (virtual machines) grouped by order of decreasing execution power. - The Central Scheduler (CS) then performs the genetic meta-ordering algorithm procedure on these two lists to find an optimal solution. - The Central Scheduler (CS) transmits the tasks to be executed to the best execution resources (virtual ma- chines) via the appropriate Local Scheduler (LS). - At the end of execution, the Local Scheduler (LS) receives the processing information via the hypervisors and transmits it to the Central Scheduler (CS). - The various users will be notified of the end of execution. - The Central Scheduler (CS) repeats the same process for new tasks that have arrived and tasks that have not been completed. Genetic Algorithm of Meta-Scheduling When the meta-scheduler has at its level a list of user tasks and a list of available virtual machines that can perform the tasks, it determines the priorities of these tasks and then arranges in ascending or descending order. Virtual machines, too, are classified by the power of execution of the tasks in the delay. The initialization of the genetic algorithm can be done under priority constraint, type of virtual machine by task and feasibility (deadline). Initial Population Initial population (Tasks reach to the VM) is generated Figure 4: The IAAS system model (Song et al., 2014) Figure 6: Architecture Each server is symbolized by a hypervisor in the Cloud. This hypervisor controls and keeps information about the execution of several virtual machines installed on it. Cloud users frequently use these virtual machines to perform their tasks. While performing these tasks, free time slots can be observed on some virtual machines that can be exploited for performing other tasks of cloud clients. The meta-scheduler will have this responsibility to collect the tasks from the cloud clients, redirect them to the best virtualized resource sites (virtual machines) with free time slots through a hypervisor. Figure 5: Server machine(Song et al., 2014) Detailed Architecture The detailed architecture consists of several entities that describe the different components of the overall system. Pa ge 15 https://journals.e-palli.com/home/index.php/ajsts Am. J. Smart. Technol. Solutions 2(2) 10-20, 2023 randomly. In the task scheduling problem, a chromosome represents a likely solution. This chromosome is encoded by a real number. The length of a chromosome is equal to the number of tasks. The value of the gene represents to which virtual machine the task is allocated. A task is characterized by the waiting time (ati), size or length (li), deadline (di). The priority tasks that have arrived for processing are arranged in a queue through the priority function given by the following formula: (1/(di-ati-li)*1/(ati+1)) (1) The available virtual machines are arranged in a queue in a decreasing manner in terms of power. Our coding is as follows: Each Ti task is assigned to an available VMj virtual ma- chine of the IaaS cloud. Suppose we have n number of tasks (Tn) and 3 virtual machines available. An example of a solution is shown in the figure. Min(Max(Tj))=Min(Max(∑m (i=1)Tij)) (3) Tij represents corresponding execution time. Selection After having evaluated each individual or chromosome of the population, it will be necessary to select those which will undergo the operators of crossing and mutation. Here, we will use the elistic selection. It consists in choosing or retaining the best individuals for the next generation. We will select the best chromosomes with small Makespan. Crossover In order to produce new chromosomes from the parent chromosomes, we will use the crossover operator and more precisely the single-point crossover. Mutation Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next. All the new individuals obtained after the crossover must undergo the operation of mutation. Each genome of the chromosome must be randomly swapped respecting the virtual machine numbers. If we have for example two virtual machines, this mutation operator takes the chosen genome and inverts the bits (i.e. if the genome bit is 1, it is changed to 0 and vice versa). Evaluation Function After the mutation process, we will reevaluate the new population obtained. It is enough to use the objective function to evaluate the new individuals in order to choose the best ones. Termination Condition Genetic Algorithm gets terminated after user specified number of generations. We generated 20 evolutions of genetic algorithm to get the better results. The pseudo code of our genetic algorithm is shown in Algorithm 1. Simulation Results and Analysis In order to obtain the results of the proposed algorithm, a simulation was performed using the Python3 simulator under Windows 10 OS with Core i3 3.90GHz processor, 500GB hard drive and hard disk and 4GB of RAM. Python is a powerful and easy to learn programming language. It has high-level data structures and allows for a simple but effective approach to object-oriented programming. Because of its elegant syntax, dynamic typing, and interpretability, Python is an ideal language for scripting and rapid application development in many areas and on most platforms. In this work, we perform the meta-scheduling of independent tasks and the best scheduling algorithm will be the one that optimizes some resource utilization loads. The goal of this algorithm is to satisfy the user in terms Figure 7: Representation of a solution Figure 8: Simplified representation of a solution A simplified representation of a solution is given in the following figure: This literally translates into: task T1 is assigned to virtual machine 3, T2 is assigned to virtual machine 2, etc. We form as many chromosomes considered as probable solutions to the problem. A valid solution must meet the following conditions: -Each mapping between the task and a virtual machine in the solution must respect: Tij