خوارزمية تطويرية لحل مشكلة جدولة توقيتات المقررات الاكاديمية
محتوى المقالة الرئيسي
الملخص
جدولة أوقات الدروس في الأقسام الكبيرة في الجامعات تعتبر مشكلة صعبة للغاية وغالبًا ما يتم حلها من قبل الموظفين على الرغم من أن النتائج مثالية بشكل جزئي. لقد حدت للغاية مشكلة جدولة الوقت من مشكلة التحسين التوافقي، يهدف هذا العمل تطبيق مبدأ الخوارزمية التطورية باستخدام النظريات الوراثية لحل مشكلة الجدولة الزمنية في محاولة الحصول على جدول زمني عشوائي ومثالي مع القدرة على إنشاء جدول زمني متعدد الاحتمالات ومثالي بشكل كامل لكل مرحلة دراسية في القسم المعني وبما يتلاءم مع القيود التي يفرضها الطلبة والكادر التدريسي وضمن ساعات عمل محددة مسبقا. تتمثل الفكرة الرئيسية في امكانية إنشاء جداول زمنية للدروس بطريقة تلقائية بعد تحديد الشروط المجدية للحصول على جدول زمني مرن ومثالي بدون تكرار من خلال تقديم جدول زمني قابل للتبديل والتدوير. تكمن المساهمة الرئيسية في هذا العمل من خلال زيادة مرونة توليد جداول زمنية مثالية بنسخ مختلفة من خلال زيادة احتمال إعطاء أفضل جدول زمني لكل مرحلة في الحرم الجامعي مع القدرة على استبدال الجدول الزمني عند الحاجة. الخوارزمية التطورية (EA) المستخدمة في هذه الورقة هي الخوارزمية الجينية (GA) التي هي عبارة عن بحث متعدد الحلول يعتمد على عدد المجتمع التطوري الذي يمكن تطبيقه لحل مشاكل معقدة مثل مشاكل الجدول الزمني. في هذا العمل، جميع المدخلات: الدروس والكادر التدريسي والوقت قد تمثلت بمجموعة واحدة لتحقيق البحث المحلي ودمج هذا التمثيل للجدول الزمني باستخدام التبادل الموجه لضمان عدم خرق الشروط الأساسية التي تم تحديدها مسبقا كدالة تطابق. قدمت النتائج نظام جدولة مرن حيث اظهرت نتائج الاختبار تنوع جميع الجداول الزمنية الممكنة التي يمكن إنشاؤها بما يتلاءم مع شروط المستخدم وحاجاته.
Received 2/6/2020
Accepted 14/2/2020
Published Online First 20/9/2021
تفاصيل المقالة
هذا العمل مرخص بموجب Creative Commons Attribution 4.0 International License.
كيفية الاقتباس
المراجع
Marczyk A. Genetic algorithms and evolutionary computation. The Talk Origins Archive: http://www. talkorigins/faqs/genalg/genalg. html. 2004 Apr.
Coello CA. An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys (CSUR). 2000 Jun 1;32(2):109-43.
Bhattacharjya RK. Introduction to genetic algorithms. IIT Guwahati. 2012 Oct 19;12.
Hammood MM. Application of data mining algorithm with genetic algorithm. TJPS. 2008;13(3):9-16.
Affenzeller M, Wagner S, Winkler S, Beham A. Genetic algorithms and genetic programming: modern concepts and practical applications. Crc Press; 2009 Apr 9.
Willemen RJ. School timetable construction--Algorithms and complexity;(2002).
Sigl B, Golub M, Mornar V. Solving timetable scheduling problem using genetic algorithms. InProceedings of the 25th International Conference on Information Technology Interfaces, 2003. ITI 2003. 2003 Jun 19 (pp. 519-524). IEEE.
Bäck T, Fogel DB, Michalewicz Z, editors. Evolutionary computation 1: Basic algorithms and operators. CRC press; 2018 Oct 3.
Burke EK, Kendall G. Search methodologies. Springer Science+ Business Media, Incorporated; 2005.
Reeves C, Rowe JE. Genetic algorithms: principles and perspectives: a guide to GA theory. Springer Science & Business Media; 2002 Dec 31.
Koza JR, Keane MA, Streeter MJ, Mydlowec W, Yu J, Lanza G. Genetic programming IV: Routine human-competitive machine intelligence. Springer Science & Business Media; 2006 Mar 4.
Chambers LD, editor. Practical handbook of genetic algorithms: complex coding systems. CRC press; 2019 Jul 17.
Ansari A, Bojewar S. Genetic Algorithm to Generate the Automatic Time-Table–An Over View. IJRITCC. 2014;2(11):3480-3.
Timilsina S, Negi R, Khurana Y, Seth J. Genetically Evolved Solution to Timetable Scheduling Problem. Int J Comput Appl. 2015 Jan 1;114(18).
Abdelhalim EA, El Khayat GA. A utilization-based genetic algorithm for solving the university timetabling problem (uga). AEJ. 2016 Jun 1;55(2):1395-409..
Soyemi J, Akinode J, Oloruntoba S. Electronic Lecture Time-Table Scheduler Using Genetic Algorithm. In2017 IEEE 15th Intl Conf on Dependable, Autonomic and Secure Computing, 15th Intl Conf on Pervasive Intelligence and Computing, 3rd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress (DASC/PiCom/DataCom/CyberSciTech) 2017 Nov 6 (pp. 710-715). IEEE.
Syahputra MF, Apriani R, Abdullah D, Albra W, Heikal M, Abdurrahman A, et al Genetic algorithm to solve the problems of lectures and practicums scheduling. InIOP Conference Series: Materials Science and Engineering 2018 Feb (Vol. 308, No. 1, p. 012046). IOP Publishing..
Ahmad IR, Sufahani S, Ali M, Razali SN. A Heuristics Approach for Classroom Scheduling Using Genetic Algorithm Technique. In Journal of Physics (IOP Science): Conference Series 2018 Apr (Vol. 995, No. 1, p. 012050). IOP Publishing..
Deeba K, Kuntal B, Samriddho R. Solving Timetable Scheduling Problems Using Genetic Algorithm. International IJRTE. February 2019; 7(5C):168-170.
Mandal AK, Kahar MN, Kendall G. Addressing Examination Timetabling Problem Using a Partial Exams Approach in Constructive and Improvement. Computation. 2020 Jun;8(2):46.
Abayomi-Alli O, Abayomi-Alli A, Misra S, Damasevicius R, Maskeliunas R. Automatic examination timetable scheduling using particle swarm optimization and local search algorithm. In Data, Engineering and Applications 2019 (pp. 119-130). Springer, Singapore.
Tilahun SL. Prey-predator algorithm for discrete problems: a case for examination timetabling problem. Turk J Elec Eng Comp Sci. 2019 Mar 1;27(2):950-60.
Lei Y, Gong M, Jiao L, Shi J, Zhou Y. An adaptive coevolutionary memetic algorithm for examination timetabling problems. IJBIC. 2017;10(4):248-57.
Leite N, Fernandes CM, Melicio F, Rosa AC. A cellular memetic algorithm for the examination timetabling problem. COR. 2018 Jun 1;94:118-38.
Pillay N, Özcan E. Automated generation of constructive ordering heuristics for educational timetabling. Ann. Oper. Res. 2019 Apr 1;275(1):181-208.