SINAV ÇİZELGELEME PROBLEMİNDE SINIF VE GÖZETMEN ATAMALARI İÇİN İKİ AŞAMALI BİR ÇÖZÜM YAKLAŞIMI

Yıl 2020, Cilt: 25 Sayı: 2, 789 - 812, 31.08.2020

Merve Köse Küçük , Büşra Tellioğlu , Fatih Çavdur

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

Öz

Bu çalışmada, sınav çizelgeleme problemi için hedef programlama tabanlı bir çözüm yaklaşımı önerilmektedir. Yakın tarihli başka bir çalışma kapsamında çeşitli kriterler dikkate alınarak sınavların zaman dilimlerine atanması için bulanık mantık ve hedef programlama tabanlı bir yaklaşım geliştirilmiştir. Bu çalışmada ise sınav çizelgesinin tamamlanması amacıyla zaman dilimlerine atanmış olan sınavların, sınıf ve gözetmen atamalarının yapılması için iki aşamalı öncelikli hedef programlama tabanlı bir yaklaşım kullanılmıştır. Geliştirilen yaklaşımda, söz konusu hedef programlama modelleri ardışık olarak çözülerek, problem boyutunda azalma ve çözüm süresinde iyileşme sağlanması amaçlanmıştır. Önerilen yaklaşım, gerçek bir sınav çizelgeleme problemine uygulanmıştır. Elde edilen çizelgenin gerçek hayattaki çizelgeyle derslik kapasite kullanım oranları, toplam kullanılan derslik ve buna bağlı olarak gözetmen sayıları gibi çeşitli performans kriterleri açısından karşılaştırılması sonucunda önerilen yaklaşımın daha iyi sonuçlar ürettiği görülmüştür. Çalışma kapsamında, gözetmen tercihlerinin ve gözetmen başına sınav sürelerinin de dikkate alınmasıyla, gözetmenler için uygunluk ve iş yükü dengesinin de iyileştirilmesi sağlanmıştır. Buna ek olarak, atamaların gerçekleştirilme süreleri açısından da uzun süreler gerektiren gerçek-hayat problem çözüm süreci ile karşılaştırıldığında, önerilen yaklaşım kullanılarak çok daha kısa sürede atamalar gerçekleştirilebilmektedir.

Anahtar Kelimeler

Sınav Çizelgeleme, matematiksel programlama, hedef programlama, sınıf atama, Gözetmen atama

A Two-Phase Solution Approach for Classroom and Proctor Assignment in Exam Timetabling Problem

Öz

In this study, a goal programming-based solution approach is proposed for exam timetabling problem. A fuzzy logic and goal programming-based approach is developed in a recent study for assigning exams to time slots considering some criteria. In this study, to complete the exam schedule, classroom and proctor assignments are performed for the exams assigned to time slots earlier using a two-phase preemptive goal programming-based approach. By solving the corresponding goal programs consecutively, it is aimed at decreasing problem size and improving solution time. Proposed approach is illustrated with a real-life problem. Comparing the resulted exam schedule with the real-life exam schedule in terms of some performance criteria, such as classroom utilizations, total number of classrooms and thus the number of required proctors, yields that the proposed approach produces better results. Considering proctor preferences and exam durations per proctor, it is also possible to improve proctor satisfaction and balance their workloads. Additionally, compared with the long durations spent for performing the allocations in the real-life problem, it is possible to perform the allocations much shorter time periods using the proposed approach.

Anahtar Kelimeler

Exam Timetabling, Mathematical Programming, Goal Programming, Classroom Assignment, Proctor Assignment

Kaynakça

• 1. Abou Kasm, O., Mohandes, B., Diabat, A. ve El Khatib, S. (2019) Exam timetabling with allowable conflicts within a time window, Computers and Industrial Engineering, 127, 263-273. doi: 10.1016/j.cie.2018.11.037
• 2. Aldeeb, B.A., Al-Betar, M.A., Abdelmajeed, A.O., Younes, M.J., Alkenani, M., Alomoush, W., Alissa, A.O. ve Alqahtani, M.A. (2019) A comprehensive review of uncapacitated university examination timetabling problem, International Journal of Applied Engineering Research, 14(24), 4524-4547
• 3. Al-Yakoob, S.M., Sherali, H. ve Al-Jazzaf, M. (2010) A mixed-integer mathematical modeling approach to exam timetabling, Computational Management Science, 7(1), 19-46. doi: 10.1007/s10287-007-0066-8
• 4. 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
• 5. 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
• 6. Beaumont, N. (1997) Scheduling staff using mixed integer programming, European Journal of Operational Research, 98(3), 473–484. doi: 10.1016/S0377-2217(97)00055-6
• 7. Bergmann, L. K., Fischer, K. ve Zurheide, S. (2014) A linear mixed-integer model for realistic examination timetabling problems, In Proceedings of the 10th International Conference on the Practice and Theory of Automated Timetabling, 82-101
• 8. Burke, E.K., Elliman, D.G., Ford, P.H. ve Weare, R.F. (1996) Examination timetabling in British universities: a survey. Burke E, Ross P, Practice and theory of automated timetabling, 76–90. doi: 10.1007 / 3-540-61794-9_52
• 9. Burke, E. K. ve Petrovic, S. (2002) Recent research directions in automated timetabling, European Journal of Operational Research, 140(2), 266-280. doi: 10.1016/S0377 2217(02)00069-3
• 10. Carter, M.W. ve Laporte, G. (1995) Recent developments in practical examination timetabling, Springer, Berlin, Heidelberg.
• 11. Carter, M.W ve Tovey, C.A. (1992) When is the classroom assignment problem hard, Operations Research,40(1),32–7. doi: 10.1287/opre.40.1.S28
• 12. Cavdur, F. ve Kose, M. (2016) A fuzzy logic and binary-goal programming-based approach for solving the exam timetabling problem to create a balanced-exam schedule, International Journal of Fuzzy Systems, 18(1), 119-129. doi: 10.1007/s40815-015-0046-z
• 13. Ceylan, Z., Yüksel, A., Yıldız, A. ve Şimşak, B. (2019) Sınav Çizelgeleme Problemi için Hedef Programlama Yaklaşımı ve Bir Uygulama, Erzincan Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 12(2), 942-956. doi: 10.18185/erzifbed.513981
• 14. Chu, S. C., Chen, Y. T. ve Ho, J. H. (2006) Timetable scheduling using particle swarm optimization, Innovative Computing, Information and Control, 3, 324-327. doi:10.1109/ICICIC.2006.541
• 15. Dammak, A., Elloumi, A. ve Kamoun H. (2006) Classroom assignment for examtimetabling, Advances in Engineering Software, 37 (10) 659–666.doi: 10.1016/j.advengsoft.2006.02.001
• 16. 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(1), 117-135. doi:10.1016/S0377-2217(03)00103-6
• 17. Dener, M. ve Calp, M.H. (2018) Solving the exam scheduling problems in central exams with genetic algorithms, Mugla Journal of Science and Technology, 102-115. doi: 10.22531/muglajsci.423185
• 18. Dorneles, A.P., Araujo, O.C.B. ve Buriol, L.S. (2017) A column generation approach to high school timetabling modeled as a multicommodiy flow problem, European Journal of Operational Research, 256, 685-695. doi: 10.1016/j.ejor.2016.07.002
• 19. Eley, M. (2006) Ant algorithms for the exam timetabling problem, International Conference on the Practice and Theory of Automated Timetabling, 364-382. doi:10.1007/978-3-540-77345-0_23
• 20. Elloumi, A., Kamoun, H., Jarboui, B. ve Dammak, A. (2014) The classroom assignment problem: Complexity, size reduction and heuristics, Applied Soft Computing Journal, PART C(14), 677-686. doi: 10.1016/j.asoc.2013.09.003
• 21. Ferland J.A. ve Roy S. (1985) Timetabling problem for university as assignment of activities to resources, Computers & Operations Research, 12(2), 207–18. doi: 10.1016/0305 0548(85)90045-0
• 22. 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
• 23. 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
• 24. Hanum, F., Romliyah, M. A. ve Bakhtiar, T. (2015) Exam invigilators assignment problem: a goal programming approach, Applied Mathematical Sciences, 9(58), 2871- 2880. doi: 10.12988/ams.2015.52134
• 25. June T.L., Obit J.H., Leau Y.B. ve Bolongkikit J. (2019) Implementation of Constraint Programming and Simulated Annealing for Examination Timetabling Problem, Springer, Singapore. doi:10.1007/978-981-13-2622-6_18
• 26. Kahar, M.N.M. ve 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. doi: 10.1016/j.ejor.2010.04.011
• 27. Leite, N., Melício, A. ve Rosa, A. (2019) A fast simulated annealing algorithm for the examination timetabling problem, Expert Systems with Applications, 122, 137-151. doi:10.1016/j.eswa.2018.12.048
• 28. Meisels, A., Gudes, E. ve Solotorevsky, G. (1996) Employee Timetabling, Constraint Networks and Knowledge-based Rules: A mixed approach, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1153, 93–105. doi: 10.1007/3-540-61794-9_53
• 29. Meisels, A. ve Kaplansky, E. (2003) Scheduling agents-distributed timetabling problems, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2740, 166–177. doi: 10.1007/978-3-540-45157-0_11
• 30. MirHassani, S. A. ve Habibi, F. (2013) Solution approaches to the course timetabling problem, Artificial Intelligence Review, 1-17. doi: 10.1007/s10462-011-9262-6
• 31. Mukherjee, A. ve Gilbert, K. (1997) Lagrangian heuristics for instructor scheduling in executive development programmes, Journal of the Operational Research Society, 48(4), 373–382. doi: 10.1057/palgrave.jors.2600368
• 32. Mullinax, C. ve Lawley, M. (2002) Assigning patients to nurses in neonatal intensive care, Journal of the Operational Research Society, 53(53), 25–35. doi: 10.1057/palgrave/jors/2601265
• 33. Mansour, N., Isahakian, V. ve Ghalayini, I. (2011) Scatter search technique for exam timetabling. Applied Intelligence, 34, 299–310. doi.org/10.1007/s10489-009-0196-5
• 34. Pillay, N. ve Banzhaf, W. (2010) An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10(2), 457-467. doi: 10.1016/j.asoc.2009.08.011
• 35. Saat, E. H. M., Ilham, N. I., Othman, N., Bakar, Z. A., Yusof, Y. ve Rahman, N. H. A. (2019) The examination timetabling problem based on expert system: a case study in malaysia, IEEE 10th Control and System Graduate Research Colloquium, Malaysia, 121-126, doi: 10.1109/ICSGRC.2019.8837058.
• 36. Saraç, T., Özçelik, F. ve Erdoğan, H. (2019) A goal programming model for the make-up/compensation examination problem, Pamukkale University Journal of Engineering Sciences, 26 (1), 203-210. doi: 10.5505/pajes.2019.01033
• 37. Schaerf A. (1999) A survey of automated timetabling, Artificial Intelligence Review,13(2),87–127. doi: 10.1023/A:1006576209967
• 38. Taha, H. A. (2000), Yöneylem Araştırması, Literatür Yayıncılık, İstanbul.
• 39. Tapkan, P. (2019) Final sınav programı hazırlama problemine ait bir matematiksel model ve uygulama, Erciyes Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi,53,138-156. doi: 10.18070/erciyesiibd.341232
• 40. Varlı, E., Alağaş, H.M., Eren, T. ve Özder, E.H. (2017) Goal Programming Solution of the Examiner Assignment Problem, Bilge International Journal of Science and Technology Research, 1(2), 105-118.
• 41. Veenstra, M. ve Vis, I. F. (2016) School timetabling problem under disturbances, Computers & Industrial Engineering, 95, 175-186. doi:10.1016/j.cie.2016.02.011
• 42. Yadollahi, M. ve Razavi, S. (2019) Using Artificial Fish Swarm Algorithm to Solve University Exam Timetabling Problem, Journal of Advances in Computer Research, 10 (2), 109-117.