Cases
Vi har udvalgt et ganske lille antal cases, som illustrerer bredden i vores erhvervssamarbejde. Der vil selvfølgelig være mange andre typer problemstillinger, som kunne være relevante.- Feedback om kunders interesser gennem analyse af store datamængder
- IMADA hjælper med at skaffe plads til teltet
- Computeren samler LEGO-modellen
- Planlægning af jobrækkefølge i Bang & Olufsens anodiseringsanlæg
- Minimering af spild ved udskæring af madrasser hos Danfoam Aps
- Optimering af ruter for hjemmeplejere og billetkontrollører
- Arbejdsplanlægning for sygeplejersker og skemalægning for SDU
Feedback om kunders interesser gennem analyse af store datamængder
Når folk klikker sig igennem information fra en virksomhed på Internettet vha. deres computer eller deres mobiltelefon, så er det interessant for virksomheden at få feedback på kundernes reaktion. Hvis man f.eks. blader en elektronisk tilbudsavis igennem, kan en registrering af kundernes klik med musen f.eks. afsløre, hvor længe man ser på bestemte sider. Information af den type kan man bruge til at målrette tilbudsmateriale til de næste uger.Ph.D. studerende Kasper Grud Skat Madsen og hans vejleder, lektor Yongluan Zhou, fra IMADA blev kontaktet af eTilbudsavis ApS. De var interesseret i at opsamle statistik på mange forskellige slags brugeropførsel i stil med eksemplet ovenfor. Den store tekniske udfordring er, at når information om hundredetusinde kunders museklik og tastetryk sendes til virksomheden, så er der tale om meget store datamængder, der til og med ankommer meget hurtigt efter hinanden.
Forskerne har med udgangspunkt i det open-source produkt, Storm, som Twitter baserer sig på, udviklet et nyt system, de kalder ENORM. Systemet analyserer data, som den kommer ind, og beregner svarene på de statistiske spørgmål, virksomheden er interesseret i. Samtidigt lagrer de data i "skyen", hvor de har valgt at bruge Amazon Web Service.
For at kunne nå at svare på mange forskellige statistiske spørgmål baseret på den samme strøm af data har det været nødvendigt at optimere, samt at sikre skalerbarhed. Optimeringerne tager udgangspunkt i at udnytte, at mange statistiske oplysninger bruger de samme beregninger. F.eks. kræver spørgsmålene "Hvor længe ser en kunde i gennemsnit på en side?" og "Hvor mange søgninger laver hver kunde i gennemsnit?" begge, at man kender antallet af kunder i et vist tidsrum. ENORM identificerer automatisk den slags fælles komponenter, så de kun bliver beregnet een gang i stedet for at blive beregnet alle de steder, de optræder. En anden væsentlig komponent i ENORM er en automatisk metode til effektivt at parallellisere afviklingen. Det betyder, at hvis man kommer op på så store datamængder og hastigheder, at computeren på trods af optimeringerne ikke kan følge med, så kan man nemt købe en computer mere, og så kan de deles om arbejdet.
Det udviklede system kan bruges langt bredere - f.eks. til analyse
af strømme af data fra sensor-netværk, finansielle data, data fra
telekommunikation, etc.
IMADA hjælper med at skaffe plads til teltet
Dancamps, som driver et antal campingpladser, kontaktede Syddansk Universitet for at få hjælp til at håndtere en bestemt type reservation: Nogle af deres kunder vil gerne have en helt konkret hytte eller teltplads i modsætning til andre kunder, der bestiller en uspecificeret plads. I en sådan situation er det faktisk meget vanskeligt at afgøre, når en kunde ringer for at foretage en reservation, om det kan lade sig gøre at anbringe folk med uspecificerede reservationer på en sådan måde, at der kan blive plads til den aktuelle reservation.
Det beregningsmæssige problem, der ligger bag ved dette, er, udtrykt i datalogisk terminologi, NP-hårdt. I praksis betyder det, at når man ser på selv ganske få reservationer, så er antallet af mulige måder at placere folk med uspecificerede reservationer langt større end antallet af elementarpartikler i universet. Blandt disse mange muligheder vil Dancamps gerne finde én, der gør, at man kan sige "ja" til kunden, hvis det overhovedet er muligt.
Dette er svært og i praksis tit umuligt for en person at overskue, så Dancamps ville gerne have datalogisk hjælp til dette, både som en hjælp til den person, der taler med kunden i telefonen, og for at kunne tilbyde muligheden for fuldautomatiserede web-baserede løsninger.
Ph.d.-studerende Martin R. Ehmsen har sammen med professor Kim Skak Larsen arbejdet på denne problemstilling og har udviklet algoritmiske tilgange, der betyder, at for alle de situationer, der ses i praksis, kan man nu på mindre end ét sekund få svar på, om en reservation kan accepteres eller ej. For Dancamps betyder det, at man nu kan sige "ja" til kunder, man før måtte afvise.
Computeren samler LEGO-modellen
I alle LEGO-æsker ligger en samlevejledning, der angiver en fornuftig
rækkefølge at sætte klodserne sammen i. Samlevejledningen skal være både
letforståelig, logisk og fysisk mulig at gennemføre (f.eks. kan de
midterste klodser i en mur ikke sættes på til sidst). LEGO har
traditionelt lavet disse samlevejledninger manuelt, dvs. ved at
en person
udvikler vejledningen ved at prøve sig frem. Dette er et tidskrævende
arbejde, ofte af størrelsesorden en måned eller mere for mellemstore
LEGO-modeller. LEGO havde derfor et ønske om at få denne proces
automatiseret ved at skabe et computerprogram, som kan udvikle
samlevejledninger for LEGO-modeller. Et sådant program ville kunne spare
arbejdstid under udviklingen af nye produkter og ville derudover være
relevant for LEGOs website, hvor brugere kan bygge deres egen LEGO-model i
et virtuelt miljø og derefter bestille en æske med netop de brikker, deres
model indeholder.
At få et computerprogram til at lave samlevejledninger er svært, blandt andet fordi det er svært at give veldefinerede mål for, hvad der kendetegner en god samlevejledning. Men i et længerevarende samarbejde med LEGO har lektor Rolf Fagerberg samt specialestuderende Jakob Allerelli og Nikolaj Blytsø arbejdet succesfuldt med at udvikle metoder til automatisk generering af samlevejledninger for LEGO-modeller og har testet metoderne systematisk i prototype-programmer.
De udviklede metoder danner i dag en del af baggrunden for automatiserede
IT-værktøjer hos LEGO, som automatisk kan foreslå samlevejledninger. Disse
værktøjer hjælper dels med at nedbringe tiden, og dermed omkostningerne,
til udvikling af højkvalitets samlevejledninger for nyudviklede modeller i
LEGOs produktlinie og tillader desuden fuldautomatiserede samlevejledninger
af fornuftig kvalitet til brug for LEGOs online site, hvilket styrker
denne alternative salgsplatform.
Planlægning af jobrækkefølge i Bang & Olufsens anodiseringsanlæg
Bang & Olufsen råder over et stort anodiseringsanlæg til
overfladebehandling af blandt andet de aluminiumsdele som bruges i deres
apparater. Der stilles meget høje kvalitetskrav til denne
behandlingsproces. Anodiseringsanlægget består af en række kar med
forskellige væsker (syre, base, vand, farve, osv.) og et antal kraner som
flytter emnerne ind i anlægget, derefter gennem en bestemt delmængde af
karrene og så ud af anlægget igen.
En lang række forskellige emner behandles i dette anlæg. For hvert af disse er der en fastlagt delmængde af karrene som emnet skal igennem og en angivelse af, hvor længe emnet mindst skal være i et kar, samt hvor længe det højst må være der (uden at blive ødelagt af f.eks. syre). Emnerne ankommer løbende (bliver klar til at komme ind) til anlægget og kan have en prioritering tilknyttet. Planlægningsopgaven går nu ud på at finde en rækkefølge i hvilken emnerne kan tages ind i anlægget, samt en plan for hvor længe de skal opholde sig i hvert af de relevante kar, sådan at planen kan udføres ved hjælp af anlæggets kraner og uden at disse kolliderer med hinanden!
Bang & Olufsen kontaktede os med denne opgave og ønskede dels at få dokumentation (i form af et computerprogram) for at dette komplicerede problem kunne løses effektivt vha. optimeringsmetoder, dels at kunne bruge et sådan program til at se, hvor meget produktionen (antal emner gennem anlægget per dag) kunne øges, såfremt man anvendte et sådan værktøj. Sidstnævnte ville kræve, at det nuværende anlæg laves om, og det ville koste et betydeligt millionbeløb at implementere denne ændring.
I et specialeprojekt ved Jakob Skov vejledt af professor Jørgen
Bang-Jensen med assistance fra Adjunkt Marco Chiarandini og Jens
Svalgaard Kohrt har vi udviklet algoritmer, der dels er i stand til at
finde en "kollisionsfri" plan meget hurtigt, dels kan dokumentere (via
detaljerede Gantt kort), at planen faktisk er kollisionsfri og endelig kan
forbedre antallet af emner, der kan føres igennem anlægget per dag ganske
betydeligt. Jakob har siden arbejdet et år hos B&O med at videreudvikle
sin software. Selv om algoritmerne ikke er direkte i brug i det daglige,
har B&O nu fået et nyttigt analyseværktøj, som kan hjælpe dem dels med
styringen af den daglige produktion, dels med at tage den rigtige
beslutning, når anlægget en gang skal skiftes ud.
Minimering af spild ved udskæring af madrasser hos Danfoam Aps
Danfoam producerer madrasser og hovedpuder af mærket Tempur, der blandt
andet anvender trykaflastende skum. Dette materiale er meget dyrt og
produceres på fabrikken i store skumblokke på ca 30 meter som efter en
passende hærdningstid skal udskæres i mange mindre stykker (typisk 110 cm
til 230 cm), der hver især bliver til en del af en madras. Når en blok
tages ind til udskæring, skal den enten bruges helt med mindst muligt
spild, eller returneres til lageret med en længde, der (typisk) er mindst 8
meter. På en typisk arbejdsdag skæres et stort antal blokke op, og opgaven
går ud på at finde ud af, hvilke stykker fra en given ordre-batch der
skal skæres fra de enkelte blokke, således at det samlede spild
minimeres.
Der er mange komplikationer i denne opgave: der er mange hundrede udskæringer i op til 10 forskellige længder, blokkens præcise længde kendes ikke før den er hentet ind fra lageret, der kan være udskæringer som mislykkes og som derfor skal skæres om med det samme, etc. Der er strenge tidskrav til processen, så en god løsning (fordeling af snit på blokke) skal kunne findes hurtigt og i realtid. Endelig skal algoritmerne kunne køre på hardware med begrænset plads- og processorkapacitet.
Sammen med Jørgen Bang-Jensen har de tre ph.d. studerende, Steffen
Godskesen, Thomas Sejr Jensen og Rune Larsen udviklet et program, der løser
denne opgave meget effektivt, både tidsmæssigt og mht. at minimere spildet,
og dermed bidraget til, at Danfoam har kunnet opnå et meget lille spild i
sin produktion.
Optimering af ruter for hjemmeplejere og billetkontrollører
Gennem to ph.d. projekter ved Steffen Godskesen og Thomas Sejr Jensen, samt
et større antal specialeprojekter, alle vejledt af Jørgen Bang-Jensen
eller Marco Chiaradini, har IMADA været involveret i en række projekter,
hvor en af de vigtigste ingredienser er at finde de bedst mulige ruter for
personer eller køretøjer med henblik på at optimere f.eks.
serviceniveauet (mere tid hos borgeren, den rigtige hjemmeplejer til borgeren,
etc.) i hjemmeplejen eller kontrollere flest mulige potentielle "snydere"
i S-togene.
Ofte har disse ruteproblemer en lang række komplicerede sidebetingelser,
så som at flere hjemmeplejere skal besøge en borger på samme tidspunkt, der
er præferencer for hvilken hjemmeplejer, der skal besøge en given borger,
eller at en billetkontrollør (naturligvis) skal rejse med S-toget, hvorfor
en evt. forsinkelse af et tog kan betyde at den planlagte rute ikke
længere kan anvendes og en ny skal kunne findes hurtigt. I sit speciale
arbejdede Lars Kjær Nielsen med sidstnævnte opgave og blev derefter ansat
af DSB S-tog i en periode med henblik på at analysere, hvilke strategier
for togrevisorerne der så mest lovende ud. Hans arbejde hos IMADA førte
til at han fik tildelt et ph.d. stipendium ved Erasmus Universitetet i
Rotterdam, hvor han i 3 år arbejdede videre med optimering indenfor
jernbanesektoren.
Arbejdsplanlægning for sygeplejersker og skemalægning for SDU
Der forskes på IMADA blandt andet i optimeringsmetoder, der er meget
anvendelige til opgaver som vedrører arbejdsplanlægning (f.eks.
vagtplaner) og skemalægning af begivenheder med komplicerede
afhængigheder. I sit speciale udviklede Henrik Berg Nielsen, med
udgangspunkt i data fra OUH og under vejledning af Jørgen Bang-Jensen, et
program, som kan lave en vagtplan (for et givet antal uger) for en
hospitalsafdeling på meget kort tid, i forhold til den tid det tager en
menneskelig planlægger i dag. Samtidig er den automatisk generede vagtplan
i stand til at tage betydeligt flere hensyn til personalets ønsker om
fridage, bestemte vagter, etc. end den manuelt fremstillede plan.
De metoder, som anvendes ovenfor, er også meget relevante, når man skal skemalægge kurser, lave holdtildelinger og eksamensplaner på et universitet, hvor der er mange forskellige timetal og varighed for kurserne, samt mange komplicerede bånd på placeringen af kurser (studerende har mange forskellige kurser, der ikke må overlappe, der er et begrænset antal egnede lokaler, der skal være en vis mindste afstand mellem eksaminer, der tages af den samme studerende, etc.). I sit speciale udviklede Anders Rasmussen, under vejledning af Marco Chiarandini og Jørgen Bang-Jensen, et program, der kan løse skemalægningsproblemer, som ligger tæt op af det fulde universitetsskemalægningsproblem. Efter sit speciale har han i en periode været ansat ved det naturvidenskabelige fakultetssekretariat på SDU. Her udviklede han blandt andet algoritmer, som nu er i brug til at lave holdtildeling for studerende, samt eksamensplanlægning.