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.

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.