[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Population based Local Search for university course timetabling problems

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Population based algorithms are generally better at exploring a search space than local search algorithms (i.e. searches based on a single heuristic). However, the limitation of many population based algorithms is in exploiting the search space. We propose a population based Local Search (PB-LS) heuristic that is embedded within a local search algorithm (as a mechanism to exploit the search space). PB-LS employs two operators. The first is applied to a single solution to determine the force between the incumbent solution and the trial current solution (i.e. a single direction force), whilst the second operator is applied to all solutions to determine the force in all directions. The progress of the search is governed by these forces, either in a single direction or in all directions. Our proposed algorithm is able to both diversify and intensify the search more effectively, when compared to other local search and population based algorithms. We use university course timetabling (Socha benchmark datasets) as a test domain. In order to evaluate the effectiveness of PB-LS, we perform a comparison between the performances of PB-LS with other approaches drawn from the scientific literature. Results demonstrate that PB-LS is able to produce statistically significantly higher quality solutions, outperforming many other approaches on the Socha dataset.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Explore related subjects

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

References

  1. Petrovic S, Burke E (2004) Educational timetabling. In: Handbook of scheduling: algorithms, models, and performance analysis, pp 41–45

    Google Scholar 

  2. Schaerf A (1999) A survey of automated timetabling. Artif Intell Rev 13(2):87–127

    Article  Google Scholar 

  3. Burke E, Bykov Y, Newall J, Petrovic S (2003) A time-predefined approach to course timetabling. Yugosl J Oper Res 13(2):139–151. ISSN: 0354-0243, EISSN: 2334-6043

    Article  MATH  Google Scholar 

  4. Elmohamed MS, Coddington P, Fox G (1998) A comparison of annealing techniques for academic course scheduling. In: Practice and theory of automated timetabling II. Springer, Berlin, pp 92–112

    Chapter  Google Scholar 

  5. Costa D (1994) A tabu search algorithm for computing an operational timetable. Eur J Oper Res 76(1):98–110

    Article  MATH  Google Scholar 

  6. Schaerf A (1999) Local search techniques for large high school timetabling problems. IEEE Trans Syst Man Cybern, Part A, Syst Hum 29(4):368–377

    Article  Google Scholar 

  7. Sabar NR, Ayob M, Kendall G, Qu R (2012) A honey-bee mating optimization algorithm for educational timetabling problems. Eur J Oper Res 216(3):533–543

    Article  MathSciNet  Google Scholar 

  8. Ayvaz D, Topcuoglu H, Gurgen F (2012) Performance evaluation of evolutionary heuristics in dynamic environments. Appl Intell 37(1):130–144. doi:10.1007/s10489-011-0317-9

    Article  Google Scholar 

  9. Lwin K, Qu R (2013) A hybrid algorithm for constrained portfolio selection problems. Appl Intell. doi:10.1007/s10489-012-0411-7, pp 1–16

    Google Scholar 

  10. Rajabalipour Cheshmehgaz H, Desa M, Wibowo A (2013) Effective local evolutionary searches distributed on an island model solving bi-objective optimization problems. Appl Intell 38(3):331–356. doi:10.1007/s10489-012-0375-7

    Article  Google Scholar 

  11. Abuhamdah A, Ayob M (2010) Adaptive randomized descent algorithm for solving course timetabling problems. Int J Phys Sci 5(16):2516–2522

    Google Scholar 

  12. Abuhamdah A, Ayob M (2009) Multi-neighbourhood particle collision algorithm for solving course timetabling problems. In: 2nd conference on data mining and optimization, 2009. DMO’09. IEEE Press, New York, 21–27

    Chapter  Google Scholar 

  13. Abuhamdah A, Ayob M (2011) MPCA-ARDA for solving course timetabling problems. In: 3rd conference on data mining and optimization (DMO). IEEE Press, New York, pp 171–177

    Chapter  Google Scholar 

  14. Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv 35(3):268–308

    Article  Google Scholar 

  15. Webster BL (2004) Solving combinatorial optimization problems using a new algorithm based on gravitational attraction. PhD thesis, College of Engineering at Florida Institute of Technology

  16. Burke EK, Hyde M, Kendall G, Ochoa G, Özcan E, Woodward JR (2010) A classification of hyper-heuristic approaches. In: Handbook of metaheuristics. Springer, Berlin, pp 449–468

    Chapter  Google Scholar 

  17. Burke EK, Hyde MR, Kendall G (2012) Grammatical evolution of local search heuristics. IEEE Trans Evol Comput 16(3):406–417

    Article  Google Scholar 

  18. Ren Z, Jiang H, Xuan J, Luo Z (2012) Hyper-heuristics with low level parameter adaptation. Evol Comput 20(2):189–227

    Article  Google Scholar 

  19. Sabar N, Ayob M, Qu R, Kendall G (2012) A graph coloring constructive hyper-heuristic for examination timetabling problems. Appl Intell 37(1):1–11. doi:10.1007/s10489-011-0309-9

    Article  Google Scholar 

  20. Soghier A, Qu R (2013) Adaptive selection of heuristics for assigning time slots and rooms in exam timetables. Appl Intell. doi:10.1007/s10489-013-0422-z

    Google Scholar 

  21. Socha K, Knowles J, Sampels M (2002) A max-min ant system for the university course timetabling problem. In: Ant algorithms. Springer, Berlin, pp 1–13

    Chapter  Google Scholar 

  22. Socha K, Sampels M, Manfrin M (2003) Ant algorithms for the university course timetabling problem with regard to the state-of-the-art. In: Applications of evolutionary computing. Springer, Berlin, pp 334–345

    Chapter  Google Scholar 

  23. Chiarandini M, Birattari M, Socha K, Rossi-Doria O (2006) An effective hybrid algorithm for university course timetabling. J Sched 9(5):403–432

    Article  MATH  MathSciNet  Google Scholar 

  24. Mcmullan P (2007) An extended implementation of the great deluge algorithm for course timetabling. In: Computational science—ICCS 2007. Springer, Berlin, pp 538–545

    Chapter  Google Scholar 

  25. Landa-Silva D, Obit JH (2008) Great deluge with non-linear decay rate for solving course timetabling problems. In: 4th international IEEE conference intelligent systems, 2008. IS’08. IEEE Press, New York, pp 8-11–8-18

    Google Scholar 

  26. Abbasian R, Mouhoub M (2013) A hierarchical parallel genetic approach for the graph coloring problem. Appl Intell. doi:10.1007/s10489-013-0429-5, pp 1–19

    Google Scholar 

  27. Abdullah S (2006) Heuristic approaches for university timetabling problems. PhD thesis, School of Computer Science, The University of Nottingham

  28. Thompson JM, Dowsland KA (1996) Variants of simulated annealing for the examination timetabling problem. Ann Oper Res 63(1):105–128

    Article  MATH  Google Scholar 

  29. Hoos HH, Stützle T (2004) In: Stochastic local search: foundations & applications. The Morgan Kaufmann series in artificial intelligence

    Google Scholar 

  30. Turabieh H, Abdullah S, McCollum B, McMullan P (2010) Fish swarm intelligent algorithm for the course timetabling problem. In: Rough set and knowledge technology. Springer, Berlin, pp 588–595

    Chapter  Google Scholar 

  31. Turabieh H, Abdullah S (2009) Incorporating tabu search into memetic approach for enrolment-based course timetabling problems. In: 2nd conference on data mining and optimization, 2009. DMO’09. IEEE Press, New York, pp 115–119

    Chapter  Google Scholar 

  32. Abdullah S, Burke EK, Mccollum B (2005) An investigation of variable neighbourhood search for university course timetabling. In: The 2nd multidisciplinary international conference on scheduling: theory and applications (MISTA), pp 413–427

    Google Scholar 

  33. Abdullah S, Turabieh H (2009) Electromagnetic like mechanism and great deluge for course timetabling problems. Paper presented at the first 2008 seminar on data mining and optimization DMO

  34. Abdullah S, Burke EK, McCollum B (2007) A hybrid evolutionary approach to the university course timetabling problem. In: IEEE Congress on evolutionary computation, 2007. CEC. IEEE Press, New York, pp 1764–1768.

    Chapter  Google Scholar 

  35. Ejaz N, Javed MY (2007) A hybrid approach for course scheduling inspired by die-hard co-operative ant behavior. In: 2007 IEEE international conference on automation and logistics, 2007. IEEE Press, New York, pp 3095–3100

    Chapter  Google Scholar 

  36. Asmuni H, Burke EK, Garibaldi JM (2005) Fuzzy multiple heuristic ordering for course timetabling. In: Proceedings of the 5th United Kingdom workshop on computational intelligence (UKCI 2005), pp 302–309. Citeseer

    Google Scholar 

  37. Abdullah S, Turabieh H (2008) Generating university course timetable using genetic algorithms and local search. In: Third international conference on convergence and hybrid information technology, 2008. ICCIT’08. IEEE Press, New York, pp 254–260

    Chapter  Google Scholar 

  38. Abdullah S, Burke EK, McCollum B (2007) Using a randomised iterative improvement algorithm with composite neighbourhood structures for the university course timetabling problem. In: Metaheuristics. Springer, Berlin, pp 153–169

    Chapter  Google Scholar 

  39. Burke EK, McCollum B, Meisels A, Petrovic S, Qu R (2007) A graph-based hyper-heuristic for educational timetabling problems. Eur J Oper Res 176(1):177–192

    Article  MATH  MathSciNet  Google Scholar 

  40. Burke EK, Kendall G, Soubeiga E (2003) A tabu-search hyperheuristic for timetabling and rostering. J Heuristics 9(6):451–470

    Article  Google Scholar 

  41. Al-Betar MA, Khader AT, Gani TA (2008) A harmony search algorithm for university course timetabling. In: 7th international conference on the practice and theory of automated timetabling (PATAT 2008), Montreal, Canada, August 18–22.

    Google Scholar 

  42. Landa-Silva D, Obit JH (2009) Evolutionary non-linear great deluge for university course timetabling. In: Hybrid artificial intelligence systems. Springer, Berlin, pp 269–276

    Chapter  Google Scholar 

  43. Obit J, Landa-Silva D, Ouelhadj D, Sevaux M (2009) Non-linear great deluge with learning mechanism for solving the course timetabling problem. In: MIC 2009: the VIII metaheuristics international conference, Hamburg, Germany, pp 1–10

    Google Scholar 

  44. Al-Betar MA, Khader AT, Liao IY (2010) A harmony search with multi-pitch adjusting rate for the university course timetabling. In: Recent advances in harmony search algorithm. Springer, Berlin, pp 147–161

    Chapter  Google Scholar 

  45. Jaradat GM, Ayob M (2010) An elitist-ant system for solving the post-enrolment course timetabling problem. In: Database theory and application, bio-science and bio-technology. Springer, Berlin, pp 167–176

    Chapter  Google Scholar 

  46. Shaker K, Abdullah S (2010) Controlling multi algorithms using round robin for university course timetabling problem. In: Database theory and application, bio-science and bio-technology. Springer, Berlin, pp 47–55

    Chapter  Google Scholar 

  47. García S, Fernández A, Luengo J, Herrera F (2010) Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: experimental analysis of power. Inf Sci 180(10):2044–2064

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, College of Computer Science and Engineering, Taibah University, 41411, Madinah, Kingdom of Saudi Arabia

    Anmar Abuhamdah

  2. Data Mining and Optimisation Research Group (DMO), Center for Artificial Intelligence Technology, Universiti Kebangsaan Malaysia, 43600, Bangi, Selangor, Malaysia

    Anmar Abuhamdah, Masri Ayob & Nasser R. Sabar

  3. ASAP Research Group, School of Computer Science, The University of Nottingham, Nottingham, NG8 1BB, UK

    Graham Kendall

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

    Graham Kendall

Authors
  1. Anmar Abuhamdah
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Masri Ayob
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Graham Kendall
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nasser R. Sabar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nasser R. Sabar.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Abuhamdah, A., Ayob, M., Kendall, G. et al. Population based Local Search for university course timetabling problems. Appl Intell 40, 44–53 (2014). https://doi.org/10.1007/s10489-013-0444-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-013-0444-6

Keywords

Search

Navigation