Elimination Mechanism-based PSO Algorithm for Cloud Workflow Scheduling with Budget Constraints

As a new computing paradigm for hosting and executing large-scale scientific applications, cloud computing can provide users with scalable and elastic computational resources. Workflow scheduling is NP-complete and becomes even more challenging under the dynamic environment of the cloud since certain quality of service (QoS) needs to be met in most cases. In this paper, a meta-heuristic scheduling algorithm, named EMPSO (Elimination Mechanism-based PSO), is proposed to minimize the makespan while satisfying the budget constraint. Firstly, a new technique for choosing the global best solution is developed to avoid the premature convergence caused by the original totally greedy selection method, which improves the global search performance of our algorithm. Then, for accelerating the convergence speed towards the global optima, time-varying parameters are introduced to keep a good balance between global search and convergence by updating particles' velocity adaptively during different optimizing stages. Finally, an elimination mechanism is embedded to further improve the overall performance by promoting the quality of inferior particles. Extensive experiments are conducted on well-known scientific workflows of different sizes and types. The experimental results demonstrate that EMPSO outperforms GA and PSO with respect to meeting the budget constraint and minimizing the makespan.