Multi-Objective Task Scheduling in the Cloud Computing based on the Patrice Swarm Optimization

Published Online April 2015 in MECS

The “Cloud” the metaphor is a reference to the ubiquitous availability and accessibility of computing resources via Internet technologies [1] . Cloud computing as a novel and entirely internet-based approach is an important concept in today’s distributed systems [2] . It is used chiefly for business applications in which computers cooperate to perform a specific service [3] . It evolved through the recent advancements in hardware, virtualization technology, distributed computing, and service delivery over the Internet. While Cloud computing may not involve a lot of new technologies, it certainly represents a new way of managing IT. In many cases, this will not only change the workflow within the IT organization, it will often result in a complete reorganization of the IT department. Cost savings and scalability can be highly achieved from cloud computing [4] . Cloud computing, which is aimed at providing infrastructures, platforms and software as services has been introduced and implemented in the last few years. It is widely recognized as the next generation of computing architecture [5] . Generally, Cloud computing services can be categorized into three main types of services:

Infrastructure as a Service, Platform as a Service and Software as a Service. These services can then be accessed through a cloud client which could be a web browser, mobile app, and so on [6] . Cloud computing provides implementation agility, lower capital expenditure, location independence, resource pooling, broad network access, reliability, scalability, elasticity, and ease of maintenance [7, 8] . Also it offers numerous advantages for data and software sharing and thus making the management of complex IT systems much simpler [9, 10] .

Job scheduler is a vital part of any distributed system like Grid [11-13] , Cloud [14-17] and P2P networks [18 20] which assigns jobs to suitable resources for execution. The scheduling of a task workflow in a distributed computing platform is a well-known NP-hard problem [21] . The problem is even more complex and challenging when the virtualized clusters are used to execute a large number of tasks in a Cloud computing platform [21, 22] . For this reason, many heuristics have been proposed, from low level execution of tasks in multiple processors to high level execution of tasks in Grid and Cloud environments [23] . Recently many papers are published which used evolutionary algorithms like genetic, ant colony, bee colony and PSO (Particle Swarm Optimization) for optimization problems [21] . Because of the success of the PSO algorithms, in this paper we propose a new method based on the PSO algorithm for task scheduling in Cloud computing. The proposed method use a multi-objective function for increasing the effectiveness of algorithm.

The rest of this paper is organized as follow. In section 2, the related works are briefly reviewed. Section 3 describes the proposed method. In section 4 the obtained results are presented. Finally, last section concludes the paper and suggests some suggestions for future researches.

• II .Related Works

In this section, the state of the art mechanisms and approaches of task scheduling in the Cloud systems are briefly reviewed and analyzed based on published years.

• •    2011

Garg, Yeo [24] have proposed the near-optimal scheduling policies to exploit heterogeneity across multiple data centers for a Cloud provider. The method is considered a number of energy efficiency factors (such as energy cost, carbon emission rate, workload, and CPU power efficiency) which change across different data centers depending on their location, architectural design, and management system. The have demonstrated that the proposed method can able to achieve on average up to 25% of energy savings in comparison to profit based scheduling  policies.  Mezmaz,  Melab [25] have investigated the problem of scheduling precedence-constrained  parallel  applications on heterogeneous computing systems like cloud computing infrastructures. They have proposed a new parallel bi-objective hybrid genetic algorithm based on dynamic voltage scaling (DVS) that takes into account, not only makespan, but also energy consumption.

• •    2012

Li, Qiu [26] have proposed two online dynamic resource allocation algorithms for the IaaS Cloud system with preemptable tasks. They algorithms adjusted the resource allocation dynamically based on the updated information of the actual task executions and the experimental results demonstrated that the proposed algorithms can significantly improve the performance in the situation where resource contention is fierce. Also

Abrishami and Naghibzadeh [27] have proposed a new QoS-based workflow scheduling algorithm based on a novel concept called Partial Critical Paths (PCP), which tries to minimize the cost of workflow execution while meeting a user-defined deadline. Lu, Jiang [28] have proposed a resources collaboration scheduling model to improve the efficiency of the virtual resources collaboration scheduling. The proposed model is based on virtual organization and makes use of the trust mechanism to estimate the credibility of the virtual organization. Finally, Wang, Zeng [29] have presented a Bayesian method based cognitive trust model, and a trust dynamic level scheduling algorithm named Cloud-DLS (Dynamic Level Scheduling) by integrating the existing DLS algorithm [30] .

• •    2013

Van den Bossche, Vanmechelen [31] have proposed a workload model which is considers non-preemptible and non-migratable workloads with a hard deadline that are characterized by CPU, memory and data transmission requirements. Also, Wang, Wang [32] have proposed a genetic algorithm for Cloud resource optimization scheduling model that promised the user needs while optimizing resource allocation. Laili, Tao [14] have combined the Service Composition Optimal Selection (SCOS) and Optimal Allocation of Computing Resources (OACR) into one-time decision in one console, named Dual Scheduling of Cloud Services and Computing Resources (DS-CSCR). Wu, Liu [16] have proposed a market-oriented hierarchical scheduling strategy in Cloud workflow systems.

• •    2014

Frîncu [33] have presented a solution based on genetic algorithm to finding the optimal number of component types needed on nodes so that every type is present on every allocated node. The have tested the algorithm in terms of node load, closeness to the optimal solution and proved the algorithm’s efficiency. Tao, Feng [15] have proposed Case Library and Pareto Solution based hybrid Genetic Algorithm CLPS-GA for Optimal Scheduling of Computing Resources (OSCR). Liu, Qu [34] have proposed a fuzzy clustering method to effectively preprocess the Cloud resources. They have proposed a new directed acyclic graph based scheduling algorithm called earliest finish time duplication algorithm for heterogeneous Cloud systems by combining the list scheduling with the task duplication scheduling scheme. Finally, the experiment demonstrates that the proposed algorithm is effectual and well-organized. Finally, Jung, Lim [35] have presented the workflow scheduling scheme that reduces the task waiting time when an instance occurs the out-of-bid situation.

• III.    Proposed Method

In this section we propose a new method based on PSO for task scheduling in Cloud computing. First, the problem statement is described.

• A.    Problem Statement

For stating the problem we use a DAG (Directed Acyclic Graph) which is a directed graph with no directed cycles. It is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again [36, 37] .

T 0 ={8, 20, M},

T 2 ={7, 15, H},

T 4 ={8, 18, L},

T 6 ={7, 20, M},

T 1 ={6, 12, L}

T 3 ={6, 15, H}

T 5 ={4, 14, H}

T 7 ={6, 10, M}

Fig. 1. An example of a DAG with 8 tasks and three resources

In a DAG vertices denote tasks and edges represent precedence constraints and/or data movements among tasks. Given a set of resources, a schedule for a DAG is an assignment which specifies the mapping of tasks and resources and the estimated start time of each task on the mapped resource. Here, the aims of DAG scheduling is to minimize the overall execution time, waiting time and the missed tasks. Fig. 1 represents an example of DAG. In this example, three resources and eight tasks are exist. Each task have three properties {ET1, deadline, priority}.

• B.    Swarm Intelligence

Swarm intelligence refers to collective intelligence. Biologists and natural scientist have been studying the behavior of social insects due to their efficiency of solving complex problems such as finding the shortest path between their nest and food source or organizing their nests. In spite of the fact that these insects are unsophisticated individually, they make wonders as a swarm by interaction with each other and their environment. In last two decades, the behaviors of various swarms that are used in finding preys or mating are simulated into a numerical optimization technique. The collective intelligence emerges from a selforganization process of agents evolving autonomously according to a set of internal rules specifying its motion patterns and interaction with the environment and other agents, such that intelligent collective behavior arises from simple individual behaviors [38] . Some important swarm intelligence techniques are ant colony optimizer, particle swarm optimizer, artificial bee colony algorithm, glowworm algorithm, firefly algorithm, cuckoo search algorithm, bat algorithm, and hunting search algorithm [39] . Most of the swarm intelligence–based algorithms are simple and robust techniques that determine the optimum solution of optimization problems efficiently without requiring much of a mathematical struggling. PSO has attracted significant attention since its inception because of its simplicity and effectiveness in solving various optimization problems [40] . Therefore, we choose PSO for solving the stated problem.

• C.    The proposed method

PSO is a metaheuristic algorithm which is developed by Kennedy and Eberhart [41] to find good solutions in optimization problems which takes its inspiration from the cooperation and communication of a swarm of birds. Inspired by social models and swarming theory, it consists of a swarm that collectively explore the solution search space of an optimization problem and stores the best solutions found. In PSO, each individual in the swarm, called a particle, behaves like an agent of a highly decentralized and intelligent environment. Each particle of the swarm contributes to the environment by following very simple rules, thus cooperating and communicating with other particles of the swarm [42]. Particles are attracted at each iteration to the best solutions found by themselves and to the best solutions found by their neighbors, thereby encouraging the exploration of nearby solutions to potentially find better ones [43]. Analogous to other evolutionary algorithms, such as GA and ACO, PSO is a population-based stochastic optimization algorithm. A swarm of particles attempts to search for superior solutions through learning, communication and interaction. The position of each particle refers to a solution. The state of particle i is described by its current position xi = [xi 1, xi 2, … xiD ] and velocity vi = [vi 1, vi

• ₂, … v_iD ], where D is the number of variables

encountered in the optimization problem. In the generic PSO with inertia weight [44] , the position and velocity of particle i are updated during the evolutionary process [40] :

v?=w× v? + c1 × T^ × (pbestf - xf )

+ c2 × ^T2 × (gbest^d - x^d)                    (1)

xf =  + V^d                                  (2)

where xt is the dth variable of the position of particle i; vd is the dth variable of the velocity of particle i; pbestf is the dth variable of the personal historical best position found by particle i; gbest is the dth variable of the global best position found by the whole swarm; c1 and c2 are the acceleration parameters commonly set to 2.0; rd and rd are two random numbers drawn from a uniform distribution over [0, 1] and w is the inertia weight used to set up the balance between the abilities of global and local search features of PSO [40, 44].

• a.    Solution Representation

As a first step in PSO, the candidate solutions must be encoded in a suitable form. Here, the solution is represented as a string of length n , where n is the number of the requested tasks. For example, fig. 2 represents a solution with 6 tasks and 4 servers. According to fig. 2, T 1 is assigned to S 1 (first server), T 2 and T 6 are assigned to S 3 and so on.

1

3

4

2

4

3

Fig. 2. An example of solution with 6 tasks and 4 server

• b.    Particle Fitness

Fitness or quality value shows how fit the solution is, i.e. how well it adapts to its environment. For a maximization problem, the fitness of a solution can be proportional to the value of the objective function [21] . We uses three terms including total execution time (Ttime), average of waiting time (Wtime) and numbers of missed tasks because of their deadline (Missed) for designing fitness function as follow:

FF1= 1/Ttime,(3)

FF2= 1/Wtime,(4)

FF= FF^+F^ ,(5)

1+Missed

Where the aim of PSO is to maximize the value of FF.

• c.    Termination Condition

The algorithm is ran until no improvement in the fitness of the gbest has been observed for 10 generations or maximum iterations is reached.

• d.    Pseudo Code

In this section the pseudo code of the proposed algorithm is described as follows:

• •    For each particle

• •    Initialize particle

• •    End For

• •    Do

• •    For each particle

• •    Calculate the fitness value of the particle fp

• •    /*updating particle’s best fitness value so far) */

• •    If fp is better than pbest

• •    Set current value as the new pbest

• •    End For

• •    /*updating population’s best fitness value so far)*/

• •    Set gbest to the best fitness value of all particles

• •    For each particle

• •    Calculate the particle velocity according to (1)

• •    Update particle position according to (2)

• •    End For

• •    End Do While maximum iterations OR no improvement in gbest in 10 interactions are reached.

• IV.    Simulation Results

In this section, we present the results to evaluate the performance of the proposed method using Matlab. We suppose the number of resources in the Cloud is 8 and the number of tasks are 40 where their execution and creation time are listed in table 1.

Table 1. Arrival time, service time, deadline and dependency of 40 tasks

Task #	Arrival Time	Service Time	Deadline	Dependency
1	14	4	8	-----
2	15	2	4	-----
3	19	5	10	1
4	14	8	16	1
5	9	9	18	-----
6	9	2	4	2
7	6	1	2	5
8	18	8	16	-----
9	20	3	6	1, 7
10	2	5	10	2, 5, 7
11	7	10	20	6
12	18	6	12	10
13	20	3	6	7, 13
14	9	10	20	8, 10
15	15	9	18	5, 3
16	9	9	18	10
17	3	7	14	-----
18	4	3	6	11
19	5	5	10	16

20	7	4	8	15, 2
21	8	3	6	15, 11
22	2	1	2	-----
23	13	7	14	8, 9, 13
24	5	8	16	5
25	7	8	16	1, 14
26	20	3	6	-----
27	13	2	4	7, 11
28	0	10	20	22, 26
29	17	9	18	8
30	11	6	12	21
31	20	6	12	19, 29
32	6	6	12	16, 19, 27
33	11	4	8	16
34	10	7	14	23
35	9	9	18	17
36	18	4	8	16
37	4	1	2	-----
38	13	4	8	31
39	17	7	14	12, 24
40	11	2	4	6, 37

To study the effectiveness of the proposed method, we compare it with First Come First Served (FCFS), Shortest Process Next (SPN) and Highest Response Ratio Next (HRRN). Fig 3 illustrates the simulation result based on the overall execution time that the PSO has better performance.

Fig 4 illustrates the simulation result based on the average service time + waiting time that the PSO has better performance.

Fig 5 illustrates the simulation result based on the average of missed tasks that the SPN has better performance.

Finally, Fig 6 illustrates the simulation result based on the resource utilization that the PSO has better performance.

Е 30 н

FCFS        SPN        HRRN        PSO

Method

Fig. 3. The simulation result based on the overall execution time

Utilization Rate (%)                                         Missed Tasks                                                       Time

Fig. 4. The simulation result based on the average service time + waiting time

Fig. 5. The simulation result based on the average of missed tasks

Fig. 6. The simulation result based on the resource utilization

• V.    Conclusion and Future Works

Cloud computing as a novel and entirely internet-based approach is an important concept in distributed systems. In Cloud computing, shared resources are provided to end-users in an on demand fashion that brings many advantages, including data ubiquity, flexibility of access, high availability of resources, and flexibility. In this type of systems many challenges are existed that the task scheduling problem is one of them. In this paper, a new algorithm based on PSO is proposed to schedule the tasks in the Cloud. The results demonstrated that the proposed algorithm has a better operation in terms of task execution time, waiting time and missed tasks in comparison of FCFS, SPN and HRRN. In the future, we plan to modify the proposed method to support the heterogeneous resources.