Monte Carlo Tree Search (MCTS) is frequently proposed for scheduling directed‑acyclic‑graph (DAG) workflows, yet most studies never compare it with a much simpler method under the same search effort. We performed such a comparison under a controlled protocol: every arm received an identical budget, i.e., the same number of candidate schedules built and evaluated. The arms were (1) a preregistered MCTS scheduler (main arm), (2) a randomized‑restart list scheduler without a search tree (control), and (3) a textbook UCT MCTS arm as a registered follow‑up. The analysis plan was locked before data collection; an independent checker verified that all 768 confirmation‑stage schedules were valid with correct finish times.
At the main budget of 2048 evaluated schedules, MCTS produced makespans 2.88% worse than the restarts (95% CI [-3.62%,-2.15%]), with 72 of 96 held‑out instances showing positive baseline‑relative headroom. The deficit is not due to budget starvation: in a separate exploration pool restarts self‑improved by 1.85% while MCTS gained only 0.24%; 700 of MCTS's first 720 results were merely the warm start it received. The studied selection rule deterministically locks onto the first‑expanded child, keeping its trials correlated, whereas restarts draw gains from the tails; the causal link to makespan remains inferential. A structural map shows restarts win on sparse irregular workflows, no detectable difference on regular layered ones, and dense workflows leave little room for improvement. Replacing the rule with textbook UCT removes most of the deficit (‑0.26%, 95% CI [-0.71%,+0.23%]) but does not reverse the sign. Results are confined to a controlled synthetic domain (N∈{8,16,32} tasks, 2‑8 processors, budgets up to 2048); we make no claim about larger budgets.
Review