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
Applicability of Constraint Solving and Simulated Annealing to Real-World Scale University Course Timetabling Problems
KTH, School of Electrical Engineering and Computer Science (EECS).
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
Tillämpbarhet av villkorsprogrammering och simulerad härdning för universitetsschemaläggningsproblem på realistisk skala (Swedish)
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.

Place, publisher, year, edition, pages
2019. , p. 23
Series
TRITA-EECS-EX ; 2019:358
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-259761OAI: oai:DiVA.org:kth-259761DiVA, id: diva2:1353500
Supervisors
Examiners
Available from: 2019-10-02 Created: 2019-09-23 Last updated: 2019-10-02Bibliographically approved

Open Access in DiVA

fulltext(756 kB)5 downloads
File information
File name FULLTEXT01.pdfFile size 756 kBChecksum SHA-512
3965dffb956c0544d7a1a0ecb2d63e9929e3801be05701ff3e9dca9337ee6dfaf333d1217f3017740f6a6c4c2e8caa7b63bc9483cbcb94854b1df5e71000021a
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: 5 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: 11 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