Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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 Comparative Evaluation of Metaheuristic Approaches to the Problem of Curriculum-Based Course Timetabling
KTH, School of Engineering Sciences (SCI).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Timetabling is an active area of research and used in a wide range of applications. As the development of most of these applications is on its way towards automation, the need for automated timetabling increases. Despite many years of research and development of automated approaches, solving NP-hard problems such as timetabling problems remains a challenge. Metaheuristic-based approaches to these problems are constantly being refined and further developed as the complexity of these applications increases. But despite the increase in complexity, the time it takes for these algorithms to solve these problems is constantly being challenged.

While this thesis covers the fundamentals in metaheuristic approaches to the problem of timetabling, its main focus is to compare how two known metaheuristic algorithms, Tabu Searchand Simulated Annealing, perform across different scales of resources that are to be scheduled. To attempt fairness, similar implementations of these two algorithms were made in order to eliminate systematic biases. For each set of resources the algorithms solves a timetabling problem under a limited amount of time and computational capacity. The collective quality of all the produced timetables were compared. The results show that Simulated Annealing perform slightly better in the majority of the instances but with little margin for the collective quality of all tables. Despite trying to set a common ground for the these similar metaheuristic approaches, the underlying difficulties in comparing algorithms are discussed.

Abstract [sv]

Schemaläggning är ett aktivt forskningsområde och har ett stort antal tillämpningsområden. Då utvecklingen av de flesta av dessa tillämpningar är på väg mot automatisering, ökar behovet avautomatiserad schemaläggning. Trots många års forskning och utveckling av automatiserade tillvägagångssätt, är det fortfarande en utmaning att lösa NP-svåra problem såsom schemaläggningsproblem. Metaheuristiska metoder som löser dessa problem förfinas ständigt och vidare utvecklasi takt med ökande komplexitet i de tillämpningar dem löser. Men trots den ökade komplexiteten utmanas ständigt tiden det tar för dessa algoritmer att lösa dessa problem.

Då denna avhandling behandlar grunderna i metaheuristiska tillvägagångssätt till schemaläggningsproblem, är dess huvudsakliga fokus att jämföra hur två kända metaheuristiska algoritmer,Tabu Search och Simulated Annealing, presterar vid olika skalor av de resurser som skall schemaläggas. För att göra jämförelsen rättvis, implementerades dessa två algoritmer likartat vilket syftar till att eliminera systematiska fel. För varje uppsättning av resurser löser algoritmerna ett schemaläggningsproblem under en begränsad tid och beräkningskapacitet. Den kollektiva kvalitén hos de producerade tidtabellerna jämförs. Resultaten visar att Simulated Annealing presterar något bättre i de flesta av fallen men med lite marginal sett till den kollektivakvalitén hos respektive algoritm. Trots försök att fastställa en gemensam grund för dessa liknande metoder, diskuteras de underliggande svårigheterna i att jämföra algoritmer.

Place, publisher, year, edition, pages
2015. , 27 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-168009OAI: oai:DiVA.org:kth-168009DiVA: diva2:813863
Supervisors
Examiners
Available from: 2015-05-25 Created: 2015-05-25 Last updated: 2015-05-25Bibliographically approved

Open Access in DiVA

fulltext(172 kB)144 downloads
File information
File name FULLTEXT01.pdfFile size 172 kBChecksum SHA-512
9b3c59479287642bbd94a9ce174098908a294709b8ab859eb91785125228279567e11aba897fefe5fca72de1a733779dbcacd137cba3b2fd94142369e3ae1d81
Type fulltextMimetype application/pdf

By organisation
School of Engineering Sciences (SCI)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 144 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: 257 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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