Sawsan Alshattnawi*, Raneen Khraisat and Hala Majdalawi
Computer Science Department, Yarmouk University, Irbid, Jordan
*Corresponding Author: Sawsan Alshattnawi, Computer Science Department, Yarmouk University, Irbid, Jordan.
Received: January 18, 2021; Published: February 16, 2021
The meta-heuristic based algorithms are used to address the NP hard problems and they prove their efficiency in solving nearly all of these problems. They produced optimal solutions for large number problems in different domains. One of these domains is the task scheduling and load balancing in Cloud computing environment. Cloud Computing offers good mechanisms to distribute tasks among several virtual resources. Suitable task and workflow scheduling solutions are required to deliver a high performance and accomplish some objectives such as: reliability, security, and load balancing in the cloud environment. In this research, different metaheuristic algorithms are discussed and a comparison between them is made by illuminated their properties.
Keywords: Meta-heuristic Algorithms; Task Scheduling; Cloud Computing
Meta-heuristic algorithms also called approximate algorithms are used in solving many different problems in the computer science field. They are used to deliver an optimal solution or near optimal solution in sensible computational time. Moreover, they produced better results compared with deterministic algorithms in terms of quality and computational time [1].
Many meta-heuristic based algorithms have been developed to deal with the two types of scheduling in the cloud environment: task scheduling and workflow scheduling. There is some quality of services that controls the Cloud resources and services available to users which are based on Pay-as-per-use manner. The high performance computing is needed especially for large and complex application due to big amount of data and computation which are executed by Cloud resources. Scheduling between tasks must be done to optimize resources utilization and reach a high quality of services.
The big solution space obtained by task and workflow scheduling made them classified as NP-hard problems. There- fore, it takes a large period of time to get the optimal solution, several scheduling methods have been proposed to solve them by many researchers, technically, task scheduling is much easier compared to workflow scheduling as it only contracts with a group of tasks without any interdependency and perform them in a random order. On the other hand, work- flow scheduling is much complex since a workflow usually comprises of a group of dependent tasks collaborating together and the scheduler would assign the workflow tasks among virtual machines VMs with respect to their dependencies and execution order.
Some performance metrics are considered when developing any scheduling Meta-heuristic algorithm. These metrics are used to assess the performance of a given method. Although, it can be seen that is not probable to consider all these metrics for an algorithm since it rely on many other factors such the working environment. The following are performance objective parameters of scheduling algorithm appeared in the literature review are:
Generally, scheduling problem includes tasks that have to be scheduled on resources depending on some several restrictions such as the agreements between users and cloud providers to improve objective function such as the good quality of services delivered to users. Many complex and computation applications can be organized as workflows. The workflow applications are usually defined as the arrangement of tasks to be treated in well-known order to achieve a certain goal. Scheduling in cloud environment for either tasks or overflow is classified as NP-hard problems. Hence, there is no ideal (optimal) solution available until now within a polynomial time for these type of problems [2]. However, meta-heuristic based algorithms treat these problems by giving close optimal solution in an acceptable time.
Despite the use of a several number of meta-heuristic algorithms, there is no ideal solution for the scheduling problem in the Cloud environment is produced. Hence, there is a need to explore and develop more scheduling algorithms that gives feasible and better solutions.
In this paper, we present a comprehensive study of various scheduling algorithms based on some meta-heuristic methods such as: Particle Swarm Optimization (PSO), Intelligent Water Drops (IWD), Ant Colony Optimization (ACO), Genetic Algorithm (GA), and other methods. A review on different meta- heuristic scheduling algorithms is done then a comparison between them is made.
Meta-heuristic algorithmsIn this paper, we concentrate on the most popular and recent used algorithms in solving the scheduling problem on cloud computing environment. Here is a brief description of some of them:
In this section, the works are explored and organized according to the used Meta-heuristic algorithm.
Task scheduling based on (PSO) algorithmA task-scheduling algorithm based on dynamic adaptive PSO (DAPSO) algorithm was presented in [7] to enhance the performance of the original PSO in such that minimize the make span and the maximize the resource utilization, therefore the task run time is optimized. This algorithm combined the (DAPSO) with Cuckoo search called (MDAPSO); the (DAPSO) algorithm is good for global searches. On the other hand, it cannot avoid local optima so in order to enhance the inertia weight and improve the trapping in a local search the Cuckoo search is used. A task-scheduling algorithm based on multi-objective optimization and PSO algorithm called (MOPSO) was presented in [8] that depend on an objectives ranking strategy and includes assessing a three objectives individually to discover the best solution of PSO algorithm and find the optimal VM for each task. These objectives are to reduce the task execution cost, reduce the expected completed time and the CPU speed of VM.
A task-scheduling algorithm based on PSO was presented in [9] which capable to balance the load among VMs by selecting the VM with the maximum compatibility for holding a request. This algorithm used the load balance stage after each initialization step in PSO. Hence, the construction of the initial population rather than a random population in order to improve the particle positions. A task-scheduling algorithm based on modified PSO algorithm was presented in [?] that combined the PSO algorithm with the Simulated Annealing algorithm (ASA) where it used to produce a high rate of convergence by avoiding the trapping in a local search. This algorithm focused on the average scheduling length and the successful execution ratio in cloud computing.
Workflow scheduling based on (IWD) algorithmProcessing of an application in cloud computing is made by splitting it into number of workflows and developing them to get the estimated result. The workflows are arranged depend on Quality of Services (QoS) that are differs based on different users. In this section, some workflow scheduling techniques based on IWD algorithm presented. A workflow- scheduling algorithm based on IWD algorithm was presented in [10] that used to decrease the cost of execution by made a tradeoff of the communication cost between resources and the cost of total resources. Moreover, it creates a kind of load balancing by allocating tasks to available resources. A virtual machine scheduling algorithm based on modified IWD algorithm was presented in [11] for dynamic allocation of virtual machines on hosts in homogeneous and heterogeneous environments in order to minimized the total cloud data center energy consumption. The algorithm selects the solution that is taking minimum power as the optimal solution. A workflow- scheduling algorithm based on IWD algorithm was presented in [12] in such that it maps the tasks of the workflow applications among resources according to the fitness function of IWD algorithm, which increased the solution quality and improve the speed of convergence. Therefore, The solution which giving minimum make span is selected. A workflowscheduling algorithm based on a modified IWD algorithm was presented in [13] that aimed to fulfil the following objectives in cloud: reducing makespan and the executing workflows cost. The modified IWD algorithms works by allocating the workflow tasks to the cloud VMs depend on the best IWD paths obtained.
Task scheduling based on GA algorithmThere are several approaches have been planned to solve any issue related to Genetic Algorithm in order to apply them in task scheduling. The work proposed in [14] present a genetic approach for the grid task scheduling to find better solutions within a minimum amount of time. They reduce the Make- span and flow-time. In addition, they get the employment of available resources. An enhanced genetic technique for static task scheduling was presented in [15] that supposed to improve the solutions of task scheduling. The benefit of evolutionary genetic algorithm and heuristic techniques can use in this research. The results approved that the proposed method supports reachability, deadlock free and fairness is- sues. A genetic Algorithm based scheduling was presented in [16], in this research there are three basic objectives that the GA has to achieve. Firstly, reduce the makespan, increase the utilization, and enhance the speedup ratio. The results of the experiment approve that the presented algorithm has big improvements over the HGAAP, GAHDCS, and PGA in terms of the investigated objectives.
The researchers in [17] used a hybrid heuristic genetic algorithm with adaptive parameter (HGAP) that depends on genetic algorithm and heuristic earliest finish time (HEFT). The crossover’s parameters possibility is adaptive according to the status of the current evolution and then finds improved solution. They have addressed just one objective, which is makespan minimization. A genetic algorithm for task scheduling on heterogeneous systems is presented in [18]. The (HEFT) approach is used to assign each task to the appropriate processor. In such that the calculation of priority of a task is extremely time consuming. This approach addressed one objective that is minimization of makespan.
Aimed at large scale and multi objective resources allocation there is an efficient non-dominated sorting genetic algorithm II (NSGA-II) addressed in [19]. In this research, at the earlier stages we have to know the entire information about the tasks. The main benefit of this algorithm is that overall task execution time and power consumption will be different. The authors improved the makespan and energy consumption simultaneously. Another proposed approach is a ”template- based genetic algorithm” (TBGA) which considered the users quality of service constraints in order to schedule the tasks [20]. the proposed approach firstly computes the size of the templates for each processor independently. Templates mean the maximum size of all the tasks that the processes can allocate. Then, the algorithm uses the size of the template to make the combination process between the processors and the tasks using GA. It measured one purpose; reduce the makespan.
Task scheduling based on AC algorithmA lot of researchers used ACO in order to solve the NP problems, which are hard to solve in an ordinary ways. Such as, graph coloring problem, vehicle and scheduling problem. Recently, many researchers used this algorithm to deal with any scheduling method. Vinh., et al. [21] used an improved ant colony algorithm to deal with different task scheduling in cloud. This research prove that ACO algorithm accelerate the clouds task comparing with Round Robin and other optimization algorithm.
A Task Scheduling algorithm based on ACO algorithm was presented in [22] to improve the system efficiency; the researcher used the modified ACO algorithm for achieving task scheduling with reduced makespan in a standard environment for cloud. In the same way, Delavar., et al. [23] addressed the concept of task scheduling in the grid-computing environment using the ant colony optimization technique to minimize the cost and the time. Kumar and Venkatesan [?], [24] introduced task-scheduling method by using the effective multi-objective Genetic Algorithm HGA-ACO can find the best task allocation method. (GA) initializes the best pheromone for ACO algorithm and the ACO use the crossover operation to enhance the GA solution.
Other approaches for schedulingMany researches are introduced in this domain which used a combination of multi-heuristic algorithms. Sundararaj [25] combined the Bee and Ant colony approaches to assign tasks to process in the cloud computing for the mobile. The proposed approach deals with two-way mobile cloud computing with offloading technique. This technique uses the ACO algorithm to minimize the overhead problems and the delay in the response time.
Mansouri., et al. [26] proposed a hybrid task scheduling approach by combining the modified particle swarm optimization and fuzzy theory. This algorithm used important issues for example length of tasks, speed of CPU, and total execution time in the fuzzy system for the calculation of the fitness. Sreenu and Malempati [27] proposed a fractional gray walf optimization technique with modification on the position of each task. This technique uses a multi-objective task scheduling. The algorithm addressed multiple objectives such as the execution of time, cost, consumption of the energy, and resource utilization.
Su., et al. [28] proposed cost efficient task scheduling that executed large number of programs on the cloud. The researchers applied this algorithm through two heuristic approaches. This method dynamically combined between tasks and the virtual machine. In addition, service providers of cloud will rent vendors cloud resources by the concept of pay per use service model.
Comparison between different meta-heuristics scheduling methodsThere are several task scheduling and workflow-scheduling methods proposed by several researchers in cloud environment, in the following table a comprehensive comparison between them is discussed.
As demonstrated in the literature review and the assessment table above, we can figure out the following characteristics of using meta-heuristic optimization techniques in scheduling algorithms in cloud and finally some future directions were mentioned:
Author Name and Year of Publication | Scheduling Al-gorithm | Objective Parameter | Findings |
---|---|---|---|
(Al-maamari and Omara, 2015) [7] |
MDAPSO |
Minimizes makespan and maxImize resource utilization |
This research introduced meta-heuristic approach based on PSO algorithm called (MDAPSO), this algorithm has been compared with the original PSO and other PSO versions and it outperforms them in terms of makespan and resource utilization. |
(Alkayal., et al. 2016) [8] |
MOPSO |
Minimizes waiting time and execution time, maximizes Throughput. |
this research introduced a multi-objective PSO based technique to optimize the task scheduling procedure. MOPSO algorithm has shown improvements in the throughput and reduction in the total execution time. |
(Ebadifard and Babamir, 2018) [9] |
PSO |
Maximizes resource utilization and Minimizes makespan |
This research introduced a PSO based algorithm besides the load balancing technique to enhance the allocation of requests without looking for the request compatibility. This algorithm has been compared with the Round Robin, and enhanced PSO task scheduling and it outperforms these algorithms in terms of resource utilization, makespan and it reach the near optimal solution very fast. |
(Jana., et al. 2019) [29] |
MPSO |
Average schedule length and ratio of successful execution. |
This research introduced a meta-heuristic approach based on PSO algorithm called (MPSO), this algorithm has been compared with Max-Min task schedul- ing and the result has shown that the proposed method average schedule length is decreased and the successful ratio is increased. |
(Sivaparthipan., et al. 2015) [10] |
IWD |
Minimize the total execution cost |
This research introduced an IWD based scheduling algorithm that decreased the total cost of execution. The result has shown that the IWD algorithm outperforms the Best Resource Selection algorithm in cost savings. |
(Verma., et al. 2017) [11] |
MIWD |
Energy savings |
This research introduced a modified IWD algorithm to optimize the energy consumption. The result has shown that MIWD algorithm attained superior energy savings with fewer number of VM migrations and growing number of VMs compared to the original IWD algorithm. |
(Kalra and Singh, 2017) [12] |
IWD |
Minimize makespan |
This research introduced an IWD based scheduling algorithm that mapping tasks to resources targeting to reduce the makespan. The result has shown that the presented method outperforms PSO and SGA algorithm according to makespan. |
(Elsherbiny. Et al, 2018) [13] |
IWDC |
Minimize makespan and cost |
This research introduced an IWDC based scheduling algorithm that allocated the tasks of the workflow to the VMs in cloud depending on the best IWD paths obtained. This algorithm has been compared with Max-Min, Round robin, FCFS, and MCT and the result has shown that IWDC algorithm has the minimum cost. |
(Singh., et al. 2019) [14] |
GA |
Reduce the make-span and the flow-time simultaneously |
This research uses a genetic algorithm for grid task scheduling to improve the efficiency . |
(Keshanchi., et al. 2017) [15] |
N- GA |
Enhance the execution time |
This research used GA besides a heuristic (HEFT) technique for the task assignment process. |
(Bose., et al. 2019) [16] |
GA |
Increase the speed up. Minimize the makespan |
In this research, they designed a genetic algorithm for multi-core system. This algorithm has big improvements in compare with the GAHDCS, HGAAP, and PGA in. |
(Ding., et al. 2017) [17] |
HGAAP |
Minimize the makespan |
In this research, a hybrid genetic algorithm with adaptive parameter (HGAAP) is discussed by combined between the heuristic scheduling algorithm and genetic algorithm. |
(Yuming., et al. 2014) [18] |
MPQGA |
Minimize the execution time |
The key point in this approach is to use a rank to each subtask when using a heuristic-based earliest finish time (EFT) approach. |
(Friese, 2016) [19] |
NSGA-II |
Optimized makespan and energy consumption at the same time |
This paper improved a chromosome structure for task scheduling using the genetic algorithm depend on collections of related tasks and machines. |
(Sheng and Li, 2016) [20] |
TBGA |
Minimizing the makespan of a given task set in Clouds |
This Research concentrated on modifying ACO to address cloud task scheduling |
(Reddy and Kumar, 2019) [22] |
MACO |
Reducing Makespan and decrease the degree of imbalance |
This research deal with cloud task scheduling based on the Modified ACO algorithm |
(Kumar and venkate- san, 2019) [24] |
HGA-ACO |
minimize response time, completion time and throughput |
This research improved the well performance in task distributions and the quality of service parameters. |
(Mansouri., et al. 2019) [26] |
FMPSO |
Enhance load balance and cloud throughput |
This research has better makespan, the ratio of enhancement, the degree of imbalance and the total execution time compared to other methods. |
(Sreenu and Malempati, 2019) [27] |
MFGMTS |
Meet the user requirement and increase the efficiency |
This approaches concentrate on reducing the execution time, decrease cost, and communication cost. |
Table 1: Comparison between different meta-heuristics scheduling methods in cloud.
Meta-heuristic optimization algorithms have become popular because of its effectiveness in a wide-range applications scope including scheduling algorithms in cloud. In this paper, we have discussed several meta-heuristic scheduling algorithms (task scheduling and workflow scheduling) in cloud computing, classified them, studied their characteristics and properties, and compared between them. In addition, we presented some points of view about using optimization algorithms in cloud scheduling and some future directions. The performance metrics in task scheduling such as makespan and resource utilization couldn’t be compared because they are applied in different data sets. Therefore, as a future work, we hope to apply most of them and compute the same metrics over the same data sets.
Citation: Sawsan Alshattnawi., et al. “Meta-heuristic Algorithms for Task and Workflow Scheduling in Cloud Computing Environment: An Overview". Acta Scientific Computer Sciences 3.3 (2021): 02-10.
Copyright: © 2021 Sawsan Alshattnawi., et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.