A Spreadsheet Based Decision Support System for Course Timetabling

Abstract

In this study, the course scheduling problem (CSP) of an engineering department is addressed. It has been very difficult to prepare the course schedules of the department due to a radical curriculum change, increasing number of students and programs, decreasing number of faculty members, and request of the students in recent years to have lecture-free days to attend long-term internships. A mixed-integer programming (MIP) model is proposed to schedule nine different programs in the department and a decision support system (DSS) that solves this model using an open source solver is developed. The DSS, which does not require any technical knowledge (coding and optimization), is able to generate schedules that address the requests of faculty members and leaves two lecture-free days for the students for long-term internships, in a short time.

Keywords

• Course scheduling problem
• decision support system
• mixed integer programming

DERS ÇİZELGELEME PROBLEMİ İÇİN ELEKTRONİK TABLO TABANLI KARAR DESTEK SİSTEMİ

Abstract

Bu çalışmada bir mühendislik bölümünün ders çizelgeleme problemi (DÇP) ele alınmıştır. Gerçekleşen köklü müfredat değişikliği, giderek artan öğrenci ve program sayısına karşın azalan öğretim elemanı sayısı ve son yıllarda öğrencilerin uzun dönemli staj için günlerini boşaltma istekleri nedeniyle bölümün ders çizelgelerini hazırlamak oldukça zorlaşmıştır. Bu problemi çözebilmek için bölüme ait dokuz adet programın derslerini çizelgeleyen bir karma tam sayılı programlama (KTP) modeli kurulmuş ve bu modeli açık kaynak kodlu çözücü kullanarak çözen bir karar destek sistemi (KDS) geliştirilmiştir. Herhangi bir teknik bilgi (kodlama ve optimizasyon gibi) gerektirmeyen bu KDS sayesinde öğretim elemanlarının isteklerini karşılayan, öğrencilerin iki günlerini boş bırakarak uzun dönemli staj imkanı sağlayan ders programları kısa sürede elde edilebilmektedir.

Keywords

• Ders çizelgeleme problemi
• karar destek sistemi
• karma tam sayılı programlama

References

1. Abdelhalim, E. A., & El Khayat, G. A., 2016, An information visibility-based university timetabling for efficient use of learning spaces (IVUT), Egyptian Informatics Journal, 17(3), 315–325.
2. Al-Qaheri, H., Hasan, M. K., & Al-Husain, R., 2011, A decision support system for a three-stage university course scheduler with an application to College of Business Administration, Kuwait University, International Journal of Data Analysis and Information Systems, 3(2), 95–110.
3. Altunay, H., & Eren, T., 2016, Ders programı çizelgeleme problemi içn 0-1 tamsayılı programlama modeli ve bir örnek uygulama, Uludağ University Journal of The Faculty of Engineering, 21(2), 473–488.
4. Ateş, A. M., & Kestane, Ö., 2014, Üniversiteler için haftalık ders programı hazırlama yazılımı, SDU Teknik Bilimler Dergisi, 4(2), 1–11.
5. Babaei, H., Karimpour, J., & Hadidi, A., 2015, A survey of approaches for university course timetabling problem, Computers & Industrial Engineering, 86, 43–49. https://doi.org/http://dx.doi.org/10.1016/j.cie.2014.11.010.
6. Bakır, M. A., & Aksop, C., 2008, A 0-1 integer programming approach to a university timetabling problem, Hacettepe Journal of Mathematics and Statistics, 37(1), 41–55.
7. Burke, E., Jackson, K., Kingston, J. H., & Weare, R., 1997, Automated university timetabling: The state of the art, The Computer Journal, 40(9), 565–571.
8. Burke, E. K., Marecek, J., Parkes, A. J., & Rudova, H., 2010, Decomposition, reformulation, and diving in university course timetabling, Computers & Operations Research, 37(3), 582–597.

9. Daskalaki, S., & Birbas, T., 2005, Efficient solutions for a university timetabling problem through integer programming, European Journal of Operational Research, 160(1), 106–120.
10. Daskalaki, S., Birbas, T., & Housos, E., 2004, An integer programming formulation for a case study in university timetabling, European Journal of Operational Research, 153(1), 117–135.
11. Demir, Y., & Çelik, C., 2016, Müfredat bazlı akademik zaman çizelgeleme probleminin çözümüne tam sayılı doğrusal programlama yaklaşımı, Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 31(1), 145–159.
12. Dimopoulou, M., & Miliotis, P., 2001, Implementation of a university course and examination timetabling system, European Journal of Operational Research. https://doi.org/10.1016/S0377-2217(00)00052-7.
13. Eren, T., Taş, C., & Bedir, N., 2018, 0-1 tam sayıı programlama ile ders programı çizelgeme probleminin çözümü: Bir Yüksek öğretim kurumda uygulama, Harran Üniversitesi Mühendislik Dergisi, 3(3), 166–175.
14. Ertuğrul, İ., & Öztaş, G. Z., 2016, Ders programı oluşturulmasında 0-1 tam sayılı bulanık hedef programlama yaklaşımı, Ömer Halisdemir Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 9(1), 159–177.
15. Fonseca, G. H. G., Santos, H. G., Carrano, E. G., & Stidsen, T. J. R., 2017, Integer programming techniques for educational timetabling, European Journal of Operational Research, 262(1), 28–39.
16. Güler, M. G., & Geçici, E., 2020, A spreadsheet based decision support system for examination timetabling, Turkish Journal of Electrical Engineering & Computer Sciences, 28(3), 1584–1598.
17. Günalay, Y., & Şahin, T., 2006, A decision support system for the university timetabling problem with instructor preferences, Asian Journal of Information Technology, 5(12), 1479–1484.
18. Kamışlı Öztürk, Z., Kasımbeyli, N., Sağır Özdemir, M., Soyuöz Acar, M., Özçetin, E., Alegöz, M., & Ceylan, G., 2016, Kullanıcı tercihlerinin dikkate alınması durumunda üniversite ders çizelgeleme problemi, Endüstri Mühendisliği Dergisi, 27(1), 2–16.
19. Kökçen, H., Özdemir, R., & 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.
20. Lemos, A., Melo, F. S., Monteiro, P. T., & Lynce, I., 2019, Room usage optimization in timetabling: A case study at Universidade de Lisboa, Operations Research Perspectives, 6, 100092.
21. Miranda, J., 2010, eClasSkeduler: a course scheduling system for the executive education unit at the Universidad de Chile, Interfaces, 40(3), 196–207. https://doi.org/10.1287/inte.1090.0485.
22. Miranda, J., Rey, P. A., & Robles, J. M., 2012, udpSkeduler: a web architecture based decision support system for course and classroom scheduling, Decision Support Systems, 52(2), 505–513. https://doi.org/10.1016/j.dss.2011.10.011.
23. Oladokun, V. O., & Badmus, S. O., 2008, An integer linear programming model of a university course timetabling problem, The Pacific Journal of Science and Technology, 9(2), 426–431.
24. Phillips, A. E., Waterer, H., Ehrgott, M., & Ryan, D. M., 2015, Integer programming methods for large- scale practical classroom assignment problems, Computers & Operations Research, 53, 42–53.
25. Piechowiak, S., & Kolski, C., 2004, Towards a generic object oriented decision support system for university timetabling: an interactive approach, International Journal of Information Technology & Decision Making, 3(01), 179–208.
26. Python, Retrieved July 30, 2019, from https://www.python.org/
27. Sánchez-Partida, D., Martínez-Flores, J. L., & Olivares-Benítez, E., 2014, An integer linear programming model for a university timetabling problem considering time windows and consecutive periods, Journal of Applied Operational Research, 6(3), 158–173.
28. Schimmelpfeng, K., & Helber, S., 2007, Application of a real-world university-course timetabling model solved by integer programming, Or Spectrum, 29(4), 783–803.
29. Siddiqui, A. W., Raza, S. A., & Tariq, Z. M., 2018, A web-based group decision support system for academic term preparation, Decision Support Systems, 114, 1–17, https://doi.org/https://doi.org/10.1016/j.dss.2018.08.005
30. Solver Studio, Retrieved November 1, 2019, from https://solverstudio.org/
31. Uçar, U., İşleyen, S., & Demir, Y., 2015, Ders çizelgeleme probleminin bulanık AHP ve çok amaçlı karışık tam sayılı matematiksel modelle çözümü, Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji, 3(3), 513–523.
32. Vermuyten, Hendrik Lemmens, S., Marques, I., & Beliën, J., 2016, Developing compact course timetables with optimized student flows, European Journal of Operational Research, 251(2), 651–661.