- Cloud computing is one of the fields that has attracted a lot of attention in recent years. Task scheduling meaning the proper permutation of user requests on virtual machines is one of the most important challenges in the cloud environment due to the increase in virtual machines as well as the diversity of users with different service quality requirements and therefore task scheduling is a NP-hard problem. This becomes more complicated when quality of service objectives conflict with each other; therefore, service providers for the proper use of cloud environment capabilities require an optimal trade-off between the various objectives and in such cases heuristic algorithms can be used for optimal scheduling. To this end, we extended a recent heuristic algorithm called Black hole and considered dependency graph of workflow tasks. The proposed method combines the heuristic algorithm and decision-making method (AHP) to solve the multi-objective workflow scheduling problem on virtual machines. We converted the single-objective Black-hole algorithm into a multi-objective by using the AHP relationship, and then it is used to solve the scheduling problem. We have implemented our proposed method using the Workflowsim tool and have compared the results with multi-objective algorithms SPEA2 and NSGA2 based on the parameters of Makespan and cost and resource utilization using a balanced and unbalanced workflow.
INTRODUCTION Workflow is a common model for modeling most scientific programs which contains a number of tasks and data dependencies between tasks. Since most tasks in applications are a set of workflows; in recent years, extensive research has been done on the workflow scheduling in the cloud environment. Workflow scheduling on resources is to select the appropriate virtual machine for a task, so that its related tasks are already executed. This selection of resources and assignment of task on them depends on the requirements of quality of service for different users and since there are different permutation of requests on virtual machines, task scheduling is a NP-hard problem [1].
A great related work has already been done on the workflow scheduling problem in the cloud environment; in most classic work, it is tried to reduce finish time, but in recent ways; in addition to Makespan, there are other objectives, such as resource utilization and cost for scheduling. And they seek to provide an optimal permutation of requests on virtual machines,
in light of these objectives [2]. This problem is presented as multi-objective scheduling, and there are different approaches to solve it. One of these methods is the use of Pareto optimal solutions. This solution allows users to have the best choices from the set of appropriate solution and thus provide a set of ultimate solutions that include optimal tradeoff between some of the QoS objectives.
In this paper we have expanded our previous work [3] which is based on the black hole algorithm [4] and it is a heuristic optimization method which can be used as an appropriate solution to the scheduling problem due to its simple structure and lack of dependence on external parameters and its high performance.
The extension is carried out in 2 aspects: (
Our main contributions can be summarized as follows: 1: Presentation of the multi-objective Black hole algorithm using the single-objective Black hole algorithm and Pareto optimizer and applying it for the multi-objective workflow scheduling in the cloud environment 2: Using the AHP technique in multi-objective domination relationship and taking into account the preferences of users in the solution of workflow scheduling 3: Targeted evaluation and analysis to illustrate the effective combination of the black hole algorithm with AHP technique to reduce Cost of resources and makespan and increase resource utilization.
We have used the WorkflowSim tool [6], which is an extension of CloudSim [7] open source tool, to evaluate our proposed method. We have developed the initial core of this tool to provide our algorithm and then compared our proposed method with previous Pareto-based algorithms such as SPEA2 [8], NSGA2 [9].
The rest of the paper is comprised of the following sections: Section 2 presents the related work of workflow scheduling. In Section 3, the mathematical model of the workflow scheduling problem and the details of the optimization objectives used have been provided and in the fourth section, we first introduced the single-objective black hole algorithm and the AHP technique and then we present the details of the proposed AHP-based multi-objective algorithm, in the fifth part, we have described the details of the evaluation of the proposed method and analyzed the results. Finally, in the final section, conclusions and future work have been presented.
II.
RELATED WORK
Many previous work have been done to solve the problem of task scheduling for independent workload and workflow in the cloud environment; since our proposed approach has been provided for the workflow, we investigate the methods of workload scheduling. There are different types of classification for workflow scheduling methods; for example, static or dynamic scheduling or other categorization based on singleobjective or multi-objective workflow scheduling. In this section, we examine the multi-objective workflow scheduling methods. In multi-objective scheduling, several objective which are often in contradictory have been considered as optimization objectives and provide the optimal tradeoff of solutions. Multiobjective scheduling methods are in the following categories:
One of the multi-objective scheduling methods is to convert a multi-objective problem to a single objective which is done by weighting objectives. In Li et al. [10], have converted the multiobjective problem into a single objective by using the heuristic method CCSH and have provided a scheduling method with cost and Makespan reduction objectives. Dongarra et al. [11] have proposed a scheduling method by using aggregation technique to increase performance and reliability. They have provided (RDLS) a reliable dynamic level scheduling algorithm based on the DLS algorithm [12]. Dogan et al. [13] have improved their method using genetic algorithm and BDLS scheduling method.
Unlike the previous method, in which only one definitive solution is presented as the result of the algorithm. In these methods, a set of non-dominated solutions is provided that allows users to choose a solution based on their expected QoS. Yu et al. [14] have used multi-objective evolutionary algorithms (MOEAs) to solve the workflow scheduling problem. This approach is aimed at reducing two conflicting objectives of cost and runtime. In addition to these two purposes, they also considered deadline and budget constraints in the algorithm and therefore provided fitness functions corresponding to objectives and constraints. The population-based algorithms SPEA2 and NSGAII [8, 9] and local search-based algorithms MOEA, PAES [15] have been provided for workflow scheduling based on different objectives and constraints. Various scheduling methods have been proposed for cost and Makespan reduction using heuristic algorithms and Pareto optimization; such as Udomkasemsub et al. [16] using ABC and WU [17] using the
RDPSO algorithm. Most of the previous methods have only considered two objectives of cost and makeapn reduction as optimization objectives; Khalili et al. [18], in their proposed method, in addition to Makespan and cost, also considered the purpose of resource efficiency and using a gray wolf algorithm, they have introduced a new Pareto-based multi-objective scheduling method. In our proposed approach, in addition to reducing the cost, Makespan that benefits of the users are supplied; increased resource utilization for the benefit of service providers has been considered. The difference of our work with previous methods is to use the new Black Hole heuristic algorithm, which is more efficient than other algorithms and converting it to a multi-objective algorithm is done using the Pareto optimizer. Also, in the proposed algorithm by combining black hole algorithm with the decision-making method (AHP), the QOS preferences are considered by the user during the execution of the algorithm and this will reduce the search space of the problem and choose the more optimal solutions with increasing requests and the variety of virtual machines.
III.
A set of tasks and edges for communication between requests is defined as workflow and in this workflow child request is not allowed to be execute as long as the parent is not executing. Figure 1 illustrates an example of a workflow in which each node represents a task and edges are the connection between tasks and the number above each edge shows the estimated cost for data transfer between the corresponding tasks. In the following, each of the objectives that we have used in the workflow scheduling problem will be explained.
t 0 0 1 2 t 1 t 2 t 3 3 1 1 2 4 t 4 t 5 t 6 0 1 2 t 7
To formulate the problem we have denoted a set of tasks Task = {t1, t2, ..., tn} where i {1, 2,..., n}. We have defined a set of m virtual machines, VM = {VM1, VM2, ...., VMj} interconnected by network where j {1, 2,..., m} . The tasks will be processed on virtual machines. Completion time of task Ti on virtual machine VMj are denoted as CTij respectively. Overall task completion time is called makespan and is defined by Eq. (3-1) (3-1)
n Makespan max CT VM j x ti
ij 1 jm i1 If the request ti is running on VMj, value of xij is equal to 1 otherwise is zero. Figure. 2 epitomizes a sample scheduling makespan for 6 tasks and 3 VMs.
For each virtual machine, resource utilization was defined as the Eq.3-8. Where xij is equal to 1, if the request ti is executing on VMj otherwise is zero.
In cloud computing, computational cost for each customer is calculated based on the timespan they use of resource at any time. Total cost for each request include:
This cost is calculated based on execution time of the request ti on the VMj and cost per processing in VMj by Eq.3-2 and the execution time of the request ti is calculated by Eq.3-3.
(3-2) Cp (ti ) ETtiVMj Cos tPer Pr occes sin ginVmj
(
MI(ti )
While MI (ti) is the number of instructions of request i and MIPS (VMJ) is the number of million instructions that the machine j executes per second.
This cost is calculated based on the time that this task is placed on the virtual machine and it is calculated according to Eq.3-4.
(
(
BW
This costs is dependent on the cost that request ti should pay for the transfer of files to their children which is calculated according to Eq. 3-6.
(
BW
The total cost is calculated by Eq. 3-7. Cloud provider calculates the cost of request ti based on the total cost presented below.
(
Makespan IV.
Heuristic algorithms have been used effectively in most optimization issues. Among them, the Black Hole heuristic algorithms can provide more optimal solutions for workflow scheduling problem in terms of its appropriate structure and efficiency compared to the PSO and GA algorithms. In this section, we have first introduced the standard black hole algorithm and then, after expressing the AHP technique, we present the details of the AHP-based multi-objective black hole algorithm.
The black hole algorithm is a population-based heuristic algorithm which was first presented by Mr. Hamtlou In the first step, this algorithm generates an initial population from candidate solutions (stars) randomly in a sample space. In the workflow scheduling problem on virtual machines, each solution is a permutation of requests on virtual machines. The value of the fitness function is calculated for each star and the star with the best value for the objective function is selected as Black Hole. The black hole is capable of absorbing the stars that have trapped it. After the black hole absorbs the stars around it, the remaining stars move toward the black hole. The motion of the stars towards the black hole is based on Eq. (4-1). i 1, 2,..., N (4-1) xi (t 1) xi (t) rand (xBH xi (t))
Where is the position of the star i at time t and t + 1. xBH is the position of the black hole in the search space and rand is a random number in the range [0,1] and N is the number of stars (candidate solutions).
This evolution of solutions continues until the algorithm termination condition is reached and at any stage, if a star has a better fitness function than a black hole, then that star replaces the black hole. The black hole algorithm can prevent being trapped in the local optimal due to the elimination of the available stars in the range of the best solution and selection the alternate star randomly in search space. The radius of the horizons in the black hole algorithm is calculated using Eq. (42). (4-2) R fBH n fi i1
Where fBH is the fitness of black holes and fi is the fitness function of the star i and n is the number of stars. When the distance between a star and a black hole is less than R, that star is eliminated and a new star is created randomly in search space. B. AHP decision making method
AHP is a multi-criteria decision-making approach which can be used to solve complex decision problems; it was presented by Saaty [5] that has been established based on using a set of pairwise comparisons. The main steps of Analytic Hierarchy Process (AHP) includes making a hierarchy, Assign weight to each metric, investigate the Consistency check of system and ultimately decision-making (determine the priorities of options) B.1: Making hierarchy:
In the first step, the decision-making elements and the relationships between them must be known in order to build hierarchy. So the options that have an impact on decision making are at the lowest level Thus objectives that have an impact on decision making are considered at lower ranks and decision making whole objective is considered at top of the hierarchy, and finally decision-making options are placed in the lowest level. In following an example for workflow scheduling problem which QoS criteria includes Makespan, cost and resource utilization, the hierarchy structure is shown in Figure. 3. In this example Studied options are members of the Pareto front, which indeed one of them should be selected.
Purpose Objective
Pareto optimal Set
Optimal workflow
scheduling Make span S1
S2
Cost …
Resource Utilization
S10 B.2: Weight calculation:
Objectives are compared with each other pairwise to determine the relative priority of each metric (weight), this Pairwise Comparison construct pairwise comparison matrix A. For example, comparing the importance between the Makespan of workflow and its cost indicates that which one has the higher degree of impact in finding the optimal solution. Numbers 1 to 9 are usually used to pairwise comparison. 1 means the same importance and 9 shows the highest degree of importance. Pairwise comparison matrix is shown with = ( ) × and is as follows: a11 A a21 a31 a12 a22 a32 a13
a23 a33 Where aii=1 and aij= 1 a ji
And m is equal to the number of objectives that in this case study is equal to the number of the optimization objectives means 3.
To calculate priority, we use the concepts of Normalization and weighted average. As first the geometric mean of each row has been calculated and then we do normalization. The values obtained from calculations that make up the priority column are called eigenvector (λ). Similarly, we perform priority determination for Pareto optimal set for each criterion. B.3: Consistency check:
Consistency check is one of the advantages of AHP which aims to testing coordination of the important degree between each metric. The concept of consistency can be expressed as if objective A is more important compared to B and objective B is more important compared to the C, the consistency check is established if the A is more important than C . The consistency index (CI) is shown by Equation (4-3)
CR (4-3) CI max m
m 1
And consistency ratio is calculated by Equation (
RI
In Equation (
The final step of analytic hierarchy process includes
determining the importance of each decision-making option in
relation to the criteria and general purpose of desired problem.
The final weight of each option is calculated of sum of
multiplying the priority of objective in weight of options in
accordance with the Equation (
m
(
i1
That Gi is weight of options and Wi is weight of the objective. In this study we have considered the same weight for options that those options are Pareto front in workflow scheduling problem. Members who value of Pi are less than other options are more appropriate than the rest of the members. It should be noted, the inverter form of resource utilization has been used because Makespan and cost should be minimized and resource utilization should be maximize in the optimization of the scheduling problem.
C. AHP base multi objective black hole
Pareto optimal set in heuristic multi-objective algorithms often involves non-dominated solutions and an optimal tradeoff between objectives. Users decide between the optimal solutions, based on their preferences between objectives and choose the right solution which includes permutations of requests on virtual machines. In such cases, in order to choose the right solution among the Pareto optimal set, we need to have a precise weight of the objectives corresponding to user preferences. Without the precise weight of the objectives, choosing the solution proportional with the user's preferences is difficult. That's why users after finding out the set of non-dominated solutions, use AHP-like techniques to choose the optimal solution that suits the user's preferences. We have also used the AHP technique in our proposed method. The difference in our approach with previous works is that we combine the AHP technique with heuristic algorithm but in the previous methods [19], after finding Pareto optimal set in the heuristic algorithm the AHP technique is used. With increasing requests and the diversity of virtual machines, the space of the problem increases and the number of solutions in Pareto optimal set increases. As a result, the AHP technique may not be able to differentiate between solutions [20].
In this paper, we combine the AHP technique with the Black Hole heuristic algorithm and, as a result, a new domination relationship has been proposed that, in the proposed domination relationship, the fitness value of a solution, in addition to the solution strong in dominating other solutions, is selected based on the amount of final weight of that solution obtained by the AHP technique. The details of the proposed algorithm are described in detail:
We have used the Pareto-optimization method to convert the
BH algorithm to PBH algorithm and accordingly, for each star,
we have considered two fitness values of R, S. As for each star,
based on the number of stars in the archives and the population
that this star is dominate, the power of S is calculated. Then, in
the next step, we obtain the value of R for each star with respect
to Eq. (
(
In the above relation, j>i is the symbol of the Pareto domination and j dominate i.
In fact, fitness R for a member is determined by the power
of its dominators in both the population and archive and the
lower R value for each star in Eq. (
The star that has the lowest R amongst all stars in the population and archives is considered as the Black Hole star and then the position of the stars in the initial population is updated according to the position of the black hole. In the next step, equal to the number of members in the archive, members are selected from the top of the arranged list and transferred to the archive set. This cycle of procedures is repeated until the achievement of finish conditions. Non-dominated solutions obtained from solving the multi-objective optimization problem (archives) are often referred to as Pareto fronts. None of the Pareto front solutions are superior to the other and depending on the circumstances, one can consider each as the optimal decision. Algorithm 1 depicts the pseudocode of the AHP Base Multi objective Black hole algorithm.
Algorithm1: AHP base multi objective black hole algorithm pseudo code 1. Create an initial population of star randomly and an empty archive 2. While (t< Max number of iterations) 3. Calculate the fitness function for all stars based on Eq.3-1, 3-7, 3-8 4. Calculate Pareto based fitness function according to Eq.4-6 5. Calculate final weight of each star by using the AHP technique. 6. Copy top ten non-dominated stars in population to the archive which has the smallest R value and the highest AHP weight value 7. Select the star with the best Pareto base fitness function from the archive (Black hole) 8. For each star 9. Update the position of current star according to Eq.4-1 10. Calculate fitness of Pareto according to Eq. 4-6 11. Calculate the distance between each star and the black hole according to the 4-2 12. If(R< distance) 13. Remove star and create a random star in search space 14. End while
To evaluate the proposed methods we have used Open source, WorkflowSim tools, then we have compared our simulation results of the proposed method with known radiationoptimizer-based algorithms SPEA2 [8] and NSGA2 [9].
For evaluation the proposed method we have used a real workflow library presented by Bahraini et al. [21]. We have used balanced (Ligo) and unbalanced workload (Montage) to evaluate the proposed method. Figure.4 shows a small sample of these two workflows.
We have used a data center consists of twenty hosts and 60 virtual machine. Host specification are according to Table 1 and characteristics of virtual machine are presented in Table 2. The input parameters for algorithms PBHO, NSGA2 and SPEA2 are also given in Table 3.
We repeated our experiments ten times and then reported the average data for three factors Makespan, Cost, and resource utilization for two workloads of montage and Ligo in sizes small, medium and large. We have used the decision-making method AHP to weigh the objectives that are used in the proposed multiobjective algorithm. If the importance of each objective to be considered as following, then matrix A will be as follows: The importance of Makespan in comparison with resource utilization: 5, The importance of Cost in comparison with Makespan: 3, The importance of Cost in comparison with resource utilization: 8.
Makespan 1 13 5 A Cos t 3 1 8
1 5 8 TABLE 1 HOSTS' TECHNICAL SPECIFICATIONS
Number of processing
Cores
Processing speed (MIPS)
Weight of Objectives is obtained as w = (0.2718, 0.6612, 0.0670) and the value of CR = 0.04 <0.1, and therefore compatibility is acceptable. Table 4 shows the values of the Makespan, resource utilization and cost for the Spea2, NSGA2, and Black hole algorithms. Compared with the most existing methods, our approaches which apply AHP on calculating the dominance relation in Black hole are able to meet user’s preferences better. Figure 5 shows optimal Pareto front obtained from AHP base multi objective black hole.
As it is clear from the results in Table 4-a and 4-b, the amount of cost in all the workloads in all sizes in AHP base multi objective black hole algorithm is more than other algorithms. Considering that the importance of cost for the user is more than other objectives, the proposed method chooses solutions with the lowest cost.
Figure. 5. Pareto front of AHP base multi objective black hole
CONCLUSION AND FUTURE WORKS
Task scheduling is one of the most important challenges for cloud providers and users. In this paper, we present a multiobjective workflow scheduling method by using the Black hole algorithm. Our proposed method, on the one hand, by reducing Makespan and cost supplies the benefit of users and on the other hand, by increasing resource utilization, considers the benefits of service providers simultaneously. In the proposed method, the Black Hole algorithm has been combined with the concept of AHP and the AHP Base Multi objective Black hole has been provided using Pareto optimizer. Since in cloud environments different users require different QoS requirement, in our proposed method, the AHP decision-making technique has been used in Pareto domination relationship, so that user preferences are taken into consideration in choosing the optimal solution at any stage and as a result, by increasing the search space of the problem, we can find a better Pareto optimal set.
In the future, we plan to consider more objectives and examine the effectiveness of this technique for the many objective problems. We can also use the proposed method for dynamic workflow scheduling. available visited: