The task of creating a university timetable has always been a difficult one. In the United Kingdom, the recent growth in student numbers and the adoption of modular degree structures by many institutions has made the scheduling of university courses and exams an even bigger problem than it used to be. In this article we will discuss automatic timetable generation. We will consider the use of traditional methods such as graph coloring and of advanced modern methods such as the application of genetic algorithms.
Get full access to this article
View all access options for this article.
References
1.
KarpR. M., Reducibility among Combinatorial Problems, in Complexity of Computer Computations, Plenum Press, New York, 1972.
2.
WelshD. J. A.PowellM. B., An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems, Computer Journal, 10, pp. 85–86, 1967.
3.
MatulaD. W.MarbleG.IsaacsonI. D., Graph Colouring Algorithms, in Graph Theory and Computing, ReadR. C. (ed.), Academic Press, New York, 1972.
4.
ChristofidesN., An Algorithm for the Chromatic Number of a Graph, The Computer Journal, 14, pp. 38–39, 1971.
5.
WilliamsM. R., Heuristic Procedures (If They Work—Leave Them Alone), Software Practical Experience, 4, pp. 237–240, 1974.
6.
BrelazD., New Methods to Color the Vertices of a Graph, Communications of the Association for Computing Machinery, 7, pp. 494–498, 1979.
7.
BurkeE.EllimanD. G.WeareR. F., Automated Scheduling of University Exams, Proceedings of the Institute of Electrical and Electronic Engineers Colloquium on “Resource Scheduling for Large Scale Planning Systems,” Digest No. 1993/144, 1993.
8.
CorneD.FangH. S.MellishC., Solving the Modular Exam Scheduling Problem with Genetic Algorithms, proceedings of the Sixth International Conference of Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Edinburgh, 1993.
9.
PaechterB.CummingA.LuchianH.PetriucM., Two Solutions to the General Timetable Problem Using Evolutionary Methods, proceedings of the Institute of Electrical and Electronic Engineers Conference of Evolutionary Computation, 1994.
10.
BurkeE.EllimanD. G.WeareR. F., A Genetic Algorithm for University Timetabling, AISB Workshop on Evolutionary Computing, Leeds, 1994.
11.
BurkeE.EllimanD. G.WeareR. F., A University Timetabling System Based on Graph Colouring and Constraint Manipulation, Journal of Research on Computing in Education, 27: 1, pp. 1–18, 1994.
12.
CarterM. W., A Survey of Practical Applications of Examination Timetabling Algorithms, Operations Research Practice, 34, pp. 193–202, 1986.
