A Lyapunov-based dynamic scheduling algorithm for heterogeneous computing clusters

The paper proposes a Lyapunov-based dynamic scheduling algorithm for heteroge-neous computing clusters, targeting fine-grained resource control under bursty and latency-sensitive workloads. By constructing a quadratic Lyapunov function and applying a drift-plus-penalty framework, the scheduling problem is formulated as a two-criteria optimization problem balancing queue stability and scheduling delay. A dynamic control parameter V is introduced to quantitatively regulate the trade-off between backlog stability and delay minimization. Sensitivity analysis demonstrates an O(1/V) backlog and O(V) delay trade-off. Experiments conducted on the Alibaba GPU cluster trace dataset show that under burst-dominant workloads, the proposed method reduces average scheduling delay to 0.2663 seconds, while achieving a 0.5459 resource utilization and a 0.6489 fairness index. The method is particularly suitable for latency-sensitive and dynamically fluctuating environments.