Abstract Examination timetabling problem is an optimization problem which consists in assigning a set of exams to a set of contiguous time slot, satisfying a set of constraints. The problem falls in the category of the NP-Complete problems and is usually tackled using heuristic methods. In this paper we describe a solution algorithm and its implementation based on the graph heuristics and the evolutionary meta-heuristic called scatter search which operates on a set of solutions by combining two or more elements. New solutions are improved before replacing others according to their quality and diversity. The implementation of the algorithm has been experimented on the popular carter’s benchmarks and compared with the best recent results.

References

[1] Abdullah S. , Ahmadi S., Burke E., and Dror M. , Investigating Ahuja-Orlin's Large Neighbourhood Search Approach for Examination Timetabling, OR Spectrum , vol. 29, no. 2, pp. 351-372, 2007.

[2] Abdullah S., Ahmadi S., Burke E., Dror M., and McCollum B., A Tabu Based Large Neighbourhood Search Methodology for the Capacitated Examination Timetabling Problem, Journal of Operational Research Society, vol. 58, no. 11, pp. 1494-1502, 2007.

[3] Abdullah S. and Burke E. , A Multi-start Large Neighbourhood Search Approach with Local Search Methods for Examination Timetabling, in Long D., Smith S., Borrajo D., and McCluskey L. (eds.) , The International Conference on Automated Planning and Scheduling (ICAPS 2006) , Cumbria, UK, pp. 334-337, 2006.

[4] Arani T. and Lotfi V., A Three Phased Approach to Final Exam Scheduling, IIE Transactions , vol. 21, no. 1, pp. 86-96, 1989.

[5] Asmuni H., Burke E., Garibaldi J., and McCollum B. , Fuzzy Multiple Ordering Criteria for Examination Timetabling, in Burke E. and Trick M. (eds.) , Practice and Theory of Automated Timetabling (PATATV 2004) , Pittsburgh, Lecture Notes in Computer Science Springer -Verlag, vol. 3616, pp. 334-353, 2005.

[6] Brelaz D., New Methods to Colour the Vertices of a Graph, Communications of the Association for Computing Machinery , vol. 22, no. 4, pp. 251-256, 1979.

[7] Boizumault P., Delon Y., and Peridy L., Constraint Logic Programming for Examination Timetabling, Journal of Logic Programming, vol. 26, no. 2, pp. 217-233, 1996.

[8] Burke E. , Bykov Y., Newall J., and Petrovic S., A Time-Predefined Local Search Approach to Exam Timetabling Problems, IIE Transactions on Operations Engineering , vol. 36, no. 6, pp. 509-528, 2004.

[9] Burke E., Bykov Y., and Petrovic S., A Multicriteria Approach to Examination Timetabling, in Burke E. and Erben W. (eds.) , Practice and Theory of Automated Timetabling (PATAT 2000) , Lecture Notes in Computer Science Springer-Verlag, Constance, Germany, vol. 2079, pp. 118-131, 2001.

[10] Burke E., Dror M., McCollum B., Petrovic S., and Qu R., Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems, in Golden B., Raghavan S., and Wasil E. (eds.) , The Next Wave in Computing, Optimization and Decision Technologies, Maryland, vol. 29, no. 1, pp. 79-91, 2005.

[11] Burke E. , McCollum B., Meisels A., Petrovic S., and Qu R. , A Graph-Based Hyper Heuristic for Educational Timetabling Problems, European Journal of Operational Research, vol. 176, no. 1, pp. 177-192, 2007.

[12] Burke E. and Newall J., Enhancing Timetable Solutions with Local Search Methods, in Burke E. and Causmaecker P. (eds.) , Practice and Theory of Automated Timetabling (PATAT 2002) , Lecture Notes in Computer Science Springer -Verlag, Gent, Belgium , vol. 2740, pp. 195-206, 2003.

[13] Burke E. , Petrovic S., and Qu R., Case Based Heuristic Selection for Timetabling Problems, Journal of Scheduling, vol. 9, no. 2, pp. 115-132, 2006.

[14] Burke E. and Newall J., Solving Examination Timetabling Problems Through Adaption of Heuristic Ordering, Annals of Operations Research , vol. 129, no. 2, pp. 107-134, 2004.

[15] Burke E., Newall J., and Weare R., A Simple Heuristically Guided Search for the Timetable Problem, in Alpaydin E. and Fyte C. (eds.) , The International ICSC Symposium on Engineering of Intelligent Systems (EIS'98), University of La Laguna, Spain, ICSC Academic Press, pp. 574-579, 1998.

[16] Burke E. and Bykov Y., Solving Exam Timetabling Problems with the Flex-Deluge Algorithm, in Proceedings of the Practice and Theory of Automated Timetabling Conference (PATAT 2006) , Brno, Czech, pp. 167-180, 2006.

[17] Burke E. , Kendall G., and Soubeiga E., A Tabu Search Hyperheuristic for Timetabling and Rostering, Journal of Heuristics , vol. 9, no. 6, pp. 451-470, 2003.

[18] Caramia, M., DellOlmo P., and Italiano G., New Algorithms for Examinations Timetabling, in Naher S. and Wagner D., (eds.) , Algorithm Engineering 4 th International Workshop WAE 2000, Saarbrucken, Germany, Lecture Notes in Computer Science, Springer-Verlag, vol. 1982, pp. 230-241, 2001.

[19] Carter M., Laporte G., and Lee S., Examination Timetabling: Algorithmic Strategies and Applications, Journal of the Operational Research Society , vol. 47, no. 3, pp. 373-383, 1996.

[20] Casey S. and Thompson J., A Hybrid Algorithm for the Examination Timetabling Problem, in Burke E. and Causmaecker P. (eds.) , Practice and Theory of Automated Timetabling (PATAT 2002), Gent Belgium, Lecture Notes in Computer Science Springer -Verlag, vol. 2740 pp. 205-230, 2002. Scatter Search and Graph Heuristics for the Examination Timetabling Problem 84

[21] C t P., Wong T., and Sabourin R., Application of a Hybrid Multi-Objective Evolutionary Algorithm to the Uncapacitated Exam Proximity Problem, in Burke E. and Trick M. (eds.) , Practice and Theory of Automated Timetabling (PATAT 2004) , Pittsburgh, Lecture Notes in Computer Science Springer -Verlag, vol. 3616, pp. 294-312, 2005.

[22] De Werra D., An Introduction to Timetabling Problem, European Journal of Operational Research, vol. 19, no. 2, pp. 151-162, 1985.

[23] Di Gaspero L. and Schaerf A., Tabu Search Techniques for Examination Timetabling, in Burke E. and Erben W. (eds.) , Practice and Theory of Automated Timetabling (PATAT 2000), Constance, Germany , Lecture Notes in Computer Science Springer-Verlag, vol. 2079, pp. 104-117, 2001.

[24] Eley M. , Ant Algorithms for the Exam Timetabling Problem, in Proceedings of the Practice and Theory of Automated Timetabling Conference (PATAT 2006) , Brno, Czech, pp. 167-180, 2006.

[25] Glover F. , Laguna M., and Marti R., Fundamentals of Scatter Search and Path Relinking, Control and Cybernetics, vol. 29, no. 3, pp. 653-684, 2000 .

[26] Glover F., Laguna M., and Marti R., Scatter Search and Path Relinking: Advances and Applications, in Glover F. and Kochenberger G. (eds.) , Handbook of Meta-Heuristics , Kluwer, pp. 1-36., 2003.

[27] Karp R., Reducibility Among Combinatorial Problems, in Miller R. and Thatcher J. (eds.) , Complexity of Computer Computations, Plenum Press, New York, pp. 85-103, 1972.

[28] Kendall G. and Mohd N. , An Investigation of a Tabu Search Based Hyperheuristic for Examination Timetabling, in Kendall G., Burke E., and Petrovic S. (eds.) , Multidisciplinary Scheduling: Theory and Applications , 1 st International Conference (MISTA 03), Nottingham, UK, pp. 309-328, 2005.

[29] Merlot L., Boland N., Hughes B., and Stuckey P., A Hybrid Algorithm for Examination Timetabling Problem, in Burke E. and Causmaecker P. (eds.) , Practice and Theory of Automated Timetabling (PATAT 2002), Lecture Notes in Computer Science Springer -Verlag, Gent, Belgium, , vol. 2740, pp. 207-231, 2003.

[30] Petrovic S., Yang Y., and Dror M., Case-Based Initialisation for Examination Timetabling, in Proceedings of the 1 st Multidisciplinary International Conference on Scheduling: Theory and Applications ( MISTA 2003) , Nottingham, UK, pp. 137-154, 2003 .

[31] Schaerf A., A Survey of Automated Timetablin g, Artificial Intelligent Revie w, vol. 13, no. 2, pp. 87-127, 1999 .

[32] Thompson J. and Dowsland K., A Robust Simulated Annealing Based Examination Timetabling System, Computers and Operations Research , vol. 25, no. 7, pp. 637-648, 1998.

[33] White G., Xie B., and Zonjic S., Using Tabu Search with Longer-Term Memory and Relaxation to create Examination Timetables, European Journal of Operational Research, vol . 153, no. 16, pp. 80-91, 2004.

[34] Yang Y. and Petrovic S., A Novel Similarity Measure For Heuristic Selection in Examination Timetabling, in Burke E. and Trick M. (eds.) , Practice and Theory of Automated Timetabling (PATAT 2004) , Lecture Notes in Computer Science Springer -Verlag, Pittsburgh, vol. 3616 , pp. 377-396, 2005. Drifa Hadjidj is a lecturer in the Department of Computer Science at Boumerdes University, Algeria. She holds the engineering degree in computer science in 1985, and the Master degree in operational research in 1999, from Algiers USTHB University. Her current research interests are in the area of timetabling problems, meta-heuristics, computational complexity, drawing graphs, and applications of operational research and artificial intelligence. Habiba Drias holds the Master degree in computer science from Case Western Reserve University, Cleveland OHIO USA in 1984, and the Doctorate degree prepared at Paris6 University from Algiers USTHB University in 1993. She has directed the computer science institute of USTHB and then the laboratory of research in artificial intelligence for many years. She has over a hundred published papers in the domain of artificial intelligence, e-commerce, and computational complexity and the satisifiability problem. She is currently the president of the National Institute of Informatics-INI-. 85 The International Arab Journal of Information Technology, Vol. 5, No. 4, October 2008