Scientific workflow applications include a set of tasks, which have complex inter dependencies with each other, along with a large number of parallel tasks. The problem of scheduling such application tasks involves careful decisions on determining the sequence in which it can be processed, causing high impact on the cost of execution and makespan (execution time), when executed on a cloud computing system. Achieving optimal schedule, which can optimize both of these objectives while keeping the dependencies between tasks intact is a real challenge. In this work, a non-dominated sorting based particle swarm optimization approach to find an optimal schedule for workflow applications in cloud computing systems is proposed. A graph is used to represent tasks in the workflow and the dependencies among tasks. The optimization problem is modelled using integer programming formulation, subject to capacity and dependency constraints among tasks and Virtual Machines (VM). Simulation studies and result comparison with other representative algorithms in the literature shows that the proposed algorithm is promising.
AbrishamiS., NaghibzadehM. and EpemaD.H.J., Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds, Journal of Future Generation Computer Systems, Elsevier23 (2013), 158–169.
2.
BaoC., XuL., GoodmanE.D. and CaoL., A novel non-dominated sorting algorithm for evolutionary multi-objective optimization, Journal of Computational Science, Elsevier23 (2017), 31–43.
3.
BeegomA.S.A. and RajasreeM.S., A particle swarm optimization based pareto-optimal task scheduling in cloud computing, Lecture Notes in Computer Science, Springer8795 (2014), 79–86.
4.
BeegomA.S.A. and RajasreeM.S., Genetic algorithm framework for bi-objective task scheduling in cloud computing systems, Lecture Notes in Computer Science, Springer8956 (2015), 356–359.
5.
BeegomA.S.A. and RajasreeM.S., Integer-pso: A discrete pso algorithm for task scheduling in cloud computing systems, Journal of Evolutionary Intelligence, Springer (2019), 1–13.
6.
ChenW.N. and ZhangJ., A set-based discrete pso for cloud workflow scheduling with user-defined qos constraints, Proc of IEEE International Conference on Systems, Man and Cybernetics, 2012, pp. 773–778.
7.
CoelloC.A.C., PulidoG.T. and LechugaM.S., Handling multiple objectives with particle swarm optimization, IEEE Transactions on Evolutionary Computation8(3) (2004), 256–279.
8.
DebK. and JainH., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints, IEEE Transactions on Evolutionary Computation18(4) (2013), 577–601.
9.
DebK., PratapA., AgarwalS. and MeyarivanT., A fast and elitist multi objective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation6(2) (2002), 182–197.
10.
DuanR., ProdanR. and LiX., Multi-objective game theoretic scheduling of bag-of-tasks workflows on hybrid cloud, IEEE Transactions on Cloud Computing2(1) (2014), 29–42.
11.
DurilloJ., NaeV. and ProdanR., Multi-objective workflow scheduling: An analysis of the energy efficiency and makespan tradeoff, Proc Of 13th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 2013, pp. 203–210.
12.
FardH.M., ProdanR. and FahringerT., A truthful dynamic work-flow scheduling mechanism for commercial multicloud environments, IEEE Transactions on Parallel and Distributed Systems24(6) (2013), 1203–1212.
13.
GuoL., ShaoG. and ZhaoS., Multi-objective task assignment in cloud computing by particle swarm optimization, Proc of 8th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), 2012, pp. 1–4.
14.
JainH. and DebK., An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part ii: Handling constraints and extending to an adaptive approach, IEEE Transactions on Evolutionary Computation18(4) (2013), 602–622.
15.
KaushalS. and VermaA., A hybrid multi-objective particle swarm optimization for scientific workflow scheduling, Parallel Computing, Elsevier62 (2017), 1–19.
16.
KennedyJ. and EberhartR., Particle swarm optimization, Proc Of IEEE International Conference on Neural Networks, 1995, pp. 1942–1948.
17.
LeenaV.A., BeegomA.S.A. and RajasreeM.S., Genetic algorithm based bi-objective task scheduling in hybrid cloud platform, International Journal of Computer Theory and Engineering8(1) (2016), 7–13.
18.
LiX., A non-dominated sorting particle swarm optimizer for multi-objective optimization, Lecture Notes in Computer Science, Springer2723 (2003), 37–48.
19.
ManasrahA.M. and AliH.B., Workflow scheduling using hybrid ga-pso algorithm in cloud computing, Journal of Wireless Communications and Mobile Computing, Wiley2018(Article Id. 1934784) (2018), 1–16.
20.
MarlerR.T. and AroraJ.S., The weighted sum method for multi-objective optimization: New insights, Structural and Multidisciplinary Optimization, Springer41(6) (2010), 853–862.
21.
PandeyS., WuL., GuruS.M. and BuyyaR., A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments, Proc of 24th IEEE Conference on Advanced Information Networking and Applications, 2010, pp. 400–407.
22.
PulidoG.T. and CoelloC.A.C., Using clustering techniques to improve the performance of a multi-objective particle swarm optimizer, Lecture Notes in computer Science, Springer3102 (2004), 225–237.
23.
RahmanM., HassanR., RanjanR. and BuyyaR., Adaptive workflow scheduling for dynamic grid and cloud computing environment, International Journal of Concurrency and Computation: Practice and Experience, Wiley25 (2013), 1816–1842.
24.
RimalB.P. and MaierM., Workflow scheduling in multi-tenant cloud computing environments, IEEE Transactions on Parallel and Distributed Systems28(1) (2017), 290–304.
25.
RodriguezM.A. and BuyyaR., Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds, IEEE Transactions on Cloud Computing2(2) (2014), 222–235.
26.
RodriguezM.A. and BuyyaR., A taxonomy and survey on scheduling algorithms for scientific workflows in iaas cloud computing environments, International Journal of Concurrency and Computation: Practice and Experience, Wiley29 (2017), 1–23.
27.
SierraM.R. and CoelloC.A.C., Improving pso based multi-objective optimization using crowding, mutation and ∈-dominance, Lecture Notes in computer Science, Springer3410 (2005), 505–519.
28.
SinghS. and ChanaI., A survey on resource scheduling in cloud computing: Issues and challenges, Journal of Grid Computing, Springer14 (2016), 217–264.
29.
SrinivasN. and DebK., Multiobjective optimization using nondominated sorting in genetic algorithms, Journal of Evolutionary Computation2(3) (1994).
30.
StanimirovicI.P., ZlatanovicM.L. and PetkovicM.D., On the linear weighted sum method for multi-objective optimization, Facta Universitatis, Series: Mathematics and Informatics26 (2011), 49–63.
31.
SzaboC. and KroegerT., Evolving multi-objective strategies for task allocation of scientific workflows on public clouds, Proc of IEEE Congress on Evolutionary Computation (CEC), 2012, pp. 1–8.
32.
ThantP.T., PowellC., SchlueterM. and MunetomoM., Multiobjective level-wise scientific workflow optimization in iaas public cloud environment, Journal of Scientific Programming2017(Article Id. 5342727) (2017), 1–17.
33.
VermaA. and KaushalS., Cost-time efficient scheduling plan for executing workflows in the cloud, Journal of Grid Computing, Springer13 (2015), 495–506.
34.
WangX. and WangY., An energy and data locality aware bi-level multiobjective task scheduling model based on mapreduce for cloud computing, Proc of IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, 2012, pp. 648–655.
35.
WuZ., NiZ. and LiuX., A revised discrete particle swarm optimization for cloud workflow scheduling, Proc of International Conference on Computational Intelligence and Security (CIS), 2010, pp. 184–188.
36.
ZhuZ., ZhangG., LiM. and LiuX., Evolutionary multi-objectivework-flowscheduling in cloud, IEEE Transactions on Parallel and Distributed Systems27(5) (2016), 1344–1357.
