Memetic Algorithm and its Application to the Arrangement of Exam Timetable

Wenhua Huang, Guisheng Yi, Sulan He

Abstract


This paper looks at Memetic Algorithm for solving timetabling problems. We present a new memetic algorithm which consists of global search algorithm and local search algorithm. In the proposed method, a genetic algorithm is chosen for global search algorithm while a simulated annealing algorithm is used for local search algorithm. In particular, we could get an optimal solution through the .NET with the real data of JiangXi Normal University. Experimental results show that the proposed algorithm can solve the university exam timetabling problem efficiently.


Keywords


Memetic Algorithm, Timetabling, Genetic Algorithm, Simulated Annealing Algorithm

References


Q. Nguyen, Q. Ta, T. Duong, A Memetic Algorithm for Timetabling, Research Informatics Vietnam-Francophony, Can Tho, Vietnam,289-294, February, 2005.

E .Burke, D. Elliman, P. Ford, R. Weare, (1995). Examination timetabling in british universities: a survey.. Lecture Notes in Computer Science, 1153, 76-90.

S. Yang, S. Jat, (2011). Genetic algorithms with guided and local search strategies for university course timetabling. IEEE Transactions on Systems Man & Cybernetics Part C, 41(1), 93-106.

R. Qu, E. Burke, B. Mccollum, L. Merlot, S. Lee, (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12(1), 55-89.

P. Boizumault, Y. Delon, L. Peridy, (1996). Constraint logic programming for examination timetabling. Journal of Logic Programming, 26(2), 217-233.

E. Burke, Y. Bykov, J. Newall, S. Petrovic, (2003). A time-predefined local search approach to exam timetabling problems. IIE Transactions, volume 36(6), 509-528.

J. Thompson, K. Dowsland, (1998). A robust simulated annealing based examination timetabling system. Computers & Operations Research, 25(7-8), 637-648.

R. Raghavjee, N. Pillay, (2011). Using genetic algorithms to solve the South African school timetabling problem. Nature and Biologically Inspired Computing (NaBIC), 2010 Second World Congress on (pp.286-292). IEEE.

S. Abdullah, H. Turabieh, B. McCollum, and E. K. Burke, An Investigation of a Genetic Algorithm and Sequential Local Search Approach for Curriculum-based Course Timetabling Problems, in Proc. Multildisciplinary International Conference on Scheduling:Theory and Applications (MISTA 2009), Dublin, Ireland (2009), pp. 727-731.

S. Abdullah, S. Ahmadi, E. Burke, & Dror, M. (2004). Investigating Ahuja-Orlin’s Large Neighbourhood Search for Examination Timetabling. OR Spectrum (Vol.volume 29, pp.351-372(22)).

J.R. Koza, R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, 1992.


Full Text: PDF

DOI: 10.19139/soic.v4i2.190

Refbacks

  • There are currently no refbacks.