A Hybrid Simulated Annealing- Genetic Algorithm for Course Time Tabling Problem
Sergio Caballero-Caballero1, Jaime Mora-Vargas2, Juan Frausto-Solís3, Miguel González Mendoza4
1MSc. Sergio Alex Caballero-Caballero, Department of Industrial Engineering, Tecnologico de Monterrey, Mexico.
2Dr. Jaime Mora-Vargas, Graduate Programs Engineering, Tecnologico de Monterrey, Atizapan, Mexico.
3Dr. Juan Frausto-Solis, Department of Computer Science, Tecnologico de Monterrey, Cuernavaca, Mexico.
4Dr. Miguel González-Mendoza, Graduate Programs Engineering, Tecnologico de Monterrey, Atizapan, Mexico.
Manuscript received on 20 March 2014 | Revised Manuscript received on 25 March 2014 | Manuscript published on 30 March 2014 | PP: 65-70 | Volume-3 Issue-1, March 2014 | Retrieval Number: A0999033114/2014©BEIESP
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Course timetabling problem (CTP) consists on assigning a set of courses into a limited group of timeslots. Among the huge variety of algorithms proposed to solve it, Simulated Annealing (SA) is one with the best performance; even though not always find the optimal solution. Besides it is known that SA converges to a very good solution whether its parameters are correctly tuned. In this sense, how to improve SA performance is an open area; two general SA features require to be researched: 1) To improve its exploration capacity and 2) To develop confident tuning schemes. In this paper, a new hybrid algorithm named SA-GA is presented which it uses SA with Genetic Algorithms (GA). This hybridization uses a Markov tuning approach with a good exploration feature given by the genetic method in order to solve CTP. Also the mathematical CTP problem is presented and a several statistical significance testing method are applied.
Keywords: (CTP), (SA), SA, CTP.
Scope of the Article: Algorithm Engineering