Back to search

University of Patras

Σχεδίαση, ανάπτυξη και εφαρμογή αλγορίθμων υπολογιστικής νοημοσύνης σε προβλήματα εύρεσης βέλτιστου ωρολογίου προγράμματος σε σχολεία δευτεροβάθμιας εκπαίδευσης (school timetabling) και χρονοπρογραμματισμού (scheduling)

Abstract

dc:description

The main topic of this thesis is the design and implementation of algorithms forsolving the school timetabling problem in a feasible and efficient way. In particular,focus is given in the well-known Particle Swarm Optimization (PSO) algorithm, whichis modified so as to fit the specific aspects of the problem’s discrete space, while enrichedwith novel ideas and techniques.It is known, for several decades, that the timetabling problems, in their generalform, belong to the NP–Hard class. Consequently, finding an exact algorithm for solvingtimetabling problems in an affordable amount of time is rather impossible whenthe size of these problems is of a great magnitude. When facing such a situation, onealternative resolution is implementing Computational Intelligence which is able to producenear optimal solutions in a reasonable amount of time by employing the set ofalgorithms it includes. Therefore, the first chapter is devoted to the hard problems ingeneral and the definition of Computational Intelligence. The second chapter dealswith the timetabling problem as it appears in the Academic world: the Exam Timetablingand University Course Timetabling. The third chapter focuses exclusively on theschool timetabling problem in detail. The fourth chapter states the description of theParticle Swarm Optimization (PSO) algorithm. The fifth chapter presents the characteristicsof the instances used for benchmarking the developed algorithms. These instancesrepresent real life situations of the Greek high school actuality. In addition, atthis chapter a novel technique based on Mixed Integer Programming is introduced inorder to either optimally solve or produce lower bounds for the aforementioned instances.In the sixth chapter, three novel algorithms are proposed for solving theschool timetabling problem. In the seventh and final chapter, the performance of the novel algorithms is studied while some open issues and directions for farther researchare introduced. The easy and simple conclusion of this thesis is that Particle SwarmOptimization (PSO), which is applied for the first time, is an excellent and promisingalternative in solving the school timetabling problem.

Degree

thesis:*
Grantor dc:publisher
University of Patras
Year dc:date
2016

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Τασσόπουλος, Ιωάννης
  • Tassopoulos, Ioannis

Subjects

dc:subject × 18

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/43898

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Τασσόπουλος, Ιωάννης; Tassopoulos, Ioannis. Σχεδίαση, ανάπτυξη και εφαρμογή αλγορίθμων υπολογιστικής νοημοσύνης σε προβλήματα εύρεσης βέλτιστου ωρολογίου προγράμματος σε σχολεία δευτεροβάθμιας εκπαίδευσης (school timetabling) και χρονοπρογραμματισμού (scheduling). University of Patras, 2016. http://hdl.handle.net/10442/hedi/43898