|
|
 |
| |
|
|
|
Dynamic Monte-Carlo Tree Search Algorithm for Multi-Objective Flexible Job-shop Scheduling Problem |
|
|
|
PP: 1531-1539 |
|
|
|
doi:10.18576/amis/100431
|
|
|
|
Author(s) |
|
|
|
Chun-Liang Lu,
Shih-Yuan Chiu,
Jiinpo Wu,
Li-Pen Chao,
|
|
|
|
Abstract |
|
|
| 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. |
|
|
|
|
|
|
|
