DBS‐W: A Resource‐ and Deadline‐Aware Scheduler for DAG‐Structured Cloud Workflows

Cloud workflows, MapReduce pipelines, scientific DAGs, and multistage analytics impose precedence constraints absent from independent‐task scheduling: A task cannot start until all predecessors finish, and one delayed task can cascade deadline violations through its descendants. Existing deadline‐aware cloud schedulers target only independent tasks and provide no mechanism for propagating a workflow‐level deadline to individual tasks, while classical workflow heuristics such as HEFT and Min‐Min optimize makespan or utilization without deadline awareness. This gap motivates DBS‐W, a resource‐ and deadline‐aware scheduler for DAG‐structured cloud workflows. DBS‐W extends a resource‐aware dynamic load–balancing framework with three mechanisms: (i) proportional subdeadline distribution, allocating a workflow’s deadline to its tasks by upward‐rank position on the critical path; (ii) precedence‐gated admission, releasing each task for scheduling only once its parents complete; and (iii) cascading rejection, propagating infeasibility to descendants of an unschedulable task. Each ready task is then scheduled via minimum‐completion‐time VM selection, deadline‐based queue reordering, and a suitable position finder (SPF) that inserts urgent tasks into existing queues without violating other tasks’ deadlines. DBS‐W was evaluated in a 50‐VM heterogeneous simulation environment against HEFT, PEFT, a precedence‐aware Min‐Min, and two ablations (DBS‐naive, lacking subdeadline distribution, and DBS‐W/NoSPF, lacking the SPF), across four load and slack scenarios, with statistical validation via the Wilcoxon signed‐rank test at a standard significance threshold and fifteen independent runs per configuration. Under heavy load, DBS‐W achieved a workflow deadline‐miss ratio of little more than one percent, compared with roughly two‐thirds of workflows missed by HEFT, half by Min‐Min, and around six percent by DBS‐naive, with every improvement statistically significant, while attaining the highest overall gain at all but the lightest load. Against PEFT, a stronger and more contemporary classical scheduler, DBS‐W’s advantage held across nearly every load condition tested. The DBS‐naive comparison isolates subdeadline distribution, rather than inherited scheduling mechanics alone, as the primary driver of these gains, showing that jointly reasoning about resources, deadlines, and precedence is necessary for dependent cloud workloads.