Generaliserat tilldelningsproblem

I tillämpad matematik förstås ett generaliserat uppdragsproblem som ett kombinatoriskt optimeringsproblem , vilket är en generalisering av uppdragsproblemet , där uppsättningen av utförare har en storlek som inte nödvändigtvis är lika med storleken på uppsättningen jobb. I det här fallet kan utföraren få i uppdrag att utföra vilket arbete som helst (inte nödvändigtvis ett verk, som i uppdragsproblemet). När man tilldelar en exekutor att utföra arbete, är två värden uppsatta - kostnader och intäkter. Varje artist har en viss budget, så summan av alla kostnader bör inte överstiga denna budget. Det krävs att hitta ett sådant uppdrag av utförare att utföra arbete för att maximera inkomsten.

Särskilda tillfällen

I fallet när budgeten för utförare och alla kostnader för arbete är lika med 1, förvandlas problemet till det maximala matchningsproblemet .

Om priser och inkomster för alla arbetsuppgifter är lika, reduceras problemet till en multiplikativ ryggsäck .

Om det bara finns ett medel, reduceras problemet till ryggsäcksproblemet .

Definition

Det finns n jobb och m artister . Varje artist har en budget . För varje par av utförare och arbete anges inkomst och vikt . Lösningen är en delmängd av jobb U och en fördelning av jobb från U bland utförare. Beslutet är acceptabelt om kostnadsbeloppet för utförarens tilldelade arbete inte överstiger budgeten . Inkomsten från beslutet är summan av alla inkomster av alla fördelningar av arbetsutförare. ${\displaystyle x_{1},\dots ,x_{n))$ ${\displaystyle b_{1},\dots ,b_{m))$ $bi}$ $w_{i}$ $bi}$ $x_{j}$ ${\displaystyle p_{i,j))$ $w_{i,j}$ $bi}$ $w_{i}$

Matematiskt kan det generaliserade uppdragsproblemet formuleras på följande sätt:

maximera

\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.

föremål för ;

\sum _{j=1}^{n}w_{ij}x_{ij}\leq w_{i}\qquad i=1,\ldots ,m

\sum _{i=1}^{m}x_{ij}\leq 1\qquad j=1,\ldots ,n

;

x_{ij}\in \{0,1\}\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n

;

Det generaliserade tilldelningsproblemet är NP-hårt och till och med APX-hårt .

Fleischer, Gomans, Mirokni och Sviridenko föreslog en kombinatorisk lokal sökalgoritm med approximation och en algoritm baserad på linjär programmering med approximation [1] . $(2+\varepsilon )$ $({\frac {e}{e-1))+\varepsilon )$

Approximationen är den mest kända approximationen av det generaliserade tilldelningsproblemet. $({\frac {e}{e-1))+\epsilon )$

Greedy Approximation Algorithm

Med hjälp av tilldelningsproblem -approximationsalgoritmen kan man skapa en ( ) -approximation för det generaliserade tilldelningsproblemet på samma sätt som en girig algoritm med hjälp av begreppet restinkomst. Algoritmen skapar iterativt en preliminär sekvens där den är tänkt att tilldela utföraren arbete vid iterationen . Valet för utföraren kan ändras senare vid tilldelning av arbete till andra utförare. Återstående inkomst av verket för den utövande utövaren är , om verket inte ges till en annan utförare, och - om verket ges till den utförare . $\alfa$ $\alpha +1$ $j$ $b_{j}$ $b_{j}$ $x_{i}$ $b_{j}$ $p_{{ij}}$ $x_{i}$ $p_{ij}$ ${\displaystyle p_{ik))$ $b_{k}$

Formellt:

Använd vektor för förval och i denna vektor $T$

T[i]=j

innebär att det är tänkt att anvisa en utförare till arbetet ,

x_{i}

b_{j}

T[i]=-1

innebär att ingen har tilldelats jobbet.

x_{i}

Den återstående inkomsten per iteration betecknas med , där $j$ $P_{j}$

{\displaystyle P_{j}[i]=p_{ij))

om inget jobb har valts (dvs. )

x_{i}

T[i]=-1

{\displaystyle P_{j}[i]=p_{ij}-p_{ik))

, om verket är tänkt att ges till utföraren (dvs. ).

x_{i}

b_{k}

T[i]=k

Så algoritmen ser ut så här:

Tilldelade initiala värden för alla

T[i]=-1

i=1\ldots n

För alla , gör:

j=1...m

En approximationsalgoritm används för att erhålla arbetsfördelningen för uppdragstagaren med hjälp av restinkomstfunktionen . Utvalda verk anges .

b_{j}

P_{j}

S_j

Rättad med , d.v.s. för alla .

T

S_j

T[i]=j

i\in S_{j}

slutet av cykeln

Se även

Uppdragsproblem

Anteckningar

↑ L. Fleischer, MX Goemans, VS Mirrokni och M. Sviridenko. Snäva approximationsalgoritmer för maximala allmänna tilldelningsproblem. I SODA'06: Proc

Länkar

Reuven Cohen, Liran Katzir och Danny Raz, "An Efficient Approximation for the Generalized Assignment Problem" , Information Processing Letters, Vol. 100, nummer 4, sid. 162–166, november 2006.
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni och Maxim Sviridenko, "Tight Approximation Algorithms for Maximum General Assignment Problems" , SODA 2006, pp. 611–620.
Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems , 2005. Springer Verlag ISBN 3-540-40286-1