Monte Carlo tree search for the multi-crane scheduling problem with temporal constraints

Abstract This study addresses the multi-crane scheduling problem with temporal constraints (MCSPTC) arising in steelmaking shops, where multiple rail-guided overhead cranes transport materials on shared tracks and must strictly avoid interference. The problem requires jointly determining task assignment and sequencing decisions while satisfying temporal constraints on task start times, including time windows and precedence relations. In practice, manufacturing execution system data are updated frequently, requiring high quality solutions to be generated repeatedly within short computation times. However, existing heuristics lack quality guarantees, while exact models do not scale to industrial-size instances within practical time limits. To tackle these challenges, we formulate the MCSPTC as a sequential decision process and propose a Monte Carlo tree search (MCTS)–based solution framework. The proposed approach performs look-ahead planning at each decision point using a schedule construction mechanism. To improve search efficiency, we develop a feasibility-based action pruning strategy that eliminates actions inevitably leading to infeasible schedules prior to node expansion. We further tailor the value backup and final action selection rules to account for the tight temporal feasibility and the varying size of the feasible action space induced by temporal constraints. Our numerical results suggest that the proposed MCTS framework yields better solutions than existing heuristics within short computation times. In particular, the proposed method improves upon the heuristic baselines by approximately 5%–7% for both small and medium-scale instances within one minute and large-scale instances within about three minutes.