Algoritmerne klarer planlægningen

Planlægningsproblemer i større virksomheder bliver meget hurtigt utroligt komplekse, når alle detaljer skal medtages.

For den enkelte planlægger kan det derfor være nødvendigt at benytte sig af beslutningsstøttesystemer som værktøj under planlægningen.

Et støttesystem inden for planlægning består af en database med relevant information, såsom aktiviteter, der skal udføres, hvornår de skal udføres hvilke kvalifikationer, der påkræves ved udførslen, og medarbejdere og deres kvalifikationer.

Planlæggeren noterer i systemet hvilke aktiviteter, der skal planlægges, hvorefter en optimeringsalgoritme beregner de bedste forslag til planer.

Planlæggeren kan herefter finjustere detaljer og udvælge den færdige plan til udførelse. Men hvordan er det lige, at støttesystemet finder gode planer?

Modellen for planlægning

Planlægningsproblemer kan beskrives ved hjælp af en matematisk heltalsmodel. I en heltalsmodel benyttes uligheder til at beskrive begrænsninger i planlægningen, f.eks. hvor mange medarbejdere der mindst kræves til udførslen af en aktivitet, eller hvornår den senest skal være afsluttet.

Beslutningsvariable bruges til at afgøre, hvilke valg der er foretaget i planen, f.eks. om en medarbejder udfører en aktivitet eller ej.

Derudover beskriver modellen også et mål for planlægningen, hvis man for eksempel ønsker den billigste plan eller den med mindst arbejdstid.

Et eksempel på en heltalsmodel for et simpelt planlægningsproblem er:

minimer 9x + 7y + 5z

mht. x + y >= 1

x + z >= 1

y + z >= 1

x,y,z enten 0 eller 1

hvor medarbejderne (variablerne) x, y og z tilsammen skal udføre tre opgaver bestemt ved de tre uligheder.

Medarbejder x har kvalifikationer til at udføre de to første opgaver, y kan lave den første og den tredje, mens z er kvalificeret til at udføre de to sidste opgaver. Målet er at minimere den samlede lønudgift, som er 9 for medarbejder x, 7 for y og 5 for z.

En optimal løsning er 12, hvor den første opgave udføres af y, den anden af z og den tredje af både y og z, mens x holder fri.

Tager algoritmer til hjælp

Med flere hundreder af medarbejdere og opgaver bliver heltalsmodellen hurtig for kompleks for en planlægger at beregne manuelt. I stedet "plugger" støttesystemet modellen ind i en algoritme, der gennemsøger mulige planer og evaluerer deres kvalitet efter planlæggerens målsætning. De computerbaserede algoritmer benytter metoder inden for det, der kaldes heltalsprogrammering.

Når en computer skal finde løsninger til heltalsmodeller ved hjælp af heltalsprogrammering (se faktaboks) laver den først en forenkling af modellen, således at variable kan antage ikke-heltallige værdier. Så kan man benytte sig af en hurtigere metode kaldet lineær programmering til det forenklede problem.

I eksemplet ovenfor vil dette resultere i at alle medarbejderne benyttes en halv gang til hver opgave og den samlede lønudgift vil blive 10,5.

Det er naturligvis ikke en mulig løsning, men ved brug af en forgreningsstrategi kan man tvinge medarbejderne til enten at udføre aktiviteten fuldt ud eller slet ikke. Så kan man opnå en lovlig plan.

Delkomponeringsalgoritmer ordner de mange hensyn

En kendetegnende struktur for planlægningsproblemer er, at der for hver medarbejder skal tages hensyn til en mængde forskellige ting, såsom vagtønsker, feriedage, samlet arbejdstid etc. I eksemplet var disse beregnet på forhånd for x, y, og z inden problemet blev formuleret.

Det er dog ikke altid muligt at gøre, og derfor er de normale løsningsmetoder inden for heltalsprogrammering oftest meget ineffektive ved læsning af planlægningsproblemer.

I stedet benytter man dekomponeringsalgoritmer (se faktaboks), der opsplitter modellen i mindre delproblemer per medarbejder, som kan løses individuelt.

Tilbage er at samle delene igen i et hovedproblem.

Heltalsprogrammering overhales af delkomponeringsalgoritmer

På trods af, at detaljerne i dekomponeringsalgoritmer endnu ikke er så forfinede og velsmurte som i de gængse heltalsprogrammeringsmetoder, eksisterer der allerede talrige eksempler, hvor dekomponeringsalgoritmerne er langt de hurtigste.

Forskningen inden for feltet er hele tiden med til at udvikle dekomponeringsalgoritmerne, og inden for de sidste år har det været muligt at overføre og benytte sig af flere tricks fra heltalsprogrammering, som man tidligere anså for at være for beregningstunge at implementere.

Derved har dekomponeringsalgoritmerne lagt yderligere afstand til de normale metoder, når der snakkes om løsning af planlægningsproblemer.

Kommercielt benyttes beslutningsstøttesystemer med implementerede dekompositionsalgoritmer især inden for skibstransport og i luftfartsindustrien, hvor der er store penge på spil, og hvor hver en optimering kan betyde en stor besparelse i brændstof og CO2-udslip.