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

Year 2018, Volume: 23 Issue: 1, 167 - 188, 24.04.2018

Fatih Çavdur , Sema Değirmen , Merve Köse Küçük

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

Cited By: 2

Abstract

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

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

Abstract

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.

Keywords

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

References

• 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