A New Approach to The University Course Timetabling Problem based on Clustering Algorithms & Fuzzy Multi-Criteria Decision Making

Subject Areas : Multimedia Processing, Communications Systems, Intelligent Systems

behzad mohammadkhani ¹ , hamed Babaei, ² , davod eskandari ³ , mohammadreza hasanzadeh ⁴

1 - Department of Civil Engineering, Faculty of Civil Engineering, Technical and Vocational University, Ahar, Iran
2 - Department of Computer Engineering, Faculty of Electrical and Computer Engineering, Technical and Vocational University, Ahar, Iran
3 - Department of Civil Engineering, Faculty of Civil Engineering, Technical and Vocational University, Ahar, Iran
4 - اهر-دانشکده فنی و مهندسی

Received: 2021-11-30 Accepted : 2022-08-20 Published : 2021-09-23

Keywords: Hybrid Algorithms, University Course Timetabling (UCTTP), clustering algorithms,

Abstract :

 Introduction: The UCTTP problem is a hybrid optimization problem that belongs to the NP-hard class, hence determining the optimal or analytical solution of this problem is challenging. This problem, which occurs at the beginning of the university semester, involves allocating events (courses, faculty, and students) to a number of time slot and specific number of rooms. The UCTTP problem must satisfy both hard and soft constraints so that feasible time tables are obtained after complete and correct satisfaction of all hard constraints. Satisfaction of soft constraints is merely for the quality improvement of the produced feasible time tables and unlike hard constraint their satisfaction is not mandatory. Another important issue associated with this problem is the multiplicity and variety of constraints (hard and soft) that are completely case dependent. The soft constraints considered by each solution (schedule) are evaluated by the penalty function, which is obtained by a summation operator. In this operator, a weight is assigned to each soft constraint, and according to these weights, a penalty function is obtained, the output of the penalty function is used in the objective function which yields final solutions. After obtaining all the final solutions, the schedule tables that have no collisions, that is, satisfy all the strict constraints, and secondly, have a higher value in terms of the value of the objective function are selected.Method: According to the simulation results, it can be said that in using clustering algorithms, the efficiency of fuzzy C-clustering algorithm in minimizing resource loss (surplus) and descending satisfaction of soft constraints of common lecturers of faculties is higher than funnel clustering algorithm and the K-mean.Findings: The optimal ratio of the number of applied penalties for the violations of lecturers’ soft constraints and the percentage of violations of lecturers among the fuzzy multi-criteria decision comparison algorithms, local search and genetics, as well as the combination of these algorithms are related to the combination of two comparison algorithms (i.e. fuzzy multi-criteria decision making and local search).Discussion and Conclusion: We observed that with regards to the percentage of satisfaction of soft constraints of common lecturers, the combination of local search algorithms with C-fuzzy clustering shows the best performance and f fuzzy multi-criteria decision comparison algorithm has the worst performance.

References:

[1] Obit, J. H., Developing Novel Meta-heuristic, Hyper-heuristic and Cooperative Search for Course Timetabling Problems, Ph.D. Thesis, School of Computer Science University of Nottingham, 2010.

[2] Gotlib, C. C., "The Construction of Class-Teacher TimeTables", Proc IFIP Congress, Vol. 62, pp. 73-77, 1963.

[3] Asmuni, H., Fuzzy Methodologies for Automated University Timetabling Solution Construction and Evaluation, Ph.D. Thesis, School of Computer Science University of Nottingham, 2008.

[4] Lewis, M. R., Metaheuristics for University Course Timetabling, Ph.D. Thesis, Napier University, 2006.

[5] Redl, T. A., A Study of University Timetabling that Blends Graph Coloring with the Satisfaction of Various Essential and Preferential Conditions, Ph.D. Thesis, Rice University, Houston, Texas, 2004.

[6] Babaei, H., Hadidi, A., "A Review of Distributed Multi-Agent Systems Approach to Solve University Course Timetabling Problem", ACSIJ Advances in Computer Science: An International Journal, Vol. 3, Issue 5, No. 11, ISSN: 2322-5157, pp. 19-28, 2014.

[7] Feizi-Derakhshi, M. R., Babaei , H., Heidarzadeh, J., "A Survey of Approaches for University Course TimeTabling Problem", Proceedings of 8^th International Symposium on Intelligent and Manufacturing Systems, Sakarya University Department of Industrial Engineering, Adrasan, Antalya, Turkey, pp. 307-321, 2012.

[8] Babaei, H., Karimpour, J., Hadidi, A., "A survey of approaches for university course timetabling problem", Computers & Industrial Engineering, 86, pp. 43–59, 2015.

 [9] Obit, J. H., Landa-Silva, D., Ouelhadj, D., Khan Vun, T., Alfred, R., "Designing a Multi-Agent Approach System for Distributed Course TimeTabling," IEEE, 2011.

[10] Shatnawi, S., Al -Rababah, K., Bani-Ismail, B., "Applying a Novel Clustering Technique Based on FP- Tree to University Timetabling Problem: A Case Study," IEEE, 2010.

[11] Wangmaeteekul, P., Using Distributed Agents to Create University Course TimeTables Addressing Essential Desirable Constraints and Fair Allocation of Resources, Ph.D. Thesis, School of Engineering & Computing Sciences Durham University, 2011.

[12] Amintoosi, M., Haddadnia, J., "Fuzzy C-means Clustering Algorithm to Group Students in A Course into Smaller Sections," Springer-Verlag Berlin Heidelberg, LNCS 3616, pp. 147–160, 2005.

[13] S. Srinivasan, J. Singh, V. Kumar, "Multi-Agent based Decision Support System Using Data Mining and Case Based Reasoning", IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011.

[14] DeWerra, D., "An Introduction to TimeTabling", European Journal of Operational Research, 19: pp. 151-162, 1985.

[15] Asham, G.M., Soliman, M.M., Ramadan, A.R., "Trans Genetic Coloring Approach for Timetabling Problem", Artificial Intelligence Techniques Novel Approaches & Practical Applications, IJCA, pp. 17-25, 2011.

[16] Daskalaki, S., Birbas, T., Housos, E., "An integer programming formulation for a case study in university timetabling", European Journal of Operational Research, 153 (2004), pp. 117–135, 2004.

[17] Daskalaki, S., Birbas, T., "Efficient solutions for a university timetabling problem through integer programming”, European Journal of Operational Research, 160 (2005), pp. 106–120, 2005.

[18] Khonggamnerd, P., Innet, S., "On Improvement of Effectiveness in Automatic University Timetabling Arrangement with Applied Genetic Algorithm", 978-0-7695-3896-9, IEEE, 2009.

[19] Alsmadi, O. MK., Abo-Hammour, Z. S., Abu-Al-Nadi, D. I., Algsoon, A., "A Novel Genetic Algorithm Technique for Solving University Course Timetabling Problems", 978-1-4577-0690-5/11, IEEE, 2011.

[20] Mayer, A., Nothegger, C., Chwatal, A., Raidl, G., "Solving the Post Enrolment Course Timetabling Problem by Ant Colony Optimization”, In Proceedings of the 7^th International Conference on the Practice and Theory of Automated Timetabling, 2008.

[21] Ayob, M., Jaradat, G., "Hybrid Ant Colony Systems for Course Timetabling Problems", 2^nd Conference on Data Mining and Optimization 27-28 October 2009, Selangor, Malaysia, IEEE, pp. 120-126, 2009.

[22] Jat, N. S., Shengxiang, Y., "A Memetic Algorithm for the University Course Timetabling Problem", 20^th IEEE International Conference on Tools with Artificial Intelligence, IEEE, pp. 427-433, 2008.

[23] Alvarez, R., Crespo, E., Tamarit, J. M., "Design and Implementation of a Course Scheduling System Using Tabu Search", European Journal of Operational Research 137, pp. 512-523, 2002.

[24] Aladag, C. H., Hocaoglu, G., Basaran, A. M., "The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem", Expert Systems with Application, 36 (2009), pp. 12349–12356, 2009.

[25] Tuga, M., Berretta, R., Mendes, A., "A Hybrid Simulated Annealing with Kempe Chain Neighborhood for the University Timetabling Problem", 6^th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007), 2007.

[26] Shengxiang, Y., Jat, N.S., "Genetic Algorithms with Guided and Local Search Strategies for University Course Timetabling", IEEE Transactions on Systems, MAN, and Cybernetics-PART C: Applications and Reviews, Vol. 41, No. 1, January 2011.

[27] Abdullah, S., Burke, E.K., McColloum, B., "An Investigation of Variable Neighborhood Search for University Course Timetabling", In The 2^th Multidisciplinary Conference on Scheduling: Theory and Applications, NY, USA, pages 413-427, 2005.

[28] Kostuch, P., "The University Course Timetabling Problem with a Three-Phase Approach", In Lecture Notes in Computer science, pages 109-125, Springer-Berlin / Heidelberg, 2005. 

[29] Shahvali Kohshori, M., Abadeh, M. S., "Hybrid Genetic Algorithms for University Course Timetabling", IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 2, No 2, March 2012.

[30] Asmuni, H., Burke, E.K., Garibaldi, J.M., "Fuzzy multiple heuristic ordering for course timetabling", The Proceedings of the 5^th United Kingdom Workshop on Computational Intelligence (UKCI05), London, UK, pp 302-309, 2005b.

[31] Golabpour, A., Mozdorani Shirazi, H., Farahi, A., kootiani, M., beige, H., "A fuzzy solution based on Memetic algorithms for timetabling", International Conference on MultiMedia and Information Technology, IEEE, pp. 108-110, 2008.

[32] Chaudhuri, A., Kajal, D., "Fuzzy Genetic Heuristic for University Course Timetable Problem", Int. J. Advance. Soft Comput. Appl., Vol. 2, No. 1, ISSN 2074-8523, March 2010.

[33] Gaspero, L.D., Missaro, S., Schaerf, A., “A Multiagent Architecture for Distributed Course Timetabling", Proceedings of the 5^th International Conference on the Practice and Theory of Automated Timetabling (PATAT '04), pp. 471-474, 2004.

[34] Meisels, A., Kaplansky, E., "Scheduling Agents-Distributed TimeTabling Problems (DisTTP)", Springer- Verlog Berlin Heldelberg, LNCS 2740, PP. 166 – 177, 2003.

[35] Nandhini, M., Kanmani, S., "Implementation of Class Timetabling Using Multi Agents", 978-1-4244-4711-4/09, IEEE, 2009.

[36] Yanga, Y., Paranjape, R.,  "A multi-agent system for course timetabling", Intelligent Decision Technologies, Computer Science and Artificial Intelligence, IOS Press, Volume 5, page 113-131, Number 2, 2011.

[37] Babaei, H., Karimpour, J., Oroji, H., "Using fuzzy c-means clustering algorithm for common lecturers timetabling among departments", 6th International Conference on Computer and Knowledge Engineering (ICCKE 2016), 978-1-5090-3586 IEEE, October 20-21, Ferdowsi University of Mashhad, 2016.

[38] Babaei H., Karimpour J., Hadidi A., "Common lecturers timetabling among departments based on funnel-shape clustering algorithm", Springer Science + Business Media New York, Applied Intelligence, DOI 10.1007/s10489-016-0828-5, 46: pp. 386-408, 2017.

[39] Babaei H., Karimpour J., Mavizi S., "Using k-means clustering algorithm for common lecturers timetabling among departments”, ACSIJ Advances in Computer Science: An International Journal, Vol. 5, Issue 1, No.19, ISSN: 2322-5157, pp. 86-102, 2016.

[40] Ross, J. T., Fuzzy logic with engineering applications. Wiley, University of New Mexico, New Mexico, 2004.

[41] Babaei, H., Karimpour, J., Hadidi, A., "Applying Hybrid Fuzzy Multi-Criteria Decision-Making Approach to Find the Best Ranking for the Soft Constraint Weights of Lecturers in UCTP", Int. J. Fuzzy Syst. Taiwan Fuzzy Systems Association and Springer -Verlag Berlin Heidelberg, 2017.

[42] Babaei H., Karimpour J., Hadidi A., "Generating an optimal timetabling for multi-departments common lecturers using hybrid fuzzy and clustering algorithms", Springer-Verlag GmbH Germany, Soft Computing, doi.org/10.1007/s00500-018-3126-9, Volume 23, Issue 13 , pp 4735–4747, 2019.

[43] Babaei H., Hadidi A., "Generating optimal timetabling for lecturers using hybrid fuzzy and clustering algorithms", Journal of Artifical Intelligence in Electrical Engineering, Vol. 6, No. 21, 2017.