DTU-ph.d.er vandt verdensmesterskabet i skemalægning - »Vi har brugt sindssygt lang tid på det«
To ph.d.-studerende fra DTU har vundet årets VM i skemalægning. Det bliver næppe en olympisk disciplin lige foreløbig, men det rene sjov er det heller ikke.
VM i skemalægning går nemlig ud på at udvikle en algoritme, som kan lægge det bedste skema for et givent planlægningsproblem. I år var opgaven at lægge skemaer for forskellige semestre på universiteter verden over. Ud over Danmark var hold fra Frankrig, Kosovo, Portugal og Schweiz udtaget til finalen.
Og nogle gange er der bare en klar årsag til succesen:
»Vi har brugt sindssygt lang tid på det i forhold til vores konkurrenter, kan vi se nu bagefter,« forklarer ph.d.-studerende Dennis Søren Holm fra DTU Management, der sammen med Rasmus Ørnstrup Mikkelsen, som er erhvervs-ph.d. fra samme sted, tog førstepladsen.
Opgavens data er informationer om klasser og oplysninger om laboratorieøvelser eller forelæsninger m.v. Så skal forelæsninger og andre aktiviteter planlægges med en tid og et lokale. Man ikke kan dobbeltbooke lokaler, og man kan ikke være to steder på én gang.
Men på samme studieretning vil man heller ikke have overlap. Man kan forestille sig kurser, der ikke må køre samme dag, fordi de er på samme studieretning eller andet. Så er der arbejdstid, hvor der må ikke være for mange arbejdstimer, og man skal helst ikke have 10 timer i et stræk, hverken som underviser eller elev.
Derfor går den ikke med brute force
Men hvorfor er det så svært at lave noget så simpelt som et skoleskema – kan man ikke bare gennemløbe hele løsningsrummet – en fremgangsmåde kendt som ‘brute force’?
»Hvis ‘brute force’ er at løbe alle løsninger igennem, så kunne man tage dagens største supercomputer og starte den ved big bang, og den ville ikke være færdig med at løbe løsningerne igennem endnu,« fortæller Dennis Søren Holm.
Han og holdkammeraten har en matematisk model, der er lavet ud fra principper i operationsanalyse, som DTU underviser i.
»Det er mere eller mindre unikt, DTU-mæssigt, at vi bruger disse modeller. Mange af vores konkurrenter bruger andre metoder, som er mere estimerende.«
Man behøver ikke gennemløbe hele det astronomisk store løsningsrum. Man kan med de to studerendes fremgangsmåde løbende udelukke dele af løsningsrummet.
»Det har vi prøvet, og det virker til dels på de små problemer, men ikke rigtig på de store. Nogle af de datasæt vi har fået, gælder for et institut på et universitet, som kan planlægges for sig selv uden at være afhængig af andre. Andre datasæt er enten kæmpestore institutter eller et helt universitet. Nogle har 38.000 studerende, som skal planlægges med hold, og andre er på et par tusind.«
Heuristik med matematisk model nedenunder
Den eksakte del-metode, der indgår i algoritmen, fortæller, hvornår der er fundet en løsning, som ikke kan blive bedre.
»Den virkede nogenlunde på visse datasæt, men ikke godt nok til, at vi var tilfredse. Derfor har vi lagt et lag oven på, hvor man låser dele af løsningsrummet fast og prøver at sub-optimere på den del: Hvis du har låst 80 procent fast, kan du flytte de sidste 20 procent og skemalægge dem optimalt ud fra, hvordan du har lagt de 80.«
Man kan vurdere løbende, om 80 procent er det rigtige tal, eller om man skal gøre det større eller mindre.
»Det er en ‘matheuristic’ – i modsætning til en almindelig heuristik har vi modellen nedenunder. Vi har en eksakt metode nedenunder, men en heuristisk ovenpå.«
De to studerende har brugt 40 af computerne i DTU’s Linux-klyngecomputer HPC til at beregne resultaterne. Nogle af opgaverne kunne løses eksakt på 3 minutter, mens andre tog 10 døgn, afhængig af problemets størrelse.
Rasmus Ø. Mikkelsen, der ud over DTU er erhvervs-ph.d. ved softwarefirmaet Macom, og Dennis Søren Holm forsker til daglig i matematisk modellering. De deltager også i et projekt, hvor de sammen med Macom og DTU undersøger, hvordan softwareprogrammet Lectio kan hjælpe universiteterne til at lægge gode skemaer.
Konkurrencen er foregået hen over et år, hvor deltagerne løbende har fået nye datasæt online, der skulle indarbejdes i deres løsningsmetode.
Det har stor betydning for universiteternes logistik og økonomi og de studerendes muligheder, at man kan få skemaer og lokaleplanlægning til at gå op, og den udfordring er ikke blevet mindre af corona-situationen.
For nylig skulle DTU således både tage højde for afstandskrav og et øget optag af studerende. Det gav de to medaljevindere mulighed for at teste deres model i praksis og hjalp DTU med at lægge planer, der sikrer, at man lever op til sundhedsmyndighedernes afstandskrav.
