An Exploration and Exploitation-Based Metaheuristic Approach for University Course Timetabling Problems
Rakesh P. Badoni,
Jayakrushna Sahoo,
Shwetabh Srivastava,
Mukesh Mann,
D. K. Gupta,
Swati Verma,
Predrag S. Stanimirović,
Lev A. Kazakovtsev,
Darjan Karabašević
Affiliations
Rakesh P. Badoni
Department of Mathematics, École Centrale School of Engineering, Mahindra University, Hyderabad 500043, India
Jayakrushna Sahoo
Department of Computer Science & Engineering, Indian Institute of Information Technology Kottayam, Kottayam 686635, India
Shwetabh Srivastava
CMP Degree College, University of Allahabad, Prayagraj 211002, India
Mukesh Mann
Department of Computer Science & Engineering, Indian Institute of Information Technology, Sonepat 131029, India
D. K. Gupta
Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur 721302, India
Swati Verma
CSIR-National Institute of Oceanography, Panaji 403004, India
Predrag S. Stanimirović
Faculty of Sciences and Mathematics, University of Niš, 18000 Niš, Serbia
Lev A. Kazakovtsev
Laboratory “Hybrid Methods of Modelling and Optimization in Complex Systems”, Siberian Federal University, Prosp. Svobodny 79, 660041 Krasnoyarsk, Russia
Darjan Karabašević
Faculty of Applied Management, Economics and Finance, University Business Academy in Novi Sad, Jevrejska 24, 11000 Belgrade, Serbia
The university course timetable problem (UCTP) is known to be NP-hard, with solution complexity growing exponentially with the problem size. This paper introduces an algorithm that effectively tackles UCTPs by employing a combination of exploration and exploitation strategies. The algorithm comprises two main components. Firstly, it utilizes a genetic algorithm (GA) to explore the search space and discover a solution within the global optimum region. Secondly, it enhances the solution by exploiting the region using an iterated local search (ILS) algorithm. The algorithm is tested on two common variants of UCTP: the post-enrollment-based course timetable problem (PE-CTP) and the curriculum-based course timetable problem (CB-CTP). The computational results demonstrate that the proposed algorithm yields competitive outcomes when compared empirically against other existing algorithms. Furthermore, a t-test comparison with state-of-the-art algorithms is conducted. The experimental findings also highlight that the hybrid approach effectively overcomes the limitation of local optima, which is encountered when solely employing GA in conjunction with local search.
