Great deluge with non-linear decay rate for solving course timetabling problems

Landa-Silva, Dario; Obit, Joe Henry

Abstract

Course timetabling is the process of allocating, subject to constraints, limited rooms and timeslots for a set of courses to take place. Usually, in addition to constructing a feasible timetable (all constraints satisfied), there are desirable goals like minimising the number of undesirable allocations (e.g. courses timetabled in the last timeslot of the day). The construction of course timetables is regarded as a complex problem common to a wide range of educational institutions. The great deluge algorithm explores neighbouring solutions which are accepted if they are better than the best solution so far or if the detriment in quality is no larger than the current water level. In the original great deluge, the water level decreases steadily in a linear fashion. In this paper, we propose a modi-fied version of the great deluge algorithm in which the decay rate of the water level is non-linear. The proposed method produces new best results in 4 of the 11 course timetabling problem instances used in our experiments. © 2008 IEEE.

• Conference Name: 2008 4th International IEEE Conference Intelligent Systems, IS 2008
• Start Date: Sep 6, 2008
• End Date: Sep 8, 2008
• Online Publication Date: Nov 11, 2008
• Publication Date: Dec 1, 2008
• Deposit Date: Feb 10, 2020
• Publisher: Institute of Electrical and Electronics Engineers
• Volume: 1
• Pages: 811-818
• DOI: https://doi.org/10.1109/IS.2008.4670447
• Public URL: https://nottingham-repository.worktribe.com/output/3088165
• Publisher URL: https://ieeexplore.ieee.org/document/4670447