Dynamic Monte-Carlo Tree Search Algorithm for Multi-Objective Flexible Job-shop Scheduling Problem

Scheduling is a key factor in real-world production management and manufacturing system. The Job-shop Scheduling Problem (JSP) is important in combinatorial optimization and well known as an NP-hard. The Flexible Job-shop scheduling problem (FJSP) is an extension of the JSP, which allows an operation may be processed by any machine from a given set. It is more complex than JSP and quite difficult to achieve an optimal solution with traditional optimization approaches owing to the high computational complexity. The intent of this paper is to develop an efficient Dynamic Monte-Carlo Tree Search model for solving the multi-objective FJSP. First, a Sequential Operation-Machine Assignment (SOMA) scheme is proposed for encoding representation, lead to potentially produce feasible candidate solutions for the FJSP. Then evolution-based FJSP mapping to a general tree search structure via the SOMA is successively completed. Second, the original single-objective UCT (Upper Confidence bound apply to Tree) algorithm is modified (called NSUCT) by using a Non-dominated Sorting strategy to be able to deal with multi-objective optimization problems. Third, the dynamic Monte-Carlo sampling technique is adopted for the tree search evaluation and guided with NSUCT to balance between exploitation and exploration during the evolution process. Finally, theMulti-Objective Monte-Carlo Tree Search (MOMCTS) algorithm is proposed to solve the FJSP for finding the Pareto-optimal solutions. Several popular benchmark problems with various conditions are considered to compare the proposed MOMCTS algorithm with the published algorithms. Simulation results show that the MOMCTS is able to acquire wide range of Pareto-optimal solutions. In addition, the more decision-makings of the results in the form of Gantt chart under the same Pareto-optimal solutions can be obtained