The week's pick
Reseach Article
A Hybrid Genetic Algorithm Approach to a Departmental Class Timetabling Problem Using Efficient Data
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 1 - Number 17 |
| Year of Publication: 2010 |
| Authors: Arvind.S.Babu, R.Chockalingam, S.Kavitha |
10.5120/352-533
|
Arvind.S.Babu, R.Chockalingam, S.Kavitha . A Hybrid Genetic Algorithm Approach to a Departmental Class Timetabling Problem Using Efficient Data. International Journal of Computer Applications. 1, 17 ( February 2010), 99-103. DOI=10.5120/352-533
Abstract
The application of Genetic Algorithm with a local search operation performed within its loop has provided very accurate results, but the algorithm take a lot of time to arrive at an optimal solution. This paper describes the use of a Hybrid Genetic Algorithm using efficient data structures to automate the construction of a departmental class timetable. This problem is concerned with the allocation of faculty resources to concerned student groups and their corresponding timeslots. The quality of the solution is determined in terms of a penalty value which determines the degree to which various constraints are satisfied. This algorithm is tested over established datasets and the performance of the algorithm over different datasets. The result has confirmed that this algorithm in conjuncture with efficient data structures is able to produce high quality solutions for a departmental class timetable with short span of time. It is thus concluded that organization of data plays a major role in the performance of the Hybrid Genetic Algorithm to produce high quality solutions.
References
- E. K. Burke, J.P. Newall, R.F Weare, "A Memetic Algorithm for University Exam timetabling", The Practice and Theory of Automated Timetabling I, Springer Lecture Notes in Computer Science Vol 1153, Springer Verlag, 241-256, 1996
- B. Patcher, A. Cunning. M G Norman, H. Luchian, "Extension to a Memetic Timetabling System", The Practice and Theory of Automated Timetabling I, Springer Lecture Notes in Computer Science Vol 1153, Springer Verlag, 251-265, 1996
- Socha, J Knowles, M. Samples, "A Max Min Ant system for the University course timetabling Problem". In the proceedings of 3rd International Workshop on Ant algorithms, ANTS2002, Springer Lecture Notes in Computer Science Vol. 2463 Springer Verlag. 1-13,2002
- B. Patcher available at http:///www.dcs.napier.ac.uk/~benp
- O. Rossi Doria, M. Samples, M. Bittari, M. Chiarandini, M. Dorigo, Paetche. L . Paquete and T. Suzzle, " A comparison of performance of different meta heuristics on the timetabling problem", Practice and Theory of Automated Timetabling V, Springer Lecture Notes in Computer Science, Vol 2740, Springer Verlag, 241-256, 1996
- E. K. Burke, G. Kendall, E. Soubeiga, "A Tabu -Search Hyperheuristic for Timetabling and Rostering". Journal of heuristics Volume 9, No:6,451-470.2003
- Salwani Abdullah. Edmund Burke and Barry Mc Collum, "A Hybrid Evolutionary Approach to University Course Timetabling Problem", proceedings of IEEE, 2007.
- S. Abdullah, E. K. Burke, B. Mc Collum, "Using a randomized iterative Improvement Algorithm with composite Neighbourhood structures for the University Course timetabling problem", Metaheuristics International Conference MIC 2005 Vienna, Austria 22nd-26th June, 2007
- W.E .Hart. N. Krasnogor, JE Smith, "Memetic Evoultionary Algorithms", Recent Advances in Memetic algorithms: Studies in Fuzziness and soft computing. Springer-Verlag 3-27, 2004
- Selection Methods from "Genetic Algorithms in Search, Optimization, and Machine Learning". ISBN 978-0201157673 by David .E. Goldberg.
Index Terms
Keywords