Change search
ReferencesLink to record
Permanent link

Direct link
Scalability of a Genetic Algorithm that solves a UniversityCourse Scheduling Problem Inspired by KTH
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2014 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Scheduling university courses is a combinatorial optimization problem where a set of events such as lectures, seminars and labs have to be scheduled into certain time slots while taking various constraints into account. The problem is considered dicult by conventional methods andthe amount of required computations usually increases exponentially with the size of the problem. However, for universities such as KTH, Royal Institute of Technology in Stockholm, this is a task that has to be dealt with regardless of its complexity. In this report, Genetic Algorithms (GAs) were applied to solve the course scheduling problem for multiple data samples inspired by KTH. The sizes of the input data were carefully designed to study the scalability of the GA. The results indicate on an exponential growth of the running time measured not in actual time but number of iterations. The scalability is highly dependent on the denition of a high quality solution as well as algorithm parameters but also      dierent methods being used in the GA.Keywords - Scheduling, Timetabling, KTH, Royal Institute of Technol-ogy, Scalability, Genetic Algorithm, GA, Constraints, Fitness, Selection,Crossover, Mutation, Repair, Extinction, Generation

Place, publisher, year, edition, pages
National Category
Computer Science
URN: urn:nbn:se:kth:diva-157687OAI: diva2:771121
Available from: 2014-12-12 Created: 2014-12-12 Last updated: 2014-12-12Bibliographically approved

Open Access in DiVA

fulltext(382 kB)170 downloads
File information
File name FULLTEXT01.pdfFile size 382 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: 170 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: 226 hits
ReferencesLink to record
Permanent link

Direct link