HIERARCHICAL MATHEMATICAL MODELLING APPROACH FOR A CASE STUDY IN UNIVERSITY TIMETABLING

Year 2019, Volume: 37 Issue: 2, 323 - 339, 01.06.2019

Yunus Demir Cafer Çelik

Abstract

This work presents a mathematical modelling based approach including many constraints encountered at Universities in Turkey. As in many other countries also in Turkey it appears that universities are too autonomous, and they have medley of individual requirements and constraints. This condition makes it very difficult to suggest a generalized model and a solution algorithm for university timetabling problem (UTP). In general, in this paper it is aimed to design compatible and flexible approach to generate timetable so as to meet all the requirements of Turkish universities. First, by reviewing the studies in which mathematical modelling approaches were used, comprehensive information about the subject has been presented. Then, proposed hierarchical mathematical modelling approach is described (HMMA). Since (UTP) is highly context-dependent the results of this study couldn’t been compared to those of the studies which are published already. Proposed approach is tested 2015-2016 academic year winter term data of Atatürk University Engineering Faculty and obtained results are presented comparatively with results obtained from manual preparation in terms of seven objectives.

Keywords

University timetabling, operational research, mathematical programming.

References

• [1] Alvarez-Valdes, R., Crespo, E., and Tamarit, J.M. (2002). Design and implementation of a course scheduling system using Tabu Search, European Journal of Operational Research, 137, 512–523.
• [2] Cooper, T.B., and Kingston, J.H. (1996). The complexity of timetable construction problems. Practice and Theory of Automated Timetabling Lecture Notes in Computer Science, 1153, 281-295.
• [3] Al-Milli N. (2010) Hybrid genetic algorithms with great deluge for course timetabling. International Journal of Computer Science and Network Security, 10(4), 283-288.
• [4] Burke E.K., McCollum B., Meisels A., Petrovic S., and Qu R. (2007) A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 176, 177–192.
• [5] Chiarandini M., Birattari, M., Socha K., and Rossi-Doria O. (2006) An effective hybrid algorithm for university course timetabling. Journal of Scheduling, 9, 403-432.
• [6] Lewis R., Paechter B. and McCollum B. (2007) Post enrolment based course timetabling: A description of the problem model used for track two of the second international timetabling competition, Cardiff Accounting and Finance Working Papers A2007/3, Cardiff University, Wales. ISSN: 1750-6658, v1.0.
• [7] Nothegger C., Mayer A., Chwatal A. and Raidl,G.R. (2012) Solving the post enrolment course timetabling problem by ant colony optimization, Annals of Operations Research, 194, 325-339.
• [8] Socha K., Knowles J. and Sampels M. (2002). A MAX-MIN ant system for the university course timetabling problem, Proceedings of the 3rd International Workshop on Ant Algorithms Lecture Notes in Computer Science, 2463, 1-13.
• [9] Kristiansen S., Sørensen M. and Stidsen T.R. (2011) Elective course planning. European Journal of Operational Research, 215, 713-720.
• [10] Ceschia S., Di Gaspero L. and Schaerf A. (2012) Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem. Computers & Operations Research, 39, 1615-1624.
• [11] Martin C.H. (2004) Ohio University's College of Business Uses Integer Programming to Schedule Classes. Interfaces, 34(6), 460-465.
• [12] Sánchez-Partida D., Martínez-Flores J.L., and Olivares-Benítez E. (2013) Modeling and solving a timetabling problem considering time windows and consecutive periods. Lecture Notes in Management Science, 5, 25-32.
• [13] Akkoyunlu E.A. (1972) A linear algorithm for computing the optimum university timetable. The Computer Journal, 16(4), 347-350.
• [14] Daskalaki S., Birbas T., and Housos E. (2004) An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153, 117-135.
• [15] Dimopoulou M., Miliotis P. (2004) An automated university course timetabling system developed in a distributed environment: A case study. European Journal of Operational Research, 153, 136-147.
• [16] MirHassani S.A. (2006) A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 175, 814–822.
• [17] Schimmelpfeng K., and Helber S. (2007) Application of a real-world university-course timetabling model solved by integer programming. OR Spectrum, 29,783–803.
• [18] Cura T. (2007) Timetabling of faculty lectures using simulated annealing algorithm. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 12, 1-20.
• [19] Gunawan A., Ng K.M, and Poh K.L. (2007) Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm. International Journal of Mechanical, Aerospace, Industrial and Mechatronics Engineering, 1(9), 520-525
• [20] Bakır M.A. and Aksop C. 2008. “A 0-1 integer programming approach to a university timetabling problem.” Hacettepe Journal of Mathematics and Statistics 37(1): 41-55.
• [21] Aizam N.A.H. and Liong C.-Y. (2013). Mathematical Modelling of University Timetabling: A Mathematical Programming Approach. International Journal of Applied Mathematics and Statistics, 37(7), 110-122.
• [22] Köçken H.G., Özdemir R. and Ahlatcıoğlu M. (2014) Üniversite ders zaman çizelgeleme problemi için ikili tamsayılı bir model ve bir uygulama. İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43(1), 28-54.
• [23] Al-Yakoob S. M. and Sherali H.D. (2007) Mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations. European Journal of Operational Research, 180, 1028–1044.
• [24] Qualizza A., Serafini P. (2004) A Column Generation Scheme for Faculty Timetabling. Practice and Theory of Automated Timetabling V Lecture Notes in Computer Science. 3616, 161-173.
• [25] Demir Y., Çelik C. (2016) Müfredat bazlı akademik zaman çizelgeleme probleminin çözümüne tam sayılı doğrusal programlama yaklaşımı. Journal of Faculty of Engineering and Architecture of Gazi University. 31(1), 145-159.
• [26] Feng X., Lee Y., and Moon I. (2016) An integer program and a hybrid genetic algorithm for the university timetabling problem. Optimization Methods and Software. DOI: 10.1080/10556788.2016.1233970.
• [27] Vermuyten H., Lemmens S., Marquesc I., Beliëna J. (2016) Developing compact course timetables with optimized student flows. European Journal of Operational Research. 251, 651–661.
• [28] Lach G., Lübbecke,M.E., (2012) Curriculum based course timetabling: new solutions to Udine benchmark instances. Annals of Operations Research. 194(1), 255-272.
• [29] Burke E.K., Mareck J., Parkes A.J., Rudova H. (2010) Decomposition, reformulation, and diving in university course timetabling. Computers & Operations Research, 37, 582 -597.
• [30] Cacchiani V., Caprara A., Roberti R., and Toth P. (2013). A new lower bound for curriculum-based course timetabling. Computers &Operations Research, 40, 2466–2477.
• [31] Benli O., and Botsali A., (2004) An Optimization-Based Decision Support System for a University Timetabling Problem: An Integrated Constraint and Binary Integer Programming Approach, [online]. Available from: https://pdfs.semanticscholar.org/f6e2/3b4ae5852681ea8c1fa866743eb259f5ca73.pdf