基于SP-MCTS算法的混合流水车间机器人调度

For the complexity of scheduling process caused by parallel equipments, machine eligibility constraints and material handling robots in hybrid flow shop, the modified Single-player Monte-Carlo Tree Search(SP-MCTS)algorithm was proposed, which included the selection policy blending standard deviation, the expansion of single branch and simulation with heuristic rules. In this algorithm, the hybrid flow shop scheduling problem with robotic transportation was transformed into the shortest time branch path problem in the process of hybrid flow shop state evolution, and Markov Decision Processes(MDP)dynamic model for Hybrid Flow Shop scheduling problem with Robotic Transportation(HFSRT)was established. During the process of optimization, the selection policy was used to evaluate the potential of branches, search high potential branches and expand traversing multiple branch nodes. On this basis, the heuristic rules were used to explore the branch, and a scheduling solution was obtained. Besides, the pruning method was applied to narrow the search range in the search process, and a single branch expansion was used to avoid multiple explorations in identical paths and improve the availability of computing resources. Benchmark examples were applied to test the proposed algorithm, which proved that SP-MCTS algorithm had certain superiority in solving the multi-stage and multi-device hybrid flow shop scheduling problem.