Top

Artificial Intelligence Review

Published in:

01-12-2015

A survey of Particle Swarm Optimization techniques for solving university Examination Timetabling Problem

Author: Souad Larabi Marie-Sainte

Published in: Artificial Intelligence Review | Issue 4/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The university Examination Timetabling Problem is one of the most important scheduling problems that numerous educational organizations have to find out a solution to manage their examinations by assigning these events to particular timeslots, rooms and/or invigilators. This problem is NP-complete due to the number of conflicting constraints that must be considered in the resolution. Particle Swarm Optimization (PSO) technique is a common intelligent method that has been successfully applied to many hard combinatorial optimization problems. The purpose of this paper is to expose a number of articles that appeared this last decade and used the PSO technique to solve the University examination timetabling problem. The overall techniques are described, focusing on the particle representation and updating. This research also offers insight into how well the PSO algorithm performs compared with other algorithms used to solve the same problem and datasets. Finally, a summary of the described algorithms and their most distinguishing features is presented in addition to future research directions.

previous article A systematic review of argumentation techniques for multi-agent systems research

next article A survey: deriving private information from perturbed data

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Aftab A, Mazhar A, Ahthasham S, Shah Bukhari AH (2011) Particle swarm based hyper-heuristic for tackling real world examinations scheduling problem. Aust J Basic Appl Sci 5(10):1406–1413

Aftab A, Li Z, (2010) Solving course timetabling problem using interrelated approach. In: IEEE international conference on granular computing. IEEE, San Jose, California, pp 651–655

Berro A, Larabi Marie-Sainte S, Ruiz-Gazen A (2010) Genetic algorithms and particle swarm optimization for exploratory projection pursuit. Ann Math Artif Intell J 60:153–178MathSciNetCrossRefMATH

Burke EK, Elliman DG, Ford PH, Weare RF (1996) examination timetabling in British universities: a survey In: Burke EK and Ross P (eds) 1st international conference on practice and theory of automated timetabling. Lecture Notes in Computer Science, vol 1153, pp 76–90

Burke EK, Kingston JH, deWerra D (2004) Applications to timetabling. In: Gross J, Yellen J (eds) The handbook of graph theory. Chapman Hall/CRC Press, Boca Raton, pp 445–474

Burke EK, De Causmaecker P, Vanden Berghe G, Van Landeghem H (2004) The state of the art of nurse rostering. J Sched 7(6):441–499MathSciNetCrossRefMATH

Burke EK, Newall JP (2004) Solving examination timetabling problems through adaptation of heuristic orderings. Ann Oper Res 129:107–134MathSciNetCrossRefMATH

Burke EK, Petrovic S (2002) Recent research directions in automated timetabling. Eur J Oper Res 140(2):266–280CrossRefMATH

Carter MW, Laporte G (1996) Recent developments in practical examination timetabling In: Burke EK and Ross P (eds) In: 1st international conference on practice and theory of automated timetabling. Lecture Notes in Computer Science, vol 1153, pp 3–21

Carter MW (1986) A survey of practical applications of examination timetabling algorithms. J Oper Res 34(2):193–202CrossRef

Carter MW, Laporte G (1996) Examination timetabling: algorithmic strategies and applications. J Oper Res Soc 47:373–383CrossRef

Chu SC, Chen YT, Ho JH (2006) Timetable scheduling using particle swarm optimization. In: Proceeddings of the 1st international conference on innovation computing, information and control, vol 3. IEEE Computer Society, Washington, DC, pp 324–327

Clerc M (2006) Particle swarm optimization. International Scientific and Technical Encyclopaedia Wiley, HobokenCrossRefMATH

Di Gaspero L, Schaerf A (2001) Tabu search techniques for examination timetabling. In: Burke EK, Erben E (eds) 3rd international conference on practice and theory of automated timetabling. Springer, Berlin, pp 104–117CrossRef

Easton K, Nemhauser G, Trick M (2004) Sports scheduling. In: Leung J (ed) Handbook of scheduling, algorithms, models, and performance analysis, Chap 52. CRC Press, Boca Raton

Fealko RD (2005) Evaluating particle swarm intelligence techniques for solving university examination timetabling problems. Ph.D Dissertation, Graduate School of Computer and Information Sciences, Nova Southeastern University, Country

Hosney M, Shaameem F (2011) A survey of genetic algorithms for the university timetabling problem. In: International conference on future information technology, IPCSIT, vol 13. IACSIT Press, Singapore

Jordehi AR, Jasni J (2015) Particle swarm optimisation for discrete optimisation problems: a review. Artif Intell Rev 43:243258

Kennedy J, Eberhart R (2005) Particle swarm optimization. In: IEEE conference on neural networks (Perth, Australia), NJ, IV, pp 1942–1948

Kolasa T, Krol D (2011) A survey of algorithms for paper-reviewer assignment problem. IETE Tech Rev 28:123–134CrossRef

Leake DB (1996) Case based reasoning: experiences, lessons, and future directions. AAAI Press/MIT Press, Cambridge

Lewis R (2008) A survey of metaheuristic-based techniques for university timetabling problems. OR Spectr J 30:167–190CrossRefMATH

McCollum BGC (2007) A perspective on bridging the gap between theory and practice in university timetabling. In: Burke EK and Rudova H (eds) 6th international conference on practice and theory of automated timetabling. Lecture Notes in Computer Science, vol 3867, pp 3–23

Mehta NK (1982) A computer-based examination management system. J Educ Technol Syst 11:185–198CrossRef

Montero E, Riff MC, Altamirano L (2011) A PSO algorithm to solve a real course+examination timetabling problem. In: International conference on swarm intelligence, ICSI, Cergy, France, pp 24-1–24-8

Morteza Alinia A, Vaki Baghmisheh MT, Badamchi Zadeh MA, Ghaemi S (2012) Hybrid particle swarm optimization transplanted into a hyper-heuristic structure for solving examination timetabling problem. Swarm Evol Comput J 7:21–34CrossRef

Pan Q-K, Tasgetiren MF, Liang Y-C (2008) A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Comput Oper Res 35:2807–2839MathSciNetCrossRefMATH

Qu R, Burke EK, McCollum B, Merlot LGT, Lee SY (2009) A survey of search methodologies and automated system development for examination timetabling. J Sched 12(1):5589MathSciNetCrossRef

Sandeep Rana R, Sanjay Jasola J, Rajesh K (2011) A review on particle swarm optimization algorithms and their applications to data clustering. Artif Intell Rev 35:211–222CrossRef

Schaerf A, Di Gaspero L (2007) Measurability and reproducibility in university timetabling research: discussion and proposals. In: Burke EK and Rudova H (eds) 6th international conference on practice and theory of automated timetabling. Lecture Notes in Computer Science, vol 3867, pp 40–49

Simonis H (1995) The CHIP system and its applications In: First international conference on principles and practice of constraint programming. Lecture Notes in Computer Science, vol 976, pp 643–646

Xianfeng Y, ShengLi L (2014) Dynamic adjustment strategies of inertia weight in particle swarm optimization algorithm. Int J Control Autom 7(5):353–364CrossRef

Title: A survey of Particle Swarm Optimization techniques for solving university Examination Timetabling Problem
Author: Souad Larabi Marie-Sainte
Publication date: 01-12-2015
Publisher: Springer Netherlands
Published in: Artificial Intelligence Review / Issue 4/2015
Print ISSN: 0269-2821
Electronic ISSN: 1573-7462
DOI: https://doi.org/10.1007/s10462-015-9437-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2015

Recommender systems in e-learning environments: a survey of the state-of-the-art and possible extensions

A survey: deriving private information from perturbed data

Dealing with the evaluation of supervised classification algorithms

Learning content design and learner adaptation for adaptive e-learning environment: a survey

A systematic review of argumentation techniques for multi-agent systems research

Premium Partner