Using k-means clustering algorithm for common lecturers timetabling among departments
Abstract
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 clustering algorithm k-means 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.
Keywords
Full Text:
PDFReferences
Babaei, H., Karimpour, J., and Hadidi, A., "A survey of approaches for university course timetabling problem," Computers & Industrial Engineering 86, 2015, pp. 43–59.
Feizi-Derakhshi, M. R., Babaei, H., and 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, 2012, pp. 307-321.
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, Nottingham, UK, 2010.
Gotlib, C. C., "The Construction of Class-Teacher TimeTables,", Proc IFIP Congress, Vol. 62, 1963, pp. 73-77.
Asmuni, H., Fuzzy Methodologies for Automated University Timetabling Solution Construction and Evaluation, Ph.D. Thesis, School of Computer Science University of Nottingham, Nottingham, UK, 2008.
Lewis, M. R., Metaheuristics for University Course Timetabling, Ph.D. Thesis, Napier University, Napier, UK, 2006.
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, USA, 2004.
Srinivasan, S., Singh, J., and Kumar, V., "Multi-Agent based Decision Support System Using Data Mining and Case Based Reasoning," IJCSI International Journal of Computer Science Issues, 2011, Vol. 8, Issue 4, No 2.
Obit, J. H., Landa-Silva, D., Ouelhadj, D., Khan Vun, T., and Alfred, R., "Designing a Multi-Agent Approach System for Distributed Course TimeTabling," 2011, IEEE.
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, Durham, UK, 2011.
Shatnawi, S., Al -Rababah, K., and Bani-Ismail, B., "Applying a Novel Clustering Technique Based on FP- Tree to University Timetabling Problem: A Case Study," 2010, IEEE.
DeWerra, D., "An Introduction to TimeTabling," European Journal of Operational Research 19, 1985, pp. 151-162.
Asham, G.M., Soliman, M.M. and Ramadan, A.R., "Trans Genetic Coloring Approach for Timetabling Problem," Artificial Intelligence Techniques Novel Approaches & Practical Applications, IJCA, 2011, pp. 17-25.
Daskalaki, S., Birbas, T., and Housos, E., "An integer programming formulation for a case study in university timetabling," European Journal of Operational Research 153, 2004, pp. 117–135.
Daskalaki, S., and Birbas, T., "Efficient solutions for a university timetabling problem through integer programming," European Journal of Operational Research 160, 2005, pp. 106–120.
Khonggamnerd, P., and Innet, S., "On Improvement of Effectiveness in Automatic University Timetabling Arrangement with Applied Genetic Algorithm," 2009, IEEE.
Alsmadi, O. MK., Abo-Hammour, Z. S., Abu-Al-Nadi, D. I., and Algsoon, A. , "A Novel Genetic Algorithm Technique for Solving University Course Timetabling Problems," 2011, IEEE.
Mayer, A., Nothegger, C., Chwatal, A., and Raidl, G., "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.
Ayob, M., and Jaradat, G., "Hybrid Ant Colony Systems For Course Timetabling Problems," 2nd Conference on Data Mining and Optimization 27-28 October 2009, Selangor, Malaysia, IEEE, 2009, pp. 120-126.
Jat N. S., and Shengxiang, Y., "A Memetic Algorithm for the University Course Timetabling Problem," 20th IEEE International Conference on Tools with Artificial Intelligence, IEEE, 2008, pp. 427-433.
Alvarez, R., Crespo, E., and Tamarit, J. M., "Design and Implementation of a Course Scheduling System Using Tabu Search," European Journal of Operational Research 137, 2002, pp. 512-523.
Aladag, C. H., Hocaoglu, G., and 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.
Tuga, M. Berretta, R. and Mendes, A., "A Hybrid Simulated Annealing with Kempe Chain Neighborhood for the university Timetabling Problem," 6th IEEE/ACIS International Conference on Computer and Information Science, 2007, ICIS.
Shengxiang, Y., and 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, 2011, Vol. 41, No. 1.
Abdullah, S., Burke, E.K., and McColloum, B., "An Investigation of Variable Neighborhood Search for University Course Timetabling," In The 2th Multidisciplinary Conference on Scheduling: Theory and Applications, NY, 2005, pp. 413-427.
Kostuch, P., "The University Course Timetabling Problem with a Three-Phase Approach," In Lecture Notes in Computer science, pages 109-125, 2005, Springer-Berlin / Heidelberg.
Shahvali Kohshori, M., and Saniee Abadeh, M., "Hybrid Genetic Algorithms for University Course Timetabling," IJCSI International Journal of Computer Science Issues, 2012, Vol. 9, Issue 2, No 2.
Asmuni, H., Burke, E.K., and Garibaldi, J.M., "Fuzzy multiple heuristic ordering for course timetabling," The Proceedings of the 5th United Kingdom Workshop on Computational Intelligence (UKCI05), 2005b, pp 302-309.
Golabpour, A., Mozdorani Shirazi, H., Farahi, A. kootiani, M., and H. beige, "A fuzzy solution based on Memetic algorithms for timetabling," International Conference on MultiMedia and Information Technology, IEEE, 2008, pp. 108-110.
Chaudhuri, A., and Kajal, D., "Fuzzy Genetic Heuristic for University Course Timetable Problem," Int. J. Advance. Soft Comput. Appl., 2010, Vol. 2, No. 1, ISSN 2074-8523.