Average late acceptance randomized descent algorithm for solving course timetabling problems

This work proposes an average late acceptance randomized descent algorithm (ALARD) to solve university course timetabling problems. The aim of this work is to produce an effective algorithm for assigning a set of courses (events) and students to a specific number of rooms and timeslots, subject to a set of constraints. The idea is based on the late acceptance strategy in hill climbing (LAHC). Both LAHC and ALARD use a list to store penalty values of some recently accepted solutions. However, ALARD differs from the basic LAHC as it uses an average quality of accepted solutions in the list as the acceptance criterion, whilst LAHC used the selected solution quality in the acceptance list as the acceptance criterion. Therefore, the performance of ALARD does not rely on the length of list (because the acceptance criterion is based on the threshold value), whilst LAHC is very much depending on the length of the list. Results tested on the Socha´s benchmark datasets showed that, ALARD produces significantly good quality solutions compared to LAHC and comparable to other approaches tested on this dataset.