=Paper= {{Paper |id=Vol-2145/p06 |storemode=property |title=Optimal Workflow Scheduling In Cloud Computing Using AHP Based Multi Objective Black Hole Algorithm |pdfUrl=https://ceur-ws.org/Vol-2145/p06.pdf |volume=Vol-2145 |authors=Fatemeh Ebadifard,Seyed Morteza Babamir }} ==Optimal Workflow Scheduling In Cloud Computing Using AHP Based Multi Objective Black Hole Algorithm== https://ceur-ws.org/Vol-2145/p06.pdf

Optimal Workflow Scheduling In Cloud Computing
Using AHP Based Multi Objective Black Hole
Algorithm
Fatemeh Ebadifard Seyed Morteza Babamir
Department of Computer, Depertment of Computer
University of Kashan, Kashan, Iran University of kashan, Kashan, Iran
Ebadifard.fatemeh@gmail.com Babamir@kashanu.ac.ir

Abstract— Cloud computing is one of the fields that has attracted in light of these objectives [2]. This problem is presented as
a lot of attention in recent years. Task scheduling meaning the multi-objective scheduling, and there are different approaches to
proper permutation of user requests on virtual machines is one of solve it. One of these methods is the use of Pareto optimal
the most important challenges in the cloud environment due to the solutions. This solution allows users to have the best choices
increase in virtual machines as well as the diversity of users with from the set of appropriate solution and thus provide a set of
different service quality requirements and therefore task ultimate solutions that include optimal tradeoff between some of
scheduling is a NP-hard problem. This becomes more complicated the QoS objectives.
when quality of service objectives conflict with each other;
therefore, service providers for the proper use of cloud In this paper we have expanded our previous work [3] which
environment capabilities require an optimal trade-off between the is based on the black hole algorithm [4] and it is a heuristic
various objectives and in such cases heuristic algorithms can be optimization method which can be used as an appropriate
used for optimal scheduling. To this end, we extended a recent solution to the scheduling problem due to its simple structure
heuristic algorithm called Black hole and considered dependency and lack of dependence on external parameters and its high
graph of workflow tasks. The proposed method combines the performance.
heuristic algorithm and decision-making method (AHP) to solve
the multi-objective workflow scheduling problem on virtual The extension is carried out in 2 aspects: (1) making our
machines. We converted the single-objective Black-hole algorithm previous work an AHP-based algorithm and using this feature to
into a multi-objective by using the AHP relationship, and then it is select the optimal solutions. To this end, we apply combination
used to solve the scheduling problem. We have implemented our of multi-objective black hole approach and Decision-Making
proposed method using the Workflowsim tool and have compared method (AHP) [5] for workflow scheduling optimization. So,
the results with multi-objective algorithms SPEA2 and NSGA2 we have been able to develop the domination relationship in the
based on the parameters of Makespan and cost and resource
utilization using a balanced and unbalanced workflow.
multi-objective algorithm by using AHP method, as a result we
could choose better solution according to the preference of users
Keywords- Cloud Computing; Workflow; Scheduling; Multi in the Pareto front.
objective; Decision-Making method ;AHP. (2) Presenting resource utilization objective to consider
provider’s preferences in selection of the best solution among
I. INTRODUCTION the optimal solutions. So that the proposed method can consider
Workflow is a common model for modeling most scientific the quality of service requirements for service provider and the
programs which contains a number of tasks and data client simultaneously.
dependencies between tasks. Since most tasks in applications are Our main contributions can be summarized as follows:
a set of workflows; in recent years, extensive research has been 1: Presentation of the multi-objective Black hole algorithm using
done on the workflow scheduling in the cloud environment. the single-objective Black hole algorithm and Pareto optimizer
Workflow scheduling on resources is to select the appropriate and applying it for the multi-objective workflow scheduling in
virtual machine for a task, so that its related tasks are already the cloud environment
executed. This selection of resources and assignment of task on 2: Using the AHP technique in multi-objective domination
them depends on the requirements of quality of service for relationship and taking into account the preferences of users in
different users and since there are different permutation of the solution of workflow scheduling
requests on virtual machines, task scheduling is a NP-hard 3: Targeted evaluation and analysis to illustrate the effective
problem [1]. combination of the black hole algorithm with AHP technique to
A great related work has already been done on the workflow reduce Cost of resources and makespan and increase resource
scheduling problem in the cloud environment; in most classic utilization.
work, it is tried to reduce finish time, but in recent ways; in We have used the WorkflowSim tool [6], which is an
addition to Makespan, there are other objectives, such as extension of CloudSim [7] open source tool, to evaluate our
resource utilization and cost for scheduling. And they seek to proposed method. We have developed the initial core of this tool
provide an optimal permutation of requests on virtual machines, to provide our algorithm and then compared our proposed
Copyright held by the author(s).

36
method with previous Pareto-based algorithms such as SPEA2 RDPSO algorithm. Most of the previous methods have only
[8], NSGA2 [9]. considered two objectives of cost and makeapn reduction as
optimization objectives; Khalili et al. [18], in their proposed
The rest of the paper is comprised of the following sections: method, in addition to Makespan and cost, also considered the
Section 2 presents the related work of workflow scheduling. In purpose of resource efficiency and using a gray wolf algorithm,
Section 3, the mathematical model of the workflow scheduling they have introduced a new Pareto-based multi-objective
problem and the details of the optimization objectives used have scheduling method. In our proposed approach, in addition to
been provided and in the fourth section, we first introduced the reducing the cost, Makespan that benefits of the users are
single-objective black hole algorithm and the AHP technique supplied; increased resource utilization for the benefit of service
and then we present the details of the proposed AHP-based providers has been considered. The difference of our work with
multi-objective algorithm, in the fifth part, we have described previous methods is to use the new Black Hole heuristic
the details of the evaluation of the proposed method and algorithm, which is more efficient than other algorithms and
analyzed the results. Finally, in the final section, conclusions and converting it to a multi-objective algorithm is done using the
future work have been presented. Pareto optimizer. Also, in the proposed algorithm by combining
II. RELATED WORK black hole algorithm with the decision-making method (AHP),
the QOS preferences are considered by the user during the
Many previous work have been done to solve the problem of execution of the algorithm and this will reduce the search space
task scheduling for independent workload and workflow in the of the problem and choose the more optimal solutions with
cloud environment; since our proposed approach has been increasing requests and the variety of virtual machines.
provided for the workflow, we investigate the methods of
workload scheduling. There are different types of classification III. PROBLEM FORMOULATION
for workflow scheduling methods; for example, static or A set of tasks and edges for communication between
dynamic scheduling or other categorization based on single- requests is defined as workflow and in this workflow child
objective or multi-objective workflow scheduling. In this request is not allowed to be execute as long as the parent is not
section, we examine the multi-objective workflow scheduling executing. Figure 1 illustrates an example of a workflow in
methods. In multi-objective scheduling, several objective which which each node represents a task and edges are the connection
are often in contradictory have been considered as optimization between tasks and the number above each edge shows the
objectives and provide the optimal tradeoff of solutions. Multi- estimated cost for data transfer between the corresponding tasks.
objective scheduling methods are in the following categories: In the following, each of the objectives that we have used in the
A. Aggregation approach workflow scheduling problem will be explained.
One of the multi-objective scheduling methods is to convert
a multi-objective problem to a single objective which is done by 1 t
0 t 0
weighting objectives. In Li et al. [10], have converted the multi- 2 4
1
objective problem into a single objective by using the heuristic
method CCSH and have provided a scheduling method with cost 1 3 1
t t t t
and Makespan reduction objectives. Dongarra et al. [11] have 7
0 2 5
proposed a scheduling method by using aggregation technique 1
to increase performance and reliability. They have provided 2 2
(RDLS) a reliable dynamic level scheduling algorithm based on t
4 t
the DLS algorithm [12]. Dogan et al. [13] have improved their 3 6
method using genetic algorithm and BDLS scheduling method.
Figure. 1. The workflow sample
B. Pareto based approach
Unlike the previous method, in which only one definitive A. Makespan
solution is presented as the result of the algorithm. In these To formulate the problem we have denoted a set of tasks
methods, a set of non-dominated solutions is provided that Task = {t1, t2, ..., tn} where i {1, 2,..., n} . We have defined a
allows users to choose a solution based on their expected QoS. set of m virtual machines, VM = {VM1, VM2, ...., VMj}
Yu et al. [14] have used multi-objective evolutionary algorithms interconnected by network where j {1, 2,..., m} . The tasks will
(MOEAs) to solve the workflow scheduling problem. This
approach is aimed at reducing two conflicting objectives of cost be processed on virtual machines. Completion time of task Ti on
and runtime. In addition to these two purposes, they also virtual machine VMj are denoted as CTij respectively. Overall
considered deadline and budget constraints in the algorithm and task completion time is called makespan and is defined by Eq.
therefore provided fitness functions corresponding to objectives (3-1)
and constraints. The population-based algorithms SPEA2 and n
Makespan  max  CTti  xij
VM j
NSGAII [8, 9] and local search-based algorithms MOEA, PAES (3-1)
[15] have been provided for workflow scheduling based on 1 j m i 1
different objectives and constraints. Various scheduling If the request ti is running on VMj, value of xij is equal to 1
methods have been proposed for cost and Makespan reduction otherwise is zero. Figure. 2 epitomizes a sample scheduling
using heuristic algorithms and Pareto optimization; such as makespan for 6 tasks and 3 VMs.
Udomkasemsub et al. [16] using ABC and WU [17] using the

37
C. Resource utilization:
For each virtual machine, resource utilization was defined
Makespan as the Eq.3-8. Where xij is equal to 1, if the request ti is executing
on VMj otherwise is zero.
VM Task1 Task4 n
1
(3-8) Utilization
 PT ij
VM Task2 Task6 VM j  i 1

2 Makespan

VM Task3 Task5
3 IV. PROPOSED METHOD
Figure. 2. Completion time of a typical workflow Heuristic algorithms have been used effectively in most
optimization issues. Among them, the Black Hole heuristic
B. Cost algorithms can provide more optimal solutions for workflow
In cloud computing, computational cost for each customer is scheduling problem in terms of its appropriate structure and
calculated based on the timespan they use of resource at any efficiency compared to the PSO and GA algorithms. In this
time. Total cost for each request include: section, we have first introduced the standard black hole
algorithm and then, after expressing the AHP technique, we
B.1. Computational cost: present the details of the AHP-based multi-objective black hole
This cost is calculated based on execution time of the request algorithm.
ti on the VMj and cost per processing in VMj by Eq.3-2 and the
A. Standard Black Hole Algorithm
execution time of the request ti is calculated by Eq.3-3.
The black hole algorithm is a population-based heuristic
(3-2) C p (ti )  ETtiVMj  Cos tPer Pr occes sin ginVmj algorithm which was first presented by Mr. Hamtlou In the first
step, this algorithm generates an initial population from
(3-3) ET VM  MI (ti )
ti
j
candidate solutions (stars) randomly in a sample space. In the
MIPS (VM j )
workflow scheduling problem on virtual machines, each
While MI (ti) is the number of instructions of request i and solution is a permutation of requests on virtual machines. The
MIPS (VMJ) is the number of million instructions that the value of the fitness function is calculated for each star and the
machine j executes per second. star with the best value for the objective function is selected as
B.2. Cost per storage: Black Hole. The black hole is capable of absorbing the stars that
have trapped it. After the black hole absorbs the stars around it,
This cost is calculated based on the time that this task is the remaining stars move toward the black hole. The motion of
placed on the virtual machine and it is calculated according to the stars towards the black hole is based on Eq. (4-1).
Eq.3-4.
(4-1)
xi (t  1)  xi (t )  rand  ( xBH  xi (t )) i  1, 2,..., N
(3-4) Cs (ti )  ( ETtiVMj  WTtVMj )  Cos tPerStoragInVMj
i 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
WTtiVMj has been the waiting time of request ti on the virtual random number in the range [0,1] and N is the number of stars
machine VMj which has depended on the time for providing (candidate solutions).
required files from its parent and is calculated according to Eq. This evolution of solutions continues until the algorithm
3-5. termination condition is reached and at any stage, if a star has a
better fitness function than a black hole, then that star replaces
(3-5) WT VMj  max input (ti ) the black hole. The black hole algorithm can prevent being
ti
BW
trapped in the local optimal due to the elimination of the
B.3. Cost per transfer: available stars in the range of the best solution and selection the
This costs is dependent on the cost that request ti should pay alternate star randomly in search space. The radius of the
for the transfer of files to their children which is calculated horizons in the black hole algorithm is calculated using Eq. (4-
according to Eq. 3-6. 2).

(4-2) R  f BH
 Output (ti ) n
(3-6) C (t ) 
T i
BW
 Cos tPerTransfer f
i 1
i

The total cost is calculated by Eq. 3-7. Cloud provider
Where fBH is the fitness of black holes and fi is the fitness
calculates the cost of request ti based on the total cost presented
function of the star i and n is the number of stars. When the
below.
distance between a star and a black hole is less than R, that star
(3-7) Ctotal (ti )  C p (ti )  Cs (ti )  CT (ti ) is eliminated and a new star is created randomly in search space.

38
B. AHP decision making method And m is equal to the number of objectives that in this case
AHP is a multi-criteria decision-making approach which can study is equal to the number of the optimization objectives
be used to solve complex decision problems; it was presented by means 3.
Saaty [5] that has been established based on using a set of To calculate priority, we use the concepts of Normalization
pairwise comparisons. The main steps of Analytic Hierarchy and weighted average. As first the geometric mean of each row
Process (AHP) includes making a hierarchy, Assign weight to has been calculated and then we do normalization. The values
each metric, investigate the Consistency check of system and obtained from calculations that make up the priority column are
ultimately decision-making (determine the priorities of options) called eigenvector (λ). Similarly, we perform priority
determination for Pareto optimal set for each criterion.
B.1: Making hierarchy:
In the first step, the decision-making elements and the B.3: Consistency check:
relationships between them must be known in order to build Consistency check is one of the advantages of AHP which
hierarchy. So the options that have an impact on decision making aims to testing coordination of the important degree between
are at the lowest level Thus objectives that have an impact on each metric. The concept of consistency can be expressed as if
decision making are considered at lower ranks and decision objective A is more important compared to B and objective B
making whole objective is considered at top of the hierarchy, is more important compared to the C, the consistency check is
and finally decision-making options are placed in the lowest established if the A is more important than C . The consistency
level. In following an example for workflow scheduling problem index (CI) is shown by Equation (4-3)
which QoS criteria includes Makespan, cost and resource max  m
utilization, the hierarchy structure is shown in Figure. 3. In this (4-3) CI 
m 1
example Studied options are members of the Pareto front, which
indeed one of them should be selected. And consistency ratio is calculated by Equation (4-4)
(4-4) CR  CI
RI
Purpose
Optimal workflow In Equation (4-4) RI value is obtained from the random
scheduling
consistency index table. If value of CR is CR<0.1 consistency is
acceptable otherwise contents of Matrix A should be revised.

B.4. Decision making and selecting definitive solution:
Objective
Make
Cost Resource The final step of analytic hierarchy process includes
span Utilization 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
Pareto
optimal Set S1 S2 … S10 accordance with the Equation (4-5)
m
(4-5) Pi   Wi  Gi
i 1

Figure. 3. The AHP hierarchy model That Gi is weight of options and Wi is weight of the
objective. In this study we have considered the same weight for
B.2: Weight calculation: options that those options are Pareto front in workflow
Objectives are compared with each other pairwise to scheduling problem. Members who value of Pi are less than
determine the relative priority of each metric (weight), this other options are more appropriate than the rest of the members.
Pairwise Comparison construct pairwise comparison matrix A. It should be noted, the inverter form of resource utilization has
For example, comparing the importance between the Makespan been used because Makespan and cost should be minimized and
of workflow and its cost indicates that which one has the higher resource utilization should be maximize in the optimization of
degree of impact in finding the optimal solution. Numbers 1 to the scheduling problem.
9 are usually used to pairwise comparison. 1 means the same C. AHP base multi objective black hole
importance and 9 shows the highest degree of importance.
Pairwise comparison matrix is shown with 𝐴 = (𝑎𝑖𝑗 )𝑚×𝑚 and is Pareto optimal set in heuristic multi-objective algorithms
often involves non-dominated solutions and an optimal tradeoff
as follows:
between objectives. Users decide between the optimal solutions,
 a11 a12 a13  based on their preferences between objectives and choose the
A   a21 a23 
right solution which includes permutations of requests on virtual
a22 machines. In such cases, in order to choose the right solution
 a31 a32 a33  among the Pareto optimal set, we need to have a precise weight
of the objectives corresponding to user preferences. Without the
1 precise weight of the objectives, choosing the solution
Where aii=1 and aij= proportional with the user's preferences is difficult. That's why
a ji

39
users after finding out the set of non-dominated solutions, use circumstances, one can consider each as the optimal decision.
AHP-like techniques to choose the optimal solution that suits the Algorithm 1 depicts the pseudocode of the AHP Base Multi
user's preferences. We have also used the AHP technique in our objective Black hole algorithm.
proposed method. The difference in our approach with previous
works is that we combine the AHP technique with heuristic Algorithm1: AHP base multi objective black hole algorithm pseudo
algorithm but in the previous methods [19], after finding Pareto code
optimal set in the heuristic algorithm the AHP technique is used.
With increasing requests and the diversity of virtual machines, 1. Create an initial population of star randomly and an empty archive
the space of the problem increases and the number of solutions 2. While (t< Max number of iterations)
3. Calculate the fitness function for all stars based on Eq.3-1, 3-7, 3-8
in Pareto optimal set increases. As a result, the AHP technique 4. Calculate Pareto based fitness function according to Eq.4-6
may not be able to differentiate between solutions [20].
5. Calculate final weight of each star by using the AHP technique.
In this paper, we combine the AHP technique with the Black 6. Copy top ten non-dominated stars in population to the archive which has
Hole heuristic algorithm and, as a result, a new domination the smallest R value and the highest AHP weight value
7. Select the star with the best Pareto base fitness function from the archive
relationship has been proposed that, in the proposed domination (Black hole)
relationship, the fitness value of a solution, in addition to the 8. For each star
solution strong in dominating other solutions, is selected based 9. Update the position of current star according to Eq.4-1
on the amount of final weight of that solution obtained by the 10. Calculate fitness of Pareto according to Eq. 4-6
AHP technique. The details of the proposed algorithm are 11. Calculate the distance between each star and the black hole according
to the 4-2
described in detail: 12. If(R< distance)
13. Remove star and create a random star in search space
We have used the Pareto-optimization method to convert the 14. End while
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 V. RESULT EVALUATION
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 evaluate the proposed methods we have used Open
to Eq. (4-6). If a star exceeds the upper time boundary and the source, WorkflowSim tools, then we have compared our
upper boundary of the cost, then the power of R is given a very simulation results of the proposed method with known radiation-
large number. optimizer-based algorithms SPEA2 [8] and NSGA2 [9].
n For evaluation the proposed method we have used a real
(4-6) R(i ) 
 (S )
j 1
j workflow library presented by Bahraini et al. [21]. We have used
j p  a
balanced (Ligo) and unbalanced workload (Montage) to
j i evaluate the proposed method. Figure.4 shows a small sample of
In the above relation, j>i is the symbol of the Pareto these two workflows.
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. (4-6), the greater fitness of the
star because that star is dominated by stars that have less power.
In the next step the final weight of each star obtained according
to the user's objectives and preferences for each objective, which
is achieved using the AHP technique. Then the members of the
archives and population set are arranged in ascending order
based on its R value and stars with the same R value are arranged
by AHP weight and star with larger AHP weight is selected.
Therefore The members of population and archive sets are
primarily arranged based on R, and secondly, based on AHP (a) (b)
weight.
The star that has the lowest R amongst all stars in the Figure. 4. The structure of two realistic scientific workflows[22].(a: Ligo) and
population and archives is considered as the Black Hole star and (b:Montage)
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 We have used a data center consists of twenty hosts and 60
to the number of members in the archive, members are selected virtual machine. Host specification are according to Table 1 and
from the top of the arranged list and transferred to the archive characteristics of virtual machine are presented in Table 2. The
set. This cycle of procedures is repeated until the achievement input parameters for algorithms PBHO, NSGA2 and SPEA2 are
of finish conditions. Non-dominated solutions obtained from also given in Table 3.
solving the multi-objective optimization problem (archives) are We repeated our experiments ten times and then reported the
often referred to as Pareto fronts. None of the Pareto front average data for three factors Makespan, Cost, and resource
solutions are superior to the other and depending on the

40
utilization for two workloads of montage and Ligo in sizes small,
medium and large. We have used the decision-making method TABLE 4.A: RESULT OF PBHO, NSGA2 AND SPEA2 FOR MONTAGE WORKFLOW
AHP to weigh the objectives that are used in the proposed multi-
objective algorithm. If the importance of each objective to be Type Algorithm Makespan Cost Resource
considered as following, then matrix A will be as follows: (ms) $ Utilization%
Spea2 125.21 4082 0.13
The importance of Makespan in comparison with resource Small
utilization: 5, Nsga2 125.49 4083 0.13
PBHO 123.22 4053 0.13
The importance of Cost in comparison with Makespan: 3, Spea2
The importance of Cost in comparison with resource utilization: 270.54 22033 0.32
medium Nsga2
8. 271.84 22299 0.30
PBHO
 1  257.11 21720 0.34
1 5
Makespan  3  Spea2 446.1598 45557.59 0.371931
  Large
A Cos t 3 1 8 Nsga2 485.6466 44624.8 0.347917
THroughput  1 1  PBHO 386.136573 42826.28 0.4073
 1
5 8 
TABLE 1 HOSTS' TECHNICAL SPECIFICATIONS TABLE4.B: RESULT OF PBHO, NSGA2 AND SPEA2 FOR LIGO WORKFLOW

Number of Processing Type Algorithm Makespan Cost Resource
Host Ram Hard Bandwidth (ms) $ Utilization%
processing speed
ID (MB) (MB) (Mbps)
Cores (MIPS) Spea2 3130.951 74027.23 0.103792
Small
Nsga2 3099.543 74984.73 0.105654
1-20 8 2000000 2048000000 1000000 10000
PBHO 3094.21 72082.71 0.103498
Spea2 3480.52 431702.2 0.464593
TABLE 2 VIRTUAL MACHINE' TECHNICAL SPECIFICATIONS medium
Nsga2 3471.826 428138.6 0.479319
Number of Processing
Host Ram Hard Bandwidth PBHO
processing speed 3322.062 418645.5 0.473009
ID (MB) (MB) (Mbps) Spea2
Cores (MIPS) 3468.511 919475.9 0.960096
Large
Nsga2 3478.975 925266.1 0.993529
1-15 1 1000 512 10000 1000
PBHO 3298.811 903725.8 0.968106
16-30 1 1000 512 10000 1000

31-45 2 1000 1024 20000 2000 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
46-60 4 2000 1024 20000 2000 objective black hole algorithm is more than other algorithms.
Considering that the importance of cost for the user is more than
TABLE 3- THE ALGORITHM PARAMETERS other objectives, the proposed method chooses solutions with
Parameter Value
the lowest cost.

Population Size (PBHO, 50
NSGA2,SPEA2)
Archive Size 10
(PBHO ,NSGA2,SPEA2)
Maximum Iteration 20
(PBHO ,NSGA2,SPEA2)
Maximum Generation (SPEA2, 100
NSGA2)
Mutation Probability 0.5
(SPEA2, NSGA2)
Crossover Probability 0.9
(SPEA2, NSGA2)

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 Figure. 5. Pareto front of AHP base multi objective black hole
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.

41
VI. CONCLUSION AND FUTURE WORKS [8] E. Zitzler, M. Laumanns, and L. Thiele, "SPEA2: Improving the strength
Pareto evolutionary algorithm,"Technical Report 103, Gloriastrasse 35,
Task scheduling is one of the most important challenges for CH-8092 Zurich, Switzerland, 2001.
cloud providers and users. In this paper, we present a multi- [9] K. Deb ; A. Pratap ; S. Agarwal ; T. Meyarivan, “A fast and elitist
objective workflow scheduling method by using the Black hole multiobjective genetic algorithm: NSGA-II”, IEEE Transactions
on Evolutionary Computation ( Volume: 6, Issue: 2, Apr 2002 ).
algorithm. Our proposed method, on the one hand, by reducing
[10] J. Li, S. Su, X. Cheng, Q. Huang, and Z. Zhang, "Cost-Conscious
Makespan and cost supplies the benefit of users and on the other Scheduling for Large Graph Processing in the Cloud," in 2011 IEEE
hand, by increasing resource utilization, considers the benefits International Conference on High Performance Computing and
of service providers simultaneously. In the proposed method, the Communications, 2011, pp. 808-813.
Black Hole algorithm has been combined with the concept of [11] J. J. Dongarra, E. Jeannot, E. Saule, and Z. Shi, "Bi-objective scheduling
AHP and the AHP Base Multi objective Black hole has been algorithms for optimizing makespan and reliability on heterogeneous
provided using Pareto optimizer. Since in cloud environments systems," presented at the Proceedings of the nineteenth annual ACM
symposium on Parallel algorithms and architectures, San Diego,
different users require different QoS requirement, in our California, USA, 2007.
proposed method, the AHP decision-making technique has been
[12] G. C. Sih and E. A. Lee, "A compile-time scheduling heuristic for
used in Pareto domination relationship, so that user preferences interconnection-constrained heterogeneous processor architectures,"
are taken into consideration in choosing the optimal solution at IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 2, pp.
any stage and as a result, by increasing the search space of the 175-187, 1993.
problem, we can find a better Pareto optimal set. [13] A. Doğan and F. Özgüner, "Biobjective Scheduling Algorithms for
Execution Time–Reliability Trade-off in Heterogeneous Computing
In the future, we plan to consider more objectives and Systems*," The Computer Journal, vol. 48, no. 3, pp. 300-314, 2005.
examine the effectiveness of this technique for the many [14] J. Yu, M. Kirley, and R. Buyya, "Multi-objective planning for workflow
objective problems. We can also use the proposed method for execution on Grids," presented at the Proceedings of the 8th IEEE/ACM
dynamic workflow scheduling. International Conference on Grid Computing, 2007.
[15] J. Knowles and D. Corne, "The Pareto archived evolution strategy: a new
baseline algorithm for Pareto multiobjective optimisation," in
REFERENCE Proceedings of the 1999 Congress on Evolutionary Computation-CEC99
(Cat. No. 99TH8406), 1999, vol. 1, pp. 1-105 Vol. 1.
[16] O. Udomkasemsub, X. Li, and T. Achalakul, "A multiple-objective
[1] F. Ebadifard and S. M. Babamir, "A PSO-based task scheduling algorithm
workflow scheduling framework for cloud data analytics," in 2012 Ninth
improved using a load-balancing technique for the cloud computing
International Conference on Computer Science and Software Engineering
environment," Concurrency and Computation: Practice and Experience,
(JCSSE), 2012, pp. 391-398.
pp. e4368-n/a, Art. no. e4368, 2017.
[17] Z. Wu, Z. Ni, L. Gu, and X. Liu, "A Revised Discrete Particle Swarm
[2] Z. Zhu, G. Zhang, M. Li, and X. Liu, "Evolutionary Multi-Objective
Optimization for Cloud Workflow Scheduling," in 2010 International
Workflow Scheduling in Cloud," IEEE Transactions on Parallel and
Conference on Computational Intelligence and Security, 2010, pp. 184-
Distributed Systems, vol. 27, no. 5, pp. 1344-1357, 2016.
188.
[3] F. Ebadifard and S. M. Babamir, "Optimizing multi objective based
[18] A. Khalili and S. M. Babamir, " Optimal Scheduling workflows in Cloud
workflow scheduling in cloud computing using black hole algorithm," in
Computing Environment Using Pareto based Grey Wolf Optimizer" In
2017 3th International Conference on Web Research (ICWR), 2017.
Concurrency and Computation: Practice and Experience,
[4] Abdolreza Hatamlou, "Black hole: A new heuristic optimization approach http://mc.manuscriptcentral.com/cpe, 2016.
for data clustering", Information Sciences, journal homepage:
[19] A. V. Dastjerdi, and R. Buyya, “Compatibility-aware Cloud Service
www.elsevier.com/locate/ins, 2013. Pp.175–184.
Composition Under Fuzzy Preferences of Users,” IEEE Transactions on
[5] T. L. Saaty, "Decision making with the analytic hierarchy process," Cloud Computing, vol.2, no.1, pp.1-13, 2014.
International Journal of Services Sciences, InderScience, vol. 1, no.1, pp.
[20] L. Liu and M. Zhang, "Multi-objective Optimization Model with AHP
83-98, 2008.
Decision making for Cloud Service Composition," KSII Transactions on
[6] W. Chen and E. Deelman, "Workflowsim: A toolkit for simulating Internet &Information Systems, vol. 9, no. 9, 2015.
scientific workflows in distributed environments," IEEE International
[21] Bharathi, S., Chervenak, A., Deelman, E., Mehta, G., Su, M.H. and Vahi,
Conference on EScience (e-Science), pp. 1-8, 2012.
K.‘‘Characterization of scientific workflows’’, The 3rd Workshop on
[7] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Workflowsim Support of Large Scale Science, Austin, TX, USA, pp. 1–
Buyya,"CloudSim: a toolkit for modeling and simulation of cloud 10 (2008).
computing environments and evaluation of resource provisioning
[22] Pegasus Workflow Management System, available
algorithms," Software: Practice and Experience, vol. 41, no. 1, pp. 23-50,
at:http://pegasus.isi.edu/workflow_gallery/index.php (Last visited:
2011.
2017).