Öz
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.
Anahtar Kelimeler
Course Scheduling Problem 0-1 Integer Programming Scheduling Operations Research
Kaynakça
- 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
Öz
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.
Anahtar Kelimeler
Ders Programı Çizelgeleme Problemi 0-1 Tamsayılı Programlama Çizelgeleme Yöneylem Araştırması
Kaynakça
- 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
Ayrıntılar
| Konular | Mühendislik |
|---|---|
| Bölüm | Araştırma Makaleleri |
| Yazarlar | |
| Yayımlanma Tarihi | 28 Kasım 2016 |
| Gönderilme Tarihi | 4 Ağustos 2015 |
| Kabul Tarihi | 27 Aralık 2016 |
| Yayımlandığı Sayı | Yıl 2016 Cilt: 21 Sayı: 2 |
Kaynak Göster
Cited By
Hedef Programlama ile Uzaktan Eğitim Ders Programı Çizelgeleme Problemi ve Bir Örnek Uygulama
Uluslararası Muhendislik Arastirma ve Gelistirme Dergisi
https://doi.org/10.29137/umagd.1118493
Sınav Çizelgeleme Problemi için Çok Amaçlı bir Matematiksel Model ve bir Uygulama
Erzincan Üniversitesi Fen Bilimleri Enstitüsü Dergisi
ZEYNEP CEYLAN
https://doi.org/10.18185/erzifbed.513981
DERS ÇİZELGELEME PROBLEMİ İÇİN ELEKTRONİK TABLO TABANLI KARAR DESTEK SİSTEMİ
Konya Journal of Engineering Sciences
Ebru GEÇİCİ
https://doi.org/10.36306/konjes.842830
Merkezi Sınavlardaki Soru Kitapçıklarına A* Algoritması ile Derslerin Yerleştirilmesi
AJIT-e Online Academic Journal of Information Technology
Sinan Kul
https://doi.org/10.5824/ajite.2021.02.002.x
DUYURU:
30.03.2021- Nisan 2021 (26/1) sayımızdan itibaren TR-Dizin yeni kuralları gereği, dergimizde basılacak makalelerde, ilk gönderim aşamasında Telif Hakkı Formu yanısıra, Çıkar Çatışması Bildirim Formu ve Yazar Katkısı Bildirim Formu da tüm yazarlarca imzalanarak gönderilmelidir. Yayınlanacak makalelerde de makale metni içinde "Çıkar Çatışması" ve "Yazar Katkısı" bölümleri yer alacaktır. İlk gönderim aşamasında doldurulması gereken yeni formlara "Yazım Kuralları" ve "Makale Gönderim Süreci" sayfalarımızdan ulaşılabilir. (Değerlendirme süreci bu tarihten önce tamamlanıp basımı bekleyen makalelerin yanısıra değerlendirme süreci devam eden makaleler için, yazarlar tarafından ilgili formlar doldurularak sisteme yüklenmelidir). Makale şablonları da, bu değişiklik doğrultusunda güncellenmiştir. Tüm yazarlarımıza önemle duyurulur.
Bursa Uludağ Üniversitesi, Mühendislik Fakültesi Dekanlığı, Görükle Kampüsü, Nilüfer, 16059 Bursa. Tel: (224) 294 1907, Faks: (224) 294 1903, e-posta: mmfd@uludag.edu.tr