Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study

Monte Carlo Tree Search (MCTS) is frequently suggested for scheduling directed-acyclic-graph (DAG) workflows. However, many studies do not conduct the necessary comparisons that could challenge this approach by applying the same search effort to a simpler method. This study addresses that gap through a controlled protocol. All methods evaluated received the same budget, which consisted of an equal number of candidate schedules built and assessed. The main arm was an MCTS scheduling method, while a randomized-restart list scheduler without a search tree served as the control. Additionally, a textbook-UCT MCTS arm was included as a registered follow-up in the same domain. The analysis plan was established prior to data collection, and an independent verifier confirmed that all 768 confirmation-stage schedules were valid and had accurate finish times. With a primary budget of 2048 evaluated schedules, MCTS performed 2.88% worse than the randomized restarts, with a 95% confidence interval of [-3.62%, -2.15%], and 72 out of 96 held-out instances showed positive baseline-relative headroom. This performance deficit was not due to budget starvation; in a separate exploration pool, the restarts improved by 1.85%, while MCTS only gained 0.24%. Notably, 700 of the 720 initial results from MCTS were simply the warm start it received. The selection rule employed deterministically focused on the first-expanded child, maintaining correlation among trials, while the restarts benefited from gains in the tails. The causal relationship to makespan remains an inference. A structural map indicates where the tree ceases to be effective: restarts excel in sparse irregular workflows, no significant difference is observed in regular layered workflows, and dense workflows offer no opportunity for improvement. Changing the selection rule to textbook UCT mitigates most of the deficit, resulting in a change of -0.26% with a 95% confidence interval of [-0.71%, +0.23%], though it does not reverse the outcome. The findings are limited to a controlled synthetic domain with task counts of N in {8, 16, 32}, 2-8 processors, and budgets up to 2048, and no claims are made regarding larger budgets.

Source: arxiv.org