Abstract
This paper presents a Greedy Randomised Adaptive Search Procedure for solving the examination scheduling problem. GRASP is a two-phased multi-start or iterative method consisting of a construction phase and an improvement phase. Each iteration builds a feasible solution using a probabilistic selection procedure, and then optimises the solution using a local search technique.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahura, R.K., Orlin, J.B., Tiwari, A.: A Greedy Genetic Algorithm for the Quadratic Assignment Problem. Technical Report. Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA (1997)
Burke, E.K., Elliman, D.G., Ford, P.H., Weare, R.F.: Examination Timetabling in British Universities – a Survey. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 76–90. Springer, Heidelberg (1996)
Burke, E.K., Newall, J., Weare, R.F.: A Memetic Algorithm for University Examination Timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 241–250. Springer, Heidelberg (1996)
Caramia, M., Dell’Olmo, P., Italiano, G.F.: New Algorithms for Examination Timetabling. In: Näher, S., Wagner, D. (eds.) WAE 2000. LNCS, vol. 1982, pp. 230–241. Springer, Heidelberg (2001)
Carter, M.W.: A Survey of Practical Applications of Examination Timetabling. Oper. Res. 34, 193–202 (1986)
Carter, M.W., Laporte, G., Chinneck, J.W.: A General Examination Scheduling System. Interfaces 24, 109–120 (1994)
Carter, M.W., Laporte, G., Lee, S.T.: Examination Timetabling: Algorithmic Strategies and Applications. J. Oper. Res. Soc. 47, 373–383 (1996)
Corne, D., Ross, P., Fang, H.L.: Fast Practical Evolutionary Timetabling. In: Fogarty, T.C. (ed.) AISB-WS 1994. LNCS, vol. 865, Springer, Heidelberg (1994)
Di Gaspero, L., Schaerf, A.: Tabu Search Techniques for Examination Timetabling. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 104–117. Springer, Heidelberg (2001)
Feo, T.A., Bard, J.: Flight Scheduling and Maintenance Base Planning. Manage. Sci. 35, 1415–1432 (1989)
Feo, T.A., Resende, M.G.C., Smith, S.H.: A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set. Oper. Res. 42, 860–878 (1994)
Fleurent, C., Glover, F.: Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory. INFORMS J. Comput. 11, 198–204 (1999)
Johnson, D.: Timetabling University Examinations. J. Oper. Res. Soc. 41, 39–47 (1990)
Klincewicz, J.: Avoiding Local Optima in the p-hub Location Problem Using Tabu Search and GRASP. Technical Report. AT&T Laboratories, Holmdel, NJ (1989)
Laporte, G., Descroches, S.: Examination Timetabling by Computer, Comput. Oper. Res. 11, 351–360 (1984)
Laguna, M., Gonzalez-Velarde, J.: A Search Heuristic for Just-in-Time Scheduling in Parallel Machines. J. Intell. Manufact. 2, 253–260 (1991)
Laguna, M., Marti, R.: A GRASP for Coloring Sparse Graphs. Technical Report. Graduate School of Business, University of Colorado, Boulder, CO (1998)
Merlot, L.T.G., Boland, N., Hughes, B.D., Stuckey, P.J.: A Hybrid Algorithm for the Examination Timetabling problem. In: Proc. 4th Int. Conf. Pract. Theory Automat. Timetabling, pp. 348–371 (2002)
Prais, M., Ribeiro, C.C.: Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment. Technical Report. Department of Computer Science, Catholic University of Rio de Janeiro, Brazil (1998)
Thompson, J.M., Dowsland, K.A.: Variants of Simulated Annealing for the Examination Timetabling Problem. Ann. Oper. Res. 63, 105–128 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Casey, S., Thompson, J. (2003). GRASPing the Examination Scheduling Problem. In: Burke, E., De Causmaecker, P. (eds) Practice and Theory of Automated Timetabling IV. PATAT 2002. Lecture Notes in Computer Science, vol 2740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45157-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-45157-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40699-0
Online ISBN: 978-3-540-45157-0
eBook Packages: Springer Book Archive