Abstract
Examination timetabling problems is the allocation of exams into feasible slots and rooms subject to a set of constraints. Constraints can be categorized into hard and soft constraints where hard constraints must be satisfied while soft constraints are not necessarily to satisfy but be minimized as much as possible in order to produce a good solution. Generally, UMSLIC produces exam timetable without considering soft constraints. Therefore, this paper proposes the application of two algorithms which are Constraint Programming and Simulated Annealing to produce a better solution. Constraint Programming is used to generate feasible solution while Simulated Annealing is applied to improve the quality of solution. Experiments have been conducted with two datasets and the results show that the proposed algorithm managed to improve the solution regardless the different problem instances.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Abdullah, S.: Heuristic Approaches For University Timetabling Problems. The School of Computer Science and Information Technology (2006).
Abramson, D.: A Very High Speed Architecture for Simulated Annealing. 27-36 (1992)
Abramson, D., Krishnamoorthy, M., & Dang, H.: Simulated Annealing Cooling Schedules for the School Timetabling problem. 1-17 (1997).
Aycan, E., & Ayav, T.: Solving the Course Scheduling Problem Using Simulated Annealing. (n.d).
Cupic, M., Golub, M., & Jakobovic, D.: Exam Timetabling Using Genetic Algorithm. 357-362 (2009).
Groves, G., & Wijck, W.: Constraint Programming and University Timetabling. 1-12 (n.d).
Kuan, Y. J., Joe, H. O., & Rayner, A.: Comparison of Simulated Annealing and Great Deluge Algorithms for University Course Timetabling Problems (UCTP). American Scientific Publishers, 4, 400-407 (2015).
Kuan, Y. J., Joe, H. O., & Rayner, A.: A Constraint Programming Approach to Solve University Course Timetabling Problem (UCTP). American Scientific Publishers, 400-407 (2016).
Kuan, Y. J., Joe, H. O., & Rayner, A.: The study of Genetic Algorithm approach for university course timetabling problem. International Conference on Computational Science and Technology, 454-463 (2017).
Landa-Silva, D., & Obit, J. H.: Great Deluge with Non-linear Decay Rate for Solving Course Timetabling Problems. IEEE, 11-18 (2008).
Landa-Silva, D., & Obit, J. H.: Evolutionary Non-linear Great Deluge for University Course Timetabling. Springer-Verlag Berlin Heidelberg, 269-276 (2009).
Landa-Silva, D., & Obit, J. H.: Comparing Hybrid Constructive Heuristics for University Course Timetabling. 222-225 (2011).
Malik, A. M., Ayob, M., & Hamdan, A. R.: Iterated Two-stage Multi-neighbourhood Tabu Search Approach for Examination Timetabling Problem. IEEE, 141-148 (2009).
Obit, J. H., & Landa-Silva, D.: Computational Study of Non-linear Great Deluge for University Course Timetabling. Springer-Verlag Berlin Heidelberg, 309-328 (2010).
Obit, J. H., Landa-Silva, D., & Ouelhadj, D.: Non-Linear Great Deluge with Learning Mechanism for the Course Timetabling Problem. Springer-Verlag Berlin Heidelberg, 1-10 (2009).
Ozcan, E., Misir, M., Ochoa, G., & Burke, E. K.: A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination Timetabling . 1-25 (n.d.).
Rankhambe, M., & Mrs.S.Kavita.: Optimization of Examination Timetable Using Harmony Search Hyper-Heuristics (HSHH). Internation Journal of Computer Science and Information Technologies, 5, 6719-6723 (2014).
Socha, K., Knowles, J., & Samples, M. (2002). A MAX-MIN Ant System for the University Course Timetabling Problem. Springer-Verlag London, 1-13 (2002).
Tuan-Anh Duong, Kim-Hoa Lam.: Combining Constraint Programming and Simulated Annealing on University Exam Timetabling. 205-210 (n.d.).
Valouxis, C., & Housos, E.: Constraint programming approach for school timetabling. Elsevier Science Ltd., 1555-1572. (2003).
Wolpert, D. M.: No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 67-82 (1997).
Wong, T., Cote, P., & Gely, P.: Final Exam Timetabling: A Practical Approach. IEEE, 726-731 (2002).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
June, T.L., Obit, J.H., Leau, YB., Bolongkikit, J. (2019). Implementation of Constraint Programming and Simulated Annealing for Examination Timetabling Problem. In: Alfred, R., Lim, Y., Ibrahim, A., Anthony, P. (eds) Computational Science and Technology. Lecture Notes in Electrical Engineering, vol 481. Springer, Singapore. https://doi.org/10.1007/978-981-13-2622-6_18
Download citation
DOI: https://doi.org/10.1007/978-981-13-2622-6_18
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2621-9
Online ISBN: 978-981-13-2622-6
eBook Packages: EngineeringEngineering (R0)