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
An Evaluation of the Great Deluge Algorithm in Course Timetabling: As Applied to the KTH-Inspired University Course Timetabling Problem
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
En utvärdering av The Great Deluge på KTH-inspirerade University Course Timetabling Problem (Swedish)
Abstract [en]

The University Course Timetabling Problem (UCTP) can be loosely described as assigning events (e.g lectures) to rooms and timeslots in a way that results in a feasible timetable that is optimal according to some custom criteria. The problem has become increasingly relevant as more programs become available in universities. Due to the complexity of UCTP, the problem is usually solved approximately using heuristics.

The KTH-inspired UCTP is a variant of the UCTP that is adapted to KTH Royal Institute of Technology. However, few heuristics have been implemented for this variant of UCTP. Therefore, this study introduces an implementation of The Great Deluge heuristic to the KTH-inspired UCTP, and compares it to a state-of-the-art solver for KTH-inspired UCTP.

The Great Deluge implementation was compared against the state-of-the-art KTH-inspired UCTP solver for different time limits. For each time limit, the output timetable quality was recorded over several executions. The comparison was done on two problem instances of varying complexity.

The results suggest a behavior that varies over time. For larger time limits, GD produced better timetables than the state-of-the-art and the overall quality of timetables was consistent over several executions. For smaller time limits, GD produced worse timetables than the state-of-the-art and the overall quality of timetables was inconsistent over several executions.

A few potential causes for the improved performance during the later stages of execution were found through further analysis of the results. Perhaps the biggest potential cause was utilizing the greedy behavior obtained during the mid to late stages of execution.

Abstract [sv]

”The University Course Timetabling Problem” (UCTP) handlar i grova drag om att, baserat på ett antal kriterier, schemalägga föreläsningar, övningar och laborationer på ett optimalt sätt. Problemets relevans har ökat allt eftersom universitet utökar sina programutbud. På grund av komplexiteten hos UCTP löses problemet vanligtvis approximativt med hjälp av heuristiker.

”KTH-inspired UCTP” är en KTH-anpassad variant av UCTP för vilken endast ett fåtal heuristiker har implementerats. Denna variant har exempelvis inte lösts av en vanlig heuristik inom UCTP, ”The Great Deluge” (GD). Denna studie fokuserar därför på att applicera GD på ”KTH-inspired UCTP” och jämföra denna med äldre implementationer, med fokus på den bästa tillgängliga implementationen.

GD-implementationen jämförs med den bästa tillgängliga implementationen för ”KTH-inspired UCTP” för olika tidsgränser. Kvaliteten hos de resulterande schemana evalueras och sparas sedan över flera körningar. Jämförelsen gjordes på två probleminstanser av olika komplexitet.

Resultatet av jämförelsen föreslår att GD producerade bättre scheman för högre tidsgränser men sämre scheman för lägre tidsgränser. Vidare analys föreslår att denna förbättring beror på utnyttjandet av det giriga beteendet som vår GD-implementation uppvisar vid senare delar av exekvering.

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

Open Access in DiVA

fulltext(532 kB)2 downloads
File information
File name FULLTEXT01.pdfFile size 532 kBChecksum SHA-512
b4fccf779a44a801c7438b6e3eac2746c09ad31d4df65e8b8ebe61c0d571bdb751931648fd38e1ed7d4659f8319a78cc52568a0f3e7398de872aeaa2092b776e
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: 2 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: 24 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