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

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • 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
Applicability of Constraint Solving and Simulated Annealing to Real-World Scale University Course Timetabling Problems
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
Tillämpbarhet av villkorsprogrammering och simulerad härdning för universitetsschemaläggningsproblem på realistisk skala (Svenska)
Abstract [en]

The university course timetabling problem is the problem of creating a schedule for university courses under certain constraints. The decision variant of this optimisation problem is NP-complete. We have researched this problem and implemented the heuristic simulated annealing. This implementation has been compared with respect to time to the constraint solver CPSolver, based on iterative forward search. Our results show that CPSolver scales better for large problem instances. Simulated annealing as implemented by us is thus not suitable in itself for generating valid solutions to this problem on a real-world scale.

Abstract [sv]

Universitetsschemaläggningsproblemet går ut på att skapa ett schema för universitetskurser under vissa villkor. Beslutsversionen av detta optimeringsproblem är NP-fullständig. Vi har undersökt problemet och implementerat heuristiken simulerad härdning. Denna har jämförts med avseende på tid med villkorsprogrammeringslösaren CPSolver, som är baserad på iterativ framåtsökning. Våra resultat visar att CPSolver skalar bättre för stora probleminstanser. Simulerad härdning som implementerad av oss är därför inte i sig lämplig för att generera giltiga lösningar till verklighetstrogna probleminstanser.

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

Open Access i DiVA

fulltext(756 kB)28 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 756 kBChecksumma SHA-512
3965dffb956c0544d7a1a0ecb2d63e9929e3801be05701ff3e9dca9337ee6dfaf333d1217f3017740f6a6c4c2e8caa7b63bc9483cbcb94854b1df5e71000021a
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: 28 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: 62 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • 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