مقایسه کارآیی رهیافت‌های حل مسئله جدول زمانبندی دروس دانشگاهی مبتنی‌بر الگوریتم‌های خوشه‌بندی و تصمیم‌گیری چندمعیارۀ فازی ترکیبی
الموضوعات : سامانه‌های پردازشی و ارتباطی چندرسانه‌ای هوشمندبهزاد محمدخانی حاجی خواجه لو 1 , حامد بابایی 2 , داود اسکندری 3 , محمدرضا حسن زاده 4
1 - دانشگاه فنی و حرفه ای، دانشکده مهندسی عمران، گروه مهندسی عمران ، اهر، ایران
2 - دانشگاه فنی و حرفه ای، دانشکده مهندسی برق و کامپیوتر، گروه مهندسی کامپیوتر، اهر، ایران
3 - دانشگاه فنی و حرفه ای، دانشکده مهندسی عمران، گروه مهندسی عمران ، اهر، ایران
4 - دانشگاه فنی و حرفه ای، دانشکده مهندسی عمران، گروه مهندسی عمران ، اهر، ایران
الکلمات المفتاحية: الگوریتم‌های ترکیبی, جدول زمانبندی دروس دانشگاهی, الگوریتم‌های خوشه‌بندی,
ملخص المقالة :
مسئله جدول زمانبندی دروس دانشگاهی، فرآیند زمانبندی دروس برای یک نیم سال تحصیلی توسط دانشکده های یک دانشگاه است. این مسئله به ترتیب رویدادها (استادان/دانشجویان/دروس) را در منابع (برش های زمانی/ کلاس های درسی)، زمانبندی و تخصیص می دهد. فرآیند تخصیص دارای دو قید حساس شامل قید سخت و نرم می باشد. در این مقاله، رهیافت های به کارگرفته شده برای زمان بندی استادان (مشترک بین دانشکده ها) شامل: الگوریتم های خوشه بندی (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 8th 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 7th International Conference on the Practice and Theory of Automated Timetabling, 2008.
[21] Ayob, M., Jaradat, G., "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.
[22] Jat, N. S., Shengxiang, Y., "A Memetic Algorithm for the University Course Timetabling Problem", 20th 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", 6th 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 2th 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 5th 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 5th 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.
_||_