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

Translated title of the contribution: SP-MCTS algorithm for hybrid flow shop scheduling problem with robotic transportation

Jian Guo, Yaoyao Shi, Wei Zhang, Yasong Pu, Junfeng Zhang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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.

Translated title of the contributionSP-MCTS algorithm for hybrid flow shop scheduling problem with robotic transportation
Original languageChinese (Traditional)
Pages (from-to)2208-2218
Number of pages11
JournalJisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS
Volume25
Issue number9
DOIs
StatePublished - 1 Sep 2019

Fingerprint

Dive into the research topics of 'SP-MCTS algorithm for hybrid flow shop scheduling problem with robotic transportation'. Together they form a unique fingerprint.

Cite this