Parallell uppgiftsschemaläggning

Parallell uppgiftsschemaläggning (även kallad parallell jobbschemaläggning eller parallell bearbetningsschemaläggning ) är ett optimeringsproblem inom datavetenskap och operationsforskning . Det är en variant av optimal jobbschemaläggning . I ett allmänt jobbschemaläggningsproblem får vi n jobb J ₁ , J ₂ , ..., J _n med varierande bearbetningstider, som måste schemaläggas på m maskiner samtidigt som man försöker minimera omfattningen - schemats totala längd (det vill säga när alla jobb är klara). I den specifika varianten som kallas parallell-uppgiftsschemaläggning är alla maskiner identiska. Varje jobb j har _j en längdparameter p _j och en storleksparameter q j _, och den måste köras i exakt p tidssteg på exakt q _j maskiner parallellt .

Veltman et al. och Drozdowski betecknar detta problem med $P|size_{j}|C_{\max }$ i trefältsnotationen introducerad av Graham et al. P betyder att det finns flera identiska maskiner som körs parallellt; storlek _j betyder att varje jobb har en storleksparameter; C _max betyder att målet är att minimera den maximala färdigställandetiden. Vissa författare använder $P|m_{j}|C_{\max }$ istället. Observera att problemet med schemaläggning av parallella maskiner är ett specialfall av schemaläggning av parallella uppgifter där $size_{j}=1$ för alla j , det vill säga varje jobb ska köras på en enda maskin.

$3/2}$ \ om inte $P=NP$ .

Definition

Det finns en uppsättning ${\mathcal {J}}$ av $n$ jobb och $m$ identiska maskiner. Varje jobb $j\in {\mathcal {J}}$ har en bearbetningstid $p_{j}\in \mathbb {N}$ (kallas även längden på j ) , och kräver samtidig användning av $q_{j}\in \mathbb {N}$ maskiner under dess körning (även kallad storleken eller bredden av j).

Ett schema tilldelar varje jobb $j\in {\mathcal {J}}$ till en starttid $s_{j}\in \mathbb {N} _{0}$ och en mängd $m_{j}\subseteq \{1,\dots ,m\}$ av $|m_{j}|=q_{j}$ maskiner som ska bearbetas på. Ett schema är genomförbart om varje processor utför högst ett jobb åt gången. Målet med problemet som anges av $P|size_{j}|C_{\max }$ är att hitta ett schema med minsta längd ${\displaystyle C_{\max }=\ max _{j\in {\mathcal {J}}}(s_{j}+p_{j})} ,$ även kallad makespan av schemat. Ett tillräckligt villkor för genomförbarheten av ett schema är följande

$\sum _{j\in {\mathcal {J}},s_ {j}\leq t<s_{j}+p_{j}}q_{j}\leq m\,\forall t\in \{s_{1},\dots ,s_{n}\}$ .

Om den här egenskapen är uppfylld för alla starttider, kan ett genomförbart schema genereras genom att tilldela lediga maskiner till jobben vid varje tidpunkt som börjar med tiden t = {\ $=0}$ . Dessutom kan antalet maskinintervall som används av jobb och lediga intervall vid varje tidssteg begränsas av $|{\mathcal {J}}|+1$ . Här är ett maskinintervall en uppsättning på varandra följande maskiner med maximal kardinalitet så att alla maskiner i denna uppsättning bearbetar samma jobb. Ett maskinintervall specificeras helt av indexet för dess första och sista maskin. Därför är det möjligt att erhålla ett kompakt sätt att koda utdata med polynomstorlek.

Beräkningshårdhet

Det här problemet är NP-svårt även när det bara finns två maskiner och storleken på alla jobb är $q_{j}=1$ (dvs varje jobb behöver bara köras på en enda maskin). Detta specialfall, betecknat med ${\displaystyle P2||C_{\max }} ,$ är en variant av partitionsproblemet , som är känt för att vara NP-hårt.

När antalet maskiner m är högst 3, det vill säga: för varianterna $P2|size_{j}|C_{\max }$ och $P3|size_{j}|C_{\max }$ , det finns en pseudopolynomisk tidsalgoritm, som löser problemet exakt.

Däremot, när antalet maskiner är minst 4, det vill säga: för varianterna $Pm|size_{j}|C_{\max }$ för alla $m\geq 4$ , problemet är också starkt NP-hårt (det här resultatet förbättrade ett tidigare resultat som visade stark NP -hårdhet för $m\geq 5$ ).

Om antalet maskiner inte begränsas av en konstant, kan det inte finnas någon approximationsalgoritm med ett approximationsförhållande som är mindre än $3/2$ om inte $\displaystyle P=NP$ . Detta gäller även för det speciella fallet där bearbetningstiden för alla jobb är $p_{j}=1$ , eftersom detta specialfall är ekvivalent med soppackningsproblemet : varje tidssteg motsvarar en bin, m är fackstorleken, varje jobb motsvarar en artikel med storlek q _j , och minimering av makespan motsvarar att minimera antalet fack.

Varianter

Flera varianter av detta problem har studerats. Följande varianter har också övervägts i kombination med varandra.

Sammanhängande jobb : I denna variant har maskinerna en fast ordning $(M_{1},\dots ,M_{m})$ . Istället för att tilldela jobben till någon delmängd $m_{j}\subseteq \{M_{1},\dots ,M_{m}\}$ har jobben ska tilldelas ett sammanhängande intervall av maskiner. Detta problem motsvarar problemformuleringen av bandpackningsproblemet .

Flera plattformar: I denna variant är uppsättningen maskiner uppdelad i oberoende plattformar. Ett schemalagt jobb kan bara använda maskinerna på en plattform och får inte sträcka sig över flera plattformar när det bearbetas.

Formbara jobb : I denna variant har varje jobb $j\in {\mathcal {J}}$ en uppsättning möjliga maskinräkningar $D_{j}\ subseteq \{1,\dots m\}$ . För varje räkning $d\in D_{j}$ , kan jobbet bearbetas på d maskiner parallellt, och i detta fall kommer dess behandlingstid att vara $p_{j ,d}$ . För att schemalägga ett jobb $j\in {\mathcal {J}}$ måste en algoritm välja ett maskinantal $d\in D_{j}$ och tilldela j till en starttid $s_{j}$ och till $d$ maskiner under tidsintervallet $[s_{j},s_{j}+p_{j,d}).$ Ett vanligt antagande för denna typ av problem är att den totala arbetsbelastningen för ett jobb, som definieras som $d\cdot p_{j,d}$ , ökar inte för ett ökande antal maskiner.

Releasedatum : I denna variant, betecknad med ${\displaystyle P|size_{j},r_{j}|C_{\max }} ,$ alla jobb är inte tillgängliga vid tidpunkten 0; varje jobb j blir tillgänglig vid en fast och känd tid r _j . Det måste schemaläggas efter den tiden.

Preemption : I denna variant, betecknad med ${\displaystyle P|size_{j},r_{j},{\text{pmtn}}|C_{\max }} , det är möjligt att avbryta jobb som redan körs$ och schemalägga andra jobb som blir tillgängliga vid den tiden.

Algoritmer

Listschemaläggningsalgoritmen av Garey och Graham har ett absolut förhållande ${\displaystyle 2},$ som påpekats av Turek et al. och Ludwig och Tiwari. Feldmann, Sgall och Teng observerade att längden på ett icke-förebyggande schema som produceras av listschemaläggningsalgoritmen faktiskt är högst ( $\displaystyle (2-1/m)}$ gånger det optimala förebyggande intervallet. Ett polynom-tidsapproximationsschema (PTAS) för det fall då antalet $m$ av processorer är konstant, betecknat med $Pm|size_{j}|C_{\max }$ presenterades av Amoura et al. och Jansen et al. Senare hittade Jansen och Thöle en PTAS för fallet där antalet processorer är polynomiellt begränsat i antalet jobb. I denna algoritm visas antalet maskiner polynomiskt i algoritmens tidskomplexitet. Eftersom antalet maskiner i allmänhet endast visas i logaritmisk storlek i instansens storlek, är denna algoritm också ett pseudopolynomiskt tidsapproximationsschema. En $(3/2+\varepsilon )$ -approximation gavs av Jansen, vilket stänger gapet till den nedre gränsen på $\displaystyle 3/2}$ förutom en liten $\varepsilon$ .

Skillnader mellan sammanhängande och icke sammanhängande jobb

Med tanke på en instans av problemet med schemaläggning av parallella uppgifter, kan det optimala fabrikatet variera beroende på begränsningen för maskinernas närhet. Om jobben kan schemaläggas på icke sammanhängande maskiner, kan det optimala fabrikatet vara mindre än i fallet att de måste schemaläggas på sammanhängande. Skillnaden mellan sammanhängande och icke-sammanhängande scheman har först demonstrerats 1992 på en instans med $n=8$ uppgifter, $m=23$ processorer, ${ \displaystyle C_{\max }^{nc}=17}$ och $C_{\max }^{c}=18$ . Błądek et al. studerade dessa så kallade c/nc-skillnader och bevisade följande punkter:

• För att ac/nc-skillnad ska uppstå måste det finnas minst tre uppgifter med $q_{j}>1.$
• För att ac/nc-skillnad ska uppstå måste det finnas minst tre uppgifter med $p_{j}>1.$
• krävs minst ${\displaystyle m=4} -processorer (och det finns en instans med ac/nc-skillnad med$$m=4$ ).
• För att ac/nc-skillnad ska uppstå måste den icke-sammanhängande schemalängden vara minst $C_{\max }^{nc}=4.$
• Den maximala c/nc-skillnaden $\sup _{I}C_{\max }^{c}(I)/C_{\max } ^{nc}(I)$ är minst $5/4$ högst $\displaystyle 2.}$
• Att avgöra om det finns en c/nc-skillnad i en given instans är NP-komplett.

Dessutom föreslog de följande två gissningar, som förblir obevisade:

• krävs minst ${\displaystyle n=7} uppgifter.$
• $\sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc }(I)=5/4$

Relaterade problem

Det finns relaterade schemaläggningsproblem där varje jobb består av flera operationer, som måste utföras i följd (snarare än parallellt). Dessa är problemen med schemaläggning av öppen butik , schemaläggning av flödesbutiker och schemaläggning av jobbbutiker .