مقایسه‌ کارآیی رهیافت‌های حل مسئله جدول زمان‌بندی دروس دانشگاهی مبتنی‌بر الگوریتم‌های خوشه‌بندی و تصمیم‌گیری چندمعیارۀ فازی ترکیبی

سامانه‌های پردازشی و ارتباطی چندرسانه‌ای هوشمند

مقاله 1، دوره 2، شماره 3 - شماره پیاپی 5، مهر 1400، صفحه 1-11   

نوع مقاله: مقاله پژوهشی

نویسندگان

بهزاد محمدخانی حاجی خواجه لو^{* 1}؛ حامد بابایی²؛ داود اسکندری¹؛ محمدرضا حسن زاده¹

¹دانشگاه فنی و حرفه ای، دانشکده مهندسی عمران، گروه مهندسی عمران ، اهر، ایران

²دانشگاه فنی و حرفه ای، دانشکده مهندسی برق و کامپیوتر، گروه مهندسی کامپیوتر، اهر، ایران

چکیده

مسئله جدول زمانبندی دروس دانشگاهی، فرآیند زمانبندی دروس برای یک نیم­سال تحصیلی توسط دانشکده های یک دانشگاه است. این مسئله به ­ترتیب رویدادها (استادان/دانشجویان/دروس) را در منابع (برش ­های زمانی/ کلاس ­های درسی)، زمانبندی و تخصیص می ­دهد. فرآیند تخصیص دارای دو قید حساس شامل قید سخت و نرم می­ باشد. در این مقاله، رهیافت­ های به­ کارگرفته ­شده برای زمان­بندی استادان (مشترک بین دانشکده ­ها) شامل: الگوریتم ­های خوشه ­بندی (K- میانگین، C- میانگین فازی و قیفی) و مقایسه تصمیم­ گیری چندمعیارۀ فازی، ترکیبی (جستجوی محلی/ ژنتیک) می­ باشد. اهداف مقاله در بر گیرندۀ کمینه­ سازی اتلاف منابع و ارضاء نزولی قیود نرم استادان (مشترک بین دانشکده ­ها) است. بهینگی و مقایسۀ کارآیی عملکرد الگوریتم ­های به ­کار رفته در این مقاله بر روی مجموعۀ داده ه­ای دانشکده­ های دانشگاه آزاد واحد اهر تحلیل و بررسی­ شده ­است.

کلیدواژه‌ها

جدول زمانبندی دروس دانشگاهی؛ الگوریتم‌های خوشه‌بندی؛ الگوریتم‌های ترکیبی

مراجع

[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.