A Deep Reinforcement Learning Algorithm with Ordered Action Space for Budget-Aware Workflow Scheduling in Heterogeneous Clouds
摘要
The optimization problem of makespan for cloud workflow scheduling under budget constraints presents significant challenges due to the heterogeneity of cloud resources and the complexity of task dependencies. Although existing deep reinforcement learning scheduling algorithms show promise in addressing the inherent limitations of traditional methods, they often lack awareness of budget constraints and struggle to manage the dynamic action space induced by budgetary considerations. To address this issue, a perception coefficient generation mechanism specifically designed to adhere to budget constraints is proposed. Additionally, an ordered action space mapping method is developed to facilitate the transition from continuous to discrete actions. Leveraging these two innovations, the twin delayed deep deterministic policy gradient (TD3) framework is leveraged to propose a budget-constrained workflow scheduling algorithm called PO-TD3, aimed at generating feasible and efficient scheduling solutions. The experimental results show that compared to the baseline algorithms, the PO-TD3 algorithm converges efficiently, achieving a 100% success rate in generating scheduling schemes that satisfy budget constraints. Additionally, it achieves optimal performance in minimizing makespan, with an average reduction of 61.43% compared to state-of-the-art algorithms.