8.2.1 Cloud Resources

Resources are any physical or virtual components with limited availability in a computer system. There are two types of resources: logical and physical [11]. This section presents the definitions of the main types of resources in a cloud system.

8.2.2 Resource Utilization

Considering the continued growth in cloud computing and that resource utilization directly impacts costs, resource management techniques enable cloud providers to consolidate workloads to achieve optimal resource utilization while adhering to SLAs at minimum cost [13]. If X is the total hardware capacity of the server, and Y is the current hardware capacity used, then:

• the workload is under‐utilized if
• the workload is over‐utilized if
• resource utilization is optimal when X ≈ Y.

8.2.3 Cloud Middleware and Components

This section presents the main middleware and components of a cloud cluster.

8.2.4 Jobs and Tasks

A job is generated by users and given to schedulers to be executed by processing nodes. Each job is made of many dependent tasks known as a directed acyclic graph (DAG). DAGs contain specific characteristics about the tasks, such as execution time, the number of required processors, and so on. Execution time governs the seconds needed for the task to be completed using the slowest CPU in the system. Note that the actual execution time for a task can be significantly decreased if it is allocated to a faster CPU. The number of processors determines the degree of parallelism of a task [4].

In a DAG, jobs are represented as different shapes, which correlate to the various classes of operations. The specifications for these representations include width, height, number of processors, time to execute, shape, and a list of the data files needed. The width is the highest number of tasks able to run concurrently within a job. The height is the number of stages or levels in a job. The number of processors is the largest number of processors needed by any one task in the job. The time to execute specifies the lowest amount of time a job can be run on the slowest CPU in the system. Lastly, the list of required data files contains the files a CPU must download prior to executing the job. The actual data required to execute individual tasks is provided either via: (i) previously existing data files listed as required data files; and/or (ii) the output of the task's immediate predecessors in the DAG. These predecessors could either be local files, temporary files, or inter‐processing messages. Job shapes can be series‐parallel, homogeneous‐parallel, heterogeneous‐parallel, and single‐task. Figure 8.3 illustrates the different job shapes [4].

8.2.5 Virtual Cluster

A virtual cluster is a collection of VMs configured in a way that makes them act as though they were a traditional high‐performance computing (HPC) cluster. This usually involves installing and configuring job management software, which includes a batch scheduler and a shared storage system (e.g. a network/distributed file system) [16].

8.2.6 Multi‐Objective Task Scheduling

A multi‐objective optimization problem (MOOP) is a problem that has several conflicting objectives that need to be optimized simultaneously:

where x ∈ X and X is the decision space.

The objectives in a MOOP often conflict with one another. Hence, Pareto dominance is used to perform a comparison between the suggested solutions as follows:

For u, v ∈ X, u dominates v if and only if,

If solution x* is not dominated by any other solution, then it is considered Pareto optimal. The term “Pareto front” describes the set containing every Pareto optimal solution within the objective space [2].

In this study, most of the reviewed papers considered task scheduling as a MOOP that optimizes some of the conflicting objectives, e.g. service cost, power consumption, makespan, response time, flow time, execution time, data/task transfer time, task queue length, and resource utilization.

8.4.1 Particle Swarm Optimization

Guo et al. [18] proposed a multi‐objective task scheduling model to lessen task execution time and the cost of using the PSO algorithm. Zhan and Huo [19] developed “Improved PSO” (IPSO) by combining PSO and simulated annealing (SA). They leveraged SA's fast convergence time in each iteration of PSO to: increase the convergence rate; improve the efficiency of the scheduling algorithm; and prevent PSO from falling into a local optima. IPSO reduces the average task running time and increases the ratio of resource utilization compared to ACO, GA, and SA.

Taheri et al. [20] considered the data files required for jobs from public or private clouds and proposed a bi‐objective job scheduling optimization model using PSO (PSO‐ParFnt). Their approach minimizes job execution as well as data file transfer times. They also revised the generic version of PSO in order to create collections of targeted swarms as an alternative to a generic large swarm.

Netjinda et al. [21] developed a workflow scheduling algorithm, called PSO‐VNS, by combining PSO with a variable neighborhood search (VNS) technique where the VNS refines the global best from every iteration of PSO to improve fitness convergence. They showed that their method outperforms both greedy methods and infrastructure‐as‐a‐service (IaaS) cloud partial critical paths in reducing costs.

Ouyang et al. [22] proposed a green cloud task scheduling algorithm (GCTA) based on improved binary PSO (BPSO). This work avoids matrix operations (that represent the tasks assigned to VMs) by using a pipeline number for VMs and redefining the position and velocity of the particles. Their simulation results show that the GCTA requires less execution time and consumes fewer resources than sequential scheduling.

Ramezani et al. [23] proposed a PSO‐based task scheduling method to minimize task execution and transfer times. The method sits within their task‐based load balancing system, which balances the system load by only transferring extra tasks from an overloaded VM rather than migrating the entire overloaded VM.

Yang et al. [24] formulated trust relationships between tasks and resource sets coupled with a trust‐based scheduling algorithm (TBHSA) that relies on a set‐based PSO (S‐PSO) method to select a trustworthy computation service. A set covering problem (SCP) tree search method selects the storage services. These authors show that TBHSA performs better than both PSO and ACO at reducing time and cost and enhancing security and reliability.

Ramezani et al. [3] consider four conflicting objectives, namely minimizing task transfer time, task execution cost, power consumption, and task queue length, to develop a comprehensive multi‐objective optimization model using PSO (MOPSO) for task scheduling. The model is essentially an extension to the PSO and GA algorithms to support these four objective functions. Its efficiency is compared against a multi‐objective GA (MOGA) using CloudSim. The results show that MOPSO is a faster and more accurate evolutionary algorithm than MOGA for solving such problems.

Alkhashai and Omara [25] proposed a new algorithm called BFPSOTS by combining Best‐Fit (BF), PSO, and the Tabu‐Search (TS) algorithms. They applied the BF algorithm to generate the initial population for the standard PSO algorithm rather than generating a random population. They also used the TS algorithm to improve PSO's local search. In an evaluation using CloudSim, the results show that BFPSOTS outperforms the standard PSO algorithm in reducing execution times for tasks, cost, and resource utilization.

Other studies focus on hybrid metaheuristic methods for task scheduling [26]. He et al. [27] combined PSO, ACO, and GA to create a more efficient task scheduling method. They improved the PSO algorithm by applying a random inertia weight to generate the initial scheduling results, then used the generated results of the IPSO as the initial pheromones for the ACO algorithm to find the optimal scheduling scheme. They also incorporated an elitist strategy and a crossover operator into the GA to improve the efficiency of the ACO algorithm. The final result is a combined algorithm that can reduce the total task makespan.

Jiang et al. (2016) combined the PSO and ACO algorithms to present a new scheduling algorithm that reduces the processing time and cost of the task. Based on their evaluation results, the combined algorithm is faster than PSO and ACO at generating the scheduling results.

Kamalinia and Ghaffari [26] combined PSO and GA to present a new heterogeneous earliest finish time (HEFT) algorithm, called PSO‐GA‐HEFT, to reduce makespans and enhance resource efficiency in comparison to HEFT_UpRank, HEFT_DownRank, HEFT_LevelRank, and the multiple priority queues and a memetic (MPQMA) algorithm.

Li et al. [28] applied PSO to propose a security and cost‐aware scheduling (SCAS) algorithm for heterogeneous tasks in scientific workflows in the cloud. The algorithm minimizes the execution cost of the total workflow while meeting a prescribed deadline and risk rate constraints.

Nirmala and Bhanu [29] proposed a metaheuristics algorithm called Catfish PSO (C‐PSO) that selects the best schedule with the least makespan and execution cost.

Shao [30] proposed a scheduling algorithm for tasks based on a PSO fission mechanism that splits the particles in an appropriate place to generate more kinds of particles so as to create diversity and, hence, avoid premature convergence of the swarm. They showed that this algorithm is faster than first in first out (FIFO) and PSO, and also solves the problem of premature convergence in PSO.

Xie et al. [31] proposed a scheduling algorithm based on PSO and the shuffled frog leaping algorithm (SFLA) that considers efficiency and trustworthiness in the cloud. The proposed algorithm avoids falling into a local optimum and outperforms GA and the TDMin‐Min algorithms.

Zhong et al. [32] combined PSO and a greedy algorithm, introducing a greedy PSO (G&PSO) algorithm that converges faster, has a stronger local and global search, and provides a better solution to balancing the workload between VMs.

Chen and Long [33] combined PSO with the ACO algorithm and incorporated parameter determination into the mix. The integrated algorithm can keep particles at a fitness level of a certain concentration. It guarantees diversity in the population, is faster, and performs better in fitting and cost than PSO.

Cui et al. [34] proposed a genetic algorithm based on a chaotic ant swarm (GA‐CAS) algorithm, in which four operators and natural selection are applied to solve a constrained multi‐objective task scheduling optimization problem that considers reliability, makespan, and flow time. They proved that GA‐CAS speeds up convergence and outperforms GA, ACO, and genetic simulated annealing (GSA), which is a hybrid heuristic algorithm comprising GA and a SA algorithm.

Gabi et al. [35] proposed an algorithm called orthogonal Taguchi‐based cat swarm optimization (OTB‐CSO) to minimize the makespan of tasks. OTB‐CSO outperforms minimum and maximum job first (Min‐Max), PSO with linear descending inertia weight (PSO‐LDIW) and a hybrid PSO with simulated annealing (HPSO‐SA) algorithms.

Gan et al. [36] introduced a niche PSO algorithm that overcomes the shortcomings of PSO in local optimization. It also improves convergence precision. The main objective of their model is to reduce execution time and cost.

Ramezani et al. [37] developed a further four‐objective PSO algorithm to embed in their bespoke multi‐objective load balancing (MO‐LB) system. This system avoids VM migration and balances the system load by transferring excessive workloads from a set of VMs allocated to an overloaded PM to other compatible VMs in the cluster with greater capacity. MO‐LB achieves better results in reducing response time, memory use, job makespan, power consumption and the time taken for the load balancing process than the VM migration technique in vMotion.

Sadhasivam and Thangaraj [38] developed a different variant of IPSO by updating the position and velocity of each iteration. This algorithm schedules applications to cloud resources while minimizing the total costs including the communication cost between resources, the task dependency cost values, and the execution cost of computer resources.

Yuan et al. [39] proposed simulated annealing PSO (SAPSO) and a temporal task scheduling model, embedded within their proposed profit maximization algorithm (PMA). This task scheduling model dynamically schedules all arriving tasks to be executed in private and public clouds based on the temporal variation of prices in hybrid clouds. They proved that the SAPSO algorithm outperforms PSO and greatly increases the throughput and the profit of a private cloud while guaranteeing the service delay bound. Yuan et al. [40] also proposed a temporal task scheduling algorithm (TTSA) by applying a hybrid SAPSO while modeling the cost as a mixed integer linear program in each iteration.

Ben Alla et al. [41] proposed two hybrid metaheuristic algorithms by combining dynamic dispatch queues (TSDQ) with PSO with fuzzy logic (TSDQ‐FLPSO) and combining TSDQ and PSO with simulated annealing (TSDQ‐SAPSO). They show that the TSDQ‐FLPSO algorithm performs better than PSO, SAPSO, and TSDQ‐SAPSO in reducing waiting times, queue length, makespan, and cost as well as optimizing resource utilization and load balancing.

Domanal and Reddy [42] considered VM loads to determine the local best and the global best particles in each iteration of PSO and proposed a modified PSO (MPSO) algorithm to schedule a bag of tasks to a set of VMs. The main goal of the model is efficient use of the cloud's resources (VMs, CPU, and memory) while optimizing the execution cost of the tasks. MOPSO outperforms round robin, first‐come‐first‐served (FCFS), ACO, and GA in executing the bag of tasks in heterogeneous cloud environments in terms of QoS parameters including reliability, time, and cost.

Guo et al. [43] developed an adaptive discrete PSO strategy with genetic algorithm operators (ADPSOGA) for scientific workflow scheduling. ADPSOGA is a PSO‐based method that also adopts the randomly two‐point crossover operator and the randomly single point mutation operator in GA. They considered minimizing the cost of execution and data transfer while meeting workflow deadlines. The performance of ADPSOGA was evaluated against multi‐cloud partial critical paths with pretreatment (MCPCPP), workflow scheduling with PSO (WPSO), and PSO with GA operators (PSOGA).

Midya et al. [44] proposed a hybrid adaptive PSO (HAPSO) algorithm, which is a combination of GA and PSO to optimize resource allocation and task scheduling for task requests arriving from on road users. They showed that HAPSO converges faster than PSO and self‐adaptive PSO in reducing the mean square error, task response time, and energy consumption.

A comparison study on the performance evaluation of PSO and GA on workflow scheduling was conducted by Shishido et al. [45] using a security and cost‐aware workflow scheduling algorithm. Their findings indicated that GA‐based algorithms significantly outperform PSO in terms of both cost‐effectiveness and response time.

Tong et al. [46] proposed a heuristic algorithm called hybrid biogeography‐based optimization (BBO) algorithm, which integrates a migration strategy into PSO. In their method, the flight strategy under the BBO migration structure is hybridized to accelerate search speeds, and HEFT_D is used to evaluate the task sequence. The objective function was makespan, and the experiments show that, compared to several classical heuristic algorithms, the new hybrid migrating BBO has the advantage in terms of global search ability, fast convergence rates, and high‐quality solutions.

Yuan et al. [47] developed a time‐aware task scheduling algorithm that considers temporal variations and schedules all admitted tasks that meet the delay bounds. In each iteration, their algorithm solves the formulated profit maximization problem with a hybrid chaotic PSO based on SA. Compared to several other scheduling algorithms, the model increases profit and throughput without violating the delay constraints of all admitted tasks. Subsequently, they used a hybrid optimization algorithm called GSA‐based PSO [47]. In the hybrid model, the genetic operators in GA increase the diversity of particles and the efficiency of global searches.

Dordaie and Navimipour [48] combined PSO with the hill climbing algorithm to optimize the scheduling workflow makespan. The algorithm initializes the population randomly using PSO. Each particle is then evaluated and ranked with makespan by HEFT processor mapping method and the hill climbing algorithm is finally applied to some selected particles. The proposed algorithm is repeated until the termination condition is satisfied.

Table 8.1 summarizes the PSO‐based methods and reports the implemented improvements, objective functions, algorithms outperformed, and evaluation tool.

8.4.2 Genetic Algorithms

Tayal [51] presented a fuzzy GA‐based optimization approach for improving the accuracy of GA's results with job scheduling. Scheduling decisions are made via the evaluation of the entire group of tasks in the job queue. Juhnke et al. [52] presented a multi‐objective scheduling algorithm intended for cloud‐based workflow applications to lessen costs and execution times by implementing a type of GA called the Pareto archived evolution strategy.

Jang et al. [53] used GA to minimize task execution times resulting in improved user satisfaction and an increase in profit for the service providers.

Wang et al. [54] performed research into reducing energy consumption in data centers and developed an improved version of GA with designed genetic operators and practical encoding/decoding methods. A local search operator was introduced with the goal of accelerating their algorithm's convergence speed.

Hu et al. [55] considered task waiting and execution times. They improved GA (IGA) with double fitness functions for genetic manipulation to reduce the probability of mutation in the early stages.

Ghorbannia Delavar and Aryan [56] developed a GA hybrid aimed at workflow scheduling that considers task priorities. The BF and round‐robin methods were merged to create an optimal initial population to ensure an ideal solution is found swiftly.

In another study on workflow scheduling, Verma and Kaushal [57] developed a deadline‐constrained GA in which the priority of each workflow task is assigned at the bottom level. These priorities are then used to create the initial population. The first individual of the initial population is created by allocating tasks to the available machines according to their level in ascending order. The remaining individuals are created by randomly assigning the tasks to available machines.

Wang et al. [58] proposed an integer bi‐level programming model to minimize power consumption. They formulated the problem as two upper‐level objective functions: (i) minimizing energy inefficiencies in the data center servers by reducing variances in each server's resource utilization; and (ii) maximizing the data locality ratio. A local search operator was used to accelerates convergence.

Hassan et al. [59] combined GA with list scheduling and earliest completion time (ECT) to develop a GA‐based task scheduling algorithm that outperforms GA in minimizing makespan.

Hung et al. [60] presented a cost–time aware genetic scheduling algorithm (CTaG) that optimizes bandwidth and costs over the cloud system.

Mahmoud et al. [61] developed a two‐phase GA‐based job scheduling model that determines the shortest job completion time with Min‐Min, Max‐Min, and suffrage techniques. The optimal job scheduling among resources is determined by the GA.

Shojafar et al. [62] presented a hybrid approach called FUGE that is based on fuzzy theory and a GA with the objective of optimizing load balancing considering execution time and cost while taking processing speeds, memory, VM bandwidth, and job length into account. They show the efficiency of the FUGE approach in terms of execution time, execution cost, and the average degree of imbalance compared to ACO and the multiple ACO (MACO) algorithms.

He et al. [27] combined PSO, ACO, and the crossover operator from GA to improve ACO. The experimental results show reduced total task completion time.

Kamalinia and Ghaffari [26] aimed to reduce makespans with the HEFT algorithm in combination with the PSO and GA algorithms. The results of the simulation show improved average makespans over traditional GA.

Peng et al. [63] proposed an improved version of niched Pareto GA (NPGA). Results of this algorithm show an improvement in task scheduling over the classical NPGA without compromising time consumption or cost.

Wang et al. [64] developed a new bi‐level GA. The results from various consumption tests show significant improvements in the energy efficiency of servers.

Abdulhamid and Latiff [65] presented a checkpointed league championship algorithm (CPLCA) with an emphasis on secure fault tolerance responsiveness. Simulations show an improvement in total average makespan, and total average response times compared to ACO, GA, and the basic LCA.

Anastasi et al. [66] proposed QBROKAGE which is a genetic approach to cloud brokering. This approach considered costs while satisfying the QoS requirements of cloud applications.

Chirkin et al. [67] aimed to provide a solution for estimating makespans. They also integrated the solution into the earlier‐developed scheduling algorithm GAHEFT, which is a hybrid algorithm based on a combination of the GA and the HEFT algorithm. Comparison tests with the Min‐Min algorithm show that GAHEFT performs better.

Cui et al. [34] proposed a chaotic ant swarm algorithm (GA‐CAS), which is GA‐based. It has the objective of optimizing reliability, makespan, and flow time. Results from simulations demonstrate GA‐CAS typically increases the speed of convergence and outperforms GA, GSA, and ACO in its objectives.

Kamalinia and Ghaffari [68] presented a hybrid metaheuristic method using HEFT algorithm. Testing shows a significant effect on improving the optimization of makespans and improving resource efficiency when compared to a GA and a differential evolution (DE) algorithm.

Shen et al. [69] proposed a genetic algorithm called E‐PAGA with the aim of achieving adaptive regulations for different requirements of energy and performance. When compared to artificial fish swarm optimization (AFSA), FCFS, and the modified best‐fit descending algorithm (MBFD), E‐PAGA had the lowest energy consumption and makespan.

Sreenu and Malempati [70] proposed the modified fractional gray wolf optimizer for multi‐objective task scheduling (MFGMTS), which aims to optimize execution time, execution cost, communication time, communication cost, energy consumption, and resource utilization. Simulation results when compared to PSO, GA, grey wolf optimizer (GWO), and the fractional grey wolf optimizer (FGWO) show MFGMTS as performing better across all measures.

Wei [71] proposed bidirectional optimization GA (BOGA) with the aim of optimizing completion time and cost and simulated the algorithm on CloudSim.

Yao et al. [72] proposed an IGA with a three‐stage selection method and a total‐division‐total genetic strategy. The algorithm improves selection and crossover operations. Using CloudSim, the results show that IGA outperforms the simple GA (SGA) in terms of completion time.

Keshanchi et al. [73] optimized task scheduling via an IGA, called N‐GA, that uses GA along with a heuristic‐based HEFT search to assign subtasks to processors. A one‐point crossover operator is used to avoid violating the precedence constraints. They also apply an elitism technique with unusual selections to avoid premature convergence. Their model outperformed three well‐known heuristics algorithms including HEFT‐B, HEFT‐L, and HEFT‐T, in reducing the total execution times and makespan.

Basu et al. [74] combined a GA with ACO to form GAACO where only the fittest task combination survives each stage. This approach was specifically designed for task scheduling and load balancing in the Internet of Things (IoT) applications. Task dependencies are considered with the aim of minimizing the total execution time (makespan) of the tasks. GAACO provides superior performance over GA and ACO alone in heterogeneous multiprocessor environments.

Casas et al. [75] developed a variant of a GA called efficient tune‐in of resources (GA‐ETI) that analyzes applications prior to execution. The characteristics studied are available computing resources, multiple scheduling configurations, and selecting optimal configurations to execute workflows. GA‐ETI adapts the conventional crossover and swap mutation from the classical GA and also includes a modified crossover and new increment and decrement mutation operators. GA‐ETI distinguishes itself from other schedulers for its adaptability to the size of jobs and the VMs. It contains a non‐monetary cost model and considers complex interdependencies between tasks. Tested in a VMware‐vSphere private cloud without increasing costs, GA‐ETI performed well with an 11–85% reduction in makespan when executing workflows.

Zhang et al. [76] proposed a new task scheduling algorithm called RC‐GA (a genetic algorithm for task scheduling based on a resource crowd‐funding model). The idea of this model is that idle resources are collected to form a virtual resource pool that can provide cloud services. Its goal is to increase task execution stability and reduce power consumption. It improves upon GA's roulette wheel selection operator, which in turn causes a reduction in random errors during the evolution process. Experiments show RC‐GA is better than non‐dominated sorting genetic algorithm (NSGA‐II) at increasing stability and reducing power consumption. Thus, the convergence speed of RC‐GA is faster than classical GA.

Singh [77] proposed a hybrid model called HGVP that involves a GA, VNS, and PSO. HGVP is an improvement over PSO in selecting the initial amounts of particles and in stabilizing non‐local searches and local utilization within one evolutionary processing period. Simulation results in Matlab show that HGVP outperforms current techniques with a focus on energy consumption compared to the PSO scheduling technique SPSO‐SA and to SLPSO‐SA.

Sathya Sofia and GaneshKumar [78] claim that reducing energy consumption in cloud service environments increases makespan, which results in customer dissatisfaction. To provide a non‐domination solution for these conflicting aims, they proposed the NSGA‐II to perform multi‐objective optimization. The results of a comparison test between NSGA‐II with and without an artificial neural network (ANN) show that incorporating an ANN decreases both makespan and energy consumption.

Aziza and Krichen [79] developed a scheduling decision support system based on a GA with two objective functions – makespan and cost. The algorithm was implemented in CloudSim.

Given there can be a very large amount of tasks in real clouds, Duan et al. [80] developed a single objective makespan‐based method. It relies on incremental GA, which has adaptive probabilities for crossover and mutation. The mutation and crossover rates vary conferring to generations and also between individuals. For the sake of evaluation, they randomly generated a large number of tasks based on the instance types in Amazon EC2 and implemented VMs with different computing capacities on CloudSim. The model performs better than the classical GA, Min‐Min, Max‐Min, SA, and artificial bee colony (ABC) at finding the optimal scheme.

The classical GA was used by Fernández‐Cerero et al. [81] for energy‐aware and time‐aware scheduling policies. The idea behind their model is to combine energy‐ and performance‐aware scheduling policies to hibernate idle VMs. Four strategies and their combinations were tested including: makespan‐centric scheduling, energy‐centric scheduling, makespan‐centric scheduling with a threshold, and energy‐centric scheduling with a threshold.

An adaptive GA was proposed by Ibrahim et al. [82] to be used in a dynamic task scheduling model based on an integer linear programming that satisfies an energy consumption objective. Their algorithm searches for an optimal (or near‐optimal) solution starting from an initial population of possible solutions (chromosomes) by selecting the fittest operators and the crossover and mutation reproduction operators. The chromosomes are encoded appropriately, and the crossover operator is specifically designed to suit the given problem. Additionally, the model is hybridized with a procedure that determines whether a chromosome (i.e. a possible solution) is feasible and, if not, the chromosome is penalized accordingly with a lower probability of selection (i.e. survival).

A hybrid GA‐PSO algorithm was proposed by Manasrah and Ali [83] to reduce makespans and cost, as well as balance the load of dependent tasks across heterogeneous resources. The idea behind this hybrid model is to distribute the number of iterations between the GA and PSO algorithms to reduce complexity.

Shishido et al. [45] compared the performance of GA and PSO for scientific workflow scheduling giving consideration to security and deadline constraints in a simulated environment. GA performed better than PSO.

Tang et al. [84] proposed a scheduling strategy aimed at industrial Internet of Things applications using a GA. The objective was to reduce energy consumption while taking task dependency, data transmission, and some constraint conditions into account, such as response time deadline and cost.

Taj and Basu [85] hybridized both GA and the group search optimization (GSO) algorithm into the genetic and group search optimization (GGSO) algorithm. This algorithm maximizes income for IaaS providers while simultaneously ensuring QoS for users. GGSO has several advantages over the GA and GSO algorithms such as faster convergence, and less computational time to the optimal solution. The results show it outperforms GSO, GA, and SLPSO algorithms at maximizing profit.

Table 8.2 summarizes the GA‐based methods and reports the implemented improvements, objective functions, algorithms outperformed, and evaluation tool.

8.4.3 Ant and Bee Colony Optimization

Early attempts to schedule cloud computing tasks using ACO were based on the work of Shi et al. [87], who tried to improve Hadoop architecture and workload balancing with respect to the cost matrix, hormone matrix, and probability matrix. According to their experiments, ACO improves both response time and throughput. Likewise, using conventional ACO, Mateos et al. [88] developed a scheduler for private clouds. Wu et al. [89] proposed a market‐oriented hierarchical scheduling strategy for cloud workflow systems, in which service level scheduling handles task‐to‐service assignments. Here, the tasks in individual workflow instances are mapped to cloud services in global cloud markets based on their functional and non‐functional QoS requirements. The task‐level scheduler optimizes task‐to‐VM assignments in local cloud data centers. Their analysis shows that service level scheduling with GA, ACO, and PSO results in improved performance with ACO in terms of optimizing makespan, cost, and CPU time. In addition to shortening the makespan of task scheduling, Xue et al. [90] used an ACO based load balancing algorithm that considers the load of VMs.

As ACO lacks rapid adaptivity, Baxodirjonovich and Choe [91] modified ACO for cloud workflow applications using probability theory to help the ants decide which machine to target. The modified ACO algorithm outperforms classical ACO.

Pacini et al. [92] used ACO for task scheduling based on several interesting metrics: the number of users receiving services and the total number of VMs created in online (non‐batch) scheduling scenarios. Their approach showed better results in a cloud simulation environment than random assignment and GA.

The improved ACO algorithm presented by Zuo et al. [93] was founded on four metrics – makespan, cost, deadline violation rate, and resource utilization – and was designed to solve multi‐objective task scheduling problems. Optimal solutions are found in a timely manner based on constraint functions for performance and cost.

Vinothina and Sridaran [94] used ACO in a public cloud scenario to minimize makespan. Massive amounts of heterogeneous resources are allocated via a pay‐per‐use model.

Moon et al. [95] adapted diversification and reinforcement strategies with slave ants and proposed an ACO algorithm that solves global task scheduling optimization problems by avoiding long paths whose pheromones are wrongly accumulated by the leading ants.

Wu et al. [96] developed a workflow scheduling algorithm based on ACO to optimize execution times and minimize costs for users. They proposed a meta‐heuristic algorithm L‐ACO as well as a simple heuristic ProLiS. ProLiS distributes the deadline to each task, proportional to a novel definition of a probabilistic upward rank. Then, a two‐step list scheduling methodology ranks the tasks and sequentially allocates each task to a service that meets a sub‐deadline and minimizes the cost. ACO is used to carry out deadline‐constrained cost optimization.

Xiang et al. [97] developed a greedy‐ant algorithm with the aim of improving workflow scheduling in heterogeneous computing environments and minimizing the total execution time of an application. Their approach includes a novel perspective on ant colony system scheduling by guiding ants to explore task priorities and simultaneously assigning tasks to machines. They also defined forward/backward dependence to indicate the global significance of each node. Based on this dependence, a novel heuristic factor helps ants search for task sequences. The end result is a greedy machine allocation strategy.

Zuo et al. [98] used ACO to optimize a finite pool of resources in a hybrid cloud computing environment based on deadlines and cost constraints. It minimizes task completion times and cost using time‐first and cost‐first single objective optimization strategies. QoS for users and profits for resource providers are maximized using an entropy optimization model.

Chen et al. [99] proposed a novel multi‐objective ant colony system for workflow scheduling based on multiple‐populations. The model includes execution time and execution cost objectives and a new pheromone update rule based on a set of non‐dominated solutions from a global archive. The update rule balances the search for both objectives by guiding each colony in a search for one objective only, and a complementary heuristic strategy ensures that each colony only focuses on its own objective. The quality improvement in the of the solution to the global archive helps to further the approach to the global Pareto front.

Jia et al. [100] developed an intelligent scheduling system from the users' perspective to reduce the expenditure of workflow subject to deadlines and other execution constraints. A new estimation model for task execution time was designed according to virtual machine settings in real public clouds and execution data from practical workflows. An adaptive ACO algorithm with a narrower search space and a self‐adaptive weight is used to adaptively meet different deadline settings.

Sebastio et al. [101] developed a new scheduling algorithm for volunteer clouds to support collaborative task execution services. The approach combines ACO and an overlay network partitioning method, called ACO‐Partitioned, to improve the QoS of computer‐intensive workloads. Colored scout ants discover the computational resources in the network and maintain the computational field. These scout ants are spawned continuously to adapt to the variability of the volunteer cloud. In a comparative efficiency evaluation with ACO, random, round robin, greedy oracle, and local diffusion, ACO‐Partitioned showed the highest increase in QoS.

Wang et al. [102] proposed cooperative multi‐task scheduling based on ACO (CMSACO) to improve completion time, resource consumption, and executive order. Simulation results show that CMSACO performs better than FCFS in a range of factors, including reduced energy consumption, increasing the number of executed tasks, and load ratio.

Applications that rely on BCO are very rare. Thanka et al. [103] improved BCO for task scheduling with a proposal called improved efficient‐artificial bee colony (IE‐ABC). Unlike the classical BCO algorithm, where the worker bee must update each time it is in a hive, and an onlooker bee selects the food source with the highest nectar quantity, these authors assigned a dedicated worker bee to the data center. This bee updates the current virtual machine's status, its capacity load, memory availability, storage, and security level in the hive table. So, each time the honeybee that is the task of the cloud environment does not want to search for the best fitness. This saves time because the bee can make a decision about whether its VM is over or underloaded when assigning the task to itself. Compared to the ABC algorithm, IE‐ABC improves resource utilization and task migration.

In a recent study, Gomathi et al. [104] used epsilon‐fuzzy dominance based on a composite discrete artificial bee colony (EDCABC) to generate Pareto‐optimal solutions for multi‐objective task scheduling problems. EDCABC applies composite mutation strategies and a fast local search method to improve local searches and avoid premature convergence. EDCABC shows higher reductions in makespans and execution costs and better resource utilization than NSGA‐II and MOPSO.

Table 8.3 summarizes the ant and bee colony‐based algorithms and reports the improvements, objective functions, algorithms outperformed, and evaluation tool.

8.4.4 Other Evolutionary Algorithms

Song et al. [105] proposed a general job selection and allocation framework that uses an adaptive filter to select jobs, while a modified heuristic algorithm (Min‐Min) allocates them. Two objectives and four criteria are considered in the optimization problem. The two objectives are to maximize the remaining CPU capacity and maximize resource utilization. The four criteria are CPU resource requirements, memory, hard disk space, and network bandwidth.

Bilgaiyan et al. [106] applied a cat‐swarm‐based multi‐objective optimization approach to schedule workflows in a cloud computing environment while minimizing costs, makespans, and CPU idle time. This approach performs better than multi‐objective PSO (MOPSO).

Abdullahi and Ngadi [107] presented a discrete symbiotic organism search (DSOS) algorithm for the optimal scheduling of tasks to cloud resources with the aim of minimizing makespans, response times, and the degree of imbalance between VMs. Symbiotic organism search (SOS) mimics symbiotic relationships (i.e. mutualism, commensalism, and parasitism) to improve the quality of the given objective functions. They prove that DSOS converges faster than PSO as the search grows larger, which makes it suitable for large‐scale scheduling problems.

Torabi and Safi‐Esfahani [108] rely on a bio‐inspired metaheuristic algorithm, chicken swarm optimization (CSO), and raven roosting optimization (RRO) for task scheduling. CSO brings efficiency in satisfying the balance between the local and the global search, and RRO overcomes the problem of premature convergence. RRO also has better performance in larger search spaces. Simulation tests performed in a cloud computing environment show improvements in terms of reducing execution times, reducing response times, and increasing throughput in dynamic scenarios.

Choudhary et al. [109] hybridized the popular metaheuristic, gravitational search (GSA), and the HEFT algorithm for workflow scheduling. In terms of its two objectives – makespan and cost – the proposed method outperformed GSA, hybrid GA, and HEFT in experiments with scientific workflows.

8.5.1 Evaluation Tools

Only two studies have included model evaluations based on real cloud environments. The majority have used simulated clouds like CloudSim to assess the efficacy of their work. Measuring the accuracy of an objective function using simulation tools tends not to be very reliable as some values like transfer and execution times cannot be calculated if they have not actually been performed. Hence, a goal should be to verify the accuracy of the presented models in a real cloud environment, such as VMware‐vSphere.

8.5.2 Objective Functions

Most studies only consider two objective functions and only four at most. Moreover, none of the existing models provide any flexibility as to the number and type of objectives. Considering the growing popularity of cloud computing, comprehensive models that incorporate all important objective functions need to be developed. This includes objective functions desired by both industry and users. Models should provide users with the opportunity to select and rank the objective functions according to their own preferences and requirements. For example, the importance of objective functions like time and cost can vary in different situations. In some cases, a user may need a task to complete in the shortest possible time no matter how much it costs. On other occasions, cost may be the most important factor.