关键词: 混合流水车间, 机器人, 调度策略, 蒙特卡洛搜索树, SP-MCTS算法

Abstract: 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.

Key words: hybrid flow shop, robot, scheduling policy, Mont Calro tree search, single-player Monte-Carlo tree search algorithm