Using fuzzy c-means clustering algorithm for common lecturer timetabling among departments
الموضوعات :hamed babaei 1 , Jaber Karimpour 2 , Sajjad Mavizi 3
1 - islamic azad university, ahar branch
2 - Department of Computer Sciences, University of Tabriz, Tabriz, Iran
3 - Department of Computer Engineering, Islamic Azad University,Shabestar Branch, Shabestar, Iran
الکلمات المفتاحية: Fuzzy c-means Clustering Algorithms, Common Lecturer TimeTabling Problem (CLTTP), University Course TimeTabling Problem (UCTTP), Multi-Agent Systems,
ملخص المقالة :
University course timetabling problem is one of the hard problems and it must be done for each term frequently which is an exhausting and time consuming task. The main technique in the presented approach is focused on developing and making the process of timetabling common lecturers among different departments of a university scalable. The aim of this paper is to improve the satisfaction of common lecturers among departments and then minimize the loss of resources within departments. The applied method is to use a collaborative search approach. In this method, at first all departments perform their scheduling process locally; then two clustering and traversing agents are used where the former is to cluster common lecturers among departments and the latter is to find unused resources among departments. After performing the clustering and traversing processes, the mapping operation in done based on principles of common lecturers constraint in redundant resources in order to gain the objectives of the problem. The problem’s evaluation metric is evaluated via using fuzzy c-means clustering algorithm on common lecturer constraints within a multi agent system. An applied dataset is based on meeting the requirements of scheduling in real world among various departments of Islamic Azad University, Ahar Branch and the success of results would be in respect of satisfying uniform distribution and allocation of common lecturers on redundant resources among different departments .
[1] Babaei, H., Karimpour, J., Hadidi, A., "A survey of approaches for university course timetabling problem," Computers & Industrial Engineering 86 (2015), pp. 43–59, 2015.
[2] Feizi-Derakhshi, M. R., Babaei, H., Heidarzadeh, J., "A Survey of Approaches for University Course TimeTabling Problem," Proceedings of 8th International Symposium on Intelligent and Manufacturing Systems, Sakarya University Department of Industrial Engineering, Adrasan, Antalya, Turkey, pp. 307-321, 2012.
[3] 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.
[4] Gotlib, C. C., "The Construction of Class-Teacher TimeTables," Proc IFIP Congress, Vol. 62, pp. 73-77, 1963.
[5] Asmuni, H., Fuzzy Methodologies for Automated University Timetabling Solution Construction and Evaluation, Ph.D. Thesis, School of Computer Science University of Nottingham, 2008.
[6] Lewis, M. R., Metaheuristics for University Course Timetabling, Ph.D. Thesis, Napier University, 2006.
[7] 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.
[8] 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.
[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] 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.
[11] 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.
[12] 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.
[13] D. DeWerra, An Introduction to TimeTabling, European Journal of Operational Research, 19: pp. 151-162, 1985.
[14] G.M. Asham, M.M. Soliman, A.R. Ramadan, Trans Genetic Coloring Approach for Timetabling Problem, Artificial Intelligence Techniques Novel Approaches & Practical Applications, IJCA, pp. 17-25, 2011.
[15] S. Daskalaki, T. Birbas, E. Housos, An integer programming formulation for a case study in university timetabling, European Journal of Operational Research, 153 (2004), pp. 117–135, 2004.
[16] S. Daskalaki, T. Birbas, Efficient solutions for a university timetabling problem through integer programming, European Journal of Operational Research, 160 (2005), pp. 106–120, 2005.
[17] P. Khonggamnerd, S. Innet, On Improvement of Effectiveness in Automatic University Timetabling Arrangement with Applied Genetic Algorithm, 978-0-7695-3896-9, IEEE, 2009.
[18] O. MK. Alsmadi, Z. S. Abo-Hammour, D. I. Abu-Al-Nadi, A. Algsoon, A Novel Genetic Algorithm Technique for Solving University Course Timetabling Problems, 978-1-4577-0690-5/11, IEEE, 2011.
[19] A. Mayer, C. Nothegger, A. Chwatal, G. Raidl, Solving the Post Enrolment Course Timetabling Problem by Ant Colony Optimization, In Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling, 2008.
[20] M. Ayob, G. Jaradat, Hybrid Ant Colony Systems For Course Timetabling Problems, 2nd Conference on Data Mining and Optimization 27-28 October 2009, Selangor, Malaysia, IEEE, pp. 120-126, 2009.
[21] N. S. Jat Y. Shengxiang, A Memetic Algorithm for the University Course Timetabling Problem, 20th IEEE International Conference on Tools with Artificial Intelligence, IEEE, pp. 427-433, 2008.
[22] R. Alvarez, E. Crespo, J. M. Tamarit, Design and Implementation of a Course Scheduling System Using Tabu Search, European Journal of Operational Research 137, pp. 512-523, 2002.
[23] C. H. Aladag, G. Hocaoglu, A. M. Basaran, The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem, Expert Systems with Application, 36 (2009), pp. 12349–12356, 2009.
[24] M. Tuga, R. Berretta, A. Mendes, A Hybrid Simulated Annealing with Kempe Chain Neighborhood for the University Timetabling Problem, 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007), 2007.
[25] Y. Shengxiang, N.S. Jat, 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.
[26] S. Abdullah, E.K. Burke, B. McColloum, An Investigation of Variable Neighborhood Search for University Course Timetabling, In The 2th Multidisciplinary Conference on Scheduling: Theory and Applications, NY, USA, pages 413-427, 2005.
[27] P. Kostuch, The University Course Timetabling Problem with a Three-Phase Approach, In Lecture Notes in Computer science, pages 109-125, Springer-Berlin / Heidelberg, 2005.
[28] M. Shahvali Kohshori, M. Saniee Abadeh, Hybrid Genetic Algorithms for University Course Timetabling, IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 2, No 2, March 2012.
[29] H. Asmuni, E.K. Burke, J.M. Garibaldi, Fuzzy multiple heuristic ordering for course timetabling, The Proceedings of the 5th United Kingdom Workshop on Computational Intelligence (UKCI05), London, UK, pp 302-309 (2005b).
[30] A. Golabpour, H. Mozdorani Shirazi, A. Farahi, M. kootiani, H. beige, A fuzzy solution based on Memetic algorithms for timetabling, International Conference on MultiMedia and Information Technology, IEEE, pp. 108-110, 2008.
[31] A. Chaudhuri, D. Kajal, Fuzzy Genetic Heuristic for University Course Timetable Problem. Int. J. Advance. Soft Comput. Appl., Vol. 2, No. 1, ISSN 2074-8523, March 2010.
[32] Ross, j., T., “Fuzzy Logic with Engineering Applications,” John Wiley & Sons Ltd, University of New Mexico, New Mexico, 2004.
