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
Variantene inkluderer tildeling med kapasitet (flere oppgaver per ressurs), tillegg av tidsplanleggings- eller flerobjektive mål, samt
Anvendelser finnes i personalplanlegging, produksjon og logistikk, produksjonsplanlegging og i sky- og datasentralressursallokering, der man ønsker