運用蒙地卡羅樹狀搜尋於多目標彈性零工式工廠排程問題

Abstract

在生產管理和組合最佳化的領域中，彈性零工式工廠排程(Flexible Job Shop Scheduling Problem, FJSP)是一個非常重要的問題，本論文最佳化FJSP是最小化以下三項目標：總時程、總工作量與最大工作量，並採用非凌越解集合(Pareto Solutions)的方式進行最佳化。 近年來，蒙地卡羅樹狀搜尋(Monte-Carlo Tree Search, MCTS) 非常成功地運用於電腦圍棋及其他許多遊戲，本論文將運用MCTS來解FJSP問題。我們的做法是結合MCTS與變鄰域下降演算法(Variable Neighborhood Descent Algorithm)，並且加入一些變異的方法如Rapid Action Value Estimates Heuristic、換位表(Transposition Table)應用於FJSP。 我們的MCTS方法能夠在116秒找出Kacem等人提出之基準問題(benchmark)的17組解：4x5共四組、10x7共三組、8x8共四組、10x10共四組、15x10共兩組，除了8x8有一組沒有找到外，其他皆是目前找到最好的，此結果是目前最好的，與蔣宗哲教授等人提出的簡易演化式演算法(Simple Evolutionary Algorithm)與模因演算法(Memetic Algorithm)相同，雖然Xiaojuan Wang等人提出的演算法有找到額外的一組8x8的解，但他們並沒有找到一些上述提到的解。 本研究是第一個用MCTS解出Kacem等人提出之基準問題中17組目前的最佳解，此結果不亞於其他演算法如基因演算法，在作業數量較多的Mk基準問題中所找到的解也與目前的最佳解相近。

Flexible job-shop scheduling problem (FJSP) is very important in both fields of production management and combinatorial optimization. This thesis addresses the multi-objective flexible job shop scheduling problem (MO-FJSP) with three objectives which minimizing makespan, maximal workload and total workload respectively. We consider these objectives with Pareto manner. Monte-Carlo Tree Search (MCTS) is successful in computer Go and many other games. In this paper, we propose an MCTS algorithm for FJSP. Our algorithm also incorporates Variable Neighborhood Descent Algorithm and other variations like Rapid Action Value Estimates Heuristic and Transposition Table are applied to improve this algorithm. Our algorithm finds Pareto solutions of benchmark problems by Kacem et al.: 4 solutions in 4x5, 3 in 10x7, 4 in 8x8, 4 in 10x10 and 2 in 15x10 within 116 seconds. These solutions are the same as the best found to date. Although one article claimed to find an extra 8x8 solution, that article did not find some of the above solutions. Of the previously attempts to solve the FJSP problem using MCTS, our method yields the best results to date. In Mk benchmark problems, Pareto solutions found by our algorithm are close to the best solutions.