A Heuristic Scheduling Algorithm based on PSO in the Cloud Computing Environment

Shengjun Xue, Wenling Shi, Xiaolong XuInternational Journal of u- and e- Service Science and Technology 2016 · DOI

TL;DR

This paper introduces PSO-SC, a novel heuristic algorithm for optimizing task scheduling in cloud computing environments. By leveraging Particle Swarm Optimization (PSO) and a price-based model, PSO-SC aims to simultaneously minimize task completion time and user costs, addressing the limitations of single-objective scheduling approaches.

What Problem Does This Paper Address?

Cloud computing environments face a significant challenge in efficiently managing a large volume of user-submitted tasks. The core problem lies in how to allocate system resources and schedule these tasks effectively to meet user demands, particularly Quality of Service (QoS) requirements. Existing scheduling algorithms often focus on a single objective, such as minimizing completion time or cost, but rarely address both simultaneously. This paper tackles the problem of workflow task scheduling, where tasks have interdependencies, and aims to optimize for multiple objectives: reducing task completion time and minimizing user expenditure within a cloud environment that operates on a pay-per-use model.

Methods

The paper proposes a heuristic scheduling algorithm called PSO-SC (Service Cost Optimization based on Particle Swarm Optimization). The core of this algorithm is the Particle Swarm Optimization (PSO) metaheuristic, which is adapted to the cloud scheduling problem.

Here's a breakdown of the key methodological aspects:

  • Workflow Model: The paper models tasks as a workflow, where tasks can have dependencies (parent-child relationships). This means a task can only be executed after its parent tasks are completed.
  • Price Model: A "reserving pricing" model is adopted, where users pay a deposit and then incur costs based on the execution time of virtual machines (VMs) and their per-unit running costs.
  • PSO Adaptation:
    • Particles: Each particle in the swarm represents a potential task scheduling strategy.
  • Position: The position of a particle is defined by how tasks are assigned to specific virtual machines.
  • Velocity: The velocity dictates how a particle's position (scheduling strategy) is updated.
  • Fitness Function: The fitness of a particle is inversely proportional to the total cost of executing the tasks according to its scheduling strategy (SumCost). This means a lower cost leads to higher fitness.
  • Adaptability Function: The paper defines an adaptability function to measure the "merits" of an allocation strategy, aiming to find particles with high adaptability (low cost).
  • Individual and Global Extrema: PSO's core mechanism of updating particle positions based on their own best-found solution (individual extremum) and the best-found solution by the entire swarm (global extremum) is employed.
  • Objective Function: The PSO-SC algorithm optimizes for a combined objective that considers both the total execution time and the total cost of tasks.

Datasets

The paper does not use pre-existing datasets. Instead, it introduces a simulated cloud computing environment for its experiments. The workflows, task lengths, and the relationships between tasks are randomly generated. The virtual machines are also defined with varying speeds and costs, as detailed in Table 2.

Key Insights and Ideas

  • Multi-objective Optimization is Crucial: The paper strongly advocates for scheduling algorithms that can handle multiple objectives (time and cost) simultaneously, as single-objective approaches are insufficient for real-world cloud scenarios.
  • PSO's Adaptability: PSO proves to be a flexible metaheuristic capable of adapting to the dynamic nature of cloud environments and optimizing for complex objectives like service cost.
  • Price Model Impact: The chosen price model significantly influences the scheduling strategy. The "reserving pricing" model, with its upfront deposit and pay-as-you-go execution costs, provides a concrete basis for cost optimization.
  • Task Interdependencies Matter: The workflow model, which accounts for task dependencies, is essential for realistic scheduling, as it reflects how complex applications are structured.
  • Proportion of VMs to Tasks is Key: The experimental results highlight that the ratio of virtual machines to tasks is a critical factor influencing the effectiveness of scheduling algorithms. A specific range (1:1 to 1:100) was found to be optimal for the proposed PSO-SC algorithm.

Key Results

The experimental results demonstrate the effectiveness of the PSO-SC algorithm compared to the traditional FIFO (First-In, First-Out) scheduling algorithm.

  • Reduced Completion Time: For proportions of virtual machines to tasks between 1:1 and 1:300, PSO-SC achieved a lower total time to complete tasks than FIFO.
  • Reduced Cost: For proportions between 1:1 and 1:100, PSO-SC resulted in a lower total cost of tasks compared to FIFO.
  • Overall Performance: Figures 6, 7, and 8 collectively show that PSO-SC generally outperforms FIFO in terms of total task completion time, running time, and total cost. The gap between PSO-SC and FIFO widens as the number of tasks increases, indicating better scalability for PSO-SC.
  • Optimal Proportion: The study suggests that a proportion of virtual machines to tasks between 1:1 and 1:100 yields the best results for PSO-SC.

Limitations and Future Work

The authors acknowledge several limitations and suggest avenues for future research:

  • Task Dependency Assumption: The current model assumes all tasks are mutually dependent, which might not fully capture the diverse relationships between tasks in real-world scenarios. Future work could explore more nuanced dependency models.
  • Task Nature Assumption: The paper assumes tasks are computationally intensive. This might not be realistic for all cloud applications. Future research could investigate scheduling for a broader range of task types.
  • Dynamic Cloud Environment: While PSO-SC is designed to adapt to dynamic environments, further exploration of its performance under highly dynamic conditions (e.g., frequent VM failures or resource fluctuations) would be beneficial.
  • Exploring Other Metaheuristics: The paper focuses on PSO. Investigating other metaheuristics or hybrid approaches for multi-objective optimization in cloud scheduling could yield further improvements.
  • Real-world Validation: While simulated, validating the PSO-SC algorithm on real-world cloud platforms would be a crucial next step to confirm its practical applicability.

Summary updated

Abstract

In the face of a large number of task requests submitted by users, the data center in the cloud need not only to finish these massive tasks but also to satisfy the user's service demand. How to divide the resources of the system reasonably and schedule these tasks efficiently is a problem that need be solved in the cloud computing. The task scheduling of workflow is a kind of scheduling model for the most part researched in cloud computing. The scheduling goal is always decided by user's QoS (Quality of Service) and the scheduling goal of existing scheduling algorithm is always single. Based on the price model a scheduling algorithm is proposed which can realize the multiple targets in this article, and the scheduling algorithm is Service Cost Optimization based on Particle Swarm Optimization (PSO-SC). PSO-SC algorithm can adapt to dynamic cloud environment, and it not only shortens the completion time of tasks but also minimizes user's cost of task when schedule tasks. In this paper, experiment and analyze the task scheduling of workflow under the cloud computing environment, and the experimental results show that the algorithm proposed in this paper has very good scheduling performance and can reach the goal of task scheduling of tasks.
BibTeX
@article{xue2016heuristic,
  author = {Shengjun Xue and Wenling Shi and Xiaolong Xu},
  title = {{A Heuristic Scheduling Algorithm based on PSO in the Cloud Computing Environment}},
  journal = {International Journal of u- and e- Service Science and Technology},
  year = {2016},
  doi = {10.14257/ijunesst.2016.9.1.36},
}
Figure