Developing A Swap Based Algorithm For Solving Proctor Assignment Problem

Yıl 2017, Cilt: 19 Sayı: 2, 492 - 506, 08.09.2017

Mehmet Özçalıcı

Öz

Modern
academic institutions are getting busy with preparing examination schedules
which includes the information of which proctor is assigned to which exams in
each semester. Each institution has its own structure which makes it a
necessity to develop institution-specific solutions. In most of the institutions, exam timetables are preparing
manually. This requires a considerable time for the responsible team. In this study, a new algorithm is proposed to assign
proctors to exams, in an efficient way. The algorithm is based on the ways that
are applied by author and his colleagues when they were preparing the
examination schedule. The algorithm is
applied to assign proctors to final exams in Kilis 7 Aralık University, Winter
Semester of 2016-2017. By applying the proposed algorithm in MATLAB
environment, it became possible to prepare a schedule which requires 35-40
minutes to prepare manually in a small fraction of a second. The proposed
algorithm can be adopted by other institutions by making small changes. Moreover,
its flexible content makes it possible to rearrange for different needs.

Anahtar Kelimeler

Proctor assignment, scheduling, algorithm, optimization, MATLAB

Sınavlara Gözetmen Atama Probleminin Çözümü İçin Takas Bazlı Bir Algoritma Önerisi

Öz

Modern akademik kurumlar, her dönemde
birkaç kere, gözetmenlerin görevli oldukları sınavların hangileri olduğunu
içeren çizelgeler hazırlamakla meşgul olmaktadırlar. Her yükseköğretim kurumunun
kendine has yapısının olması, kurumlara özel çözümlerin geliştirilmesini
zorunlu kılmaktadır.  Sınav çizelgeleri
birçok kurumda kağıt üzerinde hazırlanmaktadır. Bu durum, çizelgeyi
hazırlamakla görevli kişiler için önemli bir mesai gerektirmektedir. Bu
çalışmada, sınavlara gözetmen atama problemini etkin bir şekilde çözecek bir
algoritma önerilmektedir. Algoritmanın geliştirilmesinde, yazarın ve çalışma
arkadaşlarının kağıt üzerinde gözetmen atadıkları zamanlardaki uygulamaları
esas alınmıştır. Algoritma, Kilis 7 Aralık Üniversitesi İktisadi ve İdari
Bilimler Fakültesinin 2016-2017 Güz dönemi dönem sonu sınavlarına gözetmen atamak
için kullanılmıştır. Sonuçta, 35-40 dakikada tamamlanan atama işlemi, önerilen
algoritmanın MATLAB yazılımındaki uygulaması ile birlikte, bir saniyenin altında
bir sürede tamamlanabilmiştir. Geliştirilen algoritma, üzerinde bazı
değişiklikler gerçekleştirmek suretiyle, diğer kurumların gözetmen atama
problemlerinin çözümü için de uygulanabilir. Aynı zamanda esnek bir yapıya
sahip olması sayesinde başka ihtiyaçlar doğrultusunda yeniden düzenlenebilir. 

Anahtar Kelimeler

Gözetmen atama, çizelgeleme, algoritma, optimizasyon, MATLAB

Kaynakça

• Abdullah, S., & Turabieh, H. (2012). On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems. Information Sciences, 191, 146–168. https://doi.org/10.1016/j.ins.2011.12.018
• Acar, M. F., & Şevkli, M. (2013). Sınav Çizelgelemesi İçin Matematiksel Model Yaklaşımı. Verimlilik Dergisi, 2013(1), 75–86.
• Al-Betar, M. A., Khader, A. T., & Doush, I. A. (2014). Memetic techniques for examination timetabling. Annals of Operations Research, 218(1), 23–50. https://doi.org/10.1007/s10479-013-1500-7
• Al-Yakoob, S. M., Sherali, H. D., & Al-Jazzaf, M. (2010). A mixed-integer mathematical modeling approach to exam timetabling. Computational Management Science, 7(1), 19–46. https://doi.org/10.1007/s10287-007-0066-8
• Arbaoui, T., Boufflet, J. P., & Moukrim, A. (2016). A matheuristic for exam timetabling. IFAC-PapersOnLine, 49(12), 1289–1294. https://doi.org/10.1016/j.ifacol.2016.07.701
• Brucker, P., & Knust, S. (2010). On th complexity of scheduling. In Y. Robert & F. Vivien (Eds.), Introduction to Scheduling (pp. 1–20). CRC Press Taylor&Francis Group.
• Burke, E. K., & Newall, J. P. (2004). Solving Examination Timetabling Problems through Adaption of Heuristic Orderings. Annals of Operations Research, 129, 107–134. https://doi.org/10.1023/B:ANOR.0000030684.30824.08
• Çoruhlu, A. (2007). Sınav Personel Çizelgeleme Modeli, Yayımlanmamış Yüksek Lisans Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ekim 2007.
• Dowsland, K. A. & Thompson, J. M. (2005). Ant colony optimization for the examination scheduling problem. Journal of the Operational Research Society, 56, 426–438
• İlkuçar, M. (2011). Sınav Gözetmenlik Çizelgeleme Probleminin Optimizasyonu ve Bir Uygulama Yazılımı. In Akademik Bilişim Konferansı 11 (pp. 413–420).
• 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
• Kalayci, C. B., & Güngör, A. (2012). A genetic algorithm based examination timetabling model focusing on student success for the case of the college of engineering at Pamukkale University, Turkey. Gazi University Journal of Science, 25(1), 137–153.
• Kingston, J. H. (2013). Educational Timetabling. In A. Ş. Etaner-Uyer, E. Özcan, & N. Urquhart (Eds.), Automated Scheduling and Planning (Vol. 505, pp. 91–108). Springer-Verlag. https://doi.org/10.1007/978-3-642-39304-4
• Koide, T. (2015). Mixed integer programming approach on examination proctor assignment problem. Procedia Computer Science, 60(1), 818–823. https://doi.org/10.1016/j.procs.2015.08.244
• Leung, J. Y.-T. (2004). Introduction and Notation. In J. Y.-T. Leung (Ed.), Handbook of Scheduling Algorithms, Models and Performance Analysis. Chapman & Hall/CRC.
• Lewis, R. (2008). A survey of metaheuristic-based techniques for University Timetabling problems. OR Spectrum, 30(1), 167–190. https://doi.org/10.1007/s00291-007-0097-0
• MirHassani, S. A. (2006). A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 175, 814–822
• Özçalıcı, M. (2016). Sınavlara gözetmen atama problemlerinin çalışma sayfaları ile optimizasyonu. Niğde Üniversitesi İİBF Dergisi, 9(3), 103–114.
• Pillay, N. (2016). A review of hyper-heuristics for educational timetabling. Annals of Operations Research (Vol. 239). Springer US. https://doi.org/10.1007/s10479-014-1688-1
• Pinedo, M. L. (2016). Scheduling. Scheduling. Springer Science+Business Media. https://doi.org/10.1007/978-3-319-26580-3
• Qu, R., Burke, E. K., McCollum, B., Merlot, L. T. G., & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12(1), 55–89. https://doi.org/10.1007/s10951-008-0077-5
• Rashidi Komijan, A., & Nouri Koupaei, M. (2012). A new binary model for university examination timetabling: a case study. Journal of Industrial Engineering International, 8(1), 28. https://doi.org/10.1186/2251-712X-8-28
• Schaerf, A. (1999). Survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127. https://doi.org/10.1023/A:1006576209967
• Woumans, G., Boeck, L. De, Beliën, J., & Creemers, S. (2016). A column generation approach for solving the examination-timetabling problem. European Journal of Operational Research, 253(1), 17. https://doi.org/10.1016/j.ejor.2016.01.046