Top

Soft Computing

Published in:

01-07-2012 | Original Paper

Using particle swarm optimization to solve effectively the school timetabling problem

Authors: Ioannis X. Tassopoulos, Grigorios N. Beligiannis

Published in: Soft Computing | Issue 7/2012

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

search-config

AI-assisted search

Off

Abstract

A new hybrid adaptive algorithm based on particle swarm optimization (PSO) is designed, developed and applied to the high school timetabling problem. The proposed PSO algorithm is used to create feasible and efficient timetables for high schools in Greece. Experiments with real-world data coming from different high schools have been conducted to show the efficiency of the proposed PSO algorithm. As well as that, the algorithm has been compared with four other effective techniques found in the literature to demonstrate its efficiency and superior performance. In order to have a fair comparison with these algorithms, we decided to use the exact same input instances used by these algorithms. The proposed PSO algorithm outperforms, in most cases, other existing attempts to solve the same problem as shown by experimental results.

previous article Separation axioms in (semi)topological quotient BL-algebras

next article Control and synchronization of chaotic systems using a novel indirect model reference fuzzy controller

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

Aladag CH, Hocaoglu G, Basaran MA (2009) The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem. Expert Syst Appl 36(10):12349–12356CrossRef

AlRashidi MR, El-Hawary ME (2009) A survey of particle swarm optimization applications in electric power systems. IEEE Trans Evol Comput 13(4):913–918CrossRef

Beligiannis GN, Moschopoulos CN, Kaperonis GP, Likothanassis SD (2008) Applying evolutionary computation to the school timetabling problem: the Greek case. Comput Oper Res 35(4):1265–1280MATHCrossRef

Beligiannis GN, Moschopoulos CN, Likothanassis SD (2009) A genetic algorithm approach to school timetabling. J Oper Res Soc 60(1):23–42MATHCrossRef

Bilgin B, Özcan E, Korkmaz EE (2006) An experimental study on hyper-heuristics and exam timetabling. In: Proceedings of the 6th international conference on the practice and theory of automated timetabling, pp 123–140

Brodersen OB (2008) Eignung schwarmintelligenter Verfahren für die betriebliche Entscheidungsunterstützung. Cuvillier (in German)

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

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

Burke E, Bykov Y, Petrovic S (2001) A multicriteria approach to examination timetabling. Lecture Notes in Computer Science, vol 2079. Springer, Berlin, pp 118–131

Burke EK, MacCarthy B, Petrovic S, Qu R (2001). Case-based reasoning in course timetabling: an attribute graph approach. Lecture Notes in Computer Science, vol 2080. Springer, Berlin, pp 90–104

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

Burke E, Bykov Y, Newall J, Petrovic S (2004) A time-predefined local search approach to exam timetabling problems. IIE Trans 36(6):509–528CrossRef

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:177–192MathSciNetMATHCrossRef

Burke EK, Mareček J, Parkes AJ, Rudová H (2010) Decomposition, reformulation, and diving in university course timetabling. Comput Oper Res 37(3):582–597MathSciNetMATHCrossRef

Cambazard H, Demazeau F, Jussien N, David P (2005) Interactively solving school timetabling problems using extensions of constraint programming. Lecture Notes in Computer Science, vol 3616. Springer, Berlin, pp 190–207

Chatterjee A, Siarry P (2006) Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization. Comput Oper Res 33:859–871MATHCrossRef

Chu S-C, Chen Y-T, Ho J-H (2006) Timetable scheduling using particle swarm optimization. In: Proceedings of the 1st international conference on innovative computing, information and control, pp 324–327

Coelho JP, de Moura Oliveira PB, Boaventura Cunha J (2005) Greenhouse air temperature predictive control using the particle swarm optimisation algorithm. Comput Electron Agric 49:330–344CrossRef

De Falco I, Della Cioppa A, Tarantino E (2007) Facing classification problems with particle swarm optimization. Appl Soft Comput 7:652–658CrossRef

De Haan P, Landman R, Post G, Ruizenaar H (2006) A four-phase approach to a timetabling problem in secondary schools. In: Proceedings of the 6th international conference on the practice and theory of automated timetabling, pp 423–425

Di Gaspero L, Schaerf A (2001) Tabu search techniques for examination timetabling. Lecture Notes in Computer Science, vol 2079. Springer, Berlin, pp 104–117

Günther M (2010) Hochflexibles Workforce Management. Herausforderungen und Lösungsverfahren, Dissertation, TU Ilmenau (in German)

Günther M, Nissen V (2009) A comparison of neighbourhood topologies for staff scheduling with particle swarm optimisation. In: Mertsching B, Marcus H, Aziz Z (Hrsg): KI 2009: advances in artificial intelligence, 32nd annual conference on AI, 15–18 Sept., Paderborn, LNAI 5803. Springer, Berlin, pp 185–192

Jacobsen F, Bortfeldt A, Gehring H (2006) Timetabling at German secondary schools: tabu search versus constraint programming. In: Proceedings of the 6th international conference on the practice and theory of automated timetabling, pp 439–442

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks IV, pp 1942–1948

Kennedy J, Eberhart RC, Shi Y (2001) Swarm intelligence. Morgan Kaufmann Publishers, San Francisco

Kingston JH (2004) A tiling algorithm for high school timetabling. In: Proceedings of the 5th international conference on practice and theory of automated timetabling, pp 233–249

Kingston JH (2006) The KTS high school timetabling system. In: Proceedings of the 6th international conference on the practice and theory of automated timetabling, pp 181–195

McCollum B (2006) University timetabling: bridging the gap between research and practice. In: Proceedings of the 6th international conference on the practice and theory of automated timetabling, pp 15–35

Nedjah N, de Macedo Mourelle L (2004) Evolutionary time scheduling. In: Proceedings of the international conference on information technology, coding and computing (ITCC’04), vol 2, pp 357–361

Nissen V, Günther M, Schumann R (2011) Integrated generation of working time models and staff schedules in workforce management. In: Di Chio C (Hrsg.): Proceedings Evoapplications, 27.-29. Apr., Torino, LNCS 6625, 2. Springer, Berlin, pp 491–500

Papoutsis K, Valouxis C, Housos E (2003) A column generation approach for the timetabling problem of greek high schools. J Oper Res Soc 54(3):230–238MATHCrossRef

Petrovic S, Yang Y, Dror M (2007) Case-based selection of initialisation heuristics for metaheuristic examination timetabling. Expert Syst Appl 33(3):772–785CrossRef

Poli R (2008) Analysis of the publications on the applications of particle swarm optimisation. J Artif Evol Appl 2008:1–10

Qarouni-Fard D, Najafi-Ardabili A, Moeinzadeh M-H (2007) Finding feasible timetables with particle swarm optimization. In: Proceedings of the 4th international conference on innovations in information technology, pp 387–391

Qu R, Burke E, McCollum B, Merlot L, Lee S (2006) A survey of search methodologies and automated approaches for examination timetabling, Technical Report No. NOTTCS-TR-2006-4, School of Computer Science and IT, University of Nottingham

Ross P, Hart E, Corne D (2003) Genetic algorithms and timetabling. Natural computing series, advances in evolutionary computing: theory and applications, pp 755–777

Rossi-Doria O, Sampels M, Birattari M, Chiarandini M, Dorigo M, Gambardella LM et al (2003) A comparison of the performance of different metaheuristics on the timetabling problem. Lecture Notes in Computer Science, vol 2740. Springer, Berlin, pp 329–351

Rudova H, Murray K (2003) University course timetabling with soft constraints. Lecture Notes in Computer Science, vol 2740. Springer, Berlin, pp 310–328

Schaerf A, Meisels A (2000) Solving employee timetabling problems by generalized local search. Lecture Notes in Computer Science, vol 1792. Springer, Berlin, pp 380–389

Smith KA, Abramson D, Duke D (2003) Hopfield neural networks for timetabling: formulations, methods, and comparative results. Comput Ind Eng 44(2):283–305CrossRef

Socha K, Knowles J, Sampels M (2002) A MAX–MIN ant system for the university course timetabling problem. Lecture Notes in Computer Science, vol 2463. Springer, Berlin, pp 1–13

Ten Eikelder HMM, Willemen RJ (2001). Some complexity aspects of secondary school timetabling problems. Lecture Notes in Computer Science, vol 2079. Springer, Berlin, pp 18–27

Trick MA (2001) A schedule-then-break approach to sports timetabling. Lecture Notes in Computer Science, vol 2079. Springer, Berlin, pp 242–253

Valouxis C, Housos E (2003) Constraint programming approach for school timetabling. Comput Oper Res 30(10):1555–1572MATHCrossRef

Wang Y-Z (2003) Using genetic algorithm methods to solve course scheduling problems. Expert Syst Appl 25(1):39–50CrossRef

Wren A (1996) Scheduling, timetabling and rostering: a special relationship? Lecture Notes in Computer Science, vol 1153. Springer, Berlin, pp 46–75

Xinchao Z (2010) A perturbed particle swarm algorithm for numerical optimization. Appl Soft Comput 10(1):119–124CrossRef

Title: Using particle swarm optimization to solve effectively the school timetabling problem
Authors: Ioannis X. Tassopoulos
Grigorios N. Beligiannis
Publication date: 01-07-2012
Publisher: Springer-Verlag
Published in: Soft Computing / Issue 7/2012
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-012-0809-5

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 7/2012

Fuzzy ontologies-based user profiles applied to enhance e-learning activities

Decision making with a fuzzy ontology

Very true operators in effect algebras

Control and synchronization of chaotic systems using a novel indirect model reference fuzzy controller

OWL-FC: an upper ontology for semantic modeling of Fuzzy Control

Separation axioms in (semi)topological quotient BL-algebras

Premium Partner