TY - JOUR
T1 - 基于SP-MCTS算法的混合流水车间机器人调度
AU - Guo, Jian
AU - Shi, Yaoyao
AU - Zhang, Wei
AU - Pu, Yasong
AU - Zhang, Junfeng
N1 - Publisher Copyright:
© 2019, Editorial Department of CIMS. All right reserved.
PY - 2019/9/1
Y1 - 2019/9/1
N2 - 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.
AB - 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.
KW - Hybrid flow shop
KW - Mont Calro tree search
KW - Robot
KW - Scheduling policy
KW - Single-player Monte-Carlo tree search algorithm
UR - http://www.scopus.com/inward/record.url?scp=85076338533&partnerID=8YFLogxK
U2 - 10.13196/j.cims.2019.09.009
DO - 10.13196/j.cims.2019.09.009
M3 - 文章
AN - SCOPUS:85076338533
SN - 1006-5911
VL - 25
SP - 2208
EP - 2218
JO - Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS
JF - Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS
IS - 9
ER -