臺灣博碩士論文加值系統

在生產管理和組合最佳化的領域中，彈性零工式工廠排程(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.

摘要 .............................................................................................................. I
ABSTRACT ................................................................................................ II
誌謝 ............................................................................................................ III
目錄 ........................................................................................................... IV
圖表目錄 ..................................................................................................... V
第一章、 介紹 ............................................................................................ 1
1.1 多目標彈性零工式工廠排程問題.................................................. 1
1.2 蒙地卡羅樹狀搜尋.......................................................................... 4
1.3 本論文之目標與貢獻...................................................................... 8
1.4 論文組織.......................................................................................... 8
第二章、先前的研究 ................................................................................... 9
2.1 簡易演化式演算法應用在多目標彈性零工式工廠排程.............. 9
2.2 變鄰域下降演算法應用在多目標彈性零工式工廠排程............ 14
2.3 蒙地卡羅樹狀搜尋應用在多目標彈性零工式工廠排程............ 20
第三章、運用蒙地卡羅樹狀搜尋於多目標彈性零工式工廠排程問題 ...... 24
3.1 符號定義........................................................................................ 24
3.2 目標標準與分數計算.................................................................... 24
3.3 演算法架構.................................................................................... 26
3.4 修改蒙地卡羅樹狀搜尋................................................................ 27
3.5 其他的變異方法............................................................................ 31
第四章、實驗 ............................................................................................ 39
4.1 參數設定........................................................................................ 39
4.2 演算法比較.................................................................................... 45
第五章、結論與未來展望.......................................................................... 47
參考文獻 .................................................................................................... 49

[1] Bagheri, A., Zandieh, M., Mahdavi, I., and Yazdani, M., An artificial immune algorithm for the flexible job-shop scheduling problem, Future Generation Computer Systems 26, pp. 533–541, 2010.
[2] Brandimarte, P., Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, vol. 41, pp. 157–183, 1993.
[3] Browne, C., Monte Carlo Tree Search, http://mcts.ai/.
[4] Chiang, T.C., and Lin, H.J., A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling, International Journal of Production Economics, vol. 141, no.1, pp. 87–98, 2013.
[5] Chiang, T.C., and Lin, H.J., Flexible job shop scheduling using a multiobjective memetic algorithm, Lecture Notes in Artificial Intelligence, vol.6839, pp.49–56, August, 2011.
[6] Chou, C.W., Monte-Carlo Tree Search for Flexible Job-Shop Scheduling, French-Taiwanese Workshop on Energy Management, 2012.
[7] Coulom, R., Efficient selectivity and backup operators in monte-carlo tree search. In P. Ciancarini and H. J. van den Herik, editors. Proceedings of the 5th International Conference on Computers and Games, Turin, Italy, 2006.
[8] Coulom, R., Monte-Carlo tree search in crazy stone, in Proc. Game Prog. Workshop, pp. 74–75, Tokyo, Japan, 2007.
[9] Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactionson Evolutionary Computation 6, pp. 182–197, 2002.
[10] Gelly, S., and Silver, D., Monte-Carlo tree search and rapid action value
49
estimation in computer Go, Artificial Intelligence, pp. 1856–1875, 2011.
[11] Gelly, S., and Wang, Y., Exploration Exploitation in Go: UCT for Monte-Carlo Go, In: Twentieth Annual Conference on Neural Information Processing Systems, NIPS, 2006.
[12] Gao, J., Sun, L.Y., and Gen, M.T., A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Computers &; Operations Research 35 (2008), pp. 2892–2907, 2007.
[13] Giffler, B., and Thomspon, G.L., Algorithms for solving production-scheduling problems. Operations Research 8, pp. 487–503, 1960.
[14] Kacem, I., Hammadi, S., and Borne, P., Pareto-optimality approach for flexible job shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic, Mathematics and Computers in Simulation, vol. 60, pp. 245–276, 2002.
[15] Lee, K.M., Yamakawa, T., and Lee, K.M., Genetic Algorithm for General Machine Scheduling Problems, In: Proceedings of International Conference on Knowledge-based Intelligent Electronic Systems, pp.60–66, 1998.
[16] Li, J.Q., Pan, Q.K., and Chen,J., A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems, International Journal of Production Research, 2011.
[17] Moscato, P., and Norman, M., A memetic approach for the traveling salesman problem: implementation of a computational ecology for combinatorial optimization on message-passing systems. In: Proceedings of the international conference on parallel computing and transputer applications, Amsterdam; 1992.
50
[18] Pezzella, F., Morganti, G., and Ciaschetti, G., A genetic algorithm for the flexible job-shop scheduling problem, Computers &; Operations Research 35, pp. 3202–3212, 2008.
[19]Wang, X., Gao, L., Zhang, C., and Shao, X., A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. International Journal of Advanced Manufacturing Technology 51, pp. 757–767, 2010.
[20] Xia, W.J., and Wu, Z.M., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers &; Industrial Engineering 48, pp. 409–425, 2005.
[21] Zobrist A., A New Hashing Method with Application for Game Playing, ICCA Journal, Vol. 13, No. 2, 1990.