Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Comparing Two-Phase Hybrid Metaheuristics for the University Course Timetabling Problem (UCTP)
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Jämförelse mellan hybridiserade metaheuristiker som löser schemaläggningsproblemet UCTP i två faser (Swedish)
Abstract [en]

Timetabling is a time consuming and difficult task for large organizations. One popular research field is the university course timetabling problem (UCTP). UCTP is the NP-hard combinatorial problem of scheduling courses at a university while satisfying some constraints. In most definitions of the UCTP, there are hard constraints that defines what a valid timetable is and there are soft constraints that are only desired features of the timetable.

In this research, a few different hybrid methods for solving the UCTP are tested and compared. The hybrids tested are combinations of the metaheuristics simulated annealing, tabu search and iterated local search. The approach is to first use one of these methods to find a valid timetable that is not breaking any hard constraint. Then, a second phase begins that is attempting to minimize the soft constraint violations.

The results showed that simulated annealing was the fastest method for removing all hard constraint violations. Given a partial solution solved by simulated annealing, iterated local search was found to minimize soft constraint violations most successfully within the time limit for all tested sizes of problem instances. It was found that this hybrid in two phases could give better solutions than only using simulated annealing.

Abstract [sv]

Schemaläggning är en tidskrävande och svår uppgift för stora organisationer. Schemaläggningsproblemet UCTP är ett NP-svårt kombinatoriskt problem som går ut på att, med hjälp av en dator, lägga ett schema för ett universitet. Schemat måste också följa vissa regler och begränsningar för hur ett schema får se ut. I de flesta definitionerna av UCTP-problemet så finns det en uppdelning mellan hårda och mjuka begränsningar. För att ett schema ska vara giltigt så får det inte finnas några brott mot de hårda begränsningarna. De mjuka begränsningarna däremot är bara önskvärda egenskaper för ett schema.

I denna rapport har vi jämfört olika hybridmetoder av metaheuristiker för att lösa UCTP. De hybrider som undersökts är olika kombinationer av simulerad härdning, itererad lokalsökning och tabusökning. Först används en av dessa algoritmer för att hitta en halvfärdig lösning som inte bryter mot några hårda begränsningar. Denna lösning ges sedan till en andra fas där olika metaheuristiker jämförs utifrån hur bra de begränsar brotten mot de mjuka begränsningarna.

Resultaten visade att simulerad härdning var snabbast för att hitta en giltig lösning till UCTP. Givet en påbörjad lösning från simulerad härdning, så lyckades itererad lokalsökning minimera brotten mot svaga begränsningar mest framgångsrikt inom tidsgränsen för alla storlekar på probleminstanser som testades. Slutsatsen blev att en hybrid i två faser kunde ge bättre lösningar än att endast använda simulerad härdning för schemaläggningsproblemet UCTP.

Place, publisher, year, edition, pages
2019. , p. 31
Series
TRITA-EECS-EX ; 2019:349
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-259689OAI: oai:DiVA.org:kth-259689DiVA, id: diva2:1352996
Supervisors
Examiners
Available from: 2019-09-24 Created: 2019-09-20 Last updated: 2019-09-24Bibliographically approved

Open Access in DiVA

fulltext(603 kB)5 downloads
File information
File name FULLTEXT01.pdfFile size 603 kBChecksum SHA-512
ae3369773a58a73a8c39f0da1b72bfeaf02205f686ce424c5478f6db6a90f9ae42a9bbb654ed69abb7cff7907221d77a0b11fb789282489028eb76811ea01ebe
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 5 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf