Equal-Budget Study Finds Random-Restart Scheduling Outperforms MCTS on Many DAG Workflows

Summary

This controlled computational study tests whether Monte Carlo Tree Search (MCTS) offers an advantage over a simpler randomized-restart list scheduler when both receive the same search effort for directed-acyclic-graph workflows. The preregistered main comparison gave each method an identical number of candidate schedules to build and evaluate, while a textbook-UCT MCTS arm was tested separately. An independent checker verified all 768 confirmation-stage schedules and their finish times. At the main budget of 2,048 evaluated schedules, MCTS was 2.88% worse than randomized restarts across the reported held-out advantage set, with a 95% confidence interval of [-3.62%, -2.15%]. The exploration pool showed a similar pattern: restarts improved by 1.85%, while MCTS improved by 0.24%, and 700 of 720 MCTS first results were simply its supplied warm start. The studied selection rule deterministically favored the first-expanded child, correlating trials; the authors identify this as a possible mechanism, while noting that its causal relationship with makespan remains an inference. Restarts performed better on sparse, irregular workflows, no detectable difference appeared on regular layered workflows, and dense workflows offered little room for improvement. Replacing the selection rule with textbook UCT reduced the deficit to 0.26%, with a confidence interval crossing zero. The results are limited to a controlled synthetic domain of 8, 16, or 32 tasks, 2-8 processors, and budgets up to 2,048; the paper makes no claim about larger budgets.