Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Task scheduling algorithm, which is an NP-completeness problem, plays a key role in cloud computing systems. In this paper, we propose an optimized algorithm based on genetic algorithm to schedule independent and divisible tasks adapting to different computation and memory requirements. We prompt the algorithm in heterogeneous systems, where resources (including CPUs) are of computational and communication heterogeneity. Dynamic scheduling is also in consideration. Though GA is designed to solve combinatorial optimization problem, it's inefficient for global optimization. So we conclude with further researches in optimized genetic algorithm. <s> BIB001 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Scheduling is a very important part of the cloud computing system. This paper introduces an optimized algorithm for task scheduling based on genetic simulated annealing algorithm in cloud computing and its implementation. Algorithm considers the QOS requirements of different type tasks, the QOS parameters are dealt with dimensionless. The algorithm efficiently completes tasks scheduling in the cloud computing environment computing. <s> BIB002 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Cloud computing environments facilitate applications by providing virtualized resources that can be provisioned dynamically. However, users are charged on a pay-per-use basis. User applications may incur large data retrieval and execution costs when they are scheduled taking into account only the ‘execution time’. In addition to optimizing execution time, the cost arising from data transfers between resources as well as execution costs must also be taken into account. In this paper, we present a particle swarm optimization (PSO) based heuristic to schedule applications to cloud resources that takes into account both computation cost and data transmission cost. We experiment with a workflow application by varying its computation and communication costs. We compare the cost savings when using PSO and existing ‘Best Resource Selection’ (BRS) algorithm. Our results show that PSO can achieve: a) as much as 3 times cost savings as compared to BRS, and b) good distribution of workload onto resources. <s> BIB003 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> The scheduling of workflow applications involves the mapping of individual workflow tasks to computational resources, based on a range of functional and non-functional quality of service requirements. Workflow applications such as scientific workflows often require extensive computational processing and generate significant amounts of experimental data. The emergence of cloud computing has introduced a utility-type market model, where computational resources of varying capacities can be procured on demand, in a pay-per-use fashion. In workflow based applications dependencies exist amongst tasks which requires the generation of schedules in accordance with defined precedence constraints. These constraints pose a difficult planning problem, where tasks must be scheduled for execution only once all their parent tasks have completed. In general the two most important objectives of workflow schedulers are the minimisation of both cost and make span. The cost of workflow execution consists of both computational costs incurred from processing individual tasks, and data transmission costs. With scientific workflows potentially large amounts of data must be transferred between compute and storage sites. This paper proposes a novel cloud workflow scheduling approach which employs a Markov Decision Process to optimally guide the workflow execution process depending on environmental state. In addition the system employs a genetic algorithm to evolve workflow schedules. The overall architecture is presented, and initial results indicate the potential of this approach for developing viable workflow schedules on the Cloud. <s> BIB004 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Scheduling is a critical problem in Cloud computing, because a cloud provider has to serve many users in Cloud computing system. So scheduling is the major issue in establishing Cloud computing systems. A good scheduling technique also helps in proper and efficient utilization of the resources. Many scheduling techniques have been developed by the researchers like GA (Genetic Algorithm), PSO (Particle Swarm Optimizati on), Min-Min, Max-Min, X-Sufferage etc. Thi s paper proposes a new scheduling algorithm which is an i mproved version of Genetic Algorithm. In the proposed scheduling algorithm the Min-Min and Max-Min scheduling methods are merged in standard Genetic Algorit hm. Min-Min, Max-Mi n and Genetic Scheduling techniques are discussed and in the last the performance of t he standard Genetic Algorithm and proposed improved Genetic Algorithm is compared and is shown by graphs. <s> BIB005 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> With the increase in deployment of scientific application on public and private clouds, the allocation of workflow tasks to specific cloud instances to reduce runtime and cost has emerged as an important challenge. The allocation of scientific workflows on public clouds can be described through a variety of perspectives and parameters and has been proved to be NP-complete. This paper presents an optimization framework for task allocation on public clouds. We present a solution that considers important parameters such as workflow runtime, communication overhead, and overall execution cost. Our multi-objective optimization framework builds on a simple and extensible cost model and uses a heuristic to determine the optimal number of cloud instances to be used. Using the Amazon Elastic Compute Cloud (EC2) and Amazon Simple Storage Service (S3) as an example, we show how our optimization heuristics lead to significantly better strategies than other state-of-the-art approaches. Specifically, our single-objective optimization is slightly better than a simple heuristic and a particle swarm optimization approach for small workflows, and achieves significant improvements for larger workflows. In a similar manner, our multi-objective optimization obtains similar results to our single-objective optimization for small-size workflows, and achieves up to 80% improvement for large-size workflows. <s> BIB006 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Cloud computing has emerged as a powerful computing paradigm that enables users to access computing services anywhere on demand. It provides a flexible way to implement computation-intensive workflow applications on a pay-per-use basis. Since users are more concerned on the satisfaction of Quality of Service (QoS) in cloud systems, the cloud workflow scheduling problem that addresses different QoS requirements of users has become an important and challenging problem for workflow management in cloud computing. In this paper, we tackle a cloud workflow scheduling problem which enables users to define various QoS constraints like the deadline constraint, the budget constraint, and the reliability constraint. It also enables users to specify one preferred QoS parameter as the optimization objective. A set-based PSO (S-PSO) approach is proposed for this scheduling problem. As the allocation of service instances can be regarded as the selection problem from a set of service instances, it is found the set-based representation scheme in S-PSO is natural for the considered problem. In addition, the S-PSO provides an effective way to take advantage of problem-based heuristics to further accelerate search. We define penalty-based fitness functions to address the multiple QoS constraints and integrate the S-PSO with seven heuristics. A discrete version of the comprehensive learning PSO (CLPSO) algorithm based on the S-PSO method is implemented. Experimental results show that the proposed approach is very competitive especially on the instances with tight QoS constraints. <s> BIB007 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> In cloud computing systems, a lot of tasks and data need to deal with. However, processing these tasks and data need resources, which distribute in different position all over the world. To more effectively processing it, finding the optimal data placement makes the processing cost and the transforming time minimum. In this paper, we formulate a model for data placement in cloud computing, propose a particle swarm algorithm, compare and analyze particle swarm algorithm with crossover, mutation and local search algorithm based on particle swarm. The experimental results show our algorithm is more effective, efficient and suited for cloud computing. <s> BIB008 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Use genetic algorithm for task allocation and scheduling has get more and more scholars' attention. How to reasonable use of computing resources make the total and average time of complete the task shorter and cost smaller is an important issue. The paper presents a genetic algorithm consider total task completion time, average task completion time and cost constraint. Compared with algorithm that only consider cost constraint (CGA) and adaptive algorithm that only consider total task completion time by the simulation experiment. Experimental results show that this algorithm is a more effective task scheduling algorithm in the cloud computing environment. <s> BIB009 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Traditional multiobjective evolutionary algorithms (MOEAs) consider multiple objectives as a whole when solving multiobjective optimization problems (MOPs). However, this consideration may cause difficulty to assign fitness to individuals because different objectives often conflict with each other. In order to avoid this difficulty, this paper proposes a novel coevolutionary technique named multiple populations for multiple objectives (MPMO) when developing MOEAs. The novelty of MPMO is that it provides a simple and straightforward way to solve MOPs by letting each population correspond with only one objective. This way, the fitness assignment problem can be addressed because the individuals' fitness in each population can be assigned by the corresponding objective. MPMO is a general technique that each population can use existing optimization algorithms. In this paper, particle swarm optimization (PSO) is adopted for each population, and coevolutionary multiswarm PSO (CMPSO) is developed based on the MPMO technique. Furthermore, CMPSO is novel and effective by using an external shared archive for different populations to exchange search information and by using two novel designs to enhance the performance. One design is to modify the velocity update equation to use the search information found by different populations to approximate the whole Pareto front (PF) fast. The other design is to use an elitist learning strategy for the archive update to bring in diversity to avoid local PFs. CMPSO is comprehensively tested on different sets of benchmark problems with different characteristics and is compared with some state-of-the-art algorithms. The results show that CMPSO has superior performance in solving these different sets of MOPs. <s> BIB010 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Cloud computing is the latest distributed computing paradigm and it offers tremendous opportunities to solve large-scale scientific problems. However, it presents various challenges that need to be addressed in order to be efficiently utilized for workflow applications. Although the workflow scheduling problem has been widely studied, there are very few initiatives tailored for cloud environments. Furthermore, the existing works fail to either meet the user's quality of service (QoS) requirements or to incorporate some basic principles of cloud computing such as the elasticity and heterogeneity of the computing resources. This paper proposes a resource provisioning and scheduling strategy for scientific workflows on Infrastructure as a Service (IaaS) clouds. We present an algorithm based on the meta-heuristic optimization technique, particle swarm optimization (PSO), which aims to minimize the overall workflow execution cost while meeting deadline constraints. Our heuristic is evaluated using CloudSim and various well-known scientific workflows of different sizes. The results show that our approach performs better than the current state-of-the-art algorithms. <s> BIB011 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Cloud computing resources scheduling is significant for executing the workflows in cloud platform because it relates to both the execution time and execution cost. In order to take both the time and cost into consideration, Rodriguez and Buyya have proposed a cost-minimization and deadline-constrained workflow scheduling model on cloud computing. Their model has great applicability but the solution of their particle swarm optimization (PSO) approach is not good enough and cannot meet a tight deadline condition. In this paper, we propose a genetic algorithm (GA) approach to solve this model. In order to tackle with the tight deadline condition, a dynamic objective strategy is further proposed to let GA focus on optimize the execution time objective to meet the deadline constraint when the feasible solution hasn't been obtained. After obtaining a feasible solution, the GA focuses on optimizing the execution cost within the deadline constraint. Therefore, the proposed dynamic objective GA (DOGA) has adaptive ability to the search environment to different objectives. We have conduct extensive experiments based on workflows with different scales and different cloud resources. Experimental results show that DOGA can find better solution with smaller cost than PSO does on different scheduling scales and different deadline conditions. DOGA approach is more applicable to be used in commercial activities. <s> BIB012 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Cloud computing offers unprecedented capacity to execute large-scale workflows in the “era of big data”. In 2014, a cost-minimization and deadline-constrained workflow scheduling (CMDCWS) model is firstly proposed by Rodriguez and Buyya, which is applicable for the business need of cloud computing that a workflow task should be finished by minimizing the execute cost within a deadline constraint. As scheduling cloud computing resources for workflow is an NP-hard problem, Rodriguez and Buyya proposed to use particle swarm optimization (PSO) to solve the CMDCWS problem. In traditional PSO for CMDCWS, each dimension in the particle position stands for each task and the value of the corresponding dimension stands for the index of the cloud resource that executes this task. However, this may have drawback because the value of each dimension does not relate to the resource characteristic but is only a meaningless index number. Therefore the learning behaviors among the particles do not make sense because learning from index number may not lead to better position. In this paper, we present a resource renumber strategy to encode the particle position and design a renumber PSO (RNPSO) for CMDCWS. In RNPSO, all the resources are re-ordered and re-numbered according to their computational ability, i.e., the cost per unit time. By this, the values of particle position can make sense and the positions difference between the well-performed and poorly-performed particles can guide poorly-performed particle to promising region. We conduct experiments on test cases with small, middle, and large scales to compare the performance of PSO and RNPSO. The results show that the resource renumber strategy is promising for enhancing the PSO performance. <s> BIB013 </s> Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches <s> Scheduling for User QoS <s> Resources scheduling is a significant research topic in cloud computing, which is often modeled as a cost-minimization and deadline-constrained workflow scheduling model. This is a constrained single objective problem that to minimize the overall workflow execution cost while meeting deadline constraints. In this paper, we offer a new horizon to convert this single-objective problem to a multi-objective problem and present coevolutionary multiswarm particle swarm optimization (CMPSO) to find the non-dominated solutions with different execute cost and time. Meanwhile, the renumber strategy is adopted in CMPSO to make the learning efficient. CMPSO is compared with a renumber PSO (RNPSO) by setting the execute time in the CMPSO's non-dominated solutions as the deadline constraint of RNPSO. Results show that CMPSO not only offers many non-dominated solutions with different prices and execute time, but also obtains better solution than RNPSO under a same deadline. <s> BIB014
In this subcategory of work, the utilization objective is user QoS, including (i) the makespan, (ii) user costs, (iii) application performance, and (iv) reliability. Early in 2009, BIB001 proposed the use of a GA scheduler to schedule independent and divisible tasks in a cloud computing environment, with makespan as the objective. As M tasks being scheduled on N cloud resources, a very simple chromosome is shown in Figure 4 , with its length the same as the number of the tasks. , representing the index of the resource, indicating that the ith task T i is scheduled on the jth resource R j . Therefore, the GA is used in a very straightforward way and the chromosome coding scheme is typical for scheduling resources. Such a chromosome coding scheme was also later used by BIB005 , BIB002 , and BIB009 . In particular, Kumar and Verm [2012] optimized the makespan by combining a GA with Min-Min and Max-Min strategies to improve population initialization and the GA speed. To enhance the global search capability, BIB002 combined simulated annealing with the GA to schedule cloud resources. In their study, not only the makespan was considered, but also were the bandwidth, costs, distances, and reliability. They were combined together with the makespan to form a composite objective function. BIB009 also scheduled cloud resources with the encoding scheme of Figure 4 . They asserted that their GA approach, which considered the total makespan, the average makespan, and the user cost together, was more effective and useful in the cloud computing environment. Further from independent tasks, tasks on cloud resources can be scheduled with a desired execution order. For example, in the study by BIB004 , the tasks have an order and become workflows. Therefore, besides similarity to the coding of Figure 4 , the orders of the genes are also considered in the chromosome. Not only does the value of each gene (indicating which resource hosts the task), but also do the orders of all the genes (indicating the executing order) need to be optimized. The objective function is a combination of the makespan and the user cost.  also scheduled the cloud resources with a GA-based approach by matching the task to the virtual resources and scheduling the execution order of the tasks. In matching the task to the virtual resources, they considered both the VM and the database, as well as the network resources. Therefore, extending from the encoding scheme of Figure 4 , each GA gene in the chromosome is coded as a three-dimensional structure with the VM index, database index, and network index. BIB012 proposed using dynamic objective strategy to take the makespan as the objective first in order to meet the user deadline constraint, and then to take the cost as the objective to optimize the user benefit. In addition to optimization for a single or composite objective, multiobjective EC algorithms have also been applied to cloud resource scheduling. For example, BIB006 scheduled resources via a workflow and thus scheduled both VM match and execution orders. They also considered makespan and user costs as two objectives and used the popular NSGA-II multiobjective optimization algorithm to solve this problem. A general framework of using ACO to schedule user tasks is illustrated in Figure 6 , where each ant uses M steps to construct a solution. In the ith step to schedule the ith task T i , the ant uses pheromone and heuristic information to choose the suitable resource R j . After M steps, all the M tasks have been scheduled on different resources. In this context,  and have scheduled the M tasks one by one to the cloud resources, using the scheme in Figure 6 , because at each step the task can be scheduled on any resource of a resource set. The pheromone update scheme was modified according to different time slots of cloud service in  and the heuristic information based on the user's QoS on user cost, system reliability, response, or security was used to guide the ant to select the optimal resource in . also used an ACO-based approach to schedule cloud resource by considering makespan, user cost, network bandwidth, and system reliability. The tasks were first classified into different categories according to different QoS metrics, and then tasks in different categories were bound to the cloud resources via the ACO optimization. In addition to GA and ACO algorithms, PSO is also reported in the literature as an effective tool to have scheduled cloud resources successfully. As PSO offers generally faster convergence than other EC algorithms, many researchers have studied scheduling cloud resources by PSO. In the study by Pandey et al. to use PSO for cloud resources scheduling BIB003 , the particle was encoded similarly to the scheme of Figure 4 used in a GA. The particle position length is the same as the task number and the value of each dimension is an integer to indicate the cloud resource that executes the corresponding task. Their approach takes the user cost as the optimization objective, considering both the data transmission cost and computational cost. However, as the velocity update and position update in PSO will make the updated value of each dimension in the position not remain an integer, how to deal with the noninteger issue is not clearly stated in their method. In order to make PSO suitable for the cloud resource scheduling model, which is a discrete optimization problem, and BIB007 extended the continuous PSO to discrete PSO. Their methods are similar in that the set-based mechanism is used. The particle position consists of a set of <task_id, resource_id> pairs. Moreover, the velocity and position updating are modified accordingly to match the code scheme. For the optimization objective, optimized the user cost by combining the data transmission cost and computational cost, while Chen and Zhang [2012] optimized the user QoS such as makespan, user cost, and reliability separately. Further extending PSO to the discrete cloud resource scheduling, some other strategies are also proposed. BIB008 adopted a small position value rule by sorting all the dimensions in the position according to the real value and giving each dimension an integer-value rank number. This was to transform real-value position to integervalue position, and then to map the integer value to the cloud resource index. In the study, BIB008 combined the data transmitting time and user cost to form a single objective. In the study of BIB011 , they rounded the real number to integer number to indicate the resource index that the workflow was scheduled on. However, the index of the resource in fact does not reflect the features of the resources. Therefore, learning from the resources index might make the particles fly randomly. In order to make the guidance more efficient, BIB013 proposed a renumber strategy to use the metric of price per unit time to reorder the resources. This way, the learning among particles via resource index becomes much more clear and reasonable. Later, BIB014 further extended their work to a multiobjective scheduling model and proposed using coevolutionary multiswarm PSO BIB010 ] to solve the problem. To further compare features and strengths of the previous scheduling approaches, research progress in this field so far is mapped out in Figure 7 . It shows how research starts from the simple GA, to "algorithm enhancement," "objective extension," and "model formulation." Relationships of developments from the GA to ACO and to PSO are also mapped out. Moreover, the objectives, general comments on strengths, limitations, and experimental environments, scales, and results of these algorithms are listed and compared in Table II .