Browsing by Author "Wu, Tung-Ying"

Now showing 1 - 2 of 2

A New MCTS-Based Algorithm for Multi-Objective Flexible Job Shop Scheduling Problem
(2015)
Chou, Jen-Jai
;
Liang, Chao-Chin
;
Wu, Hung-Chun
;
Wu, I-Chen
;
Wu, Tung-Ying
Multi-objective flexible job-shop scheduling problem (MO-FJSP) is very important in both fields of production management and combinatorial optimization. Wu et al. proposed a Monte-Carlo Tree Search (MCTS) to solve MO-FJSP and successfully improved the performance of MCTS to find 17 Pareto solutions: 4 of Kacem 4x5, 3 of 10x7, 4 of 8x8, 4 of 10x10, and 2 of 15x10. This paper proposes a new MCTS-based algorithm for MO-FJSP problem by modifying their algorithm. Our experimental results show that our new algorithm significantly outperforms their algorithm for large problems, especially for Kacem 15x10. This shows that the new algorithm tends to have better potential of solving harder MO-FJSP problems.
Multi-Objective Flexible Job Shop Scheduling Problem Based on Monte-Carlo Tree Search
(2013-01-01)
Wu, Tung-Ying
;
Wu, I-Chen
;
Liang, Chao-Chin
;
資訊工程學系
;
Department of Computer Science
Flexible job-shop scheduling problem (FJSP) is very important in both fields of production management and combinatorial optimization. This paper focuses on the multi-objective flexible job shop scheduling problem (MO-FJSP) with three objectives which minimizing makespan, total workload and maximal workload, respectively, with Pareto manner. In addition, Monte-Carlo Tree Search (MCTS) is successful in computer Go and many other games. Hence, solving FJSP by MCTS is a new attempt. In this paper, we propose an MCTS algorithm for FJSP, by incorporating Variable Neighborhood Descent Algorithm and other techniques like Rapid Action Value Estimates Heuristic and Transposition Table. Our algorithm finds Pareto solutions of the benchmark problems proposed by Kacem et al. within 116 seconds: 4 solutions in 4x5, 3 in 10x7, 4 in 8x8, 4 in 10x10 and 2 in 15x10. These solutions are the same as the best found to date. Although one article claimed to have an extra 8x8 solution, that article did not find some of the above solutions.