When All Paths Lead to Dead End: Deadlock-Depth-guided Monte Carlo Tree Search for Reentrant Blocking Hybrid Flow Shops

Monte Carlo Tree Search (MCTS) performance degrades significantly in Reentrant Blocking Hybrid Flow Shop (RBHFS) scheduling, which arises in modern automated scientific laboratories. The interaction of blocking and reentrant constraints causes rollout simulations to consistently end in a “dense deadlock.” As a result, infeasible branches become indistinguishable, which undermines the exploitation capability of standard MCTS and effectively reduces it to uniform random exploration. However, we find that deadlocks are not equally uninformative. We observe that the average rollout deadlock depth—the number of steps executed before failure—across different action branches shows a strong positive correlation with true feasibility probability, making it a reliable proxy for the latent likelihood that a branch contains feasible solutions. Guided by this insight, we propose Deadlock-Depth Guided MCTS ($D^2$-MCTS). By integrating deadlock-depth statistics into the evaluation mechanism, $D^2$-MCTS is able to distinguish among otherwise indistinguishable infeasible branches. Empirical results demonstrate that $D^2$-MCTS significantly outperforms state-of-the-art baselines, demonstrating superior robustness and efficiency.