الحل الفعال للجدول الزمني للمحاضرات الجامعية باستخدام محسن سرب الجسيمات استناداً على منهجية الإرشاد العالي
محتوى المقالة الرئيسي
الملخص
عادة ما تكون مشكلة الجدول الزمني للمحاضرات الجامعية (UCTP) هي مشكلة تحسين الإندماجية. يستغرق الأمر جهود يدوية لعدة أيام للوصول إلى جدول زمني مفيد ، ولا تزال النتائج غير جيدة بما يكفي. تُستخدم طرق مختلفة من (الإرشاد أو الإرشاد المساعد) لحل UCTP بشكل مناسب. لكن هذه الأساليب عادةً ما تعطي حلول محدودة. يعالج إطار العمل الاسترشادي العالي هذه المشكلة المعقدة بشكل مناسب. يقترح هذا البحث استخدام محسن سرب الجسيمات استنادا على منهجية الإرشاد العالي (HH PSO) لمعالجة مشكلة الجدول الزمني للمحاضرات الجامعية (UCTP) . محسن سرب الجسيمات PSO يستخدام كطريقة ذات مستوى عالي لتحديد تسلسل الاستدلال ذي المستوى المنخفض (LLH) والذي من ناحية أخرى يستطيع توليد الحل الأمثل. لنهج المقترح يقسم الحل إلى مرحلتين (المرحلة الأولية ومرحلة التحسين). قمنا بتطوير LLH جديد يسمى "أقل عدد ممكن من الغرف المتبقية" لجدولة الأحداث. يتم استخدام مجموعتي بيانات مسابقة الجدول الزمني الدولية (ITC) ITC 2002 و ITC 2007 لتقييم الطريقة المقترحة. تشير النتائج الأولية إلى أن الإرشاد منخفض المستوى المقترح يساعد في جدولة الأحداث في المرحلة الأولية. بالمقارنة مع LLH الأخرى ، الطريقة LLH المقترحة جدولت المزيد من الأحداث لـ 14 و 15 من حالات البيانات من 24 و 20 حالة بيانات من ITC 2002 و ITC 2007 ، على التوالي. تظهر الدراسة التجريبية أن HH PSO تحصل على معدل خرق أقل للقيود في سبع وستة حالات بيانات من ITC 2007 و ITC 2002 ، على التوالي. واستنتج هذا البحث أن LLH المقترحة يمكن أن تحصل على حل معقول وملائم إذا تم تحديد الأولويات
Received 18/10/2021
Accepted 14/11/2021
تفاصيل المقالة
هذا العمل مرخص بموجب Creative Commons Attribution 4.0 International License.
كيفية الاقتباس
المراجع
Hosny MI. A Heuristic Algorithm for Solving the Faculty Assignment Problem. 2013;
Schaerf A. Survey of automated timetabling. Artif Intell Rev [Internet]. 1999 [cited 2021 Feb 9];13(2):87–127. Available from: https://link.springer.com/article/10.1023/A:1006576209967
Burke EK, McCollum B, Meisels A, Petrovic S, Qu R. A graph-based hyper-heuristic for educational timetabling problems. Eur J Oper Res. 2007 Jan 1;176(1):177–92.
Burke E, MacCloumn B, Meisels A, Petrovic S, Qu R. A Graph-Based Hyper Heuristic for Timetabling Problems. Eur J Oper Res [Internet]. 2010;176:177–92. Available from: http://eprints.nottingham.ac.uk/371/
Burke EK, Elliman DG, Weare R. A university timetabling system based on graph colouring and constraint manipulation. J Res Comput Educ [Internet]. 1994 [cited 2021 Feb 9];27(1):1–18. Available from: https://www.tandfonline.com/doi/abs/10.1080/08886504.1994.10782112
Iqbal Z, Shahzad W, Faiza M. A diverse clustering particle swarm optimizer for dynamic environment: To locate and track multiple optima. In: Proceedings of the 2015 10th IEEE Conference on Industrial Electronics and Applications, ICIEA 2015 [Internet]. Institute of Electrical and Electronics Engineers Inc.; 2015 [cited 2021 Feb 9]. p. 1755–60. Available from: http://ieeexplore.ieee.org/document/7334395/
Shiau DF. A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences. Expert Syst Appl. 2011 Jan 1;38(1):235–48.
Thepphakorn T, Pongcharoen P. Performance improvement strategies on Cuckoo Search algorithms for solving the university course timetabling problem. Expert Syst Appl. 2020 Dec 15;161:113732.
Tan JS, Goh SL, Sura S, Kendall G, Sabar NR. Hybrid particle swarm optimization with particle elimination for the high school timetabling problem. Evol Intell [Internet]. 2020 Aug 28 [cited 2021 Oct 17];1:1–16. Available from: https://link.springer.com/article/10.1007/s12065-020-00473-x
McCollum B, Schaerf A, Paechter B, McMullan P, Lewis R, Parkes AJ, et al. Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS J Comput [Internet]. 2010 May 19 [cited 2021 Oct 17];22(1):120–30. Available from: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.1090.0320
Goh SL, Kendall G, Sabar NR. Improved local search approaches to solve the post enrolment course timetabling problem. Eur J Oper Res. 2017 Aug 16;261(1):17–29.
Abdul Rahman S. Search Methodologies for Examination Timetabling. School of Computer Science and Information Technology. University of Nottingham. 2012.
Cambazard H, Hebrard E, Sullivan BO. Submission to ICT : Track 2. International Timetabling Compertition. 2007.
Mitsunori A, Koji N, Toshihide I. An Approach using General CSP Solver. ITC-2007 Track2. 2007.
Chiarandini M, Fawcett C, Hoos HH. A modular multiphase heuristic solver for post enrolment course timetabling. In: 7th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2008. 2008.
Müller T. ITC2007 solver description: A hybrid approach. Ann Oper Res [Internet]. 2009 Oct 18 [cited 2021 Oct 17];172(1):429–46. Available from: https://link.springer.com/article/10.1007/s10479-009-0644-y
Goh SL, Kendall G, Sabar NR, Abdullah S. An effective hybrid local search approach for the post enrolment course timetabling problem. OPSEARCH [Internet]. 2020 Jun 20 [cited 2021 Oct 17];57(4):1131–63. Available from: https://link.springer.com/article/10.1007/s12597-020-00444-x
Nothegger C, Mayer A, Chwatal A, Raidl GR. Solving the post enrolment course timetabling problem by ant colony optimization. Ann Oper Res [Internet]. 2012 Feb 9 [cited 2021 Oct 17];194(1):325–39. Available from: https://link.springer.com/article/10.1007/s10479-012-1078-5
Ross P, Marìn-Blázquez JG. Constructive hyper-heuristics in class timetabling. In: 2005 IEEE Congress on Evolutionary Computation, IEEE CEC 2005 Proceedings. 2005. p. 1493–500.
Lissovoi A, Oliveto PS, Warwicker JA. On the time complexity of algorithm selection hyper-heuristics for multimodal optimisation. In: 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 [Internet]. AAAI Press; 2019 [cited 2021 Oct 18]. p. 2322–9. Available from: https://ojs.aaai.org/index.php/AAAI/article/view/4071
Rossi-doria O, Paechter B. An hyperheuristic approach to course timetabling problem using an evolutionary algorithm. Evol Comput [Internet]. 2003 [cited 2021 Feb 9];(January 2014). Available from: https://www.researchgate.net/publication/228724044
Ross P, Marín-Blázquez JG, Hart E. Hyper-heuristics applied to class and exam timetabling problems. In: Proceedings of the 2004 Congress on Evolutionary Computation, CEC2004. 2004. p. 1691–8.
Bai R, Blazewicz J, Burke EK, Kendall G, McCollum B. A simulated annealing hyper-heuristic methodology for flexible decision support. 4OR [Internet]. 2012 Mar 23 [cited 2021 Feb 9];10(1):43–66. Available from: https://link.springer.com/article/10.1007/s10288-011-0182-8
Rattadilok P. An investigation and extension of a hyper-heuristic framework. Inform. 2010;34(4):523–34.
Soria-Alcaraz JA, Ochoa G, Swan J, Carpio M, Puga H, Burke EK. Effective learning hyper-heuristics for the course timetabling problem. Eur J Oper Res. 2014 Oct 1;238(1):77–86.
Jonasson J, Norgren E. Investigating a Genetic Algorithm - Simulated Annealing Hybrid Applied to University Course Timetabling Problem. DEGREE Proj Technol [Internet]. 2016 [cited 2021 Feb 9];37. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-186364
Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks [Internet]. IEEE; [cited 2021 Feb 9]. p. 1942–8. Available from: http://ieeexplore.ieee.org/document/488968/
Irene SFH, Deris S, Mohd Hashim SZ. A combination of PSO and local search in university course timetabling problem. In: Proceedings - 2009 International Conference on Computer Engineering and Technology, ICCET 2009. 2009. p. 492–5.
Kanoh H, Chen S, H. Kanoh & SC. Particle swarm optimization with transition probability for timetabling problems. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) [Internet]. Springer, Berlin, Heidelberg; 2013 [cited 2021 Oct 17]. p. 256–65. Available from: https://link.springer.com/chapter/10.1007/978-3-642-37213-1_27
Adrianto D. Comparison Using Particle Swarm Optimization and Genetic Algorithm for Timetable Scheduling. 2014;
Et al. M. An Analysis on the Applicability of Meta-Heuristic Searching Techniques for Automated Test Data Generation in Automatic Programming Assessment. Baghdad Sci J. 2019 Jun 20;16(2(SI)):0515.
Ilyas R, Iqbal Z. Study of hybrid approaches used for university course timetable problem (UCTP). In: Proceedings of the 2015 10th IEEE Conference on Industrial Electronics and Applications, ICIEA 2015. Institute of Electrical and Electronics Engineers Inc.; 2015. p. 696–701.
Song T, Liu S, Tang X, Peng X, Chen M. An iterated local search algorithm for the University Course Timetabling Problem. Appl Soft Comput J. 2018 Jul 1;68:597–608.
Yasari P, Ranjbar M, Jamili N, Shaelaie MH. A two-stage stochastic programming approach for a multi-objective course timetabling problem with courses cancelation risk. Comput Ind Eng. 2019 Apr 1;130:650–60.
Goh SL, Kendall G, Sabar NR. Monte carlo tree search in finding feasible solutions for course timetabling problem. Int J Adv Sci Eng Inf Technol. 2019;9(6):1936–43.
Pillay N. A review of hyper-heuristics for educational timetabling. Ann Oper Res. 2016;