A Budget-Constrained Workflow Scheduling Approach With Priority Adjustment and Critical Task Optimizing in Clouds

Abstract

In the rapidly evolving landscape of cloud computing, scheduling complex scientific workflows poses significant challenges, particularly with constraints like budget considerations. While recent years have seen considerable research focus on budget-constrained cloud workflow scheduling, existing studies primarily concentrate on constructing solutions without delving into potential enhancements. To address this gap, our paper introduces PACP-HEFT, a modified HEFT algorithm integrating priority adjustment and task optimization to minimize makespan. Leveraging the Heterogeneous Earliest-Finish-Time (HEFT) algorithm as its foundation, PACP-HEFT incorporates two priority adjusters informed by task characteristics gleaned from task dependency topology and real-time scheduling data. Additionally, a critical task optimizer conducts thorough analyses and optimizations to reduce overall makespan. Extensive experimentation with real-world workflows underscores PACP-HEFT’s superior performance compared to contemporary algorithms. Note to Practitioners—This paper presents a deterministic approach to budget-constrained scheduling problem, with the objective of minimizing the makespan. The proposed PACP-HEFT algorithm exhibits robust solution enhancement capabilities through the utilization of two priority adjusters and a critical task optimizer. The two priority adjusters fine-tune task priorities based on characteristics extracted from task dependency topology and real-time scheduling data, while the critical task optimizer performs an in-depth analysis of scheduling solutions and optimizes critical tasks to reduce overall makespan. Real-world workflow experiments clearly highlight the superior performance of PACP-HEFT compared to state-of-the-art algorithms. Validation experiments also underscore the effectiveness of each priority adjuster and the critical task optimizer. Moreover, PACP-HEFT’s ability to rapidly reach solutions further enhances its practicality, ensuring timely scheduling outcomes. Furthermore, we assess the adaptability and transferability of these components, emphasizing their potential applicability in enhancing the performance of other scheduling algorithms. For practical applications, this algorithm can be directly applied to rapidly minimize the makespan of budget-constrained scheduling problems in the cloud. Moreover, it can be integrated into other schedulers as a solution enhancement component, offering versatility and improved scheduling efficiency.

Topics & Concepts