Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
A comparative analysis of a Tabu Search and a Genetic Algorithm for solving a University Course Timetabling Problem
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

This work implements a Tabu search (TS) algorithm for solving an instance of the University Course Timetabling Problem (UCTP). The algorithm is com- pared to a Genetic algorithm (GA) implemented by Yamazaki and Pertoft (2014) that solves the same instance. The purpose of the work is to explore how the approaches dier for this particular instance, and specifically inves- tigate whether a TS algorithm alone is sucient, considering the small size of the UCTP instance. The TS was based on the OpenTS library (Harder, 2001) and reuses parts from Yamazaki and Pertoft’s (2014) GA. The results show that the TS alone is too slow. Even in a small instance of the UCTP, the search space is too big for the TS to be fast. This confirms the state of the art, that a combination of TS and GA would perform better than either of them individually. Further improvements on the TS would involve reducing the number of moves generated each iteration.

Place, publisher, year, edition, pages
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-166276OAI: oai:DiVA.org:kth-166276DiVA: diva2:810264
Supervisors
Examiners
Available from: 2015-05-28 Created: 2015-05-06 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

fulltext(676 kB)216 downloads
File information
File name FULLTEXT01.pdfFile size 676 kBChecksum SHA-512
3611f781cd0009f87290c6d0834d4b662c6f9cc90ea226aeb89d8a72b1fedea7a19233f18a3bbfb362874bcc2ed088f6e6d7db79dabd36ca0ea64c508dfe6a57
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 216 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: 227 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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