Change search
ReferencesLink to record
Permanent link

Direct link
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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-166276OAI: diva2:810264
Available from: 2015-05-28 Created: 2015-05-06 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 110 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

Total: 177 hits
ReferencesLink to record
Permanent link

Direct link