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
Comparing MAX-MIN and Rank-based Ant Colony Optimization Algorithms for solving the University Course Timetabling Problem
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Jämförelse av MAX-MIN och Rank-baserat myrkolonisystem för att lösa det universitetsbaserade schemaläggningsproblemet (Swedish)
Abstract [en]

The University Course Timetabling Problem (UCTP) is a scheduling problem regarding courses, time slots and rooms, and is often accompanied by a set of feature requirements. As non-trivial instances of the UCTP are NP-hard, traditional computational methods are ineffective. A meta-heuristic alternative is the Ant Colony Optimization (ACO) algorithm, which has previously been proven to successfully solve the UCTP. This paper investigates the relative effectiveness of the MAX-MIN ACO variation to the Rank-based ACO variation on UCTP problem sets of varying difficulty. They are also compared when using a local-search help function and a path attractiveness heuristic. This study shows that the ACO variations perform similarly well for all problem difficulties when utilizing the path attractiveness heuristic. Utilizing both local search and the heuristic produces the best results across the difficulties and ACO variations. There is, however, a need for further investigation into the parameters for both ACO variations to ensure the validity of the conclusion.

Abstract [sv]

Det universitetsbaserade schemaläggningsproblemet (UCTP) avser schemaläggning av kurser till rum och tider där hänsyn till en mängd funktionella krav ofta måste tas. Traditionella beräkningsmetoder har visats vara ineffektiva då icke-triviala fall av problemet är NP-svåra. Myrkolonisystemsalgoritmen (ACO) är ett meta-heuristiskt alternativ som framgångsrikt har använts för att lösa UCTP. Denna rapport jämför effektiviteten mellan MAX-MIN ACO-variationen och den Rank-baserade ACO-variationen i att hitta lösningar till UCTP. Variationerna jämförs också vid använding av "local search" och en vägvalsheuristik. Rapporten visar att ACO-variationerna presterar likvärdigt vid användande av vägvalsheuristiken. Användandet av både "local search" och vägvalsheuristiken leder till bästa resultat för samtliga svårighetsgrader och ACO-variationer. Efterforskning krävs angående parametrarna för ACO-variationerna för att säkerställa giltigheten av slutsatserna.

Place, publisher, year, edition, pages
2018.
Series
TRITA-EECS-EX ; 2018:211
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-229790OAI: oai:DiVA.org:kth-229790DiVA, id: diva2:1214470
Subject / course
Computer Science
Supervisors
Examiners
Available from: 2018-07-10 Created: 2018-06-06 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

fulltext(570 kB)40 downloads
File information
File name FULLTEXT01.pdfFile size 570 kBChecksum SHA-512
a87eb8183e8164adbf8bd565f37f180d61125bd60eb873261088d3521211d086dbc441212579b1c39aa2f48c4841ec9694722abcaddc851fd161340f12b861c5
Type fulltextMimetype application/pdf

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 40 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: 156 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