How to Use Predictions? Dependence-Aware Scheduling with Runtime Distributions

Non-clairvoyant schedulers choose which task to run before its runtime is known. Runtime histories can help estimate a runtime distribution for each task. Using these distributions separately misses what a completed task's runtime reveals about unfinished tasks. When runtimes are dependent, that information can change which task should run next. This raises the question: how should a scheduler use a predicted runtime distribution to choose its next action as tasks complete? We introduce a scheduler that updates a predicted joint runtime distribution using completed runtimes and the time unfinished tasks have already run. It then chooses the action with the lowest expected remaining workflow completion cost. We show that ignoring runtime dependence can increase expected total workflow completion time. Both predictions have the correct runtime distribution for each task and are passed to the same exact scheduling algorithm. We bound how prediction error affects cost relative to an optimal scheduler that knows the true distribution. From $h$ complete histories, *Truncated Joint Fitting (TJF)* caps long runtimes while preserving task pairings. For fixed model parameters and a bounded second moment of total runtime, TJF attains $O(h^{-1/n})$ expected excess cost for $n\ge 3$ under arbitrary dependence among task runtimes. A matching worst-case lower bound shows this exponent is unavoidable, while fitting tasks separately under independence attains $O(\sqrt{\log h/h})$. In a constructed four-task offline replay using recorded Alibaba runtimes, an uncapped empirical joint prediction reduces total workflow completion time by 13.94% across 1,796 held-out batches relative to independent prediction with the same task marginals.