Keywords

1 Introduction

Scheduling is one approach to achieve optimal resource allocation among all given tasks in limited time to get wanted QoS. Scheduler finds ways to assign appropriate task to limited resources for optimization of one or more objectives. Task is scheduled on some resource which is bounded by some constraints to find some optimal solution for objective function. The target of scheduling algorithm is to determine which task will be executed on which resource [1]. May it be a scheduling algorithm or the concept of threads in operating system, both remained an interesting and important topics of the research area. Not limiting, this paradigm supports access to pool of shared resources with the guarantee of QOS to the respective users. Achievement of desired performance is the key to user satisfaction and this can be done by considering the scheduling as the central theme in systems working on cloud computing [2].

Task assignment from the Internet user to the limited resource is one of the important applications of modern scheduling in distributed systems for computing. Several changes have been incorporated to these systems including the use of clusters which integrate multiple standalone computers to one single unit giving high performance. To beat the issue of cluster systems being just ready to utilize nearby assets, the following change, grid, has been produced to join all the accessible heterogeneous resources from topographically distributed organizations. Cloud computing systems use the qualities of cluster computing and grid computing [3]. Cloud computing addresses the NP-hard problems where the objective is to resolve the mapping of task on apparently large number of computing resources in cloud computing. No algorithm exists that provides an optimal solution for these types of problems within polynomial time [4, 5].

Common methods for scheduling include exhaustive and deterministic algorithms. Another type of algorithm which can be used for scheduling is metaheuristic algorithms. Practically, DAs show much better results than traditional exhaustive methods since they provide faster solutions for problems on scheduling [6]. The DAs are limited for few data distribution and do not fit to large-scale distributions of collected data. On the other hand, metaheuristic algorithms employ approximation methods and use iterative strategies to achieve optimized solutions in reasonable time. Metaheuristic algorithms have high efficiency and effectiveness in solving comparatively larger problems that incorporate complexity among them [7,8,9].

The QoS-oriented task scheduling issue is an optimization issue which guarantees the ideal mapping between each task and accessible resources, which can impact the QoS of the entire cloud computing systems [10,11,12]. Dependency forms the basis to differentiate the scheduling algorithms; i.e., task scheduling is subjected to the completion of all the parent tasks. Such type of dependency is cited under work flow scheduling. When the tasks do not follow any sequence of scheduling the process is named as independent scheduling.

As of late, to get an optimum solution, most researchers concentrated on creating nature propelled metaheuristic algorithms like ACO, PSO, GA, ABC to take care of multi-objective workflow scheduling problem thinking about different parameters [13,14,15,16,17]. To additionally raise the viability, researchers endeavor to incorporate numerous criteria into the optimization algorithms, known as multi-objective task scheduling. MOTS [18] is a most imperative point in the cloud computing by including numerous parameters like makespan, cost, QoS, load and network parameters. The objective in the cloud environment is to plan the present tasks inside the given imperatives like QoS, resource utilization cost, load balancing, and makespan [1, 19]. The current work analysis presents the review of few scheduling algorithms including traditional and metaheuristic algorithms.

2 Metrics for Scheduling Optimization

Quantification to find the quality and determine the efficiency calls for the use of some empirical analysis. In cloud computing also, we need to quantify the work analysis on some basis. These bases form the optimization metrics for the work. Cloud computing revolves around two types of entities which are service provider for the cloud and the other one is the cloud consumer. The resources are provided on the rental basis by the cloud service provider to the consumers. Later do their task submission for processing the resources provides by the former. Both components of the cloud environment have their own motivations while achieving the objectives. Consumers prefer performance while providers seek for efficiency in resource utilization. The fundamental scheduling parameters considered in the already said techniques are recorded underneath:

  1. 1.

    Makespan: It is the aggregate completion time of all tasks in a job queue. A decent algorithm of scheduling dependably endeavors to diminish the makespan.

  2. 2.

    Resource utilization: It means keeping assets as occupied as could be expected under the circumstances. Maximization of resource usage must be achieved. This rule is picking up criticalness as service providers need to acquire the greatest benefit by leasing a predetermined number of resources [20].

  3. 3.

    Resource utilization cost: It demonstrates the aggregate sum the client needs to pay to a service provider for asset usage.

  4. 4.

    Quality of Service: QoS incorporates numerous client input limitations like meeting execution cost, due date, performance, makespan, and so forth [21, 22].

  5. 5.

    Load balancing: It is the strategy for dissemination of the whole load in a cloud network crosswise over various nodes so that at once no node stay under loaded while a few nodes are over-burden [23].

  6. 6.

    Energy Consumption: Energy utilization is an issue that ought to be considered with more care nowadays. Numerous scheduling algorithms were created for reducing power utilization and enhancing performance and thus making the cloud services green [24].

  7. 7.

    Performance: Performance shows the overall effectiveness given by the scheduling algorithm in order to give great administrations to the clients according to their requirements.

  8. 8.

    Deadline: It is characterized by the timeframe from presenting a task to the time by which it must be finished. A decent scheduling algorithm dependably attempts to keep the tasks executed inside the due date imperative.

3 Traditional Scheduling

Scheduling can be characterized as designating a set of given tasks to a set of given machines subject to the imperatives of optimizing objective functions. At the point when there is a single machine, the scheduling problem is alluded to as a single-processor scheduling problem. For in excess of one machine, the scheduling problem is viewed as a multiprocessor scheduling problem. The performance for scheduling algorithms can be quantified on the basis of resource utilization cost, makespan, load balancing and QoS and its variants. Since scheduling has been extensively utilized as a part of numerous research problem domains, a few examinations endeavored to exhibit a scientific categorization of scheduling problem as far as the job depiction is concerned.

4 Metaheuristic Scheduling

The metaheuristic scheduling can be studied under a unified framework showing the initial, transition, evaluation and determination evaluators employed to the framework. The major issue that is to be addressed is applying the encoded solution for metaheuristic algorithms to optimize the scheduling problems. The transition operator changes the current state of the solution to the next by using pertubative and constructive transition methods for solving combinatorial problem [25, 26]. The complexity of the operator depends upon the design of the metaheuristic algorithm which may vary from easy to complex. The evaluation operator takes responsibility for evaluating the object function value in the problem statement. For example, this operator determines the value of makespan for the scheduling problem. Yet another operator called determination guides the search and intent to quantize the research for intensification and diversification that implicitly or explicitly influence the convergence speed.

4.1 Ant Colony Optimization Scheduling Algorithm

Ant colony optimization scheduling algorithm is based on real behavior of ants. It finds the shortest path between the source food and the ant colonies. Originally called as ant system, the approach was introduced by Dorigo in 1992. The approach makes the use of the fact that ants leave pheromone on the way while walking amid their colony and the food source. The intensity of the pheromone is increased on the passage due to the number of ants passing through and it decreases due to evaporation with time [27].

ACO algorithms are efficient in finding a solution for the discrete optimization problems which requires path finding to reach the goals. An ant colony optimization scheduling algorithm is studied in terms of its representation, operators, control parameters, evolutionary mechanism, performance metric, areas of applications as shown below.

  1. 1.

    Algorithm: Ant Colony Optimization Scheduling Algorithm

  2. 2.

    Representation: Undirected graph.

  3. 3.

    Operators: Pheromone update and measure, trail evaporation.

  4. 4.

    Control Parameters: Number of ants, iterations, pheromone evaporation rate, amount of reinforcement.

  5. 5.

    Evolutionary Mechanism: \(P_{ij} = \frac{(\tau _{ij})^\alpha (\eta _{ij})^\beta }{\sum {{_{k\in allowed}}{(\tau _{ik})^\alpha (\eta _{ik})^\beta }}}\)

  6. 6.

    Performance Metric: Makespan, load balancing, resource utilization cost, execution cost, deadline constraint, energy conservation, response time, throughput.

  7. 7.

    Areas of Application: Traveling salesman problem, classification problem in data mining, job-shop scheduling problem.

4.2 Particle Swarm Optimization Scheduling Algorithm

Particle swarm optimization algorithm is an evolutionary computation technique which is motivated by the social behavior of the particles. It exploits the motion of particles which have velocity and are aligned in some specific direction with the position vector. Their movement is traced as multidimensional motion in the search space. It follows the iterative approach where after each transition, particle adjusts its velocity on the basis of best position with respect to current position of self and the best particle in the whole population. It is the merger of global search and local search where the technique tries to balance the exploration and exploitation by the former method [28, 29].

The method incurs low-computational cost and is rapidly growing in terms of popularity due to simplicity in understanding and implementation. An algorithm is studied in terms of its representation, operators, control parameters, evolutionary mechanism, performance metric, areas of applications as shown below.

  1. 1.

    Algorithm: Particle Swarm Optimization Algorithm

  2. 2.

    Representation: D dimensional vector for position, speed, best state.

  3. 3.

    Operators: initializer, updater and evaluator.

  4. 4.

    Control Parameters: number of particles, Dimension of particles, Range of particles, inertia weight, maximum number of iterations.

  5. 5.

    Evolutionary Mechanism: \(V_{i+1}=\omega {V_i}+c_1{rand_1}*(pbest-x_i)+c_2{rand_2}*(gbest-x_i)\)

  6. 6.

    Performance Metric: Makespan, load balancing, resource utilization cost, communication cost, execution cost, throughput, energy conservation.

  7. 7.

    Areas of Application: Multimodal biomedical image registration, various scheduling problems, vehicle routing problems, color image segmentation, sequential ordering problem.

4.3 Genetic Scheduling Algorithm

Genetic scheduling algorithm (GA) is definitely a standout among the most critical population-based algorithms as far as its execution as well as the effectiveness of applying it to numerous issue areas. In GA, every chromosome (individual in the population) speaks to a conceivable answer for an issue and is made out of a series of genes. The underlying population is taken arbitrarily to fill in as the beginning stage for an algorithm. A fitness function is defined to check the appropriateness of the chromosome for the environment. Based on a value of fitness, chromosomes are chosen and crossover and mutation tasks are performed on them to deliver offspring for the new population. The fitness function assesses the quality of every offspring. The procedure is reiterated until sufficient offspring are made.

GA utilizes fitness function to assess the answers for the best fit. Fitness function works likewise to separates solutions in light of rank or proportion. The selection operator decides the search directions for the following cycle. While the crossover expects to exchange the data between the solutions, the mutation operators empower the algorithm to get away from the local optima amid the transitions.

Evaluation and determination operators of metaheuristic can be viewed as the determination technique of the GA. Distinctive outline contemplations of the fitness function can be drawn from different suspicions. The cost of data transfer, correspondence, and calculation, and in addition the profit, have all been considered in the outline of the fitness function. An algorithm is studied in terms of its representation, operators, control parameters, evolutionary mechanism, performance metric, areas of applications as shown below.

  1. 1.

    Algorithm: Genetic Scheduling Algorithm

  2. 2.

    Representation: Binary, real numbers, permutation of elements, list of rules, program elements, data structure, tree, matrix.

  3. 3.

    Operators: Crossover, mutation, selection, Inversion.

  4. 4.

    Control Parameters: Population size, maximum generation number, cross over probability, mutation probability, length of chromosome, chromosome encoding.

  5. 5.

    Evolutionary Mechanism: Depends on the maximization or minimization of Fitness funtion

  6. 6.

    Performance Metric: Makespan, Load Balancing, Resource Utilization Cost, Execution Cost, QoS, Energy Conservation.

  7. 7.

    Areas of Application: drug design, Web site optimizations, data mining problems, control system design, pattern recognition.

4.4 Artificial Bee Colony Optimization Scheduling Algorithm

Artificial bee colony optimization scheduling algorithm is an optimization technique to locate the ideal solution motivated by the foraging behavior of honey bees. There are three kinds of a population of the honey bee: Scout honey bees have an obligation to arbitrarily search for the new sustenance sources; employed honey bees need to search for the food sources and bring back the sustenance sources data to illuminate the onlooker honey bees which are holding up at the hives. At that point, the onlooker honey bees compute the fitness function and pick the ideal food source for sending the employed honey bees to gather. In the event that any food source was picked and all the food was gathered, the employed honey bees which are the proprietors of the food source will turn into the scout honey bees and they will again arbitrarily search for the new food sources. In the genuine nature, honey bees will look at the nature of food sources on the dance floor. They will move, called “Waggle Dance” to illuminate others about the direction, the distance, and the measure of honey. The onlooker honey bees will contrast all food sources for locating the best one [30, 31].

As of late, numerous scientists had used ABC in taking care of task scheduling problem. An algorithm is studied in terms of its representation, operators, control parameters, evolutionary mechanism, performance metric, areas of applications as shown below.

  1. 1.

    Algorithm: Artificial Bee Colony Optimization Scheduling Algorithm

  2. 2.

    Representation: D-dimensional vector \(x_i\) = \(x_1\), \(x_2\) to \(x_d\).

  3. 3.

    Operators: Reproduction, replacement of bee, selection.

  4. 4.

    Control Parameters: number of food sources (SN), the value of limit, the maximum cycle number (MCN).

  5. 5.

    Evolutionary Mechanism: \(p_i=\frac{fitness_i}{\sum _{i=1}^{NP}{fitness_i}}\)

  6. 6.

    Performance Metric: Makespan, Load Balancing, Resource Utilization Cost, Execution Cost, Energy Conservation.

  7. 7.

    Areas of Application: clustering, scheduling problems, assembly line balancing problem, image segmentation, training of neural networks.

4.5 Crow Search Optimization Scheduling Algorithm

Scheduling optimization problems can be resolved by using crow search optimization scheduling algorithm, which tries to reproduce the astute conduct of the crows to find the optimized solution. There are numerous similitudes between optimization process and the flocks of crows. The crows used to hide the food available with them at specific locations (concealing spots) and during their requirement, crows used to recuperate the same. In order to search for better food sources, crows have a tendency to follow another crow in a flock. Finding food source concealed by a crow is not a straightforward task since if a crow finds another is following it, the crow attempts to trap that crow by taking off to another area of nature. As per an optimization point of view, the searchers correspond to crows, the search space is complemented by the environment, possible solution corresponds to each position of the environment, objective function is represented by the quality of the food source and the global solution to the scheduling optimization problem is represented by the best food source of the environment [32].

An algorithm is studied in terms of its representation, operators, control parameters, evolutionary mechanism, performance metric, areas of applications as shown below.

  1. 1.

    Algorithm: Crow Search Optimization Scheduling Algorithm

  2. 2.

    Representation: D dimensional search space.

  3. 3.

    Operators: Flock size (N), maximum number of iterations \(iter_{max}\), flight length (fl) and awareness probability (AP).

  4. 4.

    Control Parameters: Flight length (fl) and awareness probability (AP).

  5. 5.

    Evolutionary Mechanism: \(x^{i,iter+1}=x^{i,iter}+r_i*fl^{i,iter}*(m^{j,iter}-x^{i,iter})\).

  6. 6.

    Performance Metric: Makespan, Load Balancing, Resource Utilization Cost, Energy Conservation, QoS.

  7. 7.

    Areas of Application: Solving complex engineering design problem, nonlinear and multimodal real-world optimization problems.

4.6 Penguin Search Optimization Scheduling Algorithm

The problem of scheduling optimization can be resolved by using penguin search optimization algorithm, which tries to find out the optimized solution by reproducing the hunting practice of the penguins. The penguins have attractive hunting technique since they can cooperate with each other with their endeavors and synchronize their dives to improve the global energy during the time spent in entire hunting practice [33].

All penguins speak to a result are scattered in gatherings, and each gathering looks for meal in characterized holes with differences levels. Penguins arranged all together for their groups and begin the pursuit in a particular hole & level as per meal disponibility probability. In every iteration, in like manner, the position of the penguin with each advanced solution is altered and gives three results, the best local, the last, and the new solution. The counts in the refresh, an answer is rehashed for every penguin in each gathering, and after a few doves, penguins pass on to one another the best solution which speaks to by the amount of fishes eaten, and new dispersion probability of gaps and levels is figured. An algorithm is studied in terms of its representation, operators, control parameters, evolutionary mechanism, performance metric, areas of applications as shown below.

  1. 1.

    Algorithm: Penguin Search Optimization Algorithm

  2. 2.

    Representation: 3D graph of the nonlinear multimodal Rastingin function.

  3. 3.

    Operators: the number of penguins, the number of holes and the number of levels should be large enough.

  4. 4.

    Control Parameters: distribution probability of holes and levels.

  5. 5.

    Evolutionary Mechanism: \(D_{new}=D_{LastLast}+rand()\mid X_{LocalBest}-X_{LocalLast}\mid \)

  6. 6.

    Performance Metric: Makespan, load Balancing, resource utilization cost, energy conservation, QoS.

  7. 7.

    Areas of Application: Solving NP-hard problems, applications in many fields such as aeronautics, medical imaging.

5 Discussion

Based on the survey of metaheuristic task scheduling algorithms, the following observations and challenges are identified:

  1. 1.

    The way to a task scheduling methodology is to discover a trade-off between client necessities and resource usage. Nonetheless, tasks which are put together by various clients may have diverse prerequisites on the computing time, memory space, data traffic, reaction time, and so forth.

  2. 2.

    One of the real difficulties in the present cloud arrangements is to give the required services as per the QoS level expected by the client. Cloud service providers need to affirm that adequate measure of assets is provisioned to guarantee that QoS prerequisites of cloud service consumers, like due date, execution time, energy consumption, and budget limitations are met.

  3. 3.

    In multi-objective task scheduling optimization, it is expected to use the scheduling design with various criteria, to meet the prerequisite of clients and additionally service providers. Be that as it may, the schedulers would offer ascent to the issue of high load, serious resource rivalry, and the wasteful cooperation.

  4. 4.

    The techniques utilized different objectives for task scheduling, but the utilization of multiple objectives like QoS, cost, makespan, load within one algorithm was not considered. This consideration aims to provide optimal services that too at a minimal expense to the users.

  5. 5.

    Also, the recent and effective optimization algorithms are required to solve the multiple objective-based task scheduling because the traditional algorithm is only utilized in most of the works.

Ideas extracted from the key observations must be harnessed in order to develop a new multi-objective metaheuristic optimization scheduling algorithm that will minimize the shortcomings of existing metaheuristic optimization scheduling algorithm.

6 Conclusion & Future Scope

The primary intention of this research is to have a deep insight into various multi-objective task scheduling algorithms in the cloud computing environment. For this purpose, a number of metaheuristics scheduling algorithms are studied in terms of their representation, operators, control parameters, evolutionary mechanism, performance metric, areas of applications for techniques. In the future, the comparison of various metaheuristic scheduling algorithms such as ACO, PSO, GA, ABC, CSA, and PeSOA can be done quantitatively based on various parameters identified from the detailed study of the literature like makespan, resource utilization cost, load, and QoS.