Abstract
The academic examinations are scheduled as per the academic calendar. However, due to the occurrence of unprecedented events the exam schedule will get disturbed which in turn impacts the academic calendar. In this paper, we propose a temporally optimal and topic complexity balanced re-schedule model in terms of a Markov Decision Process (MDP). This MDP is verified for the feasibility of a schedule using Bellman Equation with Temporal Difference Learning, policy iteration and value iteration algorithms of Reinforcement Learning. The objective of the proposed model is to find an optimal mapping from the state of disturbed exam to the state of plausible date of the exam. The novelty of this work is manifested in variable penalties assigned to various schedule slippage scenarios. Rescheduling is optimally automated using Bellman Equation with Temporal Difference Learning. These variable policy iteration and value iteration algorithms have demonstrated that as the learning progresses the optimal schedule gets evolved. Also, it is shown that policy iteration has converged faster than the value iteration while generating schedule. This instils confidence in utilizing the Reinforcement Learning algorithms on the grid environment-based exam rescheduling problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Burke, E.K., Rudová, H. (eds.): PATAT 2006. LNCS, vol. 3867. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77345-0
Hamilton-Bryce, R., McMullan, P., McCollum, B.: Directed selection using reinforcement learning for the examination timetabling problem. In: Proceedings of the PATAT 14 (2014)
Han, K.: Using reinforcement learning in solving exam timetabling problems. Diss. Queen's University Belfast. Faculty of Engineering and Physical Sciences (2018)
McCollum, B., et al.: Setting the research agenda in automated timetabling: The second international timetabling competition. Informs J. Comput. 22(1), 120–130 (2010)
Glover, F.: Tabu search—part I. ORSA J. Comput. 1(3), 190–206 (1989)
White, G.M., Xie, B.S.: Examination timetables and tabu search with longer-term memory. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 85–103. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44629-X_6
Paquete, L., Stützle, T.: An experimental investigation of iterated local search for coloring graphs. In: Cagnoni, S., Gottlieb, J., Hart, E., Middendorf, M., Raidl, G.R. (eds.) EvoWorkshops 2002. LNCS, vol. 2279, pp. 122–131. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46004-7_13
Ergül, A.: GA-based examination scheduling experience at Middle East Technical University. In: Burke, E., Ross, P. (eds.) Practice and Theory of Automated Timetabling. PATAT 1995. Lecture Notes in Computer Science, vol. 1153, pp. 212–226. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61794-9_61
Paquete, L.F., Fonseca, C.M.: A study of examination timetabling with multiobjective evolutionary algorithms. In: Proceedings of the 4th Metaheuristics International Conference (MIC 2001) (2001)
Ross, P., Hart, E., Corne, D.: Some observations about GA-based exam timetabling. In: Burke, E., Carter, M. (eds.) PATAT 1997. LNCS, vol. 1408, pp. 115–129. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055884
Ahmadi, S., et al.: Perturbation based variable neighbourhood search in heuristic space for examination timetabling problem. In: Proceedings of Multidisciplinary International Scheduling: Theory and Applications (MISTA 2003), pp. 155–171 (2003)
Ross, P., Marín-Blázquez, J.G., Hart, E.: Hyper-heuristics applied to class and exam timetabling problems. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753). IEEE, vol. 2. (2004)
McCollum, B., et al.: An extended great deluge approach to the examination timetabling problem. In: Proceedings of the 4th Multidisciplinary International Scheduling: Theory and Applications 2009 (MISTA 2009), pp. 424–434 (2009)
Bai, R., et al.: A simulated annealing hyper-heuristic methodology for flexible decision support. 4OR, 10, 43–66 (2012)
Burke, E., et al.: Using simulated annealing to study behaviour of various exam timetabling data sets (2003)
Özcan, E., et al.: A reinforcement learning: great-deluge hyper-heuristic for examination timetabling. In: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends. IGI Global, pp. 34–55 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Omar, M.O., Santosh, D.T., Raghava, M., Joshi, J. (2023). Rescheduling Exams Within the Announced Tenure Using Reinforcement Learning. In: Morusupalli, R., Dandibhotla, T.S., Atluri, V.V., Windridge, D., Lingras, P., Komati, V.R. (eds) Multi-disciplinary Trends in Artificial Intelligence. MIWAI 2023. Lecture Notes in Computer Science(), vol 14078. Springer, Cham. https://doi.org/10.1007/978-3-031-36402-0_53
Download citation
DOI: https://doi.org/10.1007/978-3-031-36402-0_53
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-36401-3
Online ISBN: 978-3-031-36402-0
eBook Packages: Computer ScienceComputer Science (R0)