Schemaläggning av enhetliga maskiner

Enhetlig maskinschemaläggning (även kallad enhetligt relaterad maskinschemaläggning eller relaterad maskinschemaläggning ) är ett optimeringsproblem inom datavetenskap och operationsforskning . Det är en variant av optimal jobbschemaläggning . Vi får n jobb J ₁ , J ₂ , ..., J _n med varierande bearbetningstider, som behöver schemaläggas på m olika maskiner. Målet är att minimera makespan - den totala tiden som krävs för att genomföra schemat. Den tid som maskin i behöver för att bearbeta jobb j betecknas med p _i,j . I det allmänna fallet är tiderna pi _,j orelaterade, och vilken matris som helst med positiva behandlingstider är möjlig. I den specifika varianten som kallas enhetlig maskinschemaläggning är vissa maskiner enhetligt snabbare än andra. Detta betyder att det för varje maskin i si _finns en hastighetsfaktor , och körtiden för jobb j på maskin i är p _i,j = p _j / s _i .

I standardnotationen med tre fält för optimala jobbschemaläggningsproblem, betecknas enhetsmaskinvarianten med Q i det första fältet. Till exempel är problemet betecknat med " Q|| $C_{\max }$ " ett enhetligt maskinschemaläggningsproblem utan några begränsningar, där målet är att minimera den maximala slutförandetiden. Ett specialfall av enhetlig maskinschemaläggning är identisk maskinschemaläggning , där alla maskiner har samma hastighet. Denna variant betecknas med P i det första fältet.

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 Q|| $\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 Q|| $\sum w_{i}C_{i}$ .

Algoritmer

Minimerar den genomsnittliga slutförandetiden

Minimering av den genomsnittliga slutförandetiden 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}$ .
• Horowitz och Sahni presenterar en exakt algoritm, med körtid O( n log mn ), för att minimera den genomsnittliga slutförandetiden på enhetliga maskiner, Q|| $\sum C_{i}$ .
• Bruno, Coffman och Sethi presenterar en algoritm som körs i tiden ${\displaystyle O(\max(mn^{2},n^{3}))} ,$ för att minimera genomsnittlig färdigställandetid på icke-relaterade maskiner, R|| $\sum C_{i}$ .

Minimera den viktade genomsnittliga slutförandetiden

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 en polynom-tidsapproximationsalgoritm för identiska maskiner.

Horowitz och Sahni presenterade:

• Exakta dynamiska programmeringsalgoritmer för att minimera den viktade genomsnittliga slutförandetiden på enhetliga maskiner. Dessa algoritmer körs i exponentiell tid.
• Polynom-tidsapproximationsscheman , som för alla ε >0, uppnår som mest (1+ε)OPT. För att minimera den viktade genomsnittliga slutförandetiden på två enhetliga maskiner är körtiden $O(10^{l}n^{2})$ = ${ \displaystyle O(n^{2}/\epsilon )}$ , så det är en FPTAS. De hävdar att deras algoritmer lätt kan utökas för hur många enhetliga maskiner som helst, men analyserar inte körtiden i detta fall. De presenterar inte en algoritm för viktad genomsnittlig slutförandetid på icke-relaterade maskiner.

Minimera den maximala slutförandetiden (makespan)

Att minimera den maximala slutförandetiden är NP-svårt även för identiska maskiner, genom att reducera partitionsproblemet .

En konstantfaktorapproximation uppnås av algoritmen längsta bearbetningstid-först ( LPT).

Horowitz och Sahni presenterade:

• Exakta dynamiska programmeringsalgoritmer för att minimera den maximala slutförandetiden på både enhetliga och orelaterade maskiner. Dessa algoritmer körs i exponentiell tid (kom ihåg att dessa problem alla är NP-hårda).
• Polynom-tidsapproximationsscheman , som för alla ε >0, uppnår som mest (1+ε)OPT. För att minimera den maximala slutförandetiden på två enhetliga maskiner körs deras algoritm i tiden ${\displaystyle O(10^{2l}n)} ,$ där $l$ är det minsta heltal för vilket $\epsilon \geq 2\cdot 10^{-l}$ . Därför är körtiden i ${\displaystyle O(n/\epsilon ^{2})} ,$ så det är en FPTAS . För att minimera den maximala slutförandetiden på två orelaterade maskiner är körtiden $O(10^{l}n^{2})$ = ${\ displaystyle O(n^{2}/\epsilon )}$ . De hävdar att deras algoritmer lätt kan utökas för hur många enhetliga maskiner som helst, men analyserar inte körtiden i detta fall.

Hochbaum och Shmoys presenterade flera approximationsalgoritmer för valfritt antal identiska maskiner . Senare utvecklade de en PTAS för enhetliga maskiner.

Epstein och Sgall generaliserade PTAS för enhetliga maskiner för att hantera mer allmänna objektiva funktioner. Låt C _i (för i mellan 1 och m ) vara fabrikatet av maskin i i ett givet schema. Istället för att minimera objektivfunktionen max( Ci _, ) kan man minimera objektivfunktionen max( f ( C _{i ))} där f är vilken fast funktion som helst. På liknande sätt kan man minimera den objektiva funktionen summa( f ( C _i )).

Monotonicitet och sanningsenlighet

I vissa inställningar är maskinhastigheten maskinens privata information, och vi vill uppmuntra maskiner att avslöja deras verkliga hastighet, det vill säga vi vill ha en sanningsenlig mekanism . En viktig faktor för att uppnå sanningsenlighet är monotoni . Det betyder att om en maskin rapporterar en högre hastighet, och alla andra ingångar förblir desamma, så ökar den totala bearbetningstiden som allokeras till maskinen svagt. För detta problem:

• Auletta, De Prisco, Penna och Persiano presenterade en 4-approximations monoton algoritm, som körs i polytime när antalet maskiner är fast.
• Ambrosio och Auletta bevisade att algoritmen för längsta bearbetningstid är monoton närhelst maskinhastigheterna är potenser på c ≥ 2, men inte när c ≤ 1,78. Däremot listschemaläggning inte monoton för c > 2.
• Andelman, Azar och Sorani presenterade en 5-approximations monoton algoritm, som körs i polytime även när antalet maskiner är variabelt.
• Kovacz presenterade en 3-approximations monoton algoritm.

Tillägg

Beroende jobb : I vissa fall kan jobben vara beroende. Ta till exempel fallet med att läsa användaruppgifter från konsolen, använd den sedan för att autentisera, och om autentiseringen lyckas visa några data på konsolen. Uppenbarligen är en uppgift beroende av en annan. Detta är ett tydligt fall där det finns någon form av ordning mellan uppgifterna. I själva verket är det tydligt att det kan modelleras med partiell beställning . Då, per definition, utgör uppsättningen av uppgifter en gitterstruktur . Detta lägger till ytterligare komplikationer till schemaläggningsproblemet med flera processorer.

Statisk kontra dynamisk : Maskinschemaläggningsalgoritmer är statiska eller dynamiska. En schemaläggningsalgoritm är statisk om schemaläggningsbesluten om vilka beräkningsuppgifter som kommer att tilldelas vilka processorer som görs innan programmet körs. En algoritm är dynamisk om den tas vid körning. För statiska schemaläggningsalgoritmer är ett typiskt tillvägagångssätt att rangordna uppgifterna enligt deras prioritetsförhållanden och använda en listschemaläggningsteknik för att schemalägga dem på processorerna.

Flerstegsjobb : I olika inställningar kan varje jobb ha flera operationer som måste utföras parallellt. Vissa sådana inställningar hanteras av schemaläggning för öppen butik , schemaläggning av flödesbutiker och schemaläggning av jobbbutiker .

externa länkar

• Sammanfattning av parallella maskinproblem utan förhand