You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
The work presented in this thesis concerns the problem of post enrolment-based course time-tabling. The motivation for this is the increasing importance of the automation of timetabling due to the growth in popularity of Higher Education in recent years. There were 464,910 accepted applicants to universities in the United Kingdom in 2012 which is a 12% rise in five years. This will inevitably lead to an expansion in the number of courses, modules and teachers. As a result, the ability to manually construct timetables has become increasingly impractical.\ud \ud A two-stage approach is investigated that aims to use heuristic and metaheuristic approaches to obtain a satisfactory timetable that suits the needs of the staff and students at educational institutions. The first stage consists of using selection heuristics to construct an initial solution. Two approaches that then attempt to find feasibility are presented. The first applies a tabu search algorithm with a number of neighbourhood operators that navigate the search space for feasible solutions. The second approach implements a PartialCol algorithm. \ud \ud The second stage aims to improve the solution quality by minimising the number of soft constraint violations. The feasibility ratio could be an indicator of the connectivity of the search space, so methods of increasing the feasibility ratio are presented. If the feasibility ratio can be increased then the number of soft constraint violations would be expected to decrease.\ud \ud These techniques were applied to the 24 instances provided for track two of the International Timetabling Competition 2007. The conclusions of the experimentation and investigative processes show that the PartialCol algorithm was more successful, in terms of finding feasible solutions, than the method that employs the neighbourhood operators. However, improvements to the soft constraint penalty were achieved using these neighbourhood operators.
S. Abdullah, H. Turabieh, B. McCollum, and P. McMullan. A hybrid metaheuristic approach to the university course timetabling problem. Journal of Heuristics, 18(1):1{23, 2012.
E. Angel and V. Zissimopoulos. On the landscape ruggedness of the quadratic assignment problem. Theoretical computer science, 263(1):159{172, 2001.
H. Arntzen and A. L kketangen. A tabu search heuristic for a university timetabling problem. In Metaheuristics: Progress as Real Problem Solvers, Operations Research/Computer Science Interfaces Series, pages 65{86. 2005.
H. Asmuni, E. K. Burke, J. Garibaldi, and B. McCollum. Fuzzy multiple heuristic orderings for examination timetabling. In Practice and Theory of Automated Timetabling V, volume 3616 of Lecture Notes in Computer Science, pages 334{353. 2005.
A. S. Asratian and D. de Werra. A generalized class-teacher model for some timetabling problems. European Journal of Operational Research, 143(3):531 { 542, 2002.
J. A. D. Atkin, E. K. Burke, J. Greenwood, and D. Reeson. Hybrid metaheuristics to aid runway scheduling at London Heathrow airport. Transportation Science, 41(1):90{106, 2007.
M. Atsuta, K. Nonobe, and T. Ibaraki. ITC-2007 track 2: An approach using general CSP solver. http://www.cs.qub.ac.uk/itc2007/winner/bestcoursesolutions/Atsuta et al.pdf, 2007.
V. Bardadym. Computer-aided school and university timetabling: The new wave. In Practice and Theory of Automated Timetabling, volume 1153 of Lecture Notes in Computer Science, pages 22{45. 1996.
D. P. Bertsekas and D. A. Castan~on. Parallel asynchronous hungarian methods for the assignment problem. ORSA Journal on Computing, 5(3):261{274, 1993.
G. D. Birkho . The reducibility of maps. American Journal of Mathematics, 35(2):115{128, 1913.
I. Blochliger and N. Zu erey. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 35(3):960{975, 2008.
O. C. Bosquez, P. P. Parra, and F. Lengyel. Towards a deterministic algorithm for the international timetabling competition. Proceedings of the 17th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, 2010.
D. Brelaz. New methods to color the vertices of a graph. Commun. ACM, 22(4):251{256, 1979.
S. Broder. Final examination scheduling. Commun. ACM, 7(8):494{498, 1964.
M. Bufe, T. Fischer, H. Gubbels, C. Hacker, O. Hasprich, C. Scheibel, K. Weicker, N. Weicker, M. Wenig, and C. Wolfangel. Automated solution of a highly constrained school timetabling problem - preliminary results. In Applications of Evolutionary Computing, volume 2037 of Lecture Notes in Computer Science, pages 431{440. 2001.
E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu. A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176(1):177 { 192, 2007.
G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 6(1):47 { 57, 1981.
M. Chiarandini, K. Socha, M. Birattari, and O. Rossi-Doria. International timetabling competition. A hybrid approach. Technical Report AIDA-03-049, Intellectics Group, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany, 2003.
M. Chiarandini, C. Fawcett, and H. H. Hoos. A multiphase modular heuristic solver for post enrollment course timetabling. Journal of Scheduling, pages 2{3, 2008.
A. J. Cole. The preparation of examination time-tables using a small-store computer. The Computer Journal, 7(2):117{121, 1964.
A. Colorni, M. Dorigo, and V. Maniezzo. Genetic algorithms and highly constrained problems: The time-table case. In Parallel Problem Solving from Nature, volume 496 of Lecture Notes in Computer Science, pages 55{59. 1991.
A. Colorni, M. Dorigo, and V. Maniezzo. Metaheuristics for high school timetabling. Computational Optimization and Applications, 9:275{298, 1998.
P. Corr, B. McCollum, M. McGreevy, and P. McMullan. A new neural network based construction heuristic for the examination timetabling problem. In Parallel Problem Solving from Nature - PPSN IX, volume 4193 of Lecture Notes in Computer Science, pages 392{401. 2006.
D. Costa and A. Hertz. Ants can colour graphs. Journal of the Operational Research Society, 48(3):295{305, 1997.
P. Co^te, T. Wong, and R. Sabourin. A hybrid multi-objective evolutionary algorithm for the uncapacitated exam proximity problem. In Practice and Theory of Automated Timetabling V, volume 3616 of Lecture Notes in Computer Science, pages 294{312. 2005.
J. C. Culberson and F. Luo. Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satis ability: second DIMACS implementation challenge, 26:245{284, 1996.
L. Di Gaspero and A. Schaerf. Tabu search techniques for examination timetabling. In Practice and Theory of Automated Timetabling III, volume 2079 of Lecture Notes in Computer Science, pages 104{117. 2001.
L. Di Gaspero and A. Schaerf. Multi-neighbourhood local search with application to course timetabling. In Practice and Theory of Automated Timetabling IV, pages 262{275. 2003.
M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: An autocatalytic optimizing process. Technical Report 91-016 Revised, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991a.
M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy. Technical Report 91-016, Dip. Elettronica, Politecnico di Milano, Italy, 1991b.
R. Dorne and J. K. Hao. A new genetic local search algorithm for graph coloring. In Parallel Problem Solving from Nature - PPSN V, volume 1498 of Lecture Notes in Computer Science, pages 745{754. 1998.
R. Dorne and J. K. Hao. Tabu search for graph coloring, t-coloring and set t-colorings. In Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 77{92. 1999.
K. A. Dowsland. O -the-peg or made-to-measure? timetabling and scheduling with sa and ts. In Practice and Theory of Automated Timetabling II, volume 1408 of Lecture Notes in Computer Science, pages 37{52. 1998.
K. A. Dowsland and J. M. Thompson. Ant colony optimization for the examination scheduling problem. Journal of the Operational Research Society, 56:426{438, 2004.
K. A. Dowsland and J. M. Thompson. An improved ant colony optimisation heuristic for graph colouring. Discrete Applied Mathematics, 156(3):313 { 324, 2008.
G. Dueck. New optimization heuristic: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104:86{92, 1993.
B. McCollum, A. Schaerf, B. Paechter, P. McMullan, R. Lewis, A. J. Parkes, L. D. Gaspero, R. Qu, and E. K. Burke. Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS Journal on Computing, 22:120{130, 2010.
D. Merkle, M. Middendorf, and H. Schmeck. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 6(4):333 { 346, 2002.
L. Merlot, N. Boland, B. Hughes, and P. Stuckey. A hybrid algorithm for the examination timetabling problem. In Practice and Theory of Automated Timetabling IV, volume 2740 of Lecture Notes in Computer Science, pages 207{231. 2003.
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21:1087, 1953.
D. Porumbel, J. K. Hao, and P. Kuntz. Diversity control and multi-parent recombination for evolutionary graph coloring algorithms. In Evolutionary Computation in Combinatorial Optimization, volume 5482 of Lecture Notes in Computer Science, pages 121{132. 2009.