Non-dominated sorting based PSO algorithm for workflow task scheduling in cloud computing systems

摘要

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.