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

Abstract

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.

Keywords

• 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

Abstract

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.

Keywords

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

References

1. 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. 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. 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. 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. 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. 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. 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. 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. 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. 10. Carter, M.W. ve Laporte, G. (1995) Recent developments in practical examination timetabling, Springer, Berlin, Heidelberg.
11. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 37. Schaerf A. (1999) A survey of automated timetabling, Artificial Intelligence Review,13(2),87–127. doi: 10.1023/A:1006576209967
38. 38. Taha, H. A. (2000), Yöneylem Araştırması, Literatür Yayıncılık, İstanbul.
39. 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. 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. 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. 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.