Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Comparing Two-Phase Hybrid Metaheuristics for the University Course Timetabling Problem (UCTP)
KTH, Skolan för elektroteknik och datavetenskap (EECS).
KTH, Skolan för elektroteknik och datavetenskap (EECS).
2019 (Engelska)Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)Alternativ titel
Jämförelse mellan hybridiserade metaheuristiker som löser schemaläggningsproblemet UCTP i två faser (Svenska)
Abstract [en]

Timetabling is a time consuming and difficult task for large organizations. One popular research field is the university course timetabling problem (UCTP). UCTP is the NP-hard combinatorial problem of scheduling courses at a university while satisfying some constraints. In most definitions of the UCTP, there are hard constraints that defines what a valid timetable is and there are soft constraints that are only desired features of the timetable.

In this research, a few different hybrid methods for solving the UCTP are tested and compared. The hybrids tested are combinations of the metaheuristics simulated annealing, tabu search and iterated local search. The approach is to first use one of these methods to find a valid timetable that is not breaking any hard constraint. Then, a second phase begins that is attempting to minimize the soft constraint violations.

The results showed that simulated annealing was the fastest method for removing all hard constraint violations. Given a partial solution solved by simulated annealing, iterated local search was found to minimize soft constraint violations most successfully within the time limit for all tested sizes of problem instances. It was found that this hybrid in two phases could give better solutions than only using simulated annealing.

Abstract [sv]

Schemaläggning är en tidskrävande och svår uppgift för stora organisationer. Schemaläggningsproblemet UCTP är ett NP-svårt kombinatoriskt problem som går ut på att, med hjälp av en dator, lägga ett schema för ett universitet. Schemat måste också följa vissa regler och begränsningar för hur ett schema får se ut. I de flesta definitionerna av UCTP-problemet så finns det en uppdelning mellan hårda och mjuka begränsningar. För att ett schema ska vara giltigt så får det inte finnas några brott mot de hårda begränsningarna. De mjuka begränsningarna däremot är bara önskvärda egenskaper för ett schema.

I denna rapport har vi jämfört olika hybridmetoder av metaheuristiker för att lösa UCTP. De hybrider som undersökts är olika kombinationer av simulerad härdning, itererad lokalsökning och tabusökning. Först används en av dessa algoritmer för att hitta en halvfärdig lösning som inte bryter mot några hårda begränsningar. Denna lösning ges sedan till en andra fas där olika metaheuristiker jämförs utifrån hur bra de begränsar brotten mot de mjuka begränsningarna.

Resultaten visade att simulerad härdning var snabbast för att hitta en giltig lösning till UCTP. Givet en påbörjad lösning från simulerad härdning, så lyckades itererad lokalsökning minimera brotten mot svaga begränsningar mest framgångsrikt inom tidsgränsen för alla storlekar på probleminstanser som testades. Slutsatsen blev att en hybrid i två faser kunde ge bättre lösningar än att endast använda simulerad härdning för schemaläggningsproblemet UCTP.

Ort, förlag, år, upplaga, sidor
2019. , s. 31
Serie
TRITA-EECS-EX ; 2019:349
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:kth:diva-259689OAI: oai:DiVA.org:kth-259689DiVA, id: diva2:1352996
Handledare
Examinatorer
Tillgänglig från: 2019-09-24 Skapad: 2019-09-20 Senast uppdaterad: 2019-09-24Bibliografiskt granskad

Open Access i DiVA

fulltext(603 kB)25 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 603 kBChecksumma SHA-512
ae3369773a58a73a8c39f0da1b72bfeaf02205f686ce424c5478f6db6a90f9ae42a9bbb654ed69abb7cff7907221d77a0b11fb789282489028eb76811ea01ebe
Typ fulltextMimetyp application/pdf

Av organisationen
Skolan för elektroteknik och datavetenskap (EECS)
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 25 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 59 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf