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.

 

---