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 Comparison of a Heuristic and a Hopfield Neural Network Approach for Solving Examination Timetabling Problems
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En jämförelse av en heuristik och en Hopfield Neural Network-metod för att lösa schemaläggningsproblem för examinationer (Swedish)
Abstract [en]

The Examination Timetabling Problem (ETP) is the problem of scheduling a number of exams during a set time period so that no students are required to sit two exams simultaneously. Despite the complexity of the problem, universities all over the world solve ETPs several times each year. Two known methods for solving ETPs is using either heuristics or Hopfield Neural Networks (HNN). This thesis compares the performance of a heuristic algorithm implemented with Local Search, Simulated Annealing and Tabu Search to the performance of a HNN algorithm. Both algorithms were executed on ten different ETPs reduced to Graph Colouring Problems (GCP). The results show that the heuristic algorithm always generated more satisfactory solutions to the ETPs than the HNN. The HNN was, however, implemented as software in this thesis. It is intended to be implemented as hardware and if this method were to have been used instead the HNN algorithm might have produced other results. At this stage the heuristic algorithm is more suitable than the HNN algorithm for solving ETPs.

Abstract [sv]

Schemaläggningsproblem för examinationer (ETP) syftar på problemet att schemalägga ett antal examinationer under ett bestämt tidsintervall så att ingen student behöver närvara på flera examinationer samtidigt. Det är ett komplext problem som universitet världen över behöver lösa flera gånger per år. Två kända metoder för att lösa ETPs är användning av antingen heuristiker eller Hopfield Neural Networks (HNN). Den här uppsatsen jämför prestandan av en heuristik implementerad med Lokal Sökning, Simulerad Härdning och Tabusökning med presentandan av en HNN-algoritm då båda metoderna exekveras på tio ETPs reducerade till Graffärgningsproblem (GCP). Resultaten visar att heuristiken alltid genererade mer tillfredsställande lösningar till schemaläggningsproblemen än HNN-algoritmen gjorde. HNN-algoritmen, som egentligen bör implementeras som hårdvara, implementerades dock som mjukvara i den här avhandlingen. Hade den implementerats som hårdvara istället hade kanske andra resultat producerats. För tillfället lämpar sig heuristiken bättre än HNN-algoritmen för att lösa ETPs.

Place, publisher, year, edition, pages
2019.
Series
TRITA-EECS-EX ; 2019:339
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-255266OAI: oai:DiVA.org:kth-255266DiVA, id: diva2:1338845
Subject / course
Computer and Systems Sciences
Supervisors
Examiners
Available from: 2019-07-29 Created: 2019-07-24 Last updated: 2019-07-29Bibliographically approved

Open Access in DiVA

fulltext(638 kB)21 downloads
File information
File name FULLTEXT01.pdfFile size 638 kBChecksum SHA-512
922869cfd183b88783fbe3c036005b0befe737a8d3392410f891463a21b0f2aaee24f51f8752ce975b42d9df2d29f70ba23f6ea0db30217ecd311c149ada3eec
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

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