Digitala Vetenskapliga Arkivet

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
A comparative study between a simulated annealing and a genetic algorithm for solving a university timetabling problem
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En jämförande studie mellan en algoritm baserad på simulerad glödgning och en genetisk algoritm för att lösa ett universitetsschemaläggningsproblem (Swedish)
Abstract [en]

The university timetabling problem is an NP-complete problem which schools all over the world face every semester. The aim of the problem is to schedule sets of events such as lectures and seminars into certain time slots without violating numerous specified constraints. This study aimed to automate this process with the help of simulated annealing and compare the results with a genetic algorithm. The input data sets were inspired by the Royal Institute of Technology in Stockholm. The results showed a great run time difference between the two algorithms where the simulated annealing performed much better. They also showed that even though the simulated annealing algorithm was better during all stages, the genetic algorithm had a much better performance in early stages than it had in latter. This led to the conclusion that a more optimized, hybrid algorithm could be created from the two algorithms provided that the genetic algorithm could benefit from the improvements suggested in previous research.

Abstract [sv]

Universitetsschemaläggningsproblemet är ett NP-fullständigt problem som skolor över hela världen måste hantera innan varje termin. Syftet med problemet är att schemalägga händelser, såsom föreläsningar och seminarier, utan att bryta flertalet fördefinierade villkor.

Denna studie hade som mål att automatisera denna process med hjälp av algoritmkonstuktionsmetoden simulerad glödgning och sedan jämföra resultatet med en genetisk algoritm. De datamängder som användes är inspirerade av den verkliga situationen på KTH. Resultaten visar stora tidsmässiga skillnader där algoritmen baserad på simulerad glödgning går snabbare. De visar dock också att den genetiska algoritmen har en bättre prestanda i tidigare stadier än i senare. Detta ledde till slutsatsen att en mer optimerad hybridalgoritm kan skapas av de två algoritmerna, förutsatt att den genetiska algoritmen kan dra nytta av förbättringar som föreslagits i tidigare forskning.

Place, publisher, year, edition, pages
2016. , p. 45
Keywords [en]
Simulated annealing, Genetic algorithm, University timetabling problem
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-187158OAI: oai:DiVA.org:kth-187158DiVA, id: diva2:929059
Subject / course
Computer Science
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2016-05-18 Created: 2016-05-17 Last updated: 2022-06-22Bibliographically approved

Open Access in DiVA

fulltext(728 kB)853 downloads
File information
File name FULLTEXT01.pdfFile size 728 kBChecksum SHA-512
98dcb99f145935253c2dfdb1a7566e39964956612082502223d5bac47bff5d2323faec379928c4450dfe6e5b32cbc1bd2c0b4c9c7349fd227d666a1e1b5ef383
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Fredrikson, RasmusDahl, Jonas
By organisation
School of Computer Science and Communication (CSC)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 853 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: 1250 hits
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