Hybrid particle swarm optimization with particle elimination for the high school timetabling problem | Evolutionary Intelligence
Skip to main content
Springer Nature Link
Log in

Hybrid particle swarm optimization with particle elimination for the high school timetabling problem

  • Research Paper
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

Abstract

In this paper, a PSO-based algorithm that hybridized Particle Swarm Optimization (PSO) and Hill Climbing (HC) is applied to high school timetabling problem. This hybrid has two features, a novel solution transformation and particle elimination. The proposed methodologies are tested on the XHSTT-2014 dataset (which is relatively new for the school timetabling problem) plus other additional instances. The experimental results show that the proposed algorithm is effective in solving small and medium instances compared to standalone HC and better than the conventional PSO for most instances. In a comparison to the state of the art methods, it achieved the lowest mean of soft constraint violations for 7 instances and the lowest mean of hard constraint violations for 1 instance.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. http://www.it.usyd.edu.au/ jeff/cgi-bin/hseval.cgi.

  2. https://www.utwente.nl/en/eemcs/dmmp/hstt/.

References

  1. Al-Betar MA (2017) $\beta $-Hill climbing: an exploratory local search. Neural Comput Appl 28(s1):153–168. https://doi.org/10.1007/s00521-016-2328-2

    Article  Google Scholar 

  2. Arora S, Barak B (2009) Computational complexity—modern approach. Cambridge University Press. http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264

  3. Burke EK, Kendall G et al (2005) Search methodologies. Springer, Berlin

    Book  Google Scholar 

  4. Ceschia S, Dang N, De Causmaecker P, Haspeslagh S, Schaerf A (2019) The second international nurse rostering competition. Ann Oper Res 274(1–2):171–186

    Article  MathSciNet  Google Scholar 

  5. Du KL, Swamy MNS (2016) Search and optimization by metaheuristics. Springer, Berlin. https://doi.org/10.1007/978-3-319-41192-7

    Book  MATH  Google Scholar 

  6. Feng Z, Chen L, Chen CH, Liu M, Yuan M (2020) Motion planning for redundant robotic manipulators using a novel multi-group particle swarm optimization. Evol Intel. https://doi.org/10.1007/s12065-020-00382-z

    Article  Google Scholar 

  7. Fonseca GH, Santos HG, Carrano EG, Stidsen TJ (2017) Integer programming techniques for educational timetabling. Eur J Oper Res 262(1):28–39. https://doi.org/10.1016/j.ejor.2017.03.020

    Article  MathSciNet  MATH  Google Scholar 

  8. Fonseca GHG, Santos HG, Carrano EG (2016) Integrating matheuristics and metaheuristics for timetabling. Comput Oper Res 74:108–117

    Article  MathSciNet  Google Scholar 

  9. Fonseca GHG, Santos HG, Carrano EG (2016) Late acceptance hill-climbing for high school timetabling. J Sched 19(4):453–465. https://doi.org/10.1007/s10951-015-0458-5

    Article  MathSciNet  MATH  Google Scholar 

  10. da Fonseca GHG, Santos HG, Toffolo TÂM, Brito SS, Souza MJF (2016) GOAL solver: a hybrid local search based solver for high school timetabling. Ann Oper Res 239(1):77–97. https://doi.org/10.1007/s10479-014-1685-4

    Article  MathSciNet  MATH  Google Scholar 

  11. Goh SL, Kendall G, Sabar NR (2017) Improved local search approaches to solve the post enrolment course timetabling problem. Eur J Oper Res 261(1):17–29. https://doi.org/10.1016/j.ejor.2017.01.040

    Article  MathSciNet  MATH  Google Scholar 

  12. Goh SL, Kendall G, Sabar NR (2018) Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem. J Oper Res Soc 70(6):873–888. https://doi.org/10.1080/01605682.2018.1468862

    Article  Google Scholar 

  13. Goh SL, Kendall G, Sabar NR (2019) Monte carlo tree search in finding feasible solutions for course timetabling problem. Int J Adv Sci Eng Inf Technol 9(6):1936. https://doi.org/10.18517/ijaseit.9.6.10224

    Article  Google Scholar 

  14. Goh SL, Kendall G, Sabar NR, Abdullah S (2020) An effective hybrid local search approach for the post enrolment course timetabling problem. OPSEARCH. https://doi.org/10.1007/s12597-020-00444-x

    Article  MATH  Google Scholar 

  15. Kingston JH (2014) KHE14: An algorithm for high school timetabling. In: Proceedings of the tenth international conference on practice and theory of automated timetabling, 269–291. http://www.it.usyd.edu.au/~jeff/khe/khe14.pdf

  16. Kingston JH (2014) Timetable construction: the algorithms and complexity perspective. Ann Oper Res 218(1):249–259

    Article  MathSciNet  Google Scholar 

  17. Kristiansen S, Sørensen M, Stidsen TR (2015) Integer programming for the generalized high school timetabling problem. J Sched 18(4):377–392. https://doi.org/10.1007/s10951-014-0405-x

    Article  MathSciNet  MATH  Google Scholar 

  18. Vinay Kumar SB, Rao PV, Singh MK (2019) Optimal floor planning in VLSI using improved adaptive particle swarm optimization. Evol Intel. https://doi.org/10.1007/s12065-019-00256-z

    Article  Google Scholar 

  19. Post G, Ahmadi S, Daskalaki S, Kingston JH, Kyngas J, Nurmi C, Ranson D (2012) An XML format for benchmarks in high school timetabling. Ann Oper Res 194(1):385–397. https://doi.org/10.1007/s10479-010-0699-9

    Article  MATH  Google Scholar 

  20. Post G, Kingston JH, Ahmadi S, Daskalaki S, Gogos C, Kyngas J, Nurmi C, Musliu N, Pillay N, Santos H, Schaerf A (2014) XHSTT: an XML archive for high school timetabling problems in different countries. Ann Oper Res 218(1):295–301

    Article  MathSciNet  Google Scholar 

  21. Post G, Di Gaspero L, Kingston JH, McCollum B, Schaerf A (2016) The third international timetabling competition. Ann Oper Res 239(1):69–75. https://doi.org/10.1007/s10479-013-1340-5

    Article  MathSciNet  MATH  Google Scholar 

  22. Qu R, Burke EK, McCollum B, Merlot LTG, Lee SY (2009) A survey of search methodologies and automated system development for examination timetabling. J Sched 12(1):55–89

    Article  MathSciNet  Google Scholar 

  23. Sanders WL, Wright SP, Horn SP (1997) Teacher and classroom context effects on student achievement: implications for teacher evaluation. J Pers Eval Educ 11(1):57–67

    Article  Google Scholar 

  24. Schöbel A (2017) An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transp Res Part C Emerg Technol 74:348–365

    Article  Google Scholar 

  25. Tassopoulos IX, Beligiannis GN (2012) A hybrid particle swarm optimization based algorithm for high school timetabling problems. Appl Soft Comput 12(11):3472–3489

    Article  Google Scholar 

  26. Tassopoulos IX, Beligiannis GN (2012) Using particle swarm optimization to solve effectively the school timetabling problem. Soft Comput 16(7):1229–1252. https://doi.org/10.1007/s00500-012-0809-5

    Article  Google Scholar 

  27. Yi X, Goossens D, Nobibon FT (2020) Proactive and reactive strategies for football league timetabling. Eur J Oper Res 282(2):772–785

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Optimization Research Group, Faculty of Computing and Informatics, Universiti Malaysia Sabah, Sabah, Malaysia

    Joo Siang Tan, Say Leng Goh & Suaini Sura

  2. The University of Nottingham Malaysia Campus, Jalan Broga, 43500, Semenyih, Selangor Darul Ehsan, Malaysia

    Graham Kendall

  3. The University of Nottingham, University Park, Nottingham, NG7 2RD, UK

    Graham Kendall

  4. Department of Computer Science and Information Technology, La Trobe University, Melbourne, Australia

    Nasser R. Sabar

Authors
  1. Joo Siang Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Say Leng Goh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Suaini Sura
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Graham Kendall
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Nasser R. Sabar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Say Leng Goh.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tan, J.S., Goh, S.L., Sura, S. et al. Hybrid particle swarm optimization with particle elimination for the high school timetabling problem. Evol. Intel. 14, 1915–1930 (2021). https://doi.org/10.1007/s12065-020-00473-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-020-00473-x

Keywords

Search

Navigation