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
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)289 downloads
File information
File name FULLTEXT01.pdfFile size 382 kBChecksum SHA-512
16bd0ae389e3eef6119eede9f26931a26451276dc8c6686c4898e5088f78715895e7d735924f332204b14d3b2ec4b7d8bb3c0ac9cae5a9bf8e4122f624f88507
Type fulltextMimetype application/pdf

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

Search outside of DiVA

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