A Rectification Strategy In Genetic Algorithms for Academic Timetabling Problem
DOI:
https://doi.org/10.11113/jt.v74.3041Keywords:
Academic timetabling problem, genetic algorithm, rectification strategyAbstract
The university course timetabling problem is both an NP-hard and NP-complete scheduling problem. The nature of the problem concerns with the assignment of lecturers-courses to available teaching space in an academic institution and may take on the form of high school timetabling, examination timetabling or university course timetabling. In this paper, the authors attempt to construct a feasible timetable for a faculty department in a local university in Malaysia which at the present moment; the scheduling task is performed manually by an academic registrar. The feasible timetable is constructed by means of Genetic Algorithm, embedded with a rectification strategy which transforms infeasible timetables into feasible timetables. Â
References
Bardadym, V. A. 1996. Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science. Computer-Aided School and University Timetabling: The New Wave. 1153: 22–45.
Ismayilova, N. a., Sağir, M., & Gasimov, R. N. 2007. A Multiobjective Faculty–Course–Time Slot Assignment Problem with Preferences. Mathematical and Computer Modelling. 46(7–8): 1017–1029.
Teoh, C. K., Wibowo, A., & Ngadiman, M. S. 2013. Review of State of the Art for Metaheuristic Techniques in Academic Scheduling Problems. Artificial Intelligence Review. doi:10.1007/s10462-013-9399-6.
AgustÃn-Blas, L. E., Salcedo-Sanz, S., Ortiz-GarcÃa, E. G., Portilla-Figueras, A., & Pérez-Bellido, Ã. M. 2009. A Hybrid Grouping Genetic Algorithm for Assigning Students to Preferred Laboratory Groups. Expert Systems with Applications. 36(3, Part 2): 7234–7241.
Jain, A., Jain, S., & Chande, P. K. 2010. Formulation of Genetic Algorithm to Generate Good Quality Course Timetable. 1(3): 248–251.
Kohshori, M., & Abadeh, M. 2012. Hybrid Genetic Algorithms for University Course Timetabling. International Journal of Computer Science. 9(2): 446–455.
Suyanto, S. 2010. An Informed Genetic Algorithm for University Course and Student Timetabling Problems. Proceedings of the 10th international conference on Artificial Intelligence and Soft Computing. 229–236.
Lutuksin, T., & Pongcharoen, P. 2010. Best-Worst Ant Colony System Parameter Investigation by Using Experimental Design and Analysis for Course Timetabling Problem. 2010 Second International Conference on Computer and Network Technology. 467–471.
Thepphakorn, T., Pongcharoen, P., & Hicks, C. 2014. An ant colony based timetabling tool. International Journal of Production Economics. 149(0): 131–144.
Qarouni-Fard, D., Najafi-Ardabili, A., & Moeinzadeh, M.H. 2007. Finding Feasible Timetables with Particle Swarm Optimization. Innovations in Information Technology, 2007. IIT ’07. 4th International Conference on. 387–391.
Shiau, D.F. 2011. A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences. Expert Systems with Applications. 38(1) : 235–248.
Tassopoulos, I. X., & Beligiannis, G. N. 2012. Solving Effectively the School Timetabling Problem Using Particle Swarm Optimization. Expert Systems with Applications. 39(5): 6029–6040.
Aycan, E., & Ayav, T. 2009. Solving the Course Scheduling Problem Using Simulated Annealing. Advance Computing Conference. 6–7.
Frausto-solÃs, J., Alonso-pecina, F., & Mora-vargas, J. 2008. An Efficient Simulated Annealing Algorithm for Feasible Solutions of Course Timetabling. 675–685.
Zhang, D., Liu, Y., M’Hallah, R., & Leung, S. C. H. H. 2010. A Simulated Annealing with a New Neighborhood Structure Based Algorithm for High School Timetabling Problems. European Journal of Operational Research. 203(3): 550–558.
Alvarez-Valdes, R., Crespo, E., & Tamarit, J. M. 2002. Design and Implementation of a Course Scheduling System Using Tabu Search. European Journal of Operational Research. 137(3): 512–523.
Lü, Z.P., & Hao, J.K. 2010. Adaptive Tabu Search for Course Timetabling. European Journal of Operational Research. 200(1) : 235–244.
Othman, M. 2010. Universal Tool for University Course Schedule Using Genetic Algorithm. International Journal. 2(6): 1–6.
Sivanandam, S., & Deepa, S. 2007. Introduction to Genetic Algorithms. Springer. 15–60
Pongcharoen, P., Promtet, W., Yenradee, P., & Hicks, C. 2008. Stochastic Optimisation Timetabling Tool for University Course Scheduling. International Journal of Production Economics. 112(2): 903–918.
Blum, C., & Roli, A. 2003. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys [CSUR]. 1–4.
Downloads
Published
Issue
Section
License
Copyright of articles that appear in Jurnal Teknologi belongs exclusively to Penerbit Universiti Teknologi Malaysia (Penerbit UTM Press). This copyright covers the rights to reproduce the article, including reprints, electronic reproductions, or any other reproductions of similar nature.
