Reliable cloud workflow scheduling with uncertain task execution time

Ensuring reliability—defined as the probability of flawless task execution within a specified duration—for deadline-constrained cloud workflows is challenging due to pervasive uncertainty in task execution time. This uncertainty arises from performance interference on shared infrastructure, leading to random variations in actual task durations. Existing scheduling methods often address task execution time uncertainty or reliability requirements in isolation, failing to satisfy both simultaneously under deadline constraints. To bridge this gap, this paper proposes a novel Reliable Workflow Scheduling under Uncertain task execution Time (RWSUT) algorithm. The core of RWSUT is a dynamic reliability assurance strategy that adaptively decomposes the end-to-end workflow reliability requirement into fine-grained, task-level sub-reliability constraints. These constraints are dynamically adjusted based on the actual reliability achieved by completed tasks, thereby effectively mitigating the cascading impact of execution time uncertainty. Furthermore, an elastic resource provisioning scheme is integrated to dynamically manage the virtual machine pool, which not only satisfies the fluctuating resource demands for reliability but also significantly boosts resource utilization, leading to a substantial reduction in rental costs. Extensive simulations based on real-world scientific workflows demonstrate that RWSUT consistently meets reliability constraint while simultaneously achieving a higher workflow completion rate and lower economic cost compared to state-of-the-art algorithms.