Schemaläggning av identiska maskiner

Schemaläggning av identiska maskiner är ett optimeringsproblem inom datavetenskap och operationsforskning . Vi får n jobb J ₁ , J ₂ , ..., J _n med varierande bearbetningstider, som behöver schemaläggas på m identiska maskiner, så att en viss objektiv funktion optimeras, till exempel minimeras fabrikatet .

Identisk maskinschemaläggning är ett specialfall av enhetlig maskinschemaläggning , vilket i sig är ett specialfall av optimal jobbschemaläggning . I det allmänna fallet kan handläggningstiden för varje jobb vara olika på olika maskiner; i fallet med identisk maskinschemaläggning är bearbetningstiden för varje jobb densamma på varje maskin. Därför är identisk maskinschemaläggning likvärdig med flervägsnummerpartitionering . Ett specialfall av identisk maskinschemaläggning är enmaskinsschemaläggning .

I standardnotationen med tre fält för optimala jobbschemaläggningsproblem betecknas varianten av identiska maskiner med P i det första fältet. Till exempel, " P|| $C_{\max }$ " är ett identiskt maskinschemaläggningsproblem utan några begränsningar, där målet är att minimera den maximala slutförandetiden.

I vissa varianter av problemet, istället för att minimera den maximala färdigställandetiden, är det önskvärt att minimera den genomsnittliga färdigställandetiden (i genomsnitt över alla n jobb); den betecknas med P|| $\sum C_{i}$ . Mer generellt, när vissa jobb är viktigare än andra, kan det vara önskvärt att minimera ett viktat genomsnitt av färdigställandetiden, där varje jobb har olika vikt. Detta betecknas med P|| $\sum w_{i}C_{i}$ .

Algoritmer

Minimera genomsnittlig och viktad genomsnittlig slutförandetid

Minimering av den genomsnittliga slutförandetiden ( P|| $\sum C_{i}$ ) kan göras i polynomtid. SPT -algoritmen (Shortest Processing Time First), sorterar jobben efter deras längd, kortast först, och tilldelar dem sedan till processorn med den tidigaste sluttiden hittills. Den körs i tiden O( n log n ), och minimerar den genomsnittliga slutförandetiden på identiska maskiner, P|| $\sum C_{i}$ .

• Det kan finnas många SPT-scheman; att hitta SPT-schemat med den minsta sluttiden (även kallad OMFT – optimal medelsluttid ) är NP-svårt.

Att minimera den viktade genomsnittliga färdigställandetiden är NP-svårt även på identiska maskiner, genom att minska från ryggsäcksproblemet . Det är NP-svårt även om antalet maskiner är fixat och minst 2, genom reduktion från partitionsproblemet .

Sahni presenterar en exponentiell tidsalgoritm och ett polynom-tidsapproximationsschema för att lösa båda dessa NP-hårda problem på identiska maskiner:

• Optimal genomsnittlig slutförandetid;
• Viktad-genomsnittlig färdigställandetid.

Minimera den maximala slutförandetiden (makespan)

Att minimera den maximala slutförandetiden ( P|| $C_{\max }$ ) är NP-svårt även för identiska maskiner, genom reduktion från partitionsproblemet . Många exakta och approximativa algoritmer är kända.

Graham bevisade att:

• Alla listschemaläggningsalgoritmer (en algoritm som bearbetar jobben i en godtycklig fast ordning och schemalägger varje jobb till den första tillgängliga maskinen) är en $2-1/m$ approximation för identiska maskiner. Bindningen är tät för alla m . Denna algoritm körs i tiden O( n ).
• Den specifika listschemaläggningsalgoritmen som kallas $\displaystyle 4/3-1/3m}$ Processing Time First (LPT) , som sorterar jobben efter fallande längd, är en approximation för . Det kallas även girig nummerpartitionering .

Coffman, Garey och Johnson presenterade en annan algoritm som kallas multifit algorithm , med tekniker från bin packing , som har en approximationsfaktor på 13/11≈1,182.

Huang och Lu presenterade en enkel polynom-tidsalgoritm som uppnår en 11/9≈1,222 approximation i tiden O( m log m + n ), genom det mer allmänna problemet med maximin-share allokering av sysslor .

Sahni presenterade en PTAS som uppnår (1+ε)OPT i tiden $O(n\cdot (n^{2}/\epsilon )^{m- 1})$ . Det är en FPTAS om m är fast. För m=2 förbättras körtiden till $O(n^{2}/\epsilon )$ . Algoritmen använder en teknik som kallas intervallpartitionering .

Hochbaum och Shmoys presenterade flera approximationsalgoritmer för valfritt antal identiska maskiner (även när antalet maskiner inte är fast):

• För varje r >0, en algoritm med approximationsförhållande som mest (6/5+2 ^{− r} ) i tiden $O(n(r+\log {n}))$ .
• För varje r >0, en algoritm med approximationsförhållande som mest (7/6+2 ^{− r} ) i tiden $O(n(rm^{4}+ \log {n}))$ .
• För varje ε >0, en algoritm med approximationsförhållande som mest (1+ε) i tiden $O((n/\varepsilon )^{(1/ \varepsilon ^{2})})$ . Detta är en PTAS . Observera att när antalet maskiner är en del av inmatningen är problemet starkt NP-hårt , så ingen FPTAS är möjlig.

Leung förbättrade körtiden för denna algoritm till $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ .

Maximera den minsta slutförandetiden

Maximering av minsta färdigställandetid ( P|| $C_{\min }$ ) är tillämpligt när "jobben" faktiskt är reservdelar som krävs för att hålla maskinerna igång, och de har olika livslängder. Målet är att hålla maskinerna igång så länge som möjligt. LPT -algoritmen uppnår minst ${\frac {3m-1}{4m-2}}$ av det optimala.

Woeginger presenterade en PTAS som uppnår en approximationsfaktor på $1-{\varepsilon }$ i tiden $O(c_{\varepsilon }n\log {k} )$ , där $c_{\varepsilon }$ en enorm konstant som är exponentiell i den erforderliga approximationsfaktorn ε. Algoritmen använder Lenstras algoritm för linjär heltalsprogrammering .

Allmänna målfunktioner

Alon, Azar, Woeginger och Yadid överväger en mer allmän objektiv funktion. Givet en positiv reell funktion f , som endast beror på slutförandetiderna C _i , överväger de målen att minimera $\sum _{i=1}^{m}f( C_{i})$ , minimerar $\max _{i=1}^{m}f(C_{i})$ , maximerar $\sum _{i=1}^{m}f(C_{i})$$\min _{i=1} ^{m}f(C_{i})$ maximera . De bevisar att om f är icke-negativ, konvex och uppfyller ett starkt kontinuitetsantagande som de kallar "F*", så har båda minimeringsproblemen en PTAS. På liknande sätt, om f är icke-negativ, konkav och uppfyller F*, så har båda maximeringsproblemen en PTAS. I båda fallen är körtiden för PTAS O( n ), men med konstanter som är exponentiella i 1/ ε.

Se även

• Fernandez metod

externa länkar

• Sammanfattning av parallella maskinproblem utan förhand