Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach
Main Article Content
Abstract
The university course timetable problem (UCTP) is typically a combinatorial optimization problem. Manually achieving a useful timetable requires many days of effort, and the results are still unsatisfactory. unsatisfactory. Various states of art methods (heuristic, meta-heuristic) are used to satisfactorily solve UCTP. However, these approaches typically represent the instance-specific solutions. The hyper-heuristic framework adequately addresses this complex problem. This research proposed Particle Swarm Optimizer-based Hyper Heuristic (HH PSO) to solve UCTP efficiently. PSO is used as a higher-level method that selects low-level heuristics (LLH) sequence which further generates an optimal solution. The proposed approach generates solutions into two phases (initial and improvement). A new LLH named “least possible rooms left” has been developed and proposed to schedule events. Both datasets of international timetabling competition (ITC) i.e., ITC 2002 and ITC 2007 are used to evaluate the proposed method. Experimental results indicate that the proposed low-level heuristic helps to schedule events at the initial stage. When compared with other LLH’s, the proposed LLH schedule more events for 14 and 15 data instances out of 24 and 20 data instances of ITC 2002 and ITC 2007, respectively. The experimental study shows that HH PSO gets a lower soft constraint violation rate on seven and six data instances of ITC 2007 and ITC 2002, respectively. This research has concluded the proposed LLH can get a feasible solution if prioritized.
Received 18/10/2021
Accepted 14/11/2021
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
References
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;