A Survey on the Requirements of University Course Timetabling

Authors: Nurul Liyana Abdul Aziz, Nur Aidya Hanum Aizam

Abstract:

Course timetabling problems occur every semester in a university which includes the allocation of resources (subjects, lecturers and students) to a number of fixed rooms and timeslots. The assignment is carried out in a way such that there are no conflicts within rooms, students and lecturers, as well as fulfilling a range of constraints. The constraints consist of rules and policies set up by the universities as well as lecturers’ and students’ preferences of courses to be allocated in specific timeslots. This paper specifically focuses on the preferences of the course timetabling problem in one of the public universities in Malaysia. The demands will be considered into our existing mathematical model to make it more generalized and can be used widely. We have distributed questionnaires to a number of lecturers and students of the university to investigate their demands and preferences for their desired course timetable. We classify the preferences thus converting them to construct one mathematical model that can produce such timetable.

Keywords: University course timetabling problem, integer programming, preferences, constraints.

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

References:

[1] A. Dammak, A. Elloumi, H. Kamoun, and J.A. Ferland, “Course Timetabling at a Tunisian University: a case study,” Journal of Systems Science and Systems Engineering, vol. 17, no. 3, pp. 334-352, 2008.
[2] R.M. Chen and H.F. Shih, “Solving university course timetabling problems using constriction particle swarm optimization with local search,” Algorithm, 6, pp. 227-244,2013.
[3] L.Y. Banowosari and V. Valentine, “University timetabling algorithm considering lecturer’s workload,” Proceedings of the Sixth International Multi-Conference on Computing in the Global Information Technology, pp. 31-37, 2011.
[4] R.P. Badoni, D.K. Gupta, and P. Mishra, “A new hybrid algorithm for university course timetabling problem using events based on groupings of students,” Computers & Industrial Engineering, vol. 78, pp. 12–25, 2014.
[5] N. Basir, W. Ismail, and N.M. Norwawi. “A simulated annealing for tahmidi course timetabling,” Procedia Technology, vol 11, pp. 437-445, 2013.
[6] C.H. Aladag, G.A. Hocaoglu, and M. Basaran, “The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem,” Expert Systems with Application, 36, 12349-12356, 2009.
[7] N. Boland, B.D. Hughes, L.T.G. Merlot, and P.J. Stuckey, “New integer linear programming approaches for course timetabling,” Computers & Operations Research, vol. 35, pp. 2209-2233, 2008.
[8] S.M. Al-Yakoob and H.D. Sherali, “A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations,” European Journal of Operational Research, vol. 180, no. 3, pp. 1028-1044, 2007.
[9] M. Adriaen, P.D. Causmaecker, P. Demeester, and G.V. Berghe, “Tackling the university course timetabling problem with an aggregation approach” In E. K. Burke, H. Rudová (Eds.): PATAT 2006, pp. 330–335, 2006.
[10] S.A. MirHassani, “A computational approach to enhancing course timetabling with integer programming,” Applied Mathematics and Computation, vol. 175, no. 1, pp. 814-822, 2006.
[11] L. Zhang and S. Lau, “Constructing university timetable using constraint satisfaction programming approach,” International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce, vol. 2, pp. 55-60, 2005.
[12] S. Daskalaki, T. Birbas, and E. Housos, “An integer programming formulation for a case study in university timetabling,” European Journal Operational Research, vol. 153, no. 1, pp. 117–135, 2004. H.
[13] Rudova and K. Murray, “University course timetabling with soft constraints,” In E. Burke and P. De Causmaecker, (eds.), Practice and Theory of Automated Timetabling, Selected Revised Papers, Springer-Verlag LNCS, vol. 2740, pp.310-328, 2003.
[14] E.K. Burke and S. Petrovic, “Recent research directions in automated timetabling” European Journal of Operational Research, vol. 140, no.2, pp. 226-280, 2002.
[15] M. Dimopoulou and P. Miliotis, “Implementation of a university course and examination timetabling system,” European Journal of Operational Research, vol. 130, no.1, pp. 202-213, 2001. S.
[16] Abdennadher and M. Marte, “University course timetabling using constraint handling rules,” Applied Artificial Intelligence, vol. 14, no. 4, pp. 311-325, 2000.
[17] D. Sanchez-Partida, J.L. Martinez-Flores, and E. Olivares-Benitez, “An integer linear programming model for a university timetabling problem considering time windows and consecutive periods,” Journal of Applied Operational Research, vol.6, no. 3, pp.158-173, 2014. T.
[18] T. Kanjana, “Solving the Course - Classroom Assignment Problem for a University,” Silpakorn University Science & Technologies Journal, vol.8, no. 1, 2014.
[19] S. Ribiu and S. Konjicija, “A two phase integer linear programming approach to solving the school timetable problem,” In Proceedings of the ITI 2010 32nd Int. Conf. on Information Technology Interface, June 21-24, 2010, Cavtat, Croatia, 2010.
[20] S. Daskalaki and T. Birbas, “Efficient solutions for university timetabling problem through integer programming,” European Journal of Operational Research, vol. 160, no. 1, pp. 106-120, 2005. M.A.
[21] Bakir and C. Aksop, “A 0–1 integer programming approach to a university timetabling problem,” Hacettepe Journal of Mathematics and Statistics, 37(1), 41–55, 2008.
[22] A. Dandashi and M. Al-Mouhamed, “Graph coloring for class scheduling,” Department of Computer Science. Koura, Lebanon: University of Balamand, 2010.
[23] T.A. Redl, “University timetabling via graph coloring: An alternative approach,” University of Houston, Houston, 2007.
[24] A.S. Asratian and D. de Werra, “A generalized class-teacher model for some timetabling problems,” European Journal of Operational Research, vol. 143, no. 3, pp. 531-542, 2002.
[25] R. Alvarez-Valdes, E. Crespo, and J.M. Tamarit, “Design and implementation of a course scheduling system using Tabu Search,” European Journal of Operational Research Vol. 137, pp. 512–523, 2002.
[26] N.A.H Aizam, L. Caccetta, “Computational model for timetabling problem.” Numerical Algebra, Control and Optimization, vol.4, no.1,pp. 269-285,2014.