Om att fördela resurser korrekt och snabbt

Axel Ringh som disputerade i tillämpad matematik vid KTH 2019, har tack vare ett anslag från Knut och Alice Wallenbergs Stiftelse erhållit en postdoktoral tjänst hos professor Li Qiu vid Hong Kong University of Science and Technology, Hongkong, Kina.

I många tillämpningar är planering viktig och då uppstår olika typer av schemaläggningsproblem. Det kan gälla sådana aktuella samhällsutmaningar som att planera energitilldelning till smarta elnät eller laddning av elfordon. Små schemaläggningsproblem kan alltid lösas effektivt av en dator. Men större problem med tusentals ingående komponenter kan, om man inte hittar en lämplig algoritm, ta miljontals år att lösa även med en mycket kraftfull dator.

För enkla villkor, som för en begränsad mängd resurser och uppgifter att utföra, är schemaläggningsproblemet välstuderat och kan lösas effektivt. Det blir dock mer komplicerat då det inom tillämpningarna ofta finns olika typer av extra villkor – tiden är begränsad, eller i vissa fall kan resurser till och med omfördelas. Till exempel kan ett bilbatteri som i huvudsak är inkopplat för att laddas även tillfälligt användas för att bidra med elektricitet.

Till utmaningarna hör också att det ofta tar lång tid att beräkna en lösning. Därför behöver man i förväg snabbt kunna avgöra huruvida problemet över huvud taget har en lösning eller inte. Det gäller att ta fram nödvändiga och tillräckliga villkor för existens av en lösning, som dessutom är enkla att utvärdera. Och om det finns en lösning, så finns det oftast flera olika lösningar. Då behövs det metoder för att hitta de lösningar som är optimala ur vissa perspektiv.

Axel Ringhs forskning går ut på att förstå för vilka typer av utvidgningar av schemaläggningsproblemet det fortfarande är möjligt att lösa problemet effektivt. Ett lovande angreppssätt är att utnyttja de senaste decenniernas forskning och erfarenheterinom det så kallade optimala transportproblemet, vilket framgångsrikt har använts inom bland annat behandling av signal- och bilddata.