HETEROJEN ZAMAN ARALIKLARI VE İŞ YÜKÜ ADALETİNE DAYALI SINAV ZAMAN ÇİZELGELEMESİ İÇİN ÜÇ AŞAMALI BİR MIP MODELİ ÖNERİSİ

Abstract

Bu çalışma, bir fakülteye bağlı 12 bölümün sınav çizelgeleme problemini çözmek üzere üç aşamalı bir karma tamsayılı programlama (MIP) modeli önermektedir. Modelin ilk aşaması sınavların gün ve saat atamasına, ikinci aşaması derslik tahsisine, üçüncü aşaması ise gözetmen atamasına odaklanmaktadır. Geleneksel sabit süreli sınav dilimlerinden farklı olarak, gün ve saat atama modeli 30, 60 ve 90 dakikalık heterojen zaman dilimlerini kullanmaktadır. Bu yaklaşım, her sınava en uygun süreyi atamayı mümkün kılarak zaman verimliliğini artırmakta ve boşta kalan süreleri azaltmaktadır. Ayrıca model, sınav dönemi boyunca bölümlere ait iş yükünün dengeli bir biçimde dağılmasını sağlayarak bölümler arasında adaletsiz sınav yoğunlaşmalarını önlemektedir. Derslik atama modeli, tahsis edilen salonlardaki boş koltuk sayısını en aza indirerek salon kullanımını optimize etmeyi ve kapasite planlamasını iyileştirmeyi hedeflemektedir. Gözetmen atama aşamasında ise iş yükünün gözetmenler arasında dengeli bir şekilde paylaştırılması önceliklendirilmiştir. Problemin NP-zor yapısı nedeniyle çözüm için genetik algoritma (GA) kullanılmıştır. Elde edilen çizelgeler, manuel olarak oluşturulan çizelgelerle karşılaştırılmış ve sonuçlar; adalet, verimlilik ve kaynak kullanımında belirgin iyileşmeler ortaya koyarak önerilen MIP modelinin pratik değerini göstermiştir.

Keywords

• Sınav Zaman Çizelgeleme
• Gözetmen Atama
• Karma Tamsayılı Programlama
• Genetik Algoritma

A PROPOSAL FOR A THREE-STAGE MIP MODEL FOR EXAMINATION TIMETABLING BASED ON HETEROGENEOUS TIME SLOTS AND WORKLOAD FAIRNESS

Abstract

This paper presents a three-stage mixed-integer programming (MIP) model for addressing the complex examination timetabling problem faced by 12 departments within a faculty. The first stage focuses on assigning days and time slots, the second stage allocates rooms, and the third stage assigns invigilators. Unlike traditional approaches that rely on fixed-length periods, the day and time slot assignment model incorporates heterogeneous slots of 30, 60, and 90 minutes. This design enables assigning the most appropriate time duration to each exam, thereby improving time efficiency and reducing idle periods. Furthermore, the model ensures an even distribution of departmental workload throughout the examination period, preventing unfair clustering of exams across departments. The room allocation model is formulated to minimize the number of empty seats in assigned rooms, which enhances room utilization and overall capacity planning. In the invigilator assignment stage, workload balancing is emphasized to distribute responsibilities equitably among available staff members. Due to the NP-hard complexity of the problem, a genetic algorithm (GA) was utilized to produce feasible and high-quality solutions. The generated schedules were evaluated by comparing them to manually prepared timetables, and the results demonstrated significant improvements in fairness, efficiency, and resource utilization, highlighting the practical value of the proposed MIP model.

Keywords

• Examination Timetabling
• Invigilator Assignment
• Mixed-integer Programming
• Genetic Algorithm

References

1. Al-Yakoob, S. M., Sherali, H. D., & Al-Jazzaf, M. (2010). A mixed-integer mathematical modeling approach to exam timetabling. Computational Management Science, 7, 19-46. https://doi.org/10.1007/s10287-007-0066-8
2. Al‐Hawari, F., Al‐Ashi, M., Abawi, F., & Alouneh, S. (2020). A practical three‐phase ILP approach for solving the examination timetabling problem. International Transactions in Operational Research, 27(2), 924-944. https://doi.org/10.1111/itor.12471
3. Aslan, E., Şimşek, T., & Karkacıer, A. (2017). A binary integer programming model for exam scheduling problem with several departments. The Journal of Knowledge Economy & Knowledge Management, 12(2), 169-175.
4. Ayob, M., Abdullah, S., & Malik, A. M. A. (2007). A practical examination timetabling problem at the Universiti Kebangsaan Malaysia. International Journal of Computer Science and Network Security, 7(9), 198-204.
5. Bazari, S., Pooya, A., Soleimani Fard, O., & Roozkhosh, P. (2023). Modeling and solving the problem of scheduling university exams in terms of new constraints on the conflicts of professors’ exams and the concurrence of exams with common questions. OPSEARCH, 60(4), 877–915. https://doi.org/10.1007/s12597-023-00638-z
6. Bettinelli, A., Cacchiani, V., Roberti, R., & Toth, P. (2015). An overview of curriculum-based course timetabling. Top, 23(2), 313-349. https://doi.org/10.1007/s11750-015-0366-z
7. Brogniet, A., & Ninane, C. (2016). Construction of an automated examination timetabling system for École Polytechnique de Louvain [Master’s thesis, Université catholique de Louvain].
8. Burke, E. K., Newall, J. P., & Weare, R. F. (1995). A memetic algorithm for university exam timetabling. In International Conference on the Practice and Theory of Automated Timetabling (pp. 241-250). Springer. https://doi.org/10.1007/3-540-61794-9_63

9. Carlsson, M., Ceschia, S., Di Gaspero, L., Mikkelsen, R. Ø., Schaerf, A., & Stidsen, T. J. R. (2023). Exact and metaheuristic methods for a real-world examination timetabling problem. Journal of Scheduling, 26(4), 353–367. https://doi.org/10.1007/s10951-023-00778-6
10. Cataldo, A., Ferrer, J. C., Miranda, J., Rey, P. A., & Sauré, A. (2017). An integer programming approach to curriculum-based examination timetabling. Annals of Operations Research, 258, 369-393. https://doi.org/10.1007/s10479-016-2321-2
11. Chang, L. S., & Kahar, M. N. M. (2018). Modelling the Universiti Malaysia Pahang examination timetabling problem. International Journal of Software Engineering and Computer Systems, 4(1), 106-119. https://doi.org/10.15282/ijsecs.4.1.2018.9.0042
12. Cooper, T. B., & Kingston, J. H. (1995). The complexity of timetable construction problems. In International Conference on the Practice and Theory of Automated Timetabling (pp. 281-295). Springer. https://doi.org/10.1007/3-540-61794-9_66
13. Çelik, E., Kıran, E., Özdil, A. A., & İçmen Erdem, B. (2025). Öğrenci memnuniyetini ve kaynak etkinliğini esas alan bir sınav planlama modeli: Matematiksel modelleme ve uygulamalı bir karar destek sistemi tasarımı. Verimlilik Dergisi, 59(4), 853–870. https://doi.org/10.51551/verimlilik.1675882
14. Demeester, P., Bilgin, B., De Causmaecker, P., & Berghe, G. V. (2012). A hyperheuristic approach to examination timetabling problems: benchmarks and a new problem from practice. Journal of Scheduling, 15, 83-103. https://doi.org/10.1007/s10951-011-0258-5
15. Edis, R. S., & Edis, E. B. (2019). A two-phase solution approach for a real-life examination timetabling problem. Pamukkale University Journal of Engineering Sciences, 25(1), 71-81. https://doi.org/10.5505/pajes.2018.96606
16. Even, S., Itai, A., & Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. In 16th Annual Symposium on Foundations of Computer Science (pp. 184-193). IEEE https://doi.org/10.1109/SFCS.1975.21
17. Gen, M., & Cheng, R. (2000). Genetic algorithms and engineering optimization. John Wiley & Sons.
18. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison Wesley.
19. 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. https://doi.org/10.3906/elk-1909-14
20. Güler, M. G., Geçici, E., Köroğlu, T., & Becit, E. (2021). A web-based decision support system for examination timetabling. Expert Systems with Applications, 183, 115363. https://doi.org/10.1016/j.eswa.2021.115363
21. Hanum, F., Romliyah, M. A., & Bakhtiar, T. (2015). Exam invigilators assignment problem: a goal programming approach. Applied Mathematical Sciences, 9(58), 2871-2880. https://doi.org/10.12988/ams.2015.52134
22. Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press.
23. Kağnıcıoğlu, H., & Yıldız, A. (2006). Solution to job assignment problem by a 0-1 integer fuzzy goal programming approach. Anadolu University Journal of Science and Technology, 7(2), 413-429.
24. Kahar, M. N. M., & Kendall, G. (2010). The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207(2), 557-565. https://doi.org/10.1016/j.ejor.2010.04.011
25. Kamışlı Öztürk, Z. (2010). Eğitimsel zaman çizelgeleme problemleri için çözüm yaklaşımları ve web tabanlı bir karar destek sistemi önerisi [Doktora tezi, Eskişehir Osmangazi Üniversitesi].
26. Kendall, G., & Hussin, N. M. (2004). A tabu search hyper-heuristic approach to the examination timetabling problem at the MARA University of Technology. In International Conference on the Practice and Theory of Automated Timetabling (pp. 270-293). Springer. https://doi.org/10.1007/11593577_16
27. Keskin, M. E., Döyen, A., Akyer, H., & Güler, M. G. (2018). Examination timetabling problem with scarce resources: a case study. European Journal of Industrial Engineering, 12(6), 855-874. https://doi.org/10.1504/EJIE.2018.096394
28. Köse Küçük, M., Tellioğlu, B., & Çavdur, F. (2020). Sınav çizelgeleme probleminde sınıf ve gözetmen atamaları için iki aşamalı bir çözüm yaklaşımı. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi, 25(2), 789–812. https://doi.org/10.17482/uumfd.713329
29. Lach, G., & Lübbecke, M. E. (2012). Curriculum based course timetabling: new solutions to Udine benchmark instances. Annals of Operations Research, 194, 255-272. https://doi.org/10.1007/s10479-010-0700-7
30. Laisupannawong, T., & Sumetthapiwat, S. (2024). An integer linear programming model for the examination timetabling problem: A case study of a university in Thailand. Advances in Operations Research, 2024(1), 6636563. https://doi.org/10.1155/2024/6636563
31. Lewis, R. M. R. (2006). Metaheuristics for university course timetabling. [Doctoral dissertation, Napier University]
32. Lü, Z., Hao, J. K., & Glover, F. (2011). Neighborhood analysis: a case study on curriculum-based course timetabling. Journal of Heuristics, 17, 97-118. https://doi.org/10.1007/s10732-010-9128-0
33. McCollum, B., McMullan, P., Burke, E. K., Parkes, A. J., & Qu, R. (2007). The second international timetabling competition: Examination timetabling track (Technical Report QUB/IEEE/Tech/ITC2007/-Exam/v4. 0/17). Queen’s University.
34. Merlot, L. T., Boland, N., Hughes, B. D., & Stuckey, P. J. (2002). A hybrid algorithm for the examination timetabling problem. In International Conference on the Practice and Theory of Automated Timetabling (pp. 207-231). Springer. https://doi.org/10.1007/978-3-540-45157-0_14
35. Mohammed, M. A., Khanapi, M., Ghani, A., Obaid, O. I., & Mostafa, S. (2017). A review of genetic algorithm application in examination timetabling problem. Journal of Engineering and Applied Sciences, 12(20), 5166-5181.
36. Ozturk, Z. K., Ozturk, G., & Sagir, M. (2010). An automated multi-objective invigilator-exam assignment system. International Journal of Information Technology & Decision Making, 9(2), 223–238.
37. Ozturk, Z. K., Gundogan, H. S., Mumyakmaz, E., & Kececioglu, T. (2024). Exam scheduling under pandemic conditions: A mathematical model and decision support system. Technological Forecasting and Social Change, 208, 123687.
38. Parkes, A. J., & Özcan, E. (2010). Properties of Yeditepe examination timetabling benchmark instances. In Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (pp. 531-534).
39. Pillay, N., & Banzhaf, W. (2010). An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10(2), 457-467. https://doi.org/10.1016/j.asoc.2009.08.011
40. Qu, R., Burke, E. K., McCollum, B., Merlot, L. T., & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12, 55-89. https://doi.org/10.1007/s10951-008-0077-5
41. Sagir, M., & Ozturk, Z. K. (2010). Exam scheduling: Mathematical modeling and parameter estimation with the Analytic Network Process approach. Mathematical and Computer Modelling, 52(5-6), 930–941.
42. Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13, 87-127. https://doi.org/10.1023/A:1006576209967
43. Sivanandam, S., & Deepa, S., 2008. Introduction to Genetic Algorithms. Springer.
44. Tapkan, P. Z. (2019). A mathematical model for final exam schedule and an application. Erciyes University Journal of Faculty of Economics and Administrative Sciences, 53, 138-156. https://doi.org/10.18070/erciyesiibd.341232
45. Taştan, S., & Eker, H. S. (2020). Genetik algoritma ile sınav çizelgeleme. Cumhuriyet Üniversitesi İktisadi ve İdari Bilimler Dergisi, 21(2), 47–68.
46. Varlı, E., Alağaş, H. M., Eren, T., & Özder, E. H. (2017). Goal programming solution of the examiner assignment problem. Bilge International Journal of Science and Technology Research, 1(2), 105-118.
47. Ye, T., Jovine, A. S., van Osselaer, W., Zhu, Q., & Shmoys, D. B. (2025). Cornell University uses integer programming to optimize final exam scheduling. INFORMS Journal on Applied Analytics. (Early access / ahead of print)