A Mixed-Integer Linear Programming approach for university timetabling problem with the multi-section courses: an application for Hacettepe University Department of Business Administration

Abstract

University course timetabling is an NP-Complete problem type which becomes even more difficult due to the specific requirements of each university. In this study, it was aimed to solve a university course timetabling problem by using integer programming and to develop assignment models that can be easily adapted to similar problems. The models that we developed for the solution are based on the integer programming model of Daskalaki et al. [1]. In addition, the models were developed taking into account the fact that there was an availability of multi-section courses, the minimum overlap of elective courses, and the ability to divide courses into sessions in terms of effective use of the capacity. In this framework, two different models (model 1 and model 2) were developed. Whereas model 1 assumes that all courses are processed as a single session (If a course has 3 time periods per week, then it is taught as a single session), model 2 assumes courses can be assigned by divided into multiple sessions (If a course has 3 time periods per week, then it can be divided into 1+1+1 or 2+1 sessions.). In model 2, a structure in which the model itself could determine how to split the courses in the framework of predetermined options was developed. Both models were formulated in such a way as to maximize the satisfaction of the lecturers. Finally, a larger scale problem was derived from the first problem and the performance of these two models were compared for both problems. The results showed that the optimal solution was obtained within the specified constraints, and the solution time significantly increased with an increase in the size of the problem.

Keywords

• integer programming
• Multi-section courses
• timetabling
• University course timetabling

References

1. 1. Daskalaki, S., T. Birbas, and E. Housos, An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 2004. 153(1): p. 117-135.
2. 2. Burke, E.K., et al., A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 2007. 176(1): p. 177-192.
3. 3. D. de Werra, D., The combinatorics of timetabling. European Journal of Operational Research, 1997. 96(3): p. 504-513.
4. 4. Deris, S., S. Omatu, and H. Ohta, Timetable planning using the constraint-based reasoning. Computers & Operations Research, 2000. 27(9): p. 819-840.
5. 5. Parker, R.G. and R.L. Rardin, Discrete optimization. 2014: Elsevier.
6. 6. Burke, E.K. and S. Petrovic, Recent research directions in automated timetabling. European Journal of Operational Research, 2002. 140(2): p. 266-280.
7. 7. MirHassani, S. and F. Habibi, Solution approaches to the course timetabling problem. Artificial Intelligence Review, 2013. 39(2): p. 133-149.
8. 8. Vermuyten, H., et al., Developing compact course timetables with optimized student flows. European Journal of Operational Research, 2016. 251(2): p. 651-661.

9. 9. Babaei, H., J. Karimpour, and A. Hadidi, A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 2015. 86: p. 43-59.
10. 10. Birbas, T., S. Daskalaki, and E. Housos, School timetabling for quality student and teacher schedules. Journal of Scheduling, 2009. 12(2): p. 177-197.
11. 11. Feizi-Derakhshi, M.-R., H. Babaei, and J. Heidarzadeh. A survey of approaches for university course timetabling problem. in Proceedings of 8th international symposium on intelligent and manufacturing systems (IMS 2012). 2012.
12. 12. Dandashi, A. and M. Al-Mouhamed. Graph Coloring for class scheduling. in ACS/IEEE International Conference on Computer Systems and Applications-AICCSA 2010. 2010. IEEE.
13. 13. Welsh, D.J. and M.B. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 1967. 10(1): p. 85-86.
14. 14. Dimopoulou, M. and P. Miliotis, Implementation of a university course and examination timetabling system. European Journal of Operational Research, 2001. 130(1): p. 202-213.
15. 15. Dimopoulou, M. and P. Miliotis, An automated university course timetabling system developed in a distributed environment: A case study. European Journal of Operational Research, 2004. 153(1): p. 136-147.
16. 16. Daskalaki, S. and T. Birbas, Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 2005. 160(1): p. 106-120.
17. 17. Al-Yakoob, S.M. and H.D. Sherali, Mathematical programming models and algorithms for a class–faculty assignment problem. European Journal of Operational Research, 2006. 173(2): p. 488-507.
18. 18. Al-Yakoob, S.M. and H.D. Sherali, Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations. Annals of Operations Research, 2007. 155(1): p. 119-142.
19. 19. Badri, M.A., et al., A multi-objective course scheduling model: Combining faculty preferences for courses and times. Computers & operations research, 1998. 25(4): p. 303-316.
20. 20. Kang, L. and G.M. White, A logic approach to the resolution of constraints in timetabling. European Journal of Operational Research, 1992. 61(3): p. 306-317.
21. 21. Zhang, L. and S. Lau. Constructing university timetable using constraint satisfaction programming approach. in International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06). 2005. IEEE.
22. 22. Alvarez-Valdes, R., E. Crespo, and J.M. Tamarit, Design and implementation of a course scheduling system using Tabu Search. European Journal of Operational Research, 2002. 137(3): p. 512-523.
23. 23. Aladag, C.H., G. Hocaoglu, and M.A. Basaran, The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem. Expert Systems with Applications, 2009. 36(10): p. 12349-12356.
24. 24. Hao, J.-K. and U. Benlic, Lower bounds for the ITC-2007 curriculum-based course timetabling problem. European Journal of Operational Research, 2011. 212(3): p. 464-472.
25. 25. Deris, S., et al., Incorporating constraint propagation in genetic algorithm for university timetable planning. Engineering applications of artificial intelligence, 1999. 12(3): p. 241-253.
26. 26. Wang, Y.-Z., An application of genetic algorithm methods for teacher assignment problems. Expert Systems with Applications, 2002. 22(4): p. 295-302.
27. 27. Asmuni, H., E.K. Burke, and J.M. Garibaldi. Fuzzy multiple heuristic ordering for course timetabling. in Proceedings of the 5th United Kingdom workshop on computational intelligence (UKCI 2005). 2005. Citeseer.
28. 28. Chaudhuri, A. and K. De, Fuzzy genetic heuristic for university course timetable problem. Int. J. Advance. Soft Comput. Appl, 2010. 2(1): p. 100-123.
29. 29. Abdullah, S., E.K. Burke, and B. McCollum. A hybrid evolutionary approach to the university course timetabling problem. in 2007 IEEE congress on evolutionary computation. 2007. IEEE.
30. 30. Kohshori, M.S. and M.S. Abadeh, Hybrid genetic algorithms for university course timetabling. International Journal of Computer Science Issues(IJCSI), 2012. 9(2).
31. 31. Badoni, R.P., D. Gupta, and P. Mishra, A new hybrid algorithm for university course timetabling problem using events based on groupings of students. Computers & Industrial Engineering, 2014. 78: p. 12-25.
32. 32. Bakir, M.A. and C. Aksop, A 0-1 integer programming approach to a university timetabling problem. Hacettepe Journal of Mathematics and Statistics, 2008. 37(1): p. 41-55.