Tildelingsalgoritmer

Tildelingsalgoritmer er metoder for å tildele et sett oppgaver til et sett ressurser på en måte som optimerer et gitt kriterium, vanligvis å minimere total kostnad eller å maksimere nytte. Problemet disse metodene adresserer, kalles ofte tildelingsproblemet. I en typisk modell har man en kostnad C(i,j) for å tildele oppgave i til ressurs j, og målet er å finne en tilordning som minimerer summen av de valgte kostnadene. For én-til-én-tilordning er antallet oppgaver og ressurser like; i rektangulære varianter kan antallet være forskjellig ved å bruke dummykostnader eller ved å tillate ufullstendige tilordninger.

Den mest kjente eksakte metoden er Hungers algoritme for en n x n kostnadsmatrise, som løser problemet i tid O(n^3). Andre eksakte tilnærminger bruker nettverksmodeller og min-kostnad maks-strøm-formuleringer, løst med teknikker som Ford-Fulkerson eller primal-dual-metoder. Auksjonsbaserte algoritmer gir ofte god skalerbarhet og brukes i store problemer. For større eller mer komplekse problemstillinger benyttes heuristikker og tilnærmede metoder som greedy-tilnærminger eller lokalt søk.

Variantene inkluderer tildeling med kapasitet (flere oppgaver per ressurs), tillegg av tidsplanleggings- eller flerobjektive mål, samt krav som preferanser og precedence. I grafteoretisk form er tildelingsproblemet et minimum-kostnad perfekt matching i bipartite grafer.

Anvendelser finnes i personalplanlegging, produksjon og logistikk, produksjonsplanlegging og i sky- og datasentralressursallokering, der man ønsker effektive og transparente tildelinger mellom oppgaver og ressurser.