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
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
2014.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-157687OAI: oai:DiVA.org:kth-157687DiVA: diva2:771121
Examiners
Available from: 2014-12-12 Created: 2014-12-12 Last updated: 2014-12-12Bibliographically approved

Open Access in DiVA

fulltext(382 kB)