Research On Dynamic Job Shop Rescheduling Algorithm Based On Monte Carlo Tree Search

Job shop scheduling problem(JSP),as an important production scheduling problem,has been highly valued by academics and enterprises in recent years.Existing researches focus on the problem of static job shop scheduling,and put forward a series of production scheduling models and solutions.However,in actual production,various unpredictable emergencies often occur,such as machine breakdowns,random job arrivals,and changes in processing time.In order to ensure the stable and orderly operation of the entire production system,manufacturing companies need to perform the necessary dynamic scheduling to deal with these emergencies,adjust or modify the original scheduling plan,and quickly generate a rescheduling plan.Therefore,it is of great theoretical significance and application value to study the workshop rescheduling algorithm under the influence of dynamic events.This paper studies the dynamic job shop scheduling problem(DJSP).The research contents are as follows:(1)For the static Job-shop scheduling model,the optimization goal is to minimize the maximum completion time,and an improved genetic algorithm is used to solve it.A new heuristic scheduling rule is proposed according to the characteristics of the Job-shop scheduling problem,and a new population initialization method is designed based on the six scheduling rules commonly used in the literature(SPT,LPT,FIFO,LIFO,SRPT and LRPT).Based on 29 JSP benchmark problems,comparative experiments are conducted.The experimental results show that the proposed population initialization method can significantly improve the convergence speed and solution quality of the genetic algorithm.(2)Focus on the study of the four common dynamic events in the production system,which are changes in processing time,machine breakdowns,random job arrivals and order cancellation,and establish a dynamic JSP mathematical model that integrates these four dynamic events.And according to the characteristics of each dynamic event,the corresponding rescheduling mechanism is established.In order to solve the dynamic JSP scheduling model,an event-driven rescheduling method based on Monte Carlo tree search(MCTS-ERM)is proposed is proposed.(3)The proposed MCTS-ERM includes the following research work: First,the dynamic Job-shop scheduling problem is modeled as an MCTS search tree.Secondly,in order to improve the search efficiency of MCTS,the MCTS has been improved.The main improvement methods are the use of subtree keeping and Rapid Action Value Estimates(RAVE)optimization technology.Three optimization techniques of subtree pruning,prior knowledge and Transposition Table are designed.These five optimization techniques are embedded in the search process of MCTS.Then,based on the improved MCTS,a new rescheduling method MCTS-ERM is designed,including scheduling rules and MCTS multi-stage joint scheduling mechanism design,and improvement of MCTS node selection strategy.Finally,15 DJSP benchmark problems are designed based on the benchmark problem of static JSP scheduling problem FT10,and multiple sets of comparative experiments are performed on MCTS-ERM.Experimental results show that the proposed MCTS-ERM has better performance in CPU time and solution quality than other rescheduling algorithms.