International Journal on Advanced Science, Engineering and Information Technology, Vol. 9 (2019) No. 6, pages: 1936-1943, DOI:10.18517/ijaseit.9.6.10224

Monte Carlo Tree Search in Finding Feasible Solutions for Course Timetabling Problem

Say Leng Goh, Graham Kendall, Nasser R. Sabar

Abstract

We are addressing the course timetabling problem in this work. In a university, students can select their favorite courses each semester. Thus, the general requirement is to allow them to attend lectures without clashing with other lectures. A feasible solution is a solution where this and other conditions are satisfied. Constructing reasonable solutions for course timetabling problem is a hard task. Most of the existing methods failed to generate reasonable solutions for all cases. This is since the problem is heavily constrained and an effective method is required to explore and exploit the search space. We utilize Monte Carlo Tree Search (MCTS) in finding feasible solutions for the first time. In MCTS, we build a tree incrementally in an asymmetric manner by sampling the decision space. It is traversed in the best-first manner. We propose several enhancements to MCTS like simulation and tree pruning based on a heuristic. The performance of MCTS is compared with the methods based on graph coloring heuristics and Tabu search. We test the solution methodologies on the three most studied publicly available datasets. Overall, MCTS performs better than the method based on graph coloring heuristic; however, it is inferior compared to the Tabu based method. Experimental results are discussed.

Keywords:

combinatorial optimization; timetabling; monte carlo tree search; graph coloring heuristics; tabu search.

Viewed: 226 times (since Sept 4, 2017)

cite this paper     download