A Continuous Optimization Approach for Deadline-Constrained Cloud Workflow Scheduling

In cloud computing, deadline-constrained workflow scheduling, a typical NP-hard problem, plays a vital role in meeting users’ quality-of-service (QoS) and efficiently managing cloud resources. Its core difficulty lies in handling the deadline constraint, where existing methods suffer from two major issues: fixed deadline distribution strategies, which lack adaptability to diverse workflows, and inefficient metaheuristic search, which requires discrete encodings and repair rules in the combinatorial space. To overcome these limitations, we propose a continuous optimization approach to efficiently address the deadline constraint. The basic idea is to find the suitable sub-deadline of each task by iterative optimization for each workflow. First, treating each task’s sub-deadline as a decision variable, a continuous optimization problem is established to solve deadline-constrained workflow scheduling. Then, a Dynamic Multi-Swarm Particle Swarm Optimization with Social Learning (SL-DMSPSO) algorithm is proposed for this continuous optimization problem, incorporating with the following two novel designs: 1) the entire population is divided into multiple swarms and is re-divided at each iteration, ensuring that swarms are dynamic and randomly assigned, which facilitates information exchange among swarms and enhances exploration diversity. 2) social learning is introduced when updating the particles in each swarm, combined with individual learning to balance diversity and convergence. Experiments are conducted on real-world workflows to compare SL-DMSPSO with state-of-the-art algorithms and the results reveal the superiority of SL-DMSPSO in effectively scheduling deadline-constrained workflows in clouds.