Scheduling lectures, exams, seminars etc. for a university turns out to be a harder task than what it seems to be at first glance. This problem is known as the University Course Timetabling Problem (UCTP). The UCTP has been hosted for a number of competitions throughout the years by an organization called Practice and Theory of Automated Timetabling (PATAT). Because of these competitions, the problem has been given a standard description and set of constraints as well as standard problem instances for easier comparison of research and work on the subject. However, setting a standard like this have a major drawback; no variety is introduced since new research for finding the greatest method to solve the UCTP is forced to focus on a specific set of constraints, and algorithms developed will only be optimized with these constraints in consideration. In this research we compared five well known UCTP algorithms with the standard set of constraints to a different set of constraints. The comparisons showed a difference in the rank of performance between the algorithms when some constraints were changed to fit a certain need. The differences were not great but big enough to state that previous research declaring what algorithms are best for the UCTP problem cannot be relied upon unless you use close to identical sets of constraints. If the goal is to find the best algorithm for a new set of constraints then one should not rely on a single previously defined great algorithm but instead take two or three of the top performing ones for the greatest chance of finding the most optimized solution possible. / Schemaläggning av föreläsningar, tentamen, seminarier etc. för ett universitet visar sig vara en svårare uppgift än vad det verkar vid första anblicken. Detta problem är känt som University Course Timetabling Problem (UCTP). UCTP har varit centralt i ett antal tävlingar genom åren av organisationen Practice and Theory of Automated Timetabling (PATAT). På grund av dessa tävlingar har problemet fått en standardbeskrivning och en uppsättning specifika begränsningar samt standard problemdata för enklare jämförelse av forskning och arbete i ämnet. Att sätta denna typ av standard har dock en stor nackdel; ingen variation tillförs då ny forskning för att hitta den bästa optimeringsmetoden inom UCTP tvingas att fokusera på en specifik uppsättning begränsningar och algoritmer som utvecklas kommer då endast att optimeras med dessa begränsningar i beaktande. I den här rapporten jämförde vi fem välkända UCTP algoritmer med standarduppsättningen av begränsningar mot en annan uppsättning begränsningar. Jämförelserna visade en skillnad i prestationsordningen mellan algoritmerna när vissa begränsningar ändrats för att passa ett visst behov. Skillnaderna var inte enorma men tillräckligt stora för att påvisa att tidigare forskning som förklarar vilka algoritmer som är bäst för UCTP-problemet ej är pålitlig om du inte använder nära till identiska uppsättningar av begränsningar. Om målet är att hitta den bästa algoritmen för en ny uppsättning begränsningar, bör man inte lita på en tidigare definierad effektiv algoritm utan istället använda sig utav två eller tre av de starkaste algoritmerna för den största chansen att hitta den mest optimerade lösningen.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-229695 |
| Date | January 2018 |
| Creators | Berggren, Robert, Nielsen, Timmy |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2018:232 |
Page generated in 0.0105 seconds