Skip to main content

Research Repository

See what's under the surface

Advanced Search

Automated generation of constructive ordering heuristics for educational timetabling

Pillay, Nelishia; Özcan, Ender

Authors

Nelishia Pillay

Ender Özcan ender.ozcan@nottingham.ac.uk



Abstract

Construction heuristics play an important role in solving combinatorial optimization problems. These heuristics are usually used to create an initial solution to the problem which is improved using optimization techniques such as metaheuristics. For examination timetabling and university course timetabling problems essentially graph colouring heuristics have been used for this purpose. The process of deriving heuristics manually for educational timetabling is a time consuming task. Furthermore, according to the no free lunch theorem different heuristics will perform well for different problems and problem instances. Hence, automating the induction of construction heuristics will reduce the man hours involved in creating such heuristics, allow for the derivation of problem specific heuristics and possibly result in the derivation of heuristics that humans have not thought of. This paper presents generation construction hyper-heuristics for educational timetabling. The study investigates the automatic induction of two types of construction heuristics, namely, arithmetic heuristics and hierarchical heuristics. Genetic programming is used to evolve arithmetic heuristics. Genetic programming, genetic algorithms and the generation of random heuristic combinations is examined for the generation of hierarchical heuristics. The hyper-heuristics generating both types of heuristics are applied to the examination timetabling and the curriculum based university course timetabling problems. The evolved heuristics were found to perform much better than the existing graph colouring heuristics used for this domain. Furthermore, it was found that the while the arithmetic heuristics were more effective for the examination timetabling problem, the hierarchical heuristics produced better results than the arithmetic heuristics for the curriculum based course timetabling problem. Genetic algorithms proved to be the most effective at inducing hierarchical heuristics.

Journal Article Type Article
Journal Annals of Operations Research
Print ISSN 0254-5330
Electronic ISSN 1572-9338
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
APA6 Citation Pillay, N., & Özcan, E. (in press). Automated generation of constructive ordering heuristics for educational timetabling. Annals of Operations Research, doi:10.1007/s10479-017-2625-x. ISSN 0254-5330
DOI https://doi.org/10.1007/s10479-017-2625-x
Keywords Educational timetabling; Construction heuristics; Hyper-heuristics; Genetic programming; Genetic algorithms
Publisher URL https://link.springer.com/article/10.1007%2Fs10479-017-2625-x
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
Additional Information The final publication is available at Springer via http://dx.doi.org/10.1007/s10479-017-2625-x

Composition Type:

Files

GPHH_tt.pdf (297 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;