Hybrid Scheduling Algorithm for Deadline-Aware Job Queues

Abstract

Deadline-aware job queues are central to modern compute backends—ranging from real-time analytics pipelines to latency-sensitive microservices and soft real-time batch processing. Classical policies such as Earliest Deadline First (EDF) minimize deadline misses under ideal assumptions, while size-based policies such as Shortest Remaining Processing Time (SRPT) minimize mean response time but can starve large jobs or violate deadlines. This paper proposes HSA-DAJQ (Hybrid Scheduling Algorithm for Deadline-Aware Job Queues), a practical, preemptive policy that blends (i) laxity-aware urgency from EDF, (ii) SRPT-style remaining-time tie-breaking, (iii) aging for fairness, and (iv) lightweight admission control based on predicted tardiness. HSA-DAJQ maintains three priority bands—Urgent, On-Track, and Background—and promotes/demotes jobs by monitoring relative laxity L=d−t−r^L = d - t - \hat{r}, where dd is the deadline, tt is current time, and r^\hat{r} is the predicted remaining time.

We implement HSA-DAJQ in a discrete-event simulator with preemptive-resume semantics, modest context-switch costs, and noisy runtime estimates using an online EWMA predictor. Across realistic, bursty workloads (mixtures of heavy-tailed and light-tailed job sizes) and under high utilization (ρ≈0.85\rho \approx 0.85), HSA-DAJQ reduces deadline-miss rate by 35–60% versus EDF and 70–85% versus MLFQ, while improving mean slowdown by 18–28% over SRPT-only baselines. Sensitivity analysis shows robustness to estimation error (CV ≈ 0.3–0.5) with bounded fairness loss due to aging. The algorithm operates in O(log⁡n)O(\log n) per event using heap-based queues and requires only two tunables (aging half-life and demotion/promotion laxity bands). We discuss design trade-offs, statistical testing (nonparametric comparisons with effect sizes), and limitations, and outline future extensions to heterogeneous multi-resource clusters.