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

Year 2016, Volume: 21 Issue: 2, 473 - 488, 28.11.2016

Hakan Altunay Tamer Eren

https://doi.org/10.17482/uumfd.285480

Cited By: 4

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

• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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.
• 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
• Botsalı A. R. (2000). A timetabling problem: constraint and mathematical programming approaches, Yüksek Lisans Tezi, Bilkent Üniversitesi, Ankara.
• 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
• 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
• 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
• 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
• 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
• 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.
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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.
• Güldalı, A. (1990). Seri iş-akışlı atölye çizelgelemesinde sezgisel teknikler, Yüksek Lisans Tezi, Gazi Üniversitesi, Ankara.
• 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
• 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
• 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