FGMTS: Fractional grey wolf optimizer for multi-objective task scheduling strategy in cloud computing

Abstract

Task scheduling on heterogeneous data centers of cloud computing environment is a challenging problem. The efficiency of the cloud depends on the adopted task scheduling strategy. The task scheduling algorithm schedules the required task resources of application in the cloud platform. Even though many algorithms are presented for task scheduling; they consider only the minimum objectives for the trade-off of optimal scheduling. In this paper, a multi-objective task scheduling strategy is proposed for the task scheduling problem in the cloud network as an NP-hard optimization problem. In order to solve the scheduling problem, Fractional Grey wolf Multi-objective optimization-based Task Scheduling strategy (FGMTS) is newly proposed for scheduling tasks in the cloud. The proposed FGMTS algorithm is the combination of the existing fractional theory and Grey Wolf Optimizer algorithm. Also, the multi-objective function is newly formulated to solve the multi-objective scheduling problem. The fitness function for the proposed optimization considers the parameters, such as Execution time, Communication time, Execution cost, Communication cost, Energy, and Resource utilization for optimal scheduling. The experimentation of the proposed task scheduling strategy is carried out over two cloud setups. The performance of proposed system is validated over the existing techniques, such as PSO, GA, and GWO using the metrics considered in the multi-objective formulation function. The experimental results show that the proposed FGMTS-Task scheduling scheme allocates the resource for all incoming task requests while preserving the performance of the cloud with an increase in the profit.

Keywords

Cloud computing task scheduling fractional theory grey wolf optimization algorithm multi-objectiveconstraints

1 Introduction

Scheduling is the important activity in the cloud which schedules the resources for the tasks from the cloud center [6]. By proper scheduling, proper utilization of cloud resources and load management between the resources with minimum execution time of tasks, the workload efficiency can be improved with profit in the cloud. The influence of task scheduling on the system load and performance is more. And so the task scheduling is considered crucial in cloud computing [1 –5]. Some of the traditional scheduling algorithms are round robin [29], FIFO [30], etc. On meeting the user requirement, the task scheduling must also improve the efficiency of the whole system [8]. Now a day, the numbers of the cloud centers are growing so that the efficiency, throughput and resource utilization of the cloud computing needs to be evolved [9]. The dynamic nature of the cloud environment has imperative action on scheduling [7]. The scheduling algorithm in the cloud is divided into two types; accurate algorithm and heuristic algorithm (rule based) [10]. Accurate algorithm intends to find the accurate solution for the task scheduling whereas the heuristic algorithms intends to achieve an acceptable solution but not the accurate solution. The parameters reflected for the task scheduling is significant. Most of the existing scheduling algorithm [11 –18] considers various parameters like time, cost, makespan, speed, scheduling success rate, resource utilization and so on as objective function. Even though different objectives are considered, the trade-off verdict between the parameters for the effective cloud is tough [11].

Because of varying nature, the task scheduling in the cloud is considered as a multi-objective optimization problem which is a NP-hard problem. And also it is conferred as multi-objective optimization problem so that multiple parameters are indulged for the trade-off in order to attain proper task scheduling. To solve the multi-objective problem, many of the states of art research work based on optimization algorithm like probabilistic and uncertain global optimization problems [19] have been proposed. The most common meta-heuristic techniques applied to task scheduling problems in grid and cloud computing are Genetic Algorithm (GA) [1], Particle Swarm Optimization (PSO) [20], and Ant Colony Optimization (ACO) [21]. PSO converges faster and obtains better solution than GA and ACO due to its exploratory capability for finding optimal solutions [21]. However, the search space limitation in optimization algorithm may result in faulty resource allocation for subtask.

2 FGMTS Model structure

The proposed FGMTS model structure for task scheduling in the cloud computing environment is presented in this section. The system framework for the proposed model is shown in Fig. 1.

Fig.1

FGMTS model structure.

Here, the user submitted request tasks are sent to cloud environment via a user interface (internet). In the cloud, the submitted tasks are accepted by the task buffer and managed by task manager. The task manager monitors the condition of physical serves and manages to obtain their CPU and memory information. And the information of the local resources is fed to the scheduler; FGMTS Scheduler (Fractional Grey wolf Multi-objective task scheduler).

The FGMTS scheduler is the proposed scheduler for allocating resources for submitted tasks. The sole responsibility of FGMTS is to allocate resources using the optimization scheduling method. The scheduling algorithm comprises the integration of fraction theory and grey wolf optimization algorithm. Based on the collected information from the task manager, if the particular resource of the server meets the requirements of the task, the resource is allocated by the scheduler. The requirements of task are fulfilled in such a way by employing multi-objective functions improving the performance of the cloud. The resources are allocated for task execution with minimal execution time, communication time, energy consumption and better resource utilization with the quality of service constraints. The fractional grey wolf optimization algorithm is implemented in such a way scheduling the tasks only based on their objectives not based on their priorities.

In the proposed scheduling strategy, the task scheduling algorithm is performed with following scenario’s; i)Tasks from the user request is divided into subtasks, and the amount of subtasks derived from each task will be different, ii) data transmission between subtask is possible, iii) The physical servers are heterogeneous and distributed, iv) bandwidth between virtual resources is different and varies over time.

2.1 Cloud setup

The cloud setup model is described in this section. The ultimate aim of the cloud is to allocate the resource for the execution of the user requested application task. The resources for the task execution are provided from the cloud data center. The cloud model is depicted in Fig. 2.

Fig.2

Cloud setup.

In the data center, multiple numbers of physical servers or resources are available. Using virtualization phenomena of cloud, resources are provided as the virtual resources from the physical resources. Each of the physical servers has a different number of virtual resources with different memory capacity, CPU, etc. In Fig. 2, S denotes the Physical server of the data center. The Physical server is represented by S ={ S₁, S₂, …… S_h }. For each Server S, different numbers of virtual machines are available. For the Physical server S₁, two virtual machines are available; similarly, for server S₂, three virtual resources are available and so on. The virtual resource in the physical server is epitomized by M ={ m₁, m₂, … m_j … m_n }. Each of virtual machine M_j has a processing capacity C_j and a resource cost RC_j. Based on processing capacity and resource cost, the input tasks of users are scheduled with virtual resources. If user task needs the virtual machine with more processing capacity, only M with maximal storage capacity is reflected for resource scheduling. The individual tasks are allocated with only one resource from the physical server.

2.2 Task setup

The client request tasks to the cloud are represented by Task, T ={ t₁, t₂, t₃, …… t_i, …… t_m }; m number of tasks. Each of the tasks is divided into a number of subtasks. The total number of subtask in the submitted request is given by; $Number of Subtasks = \sum_{i = 1}^{m} | t_{i} |$

Task setup model is shown in Fig. 3. Here, Task T is given by T ={ t₁, t₂, t₃, … t_m }. Each of tasks is divided into subtasks and is given by; $\begin{matrix} t_{1} = {t_{11}, t_{12}} \\ t_{2} = {t_{21}, t_{22}, t_{23}} \\ ⋮ \\ ⋮ \\ t_{m} = {t_{m_{1}}, t_{m_{L}}}; 1 ⩽ L ⩽ | t_{i} | \end{matrix}$

Fig.3

Task setup.

The bandwidth between two subtasks is given by $B_{i}^{pq}$ ; i = {1, 2, 3, … … M}; p, q = {1, 2, 3, … | t_i |}. The data length of the subtask is represented by ${DL}_{i}^{pq}$ . ${DT}_{i}^{pq}$ is interchange amount of data between subtask $t_{i}^{P}$ and $t_{i}^{q}$ . Each of subtasks is assigned with resources from virtual machines M and can be executed in parallel. The execution time of subtasks on each virtual machine is signified by set_ij = DL_i/ - C_j, where DL is data length of subtask t_i and C is processing capacity of the virtual machine m_j. Since large numbers of tasks are buffered in the cloud as per the submitted user request, the subtask execution time can be expressed by a matrix; SET ={ set_ij }; i = { 1, 2, 3 …, m }; j = { 1, 2, 3 … n }

The relation between the task T and virtual machine M is uttered by making use of a distribution matrix V, and the value of V is given by;

$V = {\begin{matrix} v_{11} & v_{12} & \dots & v_{1 n} \\ v_{21} & v_{22} & \dots & v_{2 n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ ⋮ & ⋮ & ⋮ & ⋮ \\ v_{m 1} & v_{m 2} & \dots & v_{mn} \end{matrix}}$ (1)

The elemental value of distribution matrix depends on the ability of task and virtual resource. The value of v_ij is 1 only if the task t_i (subtask) is allocated with resources by m_j. The term $W_{i}^{pqrs}$ states the condition whether subtasks of a task is allocated with resources from the same data center. The value of $W_{i}^{pqrs}$ is given by; $W_{i}^{pqrs} = {\begin{matrix} 1, if v_{ir} = v_{is} = 1 & r \neq s \\ 0, Otherwise \end{matrix}}$ (2)

Each of virtual resources has the cost of transmission of data per unit time, i.e., TC. Based on transmitting cost, resources will be selected centered on the user budget. If the user budget is hefty, the virtual resources with high transmitting cost are provided for the execution of application task, and if user budget is low, resource nodes with low transmitting cost are selected for execution.

3 Multi-objective formulation

The multi-objective formulation proposed for the FGMTS scheduling strategy is discussed in this section.

The motive for the consideration of multi-objective formulation approach is that instead of seeking an optimal solution based on single objective, multi-objective optimization approach aims to get the optimal solution based on multiple objectives [14]. However in multi-objective optimization approach solutions inherited with all objectives are difficult to attain. But the solution can be designated without worsening other objective in the multi-objectives considered, improving the performance of the cloud [23]. The proposed multi-objective model approach made a fine grain estimate of real infrastructure usage aiding in proper estimation of optimal schedule that would be consumed for each run of an application through the allocation of resources with minimal execution and communication cost and time, energy consumption, and resource utilization.

The multi-objective formulated for optimization includes the constraints related to the Quality of Service, Cost, System performance, energy consumption, completion time, etc. The main targets as the objectives in the proposed multi-objective optimization algorithm are execution time, communication time, execution cost, communication cost, energy consumption, and resource utilization. The utmost intention is to minimize the execution, communication time and cost, minimize energy consumption, and to maximize resource utilization. Consequently, six objectives are considered in the proposed multi-objective formulation approach. The objective regarding constraints of cost, time, energy consumption, resource utilization are reflected below:

Objective 1: Objective 1 considered is the execution time of the virtual resource m_j. For a successful run of user application task, the execution time of Virtual resource should be low. The execution time is the time required for execution of the user application task with the allocation of resources. The execution time rents for the distribution matrix value and execution time of each subtasks. Increase in execution time of task over-exploits the resources of data center degrading the performance of cloud. The execution time of virtual machine m is defined as follows; ${RET}_{j} = \frac{1}{max (P) * T} \sum_{i = 1}^{m} v_{ij} * {set}_{ij}$ (3)

Here, V_ij is distribution matrix relating the virtual machine resource & task, P is processing capacity of the resource; T is a number of tasks and set_ij is execution time of subtasks. Since the objective is to obtain the task run with minimum execution time, the objective function is given by; $1; \underset{min}{O_{i}} = Max ({RET}_{j}) (I)$ Objective 2: Objective 2 considered in the multi-objective formulation is communication time. Communication time of a task is the time required for the transmission of data between the virtual resources. Communication time of tasks relies on data length and bandwidth of task and condition of the resource requirement. The communication time is defined by; $CT = \frac{1}{Max (B) * \sum_{i = 1}^{m} | t_{i} |} \sum_{p = 1}^{| t_{i} | - 1} \sum_{q = p + 1}^{| t_{i} |} W_{i}^{pqrs} * (\frac{{DL}^{pq}}{B^{pq}})$ (4) where, DL is data length of subtasks, $W_{i}^{pqrs}$ signifies communication condition if the subtasks of the same task run on different resources and B is the bandwidth of subtasks. The value of $W_{i}^{pqrs}$ is crucial for communication time, if subtasks of a task run on same resources there is no communication required, and the value is equal to 0 nullifying the communication time, but if subtasks relies on different resources communication is necessary and the value of $W_{i}^{pqrs}$ given by Equation (2); $\begin{matrix} \sum_{r = 1}^{n} \sum_{s = 1}^{n_{p}} W_{i}^{pqrs} = 1; \forall p, q = {1, 2, \dots, | t_{i} |} \\ r \neq s \end{matrix}$ where, r and s are data center of task i i.e. v_ir and v_is. The objective is to minimize communication time in task scheduling and the objective function related to communication time is given by; $2; \underset{Min}{O_{2}} = Max ({CT}_{i}) II)$ Objective 3: Objective 3 considered in the multi-objective formulation is execution cost. The cost required for execution of all subtasks in the task buffer is called the execution cost. Execution cost of the virtual resource provider depends on execution time exploited by resource and resource cost of the virtual machine. The execution cost of task T by virtual resource M_j is defined by; ${EC}_{j} = \frac{1}{M} \sum_{j = 1}^{n} {RET}_{j} \times {RC}_{j}$ (5) where, RET is execution time of the virtual machine, RC is resource cost of the virtual machine. The objective function 3 is given by; $3; \underset{min}{O_{3}} = {EC}_{j} III)$ Objective 4: Objective function 4 considered in the proposed Multi-objective formulation is communication cost. Communication cost is the cost of task communication time and the cost of transmitting data per unit time. The communication cost of the task should be low for better cloud performance. The communication cost depends on the size of the task [24]. The communication cost is defined by; ${CC}_{i} = \frac{1}{T} \sum_{i = 1}^{m} {CT}_{i} \times {TC}_{i}$ (6) Here, CT_i is communication time of the task and TC_i represents the cost of transmitting data per unit time, T is a number of tasks. The objective function is given by; $4 \underset{min}{O_{4}} = {CC}_{i} IV)$ Objective 5: Objective 5 considered in proposed multi-objective formulation approach is energy consumption. The energy consumed for the execution of subtask t present in task buffer by virtual machine m from data center is called energy consumption. To calculate the total energy consumed, the energy consumed by task and the distribution matrix has to be calculated. The total energy consumed for execution all tasks in task scheduling is defined by; $E = \frac{1}{M * T} \sum_{i = 1}^{m} \sum_{j = 1}^{n} v_{ij} * e_{ij}$ (7) Here, V_ij is distribution matrix, and e_ij is energy consumed by m_j for execution of the task t_i. The objective function concerned with energy consumption is given by; $5; \underset{min}{O_{5}} = EV)$ Objective 6: Objective function 6 considered in proposed multi-objective formulation model is resource utilization. Resource utilization must be maximal for better performance of cloud. All resources in data centers must be properly utilized for execution of tasks. If the resource requirement of an application task is not fulfilled, time and cost of execution of task increases. The resource utilization is defined by; $RU = \frac{\sum_{j = 1}^{n} O_{1} - {RET}_{j}}{M \times O_{1}}$ (8) Here, O₁ is objective 1 related to execution time (maximal), RET of virtual machine and M is a total number of virtual resources. The objective function concerned with resource utilization is given by; ${O_{6}}_{min} = RUVI)$ These 6 objective functions are modeled as the multi-objective formulation for task scheduling strategy of the cloud. The trade-off between the focused objective-functions is considered for optimal schedule attainment in proposed task schedulingalgorithm.

4 FGMTS strategy

The proposed FGMTS task scheduling strategy using optimization algorithm is discussed in this section.

The Task scheduling algorithm requires us to find the optimal solution from a large number of feasible solutions in search space. Many of heuristic algorithms are used for the task scheduling algorithm such as genetic algorithm (GA) [25], Ant Colony optimization algorithm (ACO) [12], Particle Swarm optimization algorithm (PSO) [11], etc. But in the existing optimization algorithms, local optima problem and handling of multi-objectives are difficult. In this paper, task scheduling in the cloud is performed using the proposed FGMTS algorithm. Optimization algorithm developed is the integration of fractional theory [28] and fractional grey wolf optimization algorithm [26].

a) Solution Encoding:

In proposed FGMTS algorithm, a possible solution is in the form of the grey wolf population. The encoding means to denote the possible solution of optimization.

b) Fitness Evaluation:

The fitness evaluation is an important step in proposed fractional multi-objective grey wolf optimization algorithm. The fitness value is used to evaluate the user experience. The grey wolf population with higher fitness value have a greater probability to be inherited as the optimal resource for task execution. In the user experience, the task execution should be done with minimal cost, time and energy, and maximal resource utilization. In this paper, we choose 6 of formulated Multi-objective as evaluation criteria to conduct the multi-objective optimization.

The solution vector of the FGMTS algorithm is converted into distribution matrix V_ij which expresses the relation between task and virtual resource. Using the data length of task and processing capacity of virtual resource, the execution time of the task is also calculated. The value of V_ij and set_ij are calculated for computation of fitness value of concerned solution vector chosen as the optimal schedule. The fitness evaluation function is given by; $= \frac{1}{6} \sum_{g = 1}^{6} w_{g} * O_{g} VII)$ where, w_g is weight function for constraints consideration and O_g is objective function formulated. For g = 1,2,3,4,5,6, the objective function O₁, O₂, O₃, O₄, O₅, and O₆ are calculated using Equations (1– 6) respectively. The solution vector with minimal fitness function is chosen as the optimal schedule for execution of user request application tasks. a) FGMTS-Algorithm The proposed multi-objective fractional grey wolf optimization algorithm for task scheduling is described in this section. The proposed FGMTS is the integration of fractional theory [28] and grey wolf optimization algorithm [26]. Grey Wolf optimization algorithm is based on the social hierarchy behavior (leadership) and hunting technique of grey wolf. The concept of position updation of the grey wolf inside the space around the prey in any random location is used to find the best solution. In perspective of task scheduling, the solution is a grey wolf with a best fitness function. By considering multiple objectives as a fitness function for solution updation of the grey wolf, the proposed optimizer is named multi-objective grey wolf optimizer. It is integrated with a fractional theory to increase the search space of the grey wolf and to reduce the convergence problem. The subtasks which need the resource for execution are given as the input to the optimization algorithm. The grey wolf population is solution vector corresponding to subtask sets, and optimal schedule of the task is obtained by fractional position updation. The steps involved in the FGMTS algorithm are given below: Step 1. Population and Parameter Initialization The population of grey wolf is initialized randomly. H represents grey wolf population with population size of M, and it is given by; $H_{i}^{t} = {h_{1}^{t}, h_{2}^{t}, \dots \dots, h_{M}^{t}}$ (9) The parameters a, vector A and C, the maximum number of iterations ‘N_max’ are also initialized. The adaptive values of A and a assists in solution updation of population abetting to the optimal solution. The values of parameters A and C are A = 2a · r₁ -. a and C = 2. r₂, where {r₁, r₂} are random vectors in the interval [0, 1] and the value of a lies between [0, 2]. The C vector value gives a random weight for the wolf to overcome the convergence problem. Step 2. Fitness Calculation The fitness of grey wolf (search agents) in population is calculated using the fitness Equation (7) given in fitness evaluation section. The grey wolf with best fitness values are chosen as the alpha, Beta and Delta grey wolfs. The best three grey wolfs with best fitness value is given by; H_α, H_β, H_δ and the remaining grey wolfs in an initialized population with low fitness value is considered as H_ω(Omega grey wolf). Step 3. Fractional Position Updation Each of H_ω in population, update the position based on values of H_α, H_β, and H_δ. The position updation of omega grey wolfs increase the probability of attaining a best solution. The position updation of omega grey wolf in the proposed FGMTS algorithm is done using fractional calculus theory [28]. Fractional calculus is an extension of Integral and differential calculus. Adaptation of Fractional calculus increases the convergence rate of conventional grey wolf optimizer. The search space of omega grey wolf also gets increased because of fractional theory. The position updation of omega wolf is done using equation; ${\vec{H}}^{t + 1} = \frac{\vec{H_{1}} + \vec{H_{2}} + \vec{H_{3}}}{3}$ (10) The value of H₁, H₂, and H₃ depends on encircling behavior of alpha, beta and delta grey wolfs. The encircling behaviour of alpha, beta, and delta grey wolf is modeled [27] as; $D_{α} = \vec{C_{1} \cdot} \vec{H_{α}} - \vec{H^{t}}$ (11) $D_{β} = \vec{C_{2} \cdot} \vec{H_{β}} - \vec{H^{t}}$ (12) $D_{δ} = \vec{C_{3} \cdot} \vec{H_{δ}} - \vec{H^{t}}$ (13) The value of $\vec{H_{1}}$ is given by; $\vec{H_{1}} = \vec{H_{α}} - \vec{A_{1}} . D_{α}$ (14) Substituting (11) in (14) $\vec{H_{1}} = \vec{H_{α}} - \vec{A_{1}} \vec{C_{1} \cdot} \vec{H_{α}} + \vec{A_{1}} \vec{H^{t}}$ (15) Similarly, values of $\vec{H_{2}}$ , and $\vec{H_{3}}$ is obtained as; $\vec{H_{2}} = \vec{H_{α}} - \vec{A_{2}} \vec{C_{2} \cdot} \vec{H_{β}} + \vec{A_{2}} \vec{H^{t}}$ (16) $\vec{H_{3}} = \vec{H_{δ}} - \vec{A_{3}} \vec{C_{3} \cdot} \vec{H_{δ}} + \vec{A_{3}} \vec{H^{t}}$ (17) By substituting the values of $\vec{H_{1}}, \vec{H_{1}}, and \vec{H_{3}}$ in position updation Equation (10), we get; $\vec{H^{t + 1}} = \frac{1}{3} [\begin{array}{l} \overset{}{\vec{H_{α}} - \vec{A_{1}} (\vec{C_{1} \cdot} \vec{H_{α}} - \vec{H^{t}})} + \vec{H_{β}} - \vec{A_{2}} (\vec{C_{2} \cdot} \vec{H_{β}} - \vec{H^{t}}) + \\ \vec{H_{δ}} - \vec{A_{3}} (\vec{C_{3} \cdot} \vec{H_{δ}} - \vec{H^{t}}) \end{array}]$ (18) The order of the original solution updation derivative is rearranged in order to adopt the fractional theory, and on rearranging the above Equation (18); we get, $\begin{array}{l} \vec{H^{t + 1}} - \vec{H^{t}} = [\vec{H^{t}} (\vec{A_{1}} + \vec{A_{2}} + \vec{A_{3} - 1})] + \\ [(\vec{H_{α}} + \vec{H_{β}} + \vec{H_{δ}}) - (\overset{}{\vec{A_{1}}} \vec{C_{1} \cdot} \vec{H_{α}} + \vec{A_{2}} \vec{C_{2} \cdot} \vec{H_{β}} + \vec{A_{3}} \vec{C_{3} \cdot} \vec{H_{δ}})] - 2 \vec{H^{t + 1}} \end{array}$ (19) L.H.S of above Equation (19); $(\vec{H^{t + 1}} - \vec{H^{t}})$ is discrete version of derivative of order φ, leading to the following expression; $\begin{matrix} D^{φ} (\vec{H^{t + 1}}) = \vec{H^{t + 1}} - \vec{H^{t}} \\ D^{φ} (\vec{H^{t + 1}}) = \vec{H^{t + 1}} - φ \vec{H^{t}} + \frac{1}{2} φ \vec{H^{t - 1}} \end{matrix}$ The order value φ is generalized between the interval [0, 1]. In perspective off fractional calculus (FC), the discrete version derivative is added to position updation equation increasing the search space of grey wolf, because of inherent memory effect of fractional theory. The FC adapted position updation equation is given below; $\begin{array}{l} \vec{H^{t + 1}} = \frac{1}{3} {\begin{cases} φ \vec{H^{t}} - \frac{1}{2} φ \vec{H^{t - 1}} + \vec{H^{t}} [(\vec{A_{1}} + \vec{A_{2}} + \vec{A_{3}} - 1)] + \\ [(\vec{H_{α}} + \vec{H_{β}} + \vec{H_{δ}}) - (\overset{}{\vec{A_{1}}} \vec{C_{1} \cdot} \vec{H_{α}} + \vec{A_{2}} \vec{C_{2} \cdot} \vec{H_{β}} + \vec{A_{3}} \vec{C_{3} \cdot} \vec{H_{δ}})] \end{cases}} \\ \vec{H^{t + 1}} = \frac{1}{3} {φ \vec{H^{t}} - \frac{1}{2} φ \vec{H^{t - 1}} + \vec{H^{t}} [(\vec{A_{1}} + \vec{A_{2}} + \vec{A_{3}} - 1)] + [G]} \end{array}$ (20) where, $G = (\vec{H_{α}} + \vec{H_{β}} + \vec{H_{δ}}) - (\overset{}{\vec{A_{1}}} \vec{C_{1} \cdot} \vec{H_{α}} + \vec{A_{2}} \vec{C_{2} \cdot} \vec{H_{β}} + \vec{A_{3}} \vec{C_{3} \cdot} \vec{H_{δ}})$ . On considering the term G from above equation; $G = \vec{H_{α}} - \overset{}{\vec{A_{1}}} \vec{C_{1} \cdot} \vec{H_{α}} + \vec{H_{β} - \vec{A_{2}} \vec{C_{2} \cdot} \vec{H_{β}}} + \vec{H_{δ}} - \vec{A_{3}} \vec{C_{3} \cdot} \vec{H_{δ}}$ (21) By rearranging, Equations (15– 17), we get $\begin{matrix} \vec{H_{1}} - \vec{A_{1}} \vec{H^{t}} = \vec{H_{α}} - \vec{A_{1}} . \vec{C_{1} \cdot} \vec{H_{α}} \\ \vec{H_{2}} - \vec{A_{2}} \vec{H^{t}} = \vec{H_{α}} - \vec{A_{2}} . \vec{C_{2} \cdot} \vec{H_{β}} \\ \vec{H_{3}} - \vec{A_{3}} \vec{H^{t}} = \vec{H_{δ}} - \vec{A_{3}} . \vec{C_{3} \cdot} \vec{H_{δ}} \end{matrix}}$ (22) Substituting Equations (22) in (21); $\begin{matrix} G = \vec{H_{1}} - \vec{A_{1}} \vec{H^{t}} + \vec{H_{2}} - \vec{A_{2}} \vec{H^{t}} + \vec{H_{3}} - \vec{A_{3}} \vec{H^{t}} \\ G = \vec{H_{1}} + \vec{H_{2}} + \vec{H_{3}} - (\vec{A_{1}} \vec{H^{t}} + \vec{A_{2}} \vec{H^{t}} + \vec{A_{3}} \vec{H^{t}}) \\ G = \vec{H_{1}} + \vec{H_{2}} + \vec{H_{3}} - \vec{H^{t}} (\vec{A_{1}} + \vec{A_{2}} + \vec{A_{3}}) \end{matrix}$ (23) By substituting the value of G in position updation Equation (20); $\begin{matrix} \vec{H^{t + 1}} = \frac{1}{3} {\begin{matrix} φ \vec{H^{t}} - \frac{1}{2} φ \vec{H^{t - 1}} + \vec{H^{t}} [(\vec{A_{1}} + \vec{A_{2}} + \vec{A_{3}} - 1)] + \\ [\vec{H_{1}} + \vec{H_{2}} + \vec{H_{3}} - \vec{H^{t}} (\vec{A_{1}} + \vec{A_{2}} + \vec{A_{3}})] \end{matrix}} \\ \vec{H^{t + 1}} = \frac{1}{3} {φ \vec{H^{t}} - \frac{1}{2} φ \vec{H^{t - 1}} - \vec{H^{t}} + (\vec{H_{1}} + \vec{H_{2}} + \vec{H_{3}})} \end{matrix}$ (24) Equation (24) is fractionally updated position equation of grey wolf, using which the omega wolf in the population updates the position. Step 4. Solution Updation After the position updation of omega wolfs, the parameter a is decreased from 2 to 0. Upon decreasing a value, the vector values A and C are updated, and the fitness of position updated population with varying parameter values are calculated using equation (VII). Based on fitness, new solutions H_α, H_β, and H_δ are updated. Step 5. Termination Step 3 and 4 are iterated updating the position and solution of the grey wolf population until the termination criteria is achieved i.e. $\begin{matrix} t = t + 1 untill \\ t < N_{max} \end{matrix}$ (25)H_α with the best fitness is chosen as the best solution. In our perspective, the best H_α solution is selected as the optimal schedule for the taskscheduling.

5 Results and discussion

The result and discussion of experimentation of proposed task scheduling strategy using F-MOGWO algorithm are presented in this section.

A) Experimental set up:

The runtime environment of the proposed task scheduling algorithm is windows 10 with Intel i-3 core processor, 2 GB RAM, and the implementation of the proposed algorithm is performed using Cloudsim tool with Java. The experimentation of proposed FMTS strategy is performed over two cloud setups. The description of cloud setup considered for experimentation is given below;

Setup 1:

Cloud setup 1 consists of 5 physical servers, providing resources for task execution via 14 virtual machines. The user application request consists of 5 tasks which are subdivided into 17 subtasks.

Setup 2:

Cloud setup 2 consists of 10 physical servers with 24 virtual machines for providing resources for task execution. The user application requests with 10 tasks which are subdivided into 28 subtasks are considered in cloud setup 2.

B) Comparative Methods:

The performance of proposed task scheduling algorithm using FGMTS is validated over the existing task scheduling algorithms using PSO [11], GA [25], and conventional Grey Wolf optimizer.

C) Performance measures:

The performance evaluation of comparative methods is analyzed using the formulated objective functions regarding measures such as Execution Time, Communication Time, Execution Cost, Communication cost, Energy consumption and resource utilization.

5.1 Performance evaluation

The performance evaluation of proposed FGMTS task scheduling algorithm over the existing methods using formulated objective functions is presented in this section.

i) Analysis based on objective 1:

The analysis based on objective function 1 over experimentation of cloud setup 1 and cloud setup 2 is presented below. Objective function 1 resembles the minimal execution time value. The evaluation chart for analysis based on execution time is given in Fig. 4. The experimentation is performed for five iterations (t = 1, 2, 3, 4 and 5). Figure 4a represents execution time evaluation chart for cloud setup 1. At iteration t = 1, the minimal execution time value of 0.4484 is attained by proposed FGMTS method. But the value 0.715, 0.4861, and 0.4516 attained by existing PSO, GA and GWO methods respectively are larger than that of ET value attained by the proposed method. Similarly, for iteration t = 2, 3, 4, and 5, the ET value attained proposed FGMTS method is 0.4484 which is lower than values of existing methods. Figure 4b represents execution time evaluation chart for cloud setup 2. At t = 1, the execution time (ET) of existing PSO, GA and GWO method is 0.3125, 0.3125 and 0.286 respectively, whereas the proposed FGMTS method attained the ET of 0.2246 which is less than that of existing methods. Similarly, for t = 2, 3, 4 and 5, ET attained by proposed FGMTS is 0.1949, 0.2808, 0.1906, and 0.2221 respectively which is minimal than that of objective function 1 attained in the existing methods. The best case ET value of 0.1906 is attained by the proposed method at iteration t = 4 and the worst case ET value of 0.3125 is attained by PSO method for all iterations considered for experimentation.

Fig.4

Evaluation based on execution time.

ii) Analysis based on objective 2:

In this section, the performance validation of comparative methods based on objective function 2 is discussed. Objective function 2 resembles the minimal communication time. The evaluation chart based on communication time for setup 1 and setup 2 is depicted in Fig. 5a and b respectively. For cloud setup 1, at iteration t = 1, the communication time value attained by the existing methods PSO, GA, and GWO is 0.1814 respectively, whereas the proposed FGMTS method attained the CT value of 0.1814 which is same as that of value attained by existing methods. For consecutive iterations t = 2, 3, 4, and 5, the CT value attained by proposed and existing method remains same. The same CT value proves the fact that proposed FGMTS algorithm doesn’t degrade below the existing methods. For cloud setup 2, at iteration t = 1, the CT attained by the proposed FGMTS method is 0.1747, at the same time CT value attained by existing method PSO, GA and GWO is 0.1747 respectively. For entire iterations considered for experimentation, CT value attained by all comparative methods is equal. By totaling the communication time of existing method, the proposed FGMTS method proves the ability in task scheduling algorithm ofthe cloud.

Fig.5

Evaluation based on communication time.

iii) Analysis based on objective 3:

The evaluation based on objective function 3 is deliberated in this section. Objective function 3 resembles the minimal execution cost. Figure 6a and b represent the evaluation chart for analysis based on execution cost for cloud setup 1 and cloud setup 2 respectively. From Fig. 6a, it is evident that, at t = 1, the execution cost value attained by the proposed method is 0.0814 whereas the existing methods PSO, GA and GWO attained EC value of 0.0856, 0.0861, and 0.0854 respectively. The EC value of proposed FGMTS method is minimal compared to EC value of existing methods. For iteration t = 3, 4, and 5, the EC value attained by existing methods PSO, GA and GWO is 0.09, 0.0861, and 0.0854 respectively which is greater than value 0.0814 attained by proposed FGMTS. From 6b, it is clear that for cloud setup 2, at iteration t = 1, the execution cost value attained by the existing methods PSO, GA, and GWO is 0.0175, 0.0146, and 0.0187 respectively, whereas the proposed FGMTS method attained the execution cost of 0.0178. With the increase in the iteration, the EC values of existing PSO and GWO remains same. But the EC value of GA falls for consecutive iterations compared to PSO and GA. However, the EC value attained by the proposed FGMTS method for iterations t = 2, 3, 4, and 5 is lower than that of existing methods proving the efficacy of proposed scheduling algorithm.

Fig.6

Evaluation based on execution cost.

iv) Analysis based on objective 4:

In this section, the analysis based on objective function 4 is presented. Objective function resemblesminimal communication cost for task execution in the cloud. The evaluation chart for analysis based on communication cost is given in Fig. 7. For cloud setup 1 as shown in 7a, at t = 1, the CC value attained by proposed FGMTS method is 0.009 less than value attained by existing PSO and GA method and 0.0057 less than value attained by GWO method. Likewise, for iteration t = 2, the CC value attained by existing methods PSO, GA, and GWO is 0.109, 0.109, and 0.1057 respectively, whereas the proposed FGMTS method attained the CC value of 0.1 which is minimal than the value attained by existing methods. For consecutive iterations, the CC value of proposed methods seems minimal compared to the value of PSO, GA and GWO method. For cloud setup 2, as shown in Fig. 7b, at t = 1, the communication cost value attained by the proposed method is 0.087, whereas the existing method PSO, GA and GWO attained the CC value of 0.09, 0.0871 and 0.0871 respectively which are greater than the value achieved by the proposed method. Greater the communication cost, worse the performance of cloud. At iteration t = 2, 3, 4, and 5, the CC value remains the same as attained in iteration 1. The best case CC value of 0.087 is attained by proposed FGMTS method for all iterations, and the worst case CC value of 0.09 is attained by existing PSO method for all iterations.

Fig.7

Evaluation based on communication cost.

5.2 Comparative discussion

Table 1 shows the comparative discussion of the proposed method with the existing methods for setup 1 and setup 2. For setup 1, the existing methods, such as PSO, GA, and GWO have the execution time of 0.4681, 0.4681, and 0.4516 respectively. On the other hand, the proposed FGMTS has the execution time of 0.4484. The existing methods, like PSO, GA, and GWO and the proposed method have the communication time of 0.1814. The proposed FGMTS has the execution cost of 0.0814 while the existing methods, PSO, GA, and GWO have the execution cost of 0.0768, 0.0861, and 0.0854.The proposed method has the minimum communication cost of 0.1 than the existing methods. The existing methods, such as GA, and GWO have the energy consumption of 0.0336 and 0.3145 but the proposed method has the minimum energy consumption of 0.3048. Similarly, the proposed method has the minimum resource utilization of 0.5674 than the existing methods, such as GA and GWO. Similarly, for setup 2, the proposed method has the better performance than the existing methods by obtaining the minimum execution time, execution cost, communication cost, energy consumption, and resource utilization.

Table 1
Comparative Discussion of the proposed method with the existing methods

Objectives PSO GA GWO FGMTS

Setup 1 Execution time 0.4681 0.4681 0.4516 0.4484

Communication time 0.1814 0.1814 0.1814 0.1814

Execution Cost 0.0768 0.0861 0.0854 0.0814

Communication Cost 0.109 0 0.109 0 0.1057 0.1 000

Energy Consumption 0.0287 0.0336 0.3145 0.3048

Resource utilization 0.5615 0.5976 0.5751 0.5674

Setup 2 Execution time 0.3125 0.2816 0.2816 0.1906

Communication time 0.1747 0.1747 0.1747 0.1747

Execution Cost 0.0175 0.0146 0.0187 0.0178

Communication Cost 0.09 00 0.0871 0.0871 0.087 0

Energy Consumption 0.0142 0.0131 0.0123 0.0122

Resource utilization 0.8945 0.8867 0.8867 0.8857

	Objectives	PSO	GA	GWO	FGMTS
Setup 1	Execution time	0.4681	0.4681	0.4516	0.4484
	Communication time	0.1814	0.1814	0.1814	0.1814
	Execution Cost	0.0768	0.0861	0.0854	0.0814
	Communication Cost	0.109 0	0.109 0	0.1057	0.1 000
	Energy Consumption	0.0287	0.0336	0.3145	0.3048
	Resource utilization	0.5615	0.5976	0.5751	0.5674
Setup 2	Execution time	0.3125	0.2816	0.2816	0.1906
	Communication time	0.1747	0.1747	0.1747	0.1747
	Execution Cost	0.0175	0.0146	0.0187	0.0178
	Communication Cost	0.09 00	0.0871	0.0871	0.087 0
	Energy Consumption	0.0142	0.0131	0.0123	0.0122
	Resource utilization	0.8945	0.8867	0.8867	0.8857

6 Conclusion

In this paper, a novel multi-objective scheduling strategy, FGMTS was proposed. The proposed scheduling algorithm is the combination of the fractional theory and Grey Wolf optimization algorithm. The integration of the fractional theory and Grey Wolf optimization algorithm increased the convergence in attaining an optimal solution. The fitness function adopted in the proposed FGWO algorithm obtained the optimal solution with maximized resource utilization increasing the profit of the cloud provider and with minimized execution time, communication time, execution cost, communication cost and energy. Thereby, task scheduling was done with a proper trade-off between multiobjective parameters. The experimentation of the proposed FGWO-MT Strategy is performed over two cloud setups. The performance of the proposed task scheduling strategy is compared over the existing technique using the measures execution time, communication time, execution cost, communication cost, resource utilization rate, and energy. The experimental results show that FGWO based MTS algorithm is an effective scheduling algorithm, producing more stable and acceptable schedules for the user application task.

References

Buyya

, Yeo

C.S.

, Venugopal

, Broberg

and Brandic

, Cloud computing and emerging IT platforms: Vision, hype and reality for delivering computing as the 5th utility, Future Generation Computing System 25(6) (2009), 599–616.

Boss

, Malladi

, Quan

, Legregni

and Hall

, Cloud computing, IBM White Paper 321 (2007), 224–231.

Sanaei

, Abolfazli

, Gani

and Buyya

, Heterogeneity in mobile cloud computing: Taxonomy and open challenges, IEEE Communications Surveys Tutorials 16(1) (2014), 369–392.

Mollah

M.B.

, Islam

K.R.

and Islam

S.S.

, Next generation of computing through cloud computing technology, In Proceedings of IEEE Canadian Conference on Electrical and Computer Engineering 2012, pp. 1–6.

and Zhang

, An improved genetic-based approach to task scheduling in inter cloud environment, International Journal of Computer Science and Software Engineering (IJCSSE) 5(3) (2016), 28–35.

Sridhar

, Rama Mohan Babu, G., Hybrid Particle Swarm Optimization Scheduling for Cloud Computing, In Proceedings of IEEE International Conference on Advance Computing 2015, pp. 1196–1200.

Takabi

and Joshi

J.B.D.

, Security and privacy challenges in cloud computing environments, IEEE Security & Privacy 8(6) (2010).

Zhu

, Leung

V.C.M.

, Hu

, Shu

and Yang

L.T.

, A review of key issues that concern the feasibility of mobile cloud computing, In Proceedings of IEEE International Conference on Cyber, Physical and Social Computing 2013, pp. 769–776.

Ahmed

and Hossain

M.A.

, Cloud computing and security issues in the cloud, Network Security & Its Applications 6(1) (2014), 25–36.

10.

Ming

and Li

, An improved algorithm based on max-min for cloud task scheduling, Recent Advances in Computer Science and Information Engineering 125 (2012), 217–223.

11.

Awad

A.I.

, El-Hefnawy

N.A.

and Abdel_kader

H.M.

, Enhanced particle swarm optimization for task scheduling in cloud computing environments, Procedia Computer Science 65 (2015), 920–929.

12.

, Xu

, Pang

and Zhao

, AMTS: Adaptive multi-objective task scheduling strategy in cloud computing, China Communications 13(4) (2016).

13.

Rodriguez

M.A.

and Buyya

, Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds, IEEE Transactions on Cloud Computing 2(2) (2014), 222–235.

14.

Tsai

J.-T.

, Fang

J.-C.

and Chou

J.-H.

, Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm, Computers & Operations Research 40(12) (2013), 3045–3055.

15.

Zhu

, Zhang

, Li

and Liu

, Evolutionary multi-objective workflow scheduling in cloud, IEEE Transactions on Parallel and Distributed Systems 27(5) (2015), 1344–1357.

16.

Kim

S.-S.

, Byeon

J.-H.

, Yu

and Liu

, Biogeography-based optimization for optimal job scheduling in cloud computing, Applied Mathematics and Computation 247 (2014), 266–280.

17.

Vasile

M.-A.

, Pop

, Tutueanu

R.-I.

, Cristea

and Kołodziej

, Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing, Future Generation Computer Systems 51 (2015), 61–71.

18.

Zuo

, Shu

, Dong

, Zhu

and Hara

, A multi-objective optimization scheduling method based on the ant colony algorithm in cloud computing, IEEE Transactions 3 (2015), 2687–2699.

19.

Lakra

A.V.

and Yadav

D.K.

, Multi-objective tasks scheduling algorithm for cloud computing throughput optimization, Procedia Computer Science 48 (2015), 107–113.

20.

Wang

and Zeng

, A comparison of four popular heuristics for task scheduling problem in computational grid, In Proceedings International Conference on Wireless Communications Networking and Mobile Computing 2010, pp. 1–4.

21.

Xue

, Li

, Xu

and Jingyi

, An ACO-LB algorithm for task scheduling in the cloud environment, Journal of Software 9(2) (2014), 466–473.

22.

Abdullahi

, Ngadi

M.A.

and Abdulhamid

S.M.

, Symbiotic organism search optimization based task scheduling in cloud computing environment, Future Generation Computer Systems 56 (2016), 640–650.

23.

Habibi

and Navimipour

N.J.

, Multi-objective task scheduling in cloud computing using an imperialist competitive algorithm, International Journal of Advanced Computer Science and Applications 7(5) (2016).

24.

Kurunji

, Ge

, Liu

and Chen

C.X.

, Communication Cost Optimization for Cloud Data Warehouse Queries, In Proceedings of IEEE International Conference on Cloud computing Technology and Science 2012, pp. 512–519.

25.

Omara

F.A.

and Arafa

M.M.

, Genetic algorithms for task scheduling problem, Journal of Parallel and Distributed Computing 70(1) (2010), 13–22.

26.

Mirjalili

, Mirjalili

S.M.

and Lewis

, Grey wolf optimizer, Advances in Engineering Software 69 (2014), 46–61.

27.

Mirjalili

, Saremi

, Mirjalili

S.M.

and Coelho

L.D.S.

, Multi-objective grey wolf optimizer: A novel algorithm for multi-criterion optimization, Expert Systems with Applications 47 (2016), 106–119.

28.

Solteiro Pires

E.J.

, Tenreiro Machado

J.A.

, de Moura Oliveira

P.B.

, Boaventura Cunha

and Mendes

, Particle swarm optimization with fractional-order velocity, Nonlinear Dynamics 61(1-2) (2010), 295–301.

29.

Chen

, DeWitt

, Tian

, Wang

and Niagara

C.Q.

, A scalable continuous query system for internet databases, In Proceedings of ACM SIGMOD 2000, pp. 379–390.

30.

Dan

and Towsley

, An approximate analysis of the lru and fifo buffer replacement schemes, In Proceedings of ACM SIGMETRICS 1990, pp.143–152.