A 0-1 Integer Programming Model for the Course Scheduling Problem and A Case Study

Abstract

The course scheduling problem is one of the most common timetabling problems which are frequently encountered in all educational institutions, especially universities. This problem which is getting harder to solve day by day, means the assignment of the lessons and lecturers into the most suitable time-slots and classrooms, provided that various constraints are taken into account. These constraints peculiar to the problem are consisted due to various factors such as the characteristics and the rules of the educational institutions, preferences of lecturers, students’ requests and suggestions. In this study, a novel 0-1 integer programming model that considers preferences of lecturers is proposed for the course scheduling problem. The proposed mathematical model is also tested with a case study from Uludag University. Thus, the performance of the mathematical model can be tested and the results can be analyzed. The results of the carried out application show efficient results in preparing a course schedule that meets the preferences of the lecturers and complies with the rules of the institutions. 

Keywords

• Course Scheduling Problem,0-1 Integer Programming,Scheduling,Operations Research

DERS PROGRAMI ÇİZELGELEME PROBLEMİ İÇİN 0-1 TAMSAYILI PROGRAMLAMA MODELİ VE BİR ÖRNEK UYGULAMA

Abstract

Ders programı çizelgeleme problemi, başta üniversiteler olmak üzere bütün eğitim kurumlarında sıklıkla karşılaşılan, en yaygın zaman çizelgeleme problemlerinden birisidir. Çözümü gün geçtikçe zorlaşan bu problem, çeşitli kısıt yapıları dikkate alınmak koşuluyla, derslerin ve öğretim üyelerinin en uygun zaman dilimleri ve dersliklere atanmasını ifade etmektedir. Probleme özgü bu kısıt yapıları; eğitim kurumlarının özellikleri ve kuralları, öğretim üyelerinin talepleri, öğrencilerin istek ve önerileri gibi çeşitli faktörlere göre oluşturulmaktadır. Bu çalışmada, ders programı çizelgeleme problemi için öğretim üyelerinin istek ve taleplerini dikkate alan yeni bir 0-1 tamsayılı programlama modeli önerilmiştir. Önerilen bu matematiksel programlama modeli Uludağ Üniversitesinde yapılan bir örnek uygulama ile desteklenmiştir. Bu sayede matematiksel modelin bir gerçek hayat problemi üzerinde test edilmesi ve üretilen sonuçların analiz edilmesi sağlanmıştır. Yapılan uygulama çalışmasının sonuçları, önerilen matematiksel programlama modelinin kurum kurallarını ve öğretim üyelerinin tercihlerini karşılayan haftalık bir ders çizelgesinin elde edilmesinde verimli sonuçlar ürettiğini göstermektedir. 

Keywords

• Ders Programı Çizelgeleme Problemi,0-1 Tamsayılı Programlama,Çizelgeleme,Yöneylem Araştırması

References

1. Akkoyunlu, E. A. (1973) A linear algorithm for computing the optimum university timetable, The Computer Journal, 16(4), 347-350. doi: 10.1093/comjnl/16.4.347
2. Altunay, H. ve Eren, T. (2016) Ders programı çizelgeleme problemi için bir literatür taraması, Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. doi: 10.5505/pajes.2016.37233
3. Al-Yakoob, S. M. ve Sherali, H. D. (2006) Mathematical programming models and algorithms for a class-faculty assignment problem, European Journal of Operational Research, 173(2), 488-507. doi: 10.1016/j.ejor.2005.01.052
4. Al-Yakoob, S. M. ve Sherali, H. D. (2007) 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(3): 1028-1044, 2007. doi: 10.1016/j.ejor.2006.04.035
5. Avella P. ve Vasiliev I. (2005) A computational study of a cutting plane algorithm for university course timetabling, Journal of Scheduling, 8(6), 497-514. doi: 10.1007/s10951-005-4780-1
6. Badri, M. A. (1996) A two-stage multiobjective scheduling model for faculty-course-time assignments, European Journal of Operational Research, 94, 16–28. doi: 10.1016/0377-2217(95)00204-9
7. Badri, M. A., Davis, D. L., Davis, F. D. ve Hollingsworth, J. (1998) A multi-objective course scheduling model: Combining faculty preferences for courses and times, Computers and Operations Research, 25(4), 303-316. doi: 10.1016/S0305-0548(97)00048-8
8. Baker K. R., Magazine M. J. ve Polak G. G. (2002) Optimal Block Design Models for Course Timetabling, Operations Research Letters, 30, 1-8. doi: 10.1016/S0167-6377(01)00116-X

9. Bakır, M. A. ve Aksop, C. (2008) A 0-1 integer programming approach to a university timetabling problem, Hacettepe Journal of Mathematics and Statistics, 37(1), 41–55.
10. Boronico, J. (2000) Quantitative modeling and technology driven departmental course scheduling, The International Journal of Management Science, 28(3), 327-346. doi: 10.1016/S0305-0483(99)00056-0
11. Botsalı A. R. (2000). A timetabling problem: constraint and mathematical programming approaches, Yüksek Lisans Tezi, Bilkent Üniversitesi, Ankara.
12. Burke, E. K. MacCarthy, B. Petrovic, S. ve Qu, R. (2001) Case-based reasoning in course timetabling: An attribute graph approach, Case-Based Reasoning Research and Development, Jul-Aug, Proceedings of the 4th International Conference on Case-Based Reasoning, Vancouver, Canada, 90-104. doi: 10.1007/3-540-44593-5_7
13. Burke, E. K. Petrovic, S. ve Qu, R. (2006) Case-based heuristic selection for timetabling problems, Journal of Scheduling, 9(2), 115-132. doi: 10.1007/s10951-006-6775-y
14. Burke, E.K. Marecek, J. Parkes, A. J. ve Rudová, H. (2008) Penalizing patterns in timetables: Novel integer programming formulations, Operations Research Proceedings, Berlin, Springer, Germany, ISSN 0721-5924, 2007, 409-414. doi: 10.1007/978-3-540-77903-2 63
15. Cacchiani V. Caprara A. Roberti R. ve Toth P. (2013) A new lower bound for curriculum-based course timetabling, Computers and Operations Research, 40(10), 2466-2477. doi: 10.1016/j.cor.2013.02.010
16. Carter M.W. ve Laporte G. (1998) Recent developments in practical course scheduling, in: E.K. Burke, P. Ross (Eds.), The Practice and Theory of Automated Timetabling, 2, 3-19. doi:10.1007/3-540-61794-9_49
17. Cheng, E. ve Kruk, S. (2007) A case study of an integer programming model for instructor assignments and scheduling problem, Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), Paris, France, 267-275.
18. Daskalaki, S. Birbas, T. ve Housos, E. (2004) An integer programming formulation for a case study in university timetabling, European Journal of Operational Research, 153, 117–135. doi: 10.1016/S0377-2217(03)00103-6
19. Daskalaki, S. ve Birbas, T. (2005) Efficient solutions for a university timetabling problem through integer programming, European Journal of Operational Research, 160(1), 106-120. doi: 10.1016/j.ejor.2003.06.023
20. Dimopoulou, M. ve Miliotis, P. (2001) Implementation of a university course and examination timetabling system, European Journal of Operational Research, 130, 202-213. doi: 10.1016/S0377-2217(00)00052-7
21. Dimopoulou, M. ve 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. doi: 10.1016/S0377-2217(03)00104-8
22. Dinkel, J. J. Mote, J. ve Venkataramanan, M. A. (1989) An efficient decision support system for academic course scheduling, Operations Research, 37(6), 853-864. doi: 10.1287/opre.37.6.853
23. Ferland, J. A. ve Roy, S. (1985) Timetabling problem for university as assignment of activities to resources, Computers and Operations Research, 12(2), 207-218. doi: 10.1016/0305-0548(85)90045-0
24. Ferland, J. A. ve Fleurent, C. (1994) SAPHIR: A decision support system for course scheduling, Interfaces, 24, 105-115. doi: 10.1287/inte.24.2.105
25. Gosselin, K. ve Truchon, M. (1986) Allocation of classrooms by linear programming, The Journal of the Operational Research Society, 37(6), 561-569. doi: 10.1057/jors.1986.98
26. Gunawan, A. Ng, K. M. ve Ong, H. L. (2008) A genetic algorithm for the teacher assignment problem for a university in Indonesia, Information and Management Sciences, 19(1), 1-16.
27. Güldalı, A. (1990). Seri iş-akışlı atölye çizelgelemesinde sezgisel teknikler, Yüksek Lisans Tezi, Gazi Üniversitesi, Ankara.
28. Günalay, Y. ve Şahin, T. (2006) A decision support system for the university timetabling problem with instructor preferences, Asian Journal of Information Technology, 5(12), 1479-1484. doi: ajit.2006.1479.1484
29. Harwood, G. B. ve Lawless, R. W. (1975) Optimizing organizational goals in assigning faculty teaching schedules, Decision Sciences, 6(3), 513-524. doi: 10.1111/j.1540-5915.1975.tb01040.x
30. Ismayilova, N. A. Sagir, M. ve Gasimov, R. N. (2007) A multiobjective faculty-course-time slot assignment problem with preferences, Mathematical and Computer Modelling, 46(7-8), 1017-1029. doi: 10.1016/j.mcm.2007.03.012