Non-Linear Great Deluge with Reinforcement Learning for University Course Timetabling

Abstract. This paper describes a non-linear great deluge hyper-heuristic incorporating a reinforcement learning mechanism for the selection of low-level heuristics and a non-linear great deluge acceptance criterion. The proposed hyper-heuristic deals with complete solutions, i.e. it is a solution improvement approach not a constructive one. Two types of re-inforcement learning are investigated: learning with static memory length and learning with dynamic memory length. The performance of the pro-posed algorithm is assessed using eleven test instances of the univer-sity course timetabling problem. The experimental results show that the non-linear great deluge hyper-heuristic performs better when using static memory than when using dynamic memory. Furthermore, the algorithm with static memory produced new best results for five of the test in-stances while the algorithm with dynamic memory produced four best results compared to the best known results from the literature.