Skip to main content
SpringerLink
Log in

A memetic algorithm for university exam timetabling

  • Genetic Algorithms
  • Conference paper
  • First Online:
Practice and Theory of Automated Timetabling (PATAT 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1153))

Abstract

The scheduling of exams in institutions of higher education is known to be a highly constrained problem. The advent of modularity in many institutions in the UK has resulted in a significant increase in its complexity, imposing even more difficulties on university administrators who must find a solution, often without any computer aid.

Of the many methods that have been applied to solving the problem automatically, evolutionary techniques have shown much promise due to their general purpose optimisation capabilities. However, it has also been found that hybrid evolutionary methods can yield even better results. In this paper we present such a hybrid approach in the form of an evolutionary algorithm that incorporates local search methods (known as a memetic algorithm).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Peter Ross, Dave Corne: Improving evolutionary timetabling with delta evaluation and directed mutation. Parallel Problem Solving in Nature III, Ed. Y. Davidor, Springer Verlag, (1994)

    Google Scholar 

  2. E. K. Burke, D. G. Elliman, R. F. Weare: Examination Timetabling in British Universities — A Survey. Proceedings of the 1st International Conference on the Practice and Theory of Automated Timetabling, (Napier University, Edinburgh, UK) (1995)

    Google Scholar 

  3. E. K. Burke, D. G. Elliman, R. F. Weare: Specialised Recombinative Operators for Timetabling Problems. Lecture Notes in Computer Science 993 (Evolutionary Computing), Springer-Verlag, Ed. T. C. Fogarty, 1995, pp 75–85

    Google Scholar 

  4. E. K. Burke, D. G. Elliman, R. F. Weare: A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems. 6th International Conference on Genetic Algorithms (Pittsburgh, USA), 15–19 July 1995

    Google Scholar 

  5. Peter Ross, Dave Corne: Applications of Genetic Algorithms. AISB Quarterly 89, Ed. T.C. Fogarty, (1994), 23–30

    Google Scholar 

  6. Dave Corne, Peter Ross, Hsiao-Lan Fang: Fast Practical Evolutionary Timetabling, Lecture Notes in Computer Science 865 (Evolutionary Computing), Springer-Verlag, Ed T. C. Fogarty, (1994), 250–263

    Google Scholar 

  7. Nicholas J. Radcliffe, Patrick D. Surry: Formal Memetic Algorithms. Lecture Notes in Computer Science 865 (Evolutionary Computing) Springer-Verlag, Ed. T. C. Fogarty, (1994), 250–263

    Google Scholar 

  8. Pablo Moscato, Michael G. Norman: A “Memetic” approach for the travelling salesman problem — implementation of a computational ecology for combinatorial optimisation on message-passing systems. Proceedings of the International Conference on Parallel computing and Transputer Applications, IOS Press (Amsterdam)

    Google Scholar 

  9. E.K. Burke, D.G. Elliman, R.F. Weare: Extensions to a University Exam Timetabling Systems. IJCAI '93 Workshop on Knowledge-Based Production Planning, Scheduling and Control (1993)

    Google Scholar 

  10. E.K. Burke, D.G. Elliman, R.F. Weare: A University Timetabling System Based on Graph Colouring and Constraint Manipulation, Journal of Research on Computing in Education, (1993)

    Google Scholar 

  11. EK Burke, DG Elliman, RF Weare: A Genetic Algorithm based University Timetabling System. 22nd East-West International Conference on Computer Technologies in Education (Crimea, Ukraine, 19th–23rd Sept 1994) (1994) 35–40

    Google Scholar 

  12. Davis L.: Handbook of Genetic Algorithms. Van Nostrand Reinhold, (1991)

    Google Scholar 

  13. Dawkins R.: The Selfish Gene. Oxford University Press, (1976)

    Google Scholar 

  14. Paechter B., Cumming A., Luchian H.: The Use of Local Search Suggestion Lists for Improving the Solution of Timetabling Problems with Evolutionary Algorithms. Lecture Notes in Computer Science 993 (Evolutionary Computing), Springer-Verlag, Ed. T. Fogarty, (1995), 86–93

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Nottingham, University Park, Nottingham, UK

    E. K. Burke, J. P. Newall & R. F. Weare

Authors
  1. E. K. Burke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. P. Newall
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. F. Weare
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Edmund Burke Peter Ross

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Burke, E.K., Newall, J.P., Weare, R.F. (1996). A memetic algorithm for university exam timetabling. In: Burke, E., Ross, P. (eds) Practice and Theory of Automated Timetabling. PATAT 1995. Lecture Notes in Computer Science, vol 1153. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61794-9_63

Download citation

  • DOI: https://doi.org/10.1007/3-540-61794-9_63

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61794-5

  • Online ISBN: 978-3-540-70682-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation