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

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

1. Alsabti, K., Ranka, S. ve Singh, V. (1997) An efficient k-means clustering algorithm, Electrical Engineering and Computer Science.
2. 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
3. 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
4. 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
5. 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.
6. 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
7. 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
8. Bijuraj, L. V. (2013) Clustering and its applications, Proceedings of National Conference on New Horizons in IT-NCNHIT, 169-172.

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. 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
11. 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
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. 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
14. 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
15. Dutt, A., Ismail, M. A. ve Herawan, T. (2017) A systematic review on educational data mining, IEEE Access. doi:10.1109/ACCESS.2017.2654247
16. 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
17. Everitt, B. S., Landau, S., Leese, M. ve Stahl, D. (2011) Hierarchical clustering, Cluster Analysis, 5th Edition, 71-110.
18. 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
19. 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
20. Hamerly, G. (2003) Learning structure and concepts in data using data clustering, Unpublished Doctoral Dissertation, University of California, San Diego.
21. 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
22. Ilic, M., Spalevic, P., Ilic, S., Milivojevic, Z., Veinovic, M. ve Prlincevic, B. (2015) Data mining techniques for student timetable optimization, INFOTEH-JAHORINA, 14.
23. 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
24. Johnes, J. (2015) Operational research in education, European Journal of Operational Research, 243(3), 683-696. doi:10.1016/j.ejor.2014.10.043
25. 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.
26. 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.
27. 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.
28. Madhulatha, T. S. (2012) An overview on clustering methods, IOSR Journal of Engineering, 2(4), 719-725.
29. 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
30. 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
31. Omran, M. G., Engelbrecht, A. P. ve Salman, A. (2007) An overview of clustering methods, Intelligent Data Analysis, 11(6), 583-605.
32. 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
33. 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
34. 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
35. 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.
36. Turi, R. H. (2001) Clustering-based colour image segmentation, PhD Thesis, Monash University.
37. Ü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
38. 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
39. 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
40. Ward Jr, J. H. (1963) Hierarchical grouping to optimize an objective function, Journal of the American Statistical Association, 58(301), 236-244.
41. 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