Timetabling Communities’ Demands for an Effective Examination Timetabling Using Integer Linear Programming

Authors: N. F. Jamaluddin, N. A. H. Aizam

Abstract:

This paper explains the educational timetabling problem, a type of scheduling problem that is considered as one of the most challenging problem in optimization and operational research. The university examination timetabling problem (UETP), which involves assigning a set number of exams into a set number of timeslots whilst fulfilling all required conditions, has been widely investigated. The limitation of available timeslots and resources with the increasing number of examinations are the main reasons in the difficulty of solving this problem. Dynamical change in the examination scheduling system adds up the complication particularly in coping up with the demand and new requirements by the communities. Our objective is to investigate these demands and requirements with subjects taken from Universiti Malaysia Terengganu (UMT), through questionnaires. Integer linear programming model which reflects the preferences obtained to produce an effective examination timetabling was formed.

Keywords: Demands, educational timetabling, integer linear programming, scheduling, university examination timetabling problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1124459

References:

[1] Abdullah, S., Shaker, K., & Shaker, H., “Investigating a round robin strategy over multi algorithms in optimising the quality of university course timetable,” International Journal of the Physical Science, 6, 2011, pp. 1452-1462.
[2] Abuhamdah, A., & Ayob, M., “Adaptive randomized descent algorithm for solving course timetabling problems,” International Journal of the Physical Sciences, 5, 2010, pp. 2516-2522.
[3] Aizam, N. A. H., Jamaluddin, N. F. & Ahmad, S, “A Survey on the Timetabling Communities’ Demands for an Effective Examination Timetabling in Universiti Malaysia Terengganu,” Malaysian Journal of Mathematical Sciences, 2014.
[4] Aizam, N. A. H. & Sithamparam, T., “General Basic 0-1 Integer Programming Model for Timetabling Problems,” Malaysian Journal of Mathematical Sciences, 2014.
[5] Aizam, N. A. H., & Uvaraja, V., “Generic Model for Timetabling Problems by Integer Linear Programmimg Approach,” World Academy of Science, Engineering and Technology, International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, vol. 9, no. 12, 2015, pp. 668-675.
[6] Al-Yakoob, S. M. & Sherali, H. D., “A mixed integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations,” European Journal of Operational Research, 180, 2007, pp. 1028-1044.
[7] Al-Yakoob, S. M., Sherali, H. D., & AL-Jazzaf, M., “A mixed-integer mathematical modeling approach to exam timetabling,” Computational Management Science, 7, 2010, pp. 19-46.
[8] Arbaoui, T., Boufflet, J. P., & Moukrim, A., "Preprocessing and an improved MIP model for examination timetabling,” Annals of Operations Research, 229, no. 1, 2015, pp. 19-40.
[9] Asmuni, H., Burke, E. K., Garibaldi, J. M., & McCollum, B., “Fuzzy multiple heuristic orderings for Examination timetabling,” in Practice and Theory of Automated Timetabling, vol 3616, E. Burke & M. Trick, Eds. Berlin: Springer, 2005.
[10] Barlett, A. C., Chartier, T. P., Langville, A. N. & Rankin, T. D., “An integer programming model for Sudoku problem,” J. of Online Mathematics and its Applications, 8, May 2008.
[11] Burke, E., Elliman, D., Ford, P., & Weare, R., “Examination timetabling in British universities: A survey,” in Practice and Theory of Automated Timetabling, Berlin: Springer, 1996, pp. 76-90.
[12] Carter, M.W. and Laporte, G., “Recent developments in practical examination timetabling,” In E.K. Burke and P. Ross (eds), Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, LNCS 1153, Springer-Verlag, Berlin, Heidelberg, 1996, pp. 3-21.
[13] Cowling, P., Kendall, G., & Hussin, N. M., “A survey and case study of practical examination timetabling problems,” In Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling, 2002, pp. 258-261.
[14] Desai, N. P., “Preferences of teachers and students for auto generation of sensitive timetable: A case study,” Indian Journal of Computer Science and Engineering, 2, 2011, pp. 461-465.
[15] de Werra, D., “An introduction to timetabling,” European journal of operational research, 19, 1985, pp. 151-162.
[16] McCollum, B., McMullan, P., Parkes, A. J., Burke, E. K., & Qu, R., “A new model for automated examination timetabling,” Annals of Operations Research, 194, no. 1, 2012, 291-315.
[17] Mohmad Kahar, M. N. & Kendall, G., "Universiti Malaysia Pahang examination timetabling problem: scheduling invigilators," Journal of the Operational Research Society, 65, 2014, pp. 214-226.
[18] MirHassani, S. A., Improving paper spread in examination timetables using integer programming,” Applied Mathematics and Computation. 179, 2006, pp. 702-706.
[19] Qu, R., Burke, E., McCollum, B., Merlot, L. T. & Lee, S. Y., A survey of search methodologies and automated approaches for examination timetabling Nottingham: University of Nottingham, 2006.
[20] Schaerf, A., “A survey of automated timetabling (Review of the Artificial Intelligence Review a survey of automated timetabling),” Artificial Intelligence Review, 13, 1999, pp. 87-127.
[21] Teixeira Jr., R. F., Fernandes, F. C. F. & Pereira, A. N., "Binary integer programming formulations for scheduling in market-driven foundries." Computers & Industrial Engineering 59, no. 3, 2010, pp. 425-435.