FATİH ÇAVDUR, Sema DEĞİRMEN, MERVE KÖSE KÜÇÜK

SINAV ÇİZELGELEME PROBLEMLERİNDE HOMOJEN SINAV DAĞILIMININ OLUŞTURULMASI İÇİN KÜMELEME VE HEDEF PROGRAMLAMA TEMELLİ BİR YAKLAŞIM

Bu çalışma, dengeli bir sınav programı oluşturmak için kümeleme ve hedef programlama tabanlı bir yaklaşım sunmaktadır. Çalışmada, kişisel iş yükü açısından öğrencileri ve öğretim üyelerini belirli bir düzeyde memnun edecek, dengeli bir sınav programı oluşturmak amaçlanmaktadır. Bu kapsamında öncelikle, derslerin kredisi, başarı oranı ve türü olmak üzere üç parametre kullanılarak sınav kritiklik seviyelerinin belirlenmesi için k-ortalamalar kümeleme algoritması önerilmektedir. Daha sonra, belirlenen kritiklik seviyeleri ve diğer problem kısıtları dikkate alınarak bir hedef programlama modeli ile sınav çizelgesi oluşturulmaktadır. Önerilen yaklaşım, bir gerçek hayat problemi üzerinde örneklendirilmiştir. Yaklaşım sonucu oluşturulan çizelge, gerçek hayatta oluşturulan çizelge ile karşılaştırıldığında, sınavların kritiklik seviyelerini de dikkate alan dengeli bir sınav çizelgesinin oluşturulduğu görülmektedir. Buna ek olarak, önerilen yaklaşımın daha büyük boyutlu gerçek hayat problemlerinde de kullanılma potansiyeli bulunmaktadır.

Anahtar Kelimeler:

Sınav çizelgeleme, kümeleme, k-ortalamalar, hedef programlama

A Clustering and Goal Programming-Based Approach for Homogeneous Exam Distribution in Exam Scheduling Problems

This study presents a clustering and binary goal programming-based approach to create a balanced-exam schedule. The aim of the study is to create a balanced-exam schedule in terms of person workloads to achieve a certain level of satisfaction for students and professors. We first propose Ward’s method and k-means clustering algorithm for criticality level identification using credits, success ratios and types of classes. A goal programming model is then used to create an exam schedule using the criticality levels and other problem constraints. Proposed approach is illustrated with a real-life case study. We compare the exam schedule produced by the proposed approach with the real-life exam schedule. It is noted that a balanced-exam schedule is produced by our approach where the criticality levels of exams are considered. In addition, we also note that the proposed approach has a potential to be used for larger real-life exam scheduling problems.

Keywords:

Exam scheduling clustering, k-means, Ward’s method, goal programming,

PDF

___

Alsabti, K., Ranka, S. ve Singh, V. (1997) An efficient k-means clustering algorithm, Electrical Engineering and Computer Science.
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
Al-Yakoob, S. M. ve Sherali, H. D. (2015) Mathematical models and algorithms for a high school timetabling problem, Computers & Operations Research, 61, 56-68. doi:10.1016/j.cor.2015.02.011
Babaei, H., Karimpour, J. ve Hadidi, A. (2015) A survey of approaches for university course timetabling problem, Computers & Industrial Engineering, 86, 43-59. doi:10.1016/j.cie.2014.11.010
Babaei, H., Karimpour, J. ve Mavizi, S. (2016) Using k-means clustering algorithm for common lecturers timetabling among departments, Advances in Computer Science: An International Journal, 5(1), 86-102.
Babaei, H., Karimpour, J. ve Mavizi, S. (2017) Using fuzzy c-means clustering algorithm for common lecturer timetabling among departments, Journal of Advances in Computer Engineering and Technology, 3(1). doi:10.1109/ICCKE.2016.7802147
Badoni, R. P., Gupta, D. K. ve Mishra, P. (2014) A new hybrid algorithm for university course timetabling problem using events based on groupings of students, Computers & Industrial Engineering, 78, 12-25. doi:10.1016/j.cie.2014.09.020
Bijuraj, L. V. (2013) Clustering and its applications, Proceedings of National Conference on New Horizons in IT-NCNHIT, 169-172.
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
Burke, E. K., Petrovic, S. ve Qu, R. (2006) Case-based heuristic selection for timetabling problems, Journal of Scheduling, 9(2), 115-132. doi:10.1007/s10951-006-6775-y
Carter, M. W., Laporte, G. ve Chinneck, J. W. (1994) A general examination scheduling system. Interfaces, 24(3), 109-120. doi: 10.1287/inte.24.3.109
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
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
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
Dutt, A., Ismail, M. A. ve Herawan, T. (2017) A systematic review on educational data mining, IEEE Access. doi:10.1109/ACCESS.2017.2654247
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
Everitt, B. S., Landau, S., Leese, M. ve Stahl, D. (2011) Hierarchical clustering, Cluster Analysis, 5th Edition, 71-110.
Fonseca, G. H., Santos, H. G., Carrano, E. G. ve Stidsen, T. J. (2017) Integer programming techniques for educational timetabling, European Journal of Operational Research, 262(1), 28-39. doi:10.1016/j.ejor.2017.03.020
Frigui, H. ve Krishnapuram, R. (1999) A robust competitive clustering algorithm with applications in computer vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(5), 450-465. doi:10.1109/34.765656
Hamerly, G. (2003) Learning structure and concepts in data using data clustering, Unpublished Doctoral Dissertation, University of California, San Diego.
Hartigan, J. A., ve Wong, M. A. (1979) Algorithm AS 136: A k-means clustering algorithm, Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1), 100-108. doi:10.2307/2346830
Ilic, M., Spalevic, P., Ilic, S., Milivojevic, Z., Veinovic, M. ve Prlincevic, B. (2015) Data mining techniques for student timetable optimization, INFOTEH-JAHORINA, 14.
Jain, A. K. (2010) Data clustering: 50 years beyond k-means, Pattern Recognition Letters, 31(8), 651-666. doi:10.1016/j.patrec.2009.09.011
Johnes, J. (2015) Operational research in education, European Journal of Operational Research, 243(3), 683-696. doi:10.1016/j.ejor.2014.10.043
Kaur, E. J. ve Kaur, E. A. (2014) Timetable scheduling using modified clustering, International Journal of Research in Information Technology (IJRIT), 2(7), 1-8.
Kaur, N., Sahiwal, J. K. ve Kaur, N. (2012) Efficient k-means clustering algorithm using ranking method in data mining, International Journal of Advanced Research in Computer Engineering & Technology (IJARCET), 1(3), pp-85.
MacQueen, J. (1967), Some methods for classification and analysis of multivariate observations, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1(14), 281-297.
Madhulatha, T. S. (2012) An overview on clustering methods, IOSR Journal of Engineering, 2(4), 719-725.
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
Muklason, A., Parkes, A. J., Özcan, E., McCollum, B. ve McMullan, P. (2017) Fairness in examination timetabling: Student preferences and extended formulations, Applied Soft Computing, 55, 302-318. doi:10.1016/j.asoc.2017.01.026
Omran, M. G., Engelbrecht, A. P. ve Salman, A. (2007) An overview of clustering methods, Intelligent Data Analysis, 11(6), 583-605.
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
Pongcharoen, P., Promtet, W., Yenradee, P. ve Hicks, C. (2008) Stochastic optimisation timetabling tool for university course scheduling, International Journal of Production Economics, 112(2), 903-918. doi:10.1016/j.ijpe.2007.07.009
Romero, C. ve Ventura, S. (2007) Educational data mining: A survey from 1995 to 2005, Expert Systems with Applications, 33(1), 135-146. doi:10.1016/j.eswa.2006.04.005
Shatnawi, S. M., Albalooshi, F. ve Rababa'h, K. (2012) Generating Timetable and Students schedule based on data mining techniques, International Journal of Engineering Research and Applications (IJERA), 2(4), 1638-1644.
Turi, R. H. (2001) Clustering-based colour image segmentation, PhD Thesis, Monash University.
Ünal, Y. Z. ve Uysal, Ö. (2014) A new mixed integer programming model for curriculum balancing: Application to a Turkish university, European Journal of Operational Research, 238(1), 339-347. doi:10.1016/j.ejor.2014.03.015
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
Vermuyten, H., Lemmens, S., Marques, I. ve Beliën, J. (2016) Developing compact course timetables with optimized student flows, European Journal of Operational Research, 251(2), 651-661. doi:10.1016/j.ejor.2015.11.028
Ward Jr, J. H. (1963) Hierarchical grouping to optimize an objective function, Journal of the American Statistical Association, 58(301), 236-244.
Wu, X., Kumar, V., Quinlan, J. R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G. J., Ng, A., Liu, B., Yu, P. S., Zhou, Z. H., Steinbach, M., Hand, D. J. ve Steinberg, D. (2008) Top 10 algorithms in data mining, Knowledge and Information Systems, 14(1), 1-37. doi:10.1007/s10115-007-0114-2