Kairos: Time-Sensitive Scheduling for Ad-Oriented ML Workloads with Heterogeneous Time-Utility Functions

Digital advertising relies heavily on machine learning models for accurate recommendations, yet the training tasks for these models exhibit unique time-sensitive characteristics that are often overlooked by current scheduling systems. Unlike general-purpose ML workloads, recommendation tasks are highly time-sensitive because their business value decays rapidly when execution is delayed. However, existing schedulers lack precise functions of such value decay and primarily optimize system-level metrics such as throughput or fairness, thereby failing to preserve the time-dependent business utility of these tasks. To bridge this gap, this paper identifies three distinct types of ad recommendation tasks (i.e.,, SLO, softSLO and BE tasks), each with characteristic value decay patterns, and develop empirically-grounded Time-Utility Functions (TUFs) using real-world datasets, which offer a robust abstraction that transforms noisy, non-stationary business data into tractable utility functions suitable for scheduling. Then we propose Kairos, a utility-theoretic scheduling algorithm that jointly reasons about elastic parallelism, heterogeneous deadlines, and time-decaying utilities to maximize total system value. Kairos guarantees an approximation ratio of 1-√2 ln(nT)/C for SLO tasks and (1-ε)(1-η)/2(1+η) for BE tasks with linear relaxation and knapsack approximation. Experiments demonstrate that Kairos achieves up to 47% improvement in overall utility preservation compared to state-of-the-art schedulers.