Planowanie interwałowe

Szeregowanie interwałowe to klasa problemów w informatyce , szczególnie w obszarze projektowania algorytmów . Problemy dotyczą zestawu zadań. Każde zadanie jest reprezentowane przez interwał opisujący czas, w którym musi zostać przetworzone przez jakąś maszynę (lub równoważnie zaplanowane na jakiś zasób). Na przykład zadanie A może trwać od 2:00 do 5:00, zadanie B może trwać od 4:00 do 10:00, a zadanie C może trwać od 9:00 do 11:00. Podzbiór interwałów jest zgodny jeśli żadne dwa interwały nie nakładają się na maszynę/zasób. Na przykład podzbiór {A,C} jest zgodny, podobnie jak podzbiór {B}; ale ani {A,B}, ani {B,C} nie są zgodnymi podzbiorami, ponieważ odpowiednie przedziały w każdym podzbiorze nakładają się.

Problem maksymalizacji planowania interwałów (ISMP) polega na znalezieniu największego zgodnego zestawu, tj. zbioru nienakładających się przedziałów o maksymalnym rozmiarze. Celem jest tutaj wykonanie jak największej liczby zadań, czyli maksymalizacja przepustowości . Jest to równoważne znalezieniu maksymalnego zbioru niezależnego na wykresie przedziałowym .

Uogólnienie problemu $uwzględnia$ zasoby Tutaj celem jest znalezienie $podzbiorów$ , których związek jest największy.

W ulepszonej wersji problemu interwały są podzielone na grupy. Podzbiór przedziałów jest zgodny , jeśli żadne dwa przedziały się nie nakładają, a ponadto żadne dwa przedziały nie należą do tej samej grupy (tj. podzbiór zawiera co najwyżej jednego przedstawiciela każdej grupy). Każda grupa interwałów odpowiada pojedynczemu zadaniu i reprezentuje kilka alternatywnych interwałów, w których można je wykonać.

Problem decyzyjny planowania przedziałów grupowych (GISDP) polega na podjęciu decyzji, czy istnieje zgodny zestaw, w którym reprezentowane są wszystkie grupy. Celem jest tutaj wykonanie jednego reprezentatywnego zadania z każdej grupy. GISDPk to ograniczona wersja GISDP, w której liczba przedziałów w każdej grupie wynosi co najwyżej k .

Problem maksymalizacji harmonogramowania przedziałów grupowych (GISMP) polega na znalezieniu największego kompatybilnego zestawu - zbioru nienakładających się przedstawicieli o maksymalnym rozmiarze. Celem jest tutaj wykonanie reprezentatywnego zadania z jak największej liczby grup. GISMPk to ograniczona wersja GISMP, w której liczba przedziałów w każdej grupie wynosi co najwyżej k . Ten problem jest często nazywany JISPk, gdzie J oznacza Job .

GISMP to najbardziej ogólny problem; pozostałe dwa problemy można postrzegać jako szczególne przypadki:

• ISMP to szczególny przypadek, w którym każde zadanie należy do własnej grupy (tj. jest równe GISMP1).
• GISDP to problem z podjęciem decyzji, czy maksimum jest dokładnie równe liczbie grup.

Wszystkie te problemy można uogólnić, dodając wagę dla każdego przedziału, reprezentującą zysk z wykonania zadania w tym przedziale. Następnie celem jest maksymalizacja masy całkowitej.

Wszystkie te problemy są szczególnymi przypadkami planowania na jednej maszynie , ponieważ zakładają, że wszystkie zadania muszą być wykonywane na jednym procesorze. Planowanie dla pojedynczej maszyny to szczególny przypadek optymalnego planowania zadań .

Maksymalizacja planowania z pojedynczym interwałem

Nieważone

Kilka algorytmów, które na pierwszy rzut oka mogą wyglądać obiecująco, w rzeczywistości nie znajduje optymalnego rozwiązania:

• Wybór interwałów, które rozpoczynają się najwcześniej, nie jest rozwiązaniem optymalnym, ponieważ jeśli najwcześniejszy interwał jest bardzo długi, zaakceptowanie go spowodowałoby odrzucenie wielu innych krótszych próśb.
• Wybieranie najkrótszych interwałów lub wybieranie interwałów z najmniejszą liczbą konfliktów również nie jest optymalne.

Poniższy algorytm zachłanny , zwany planowaniem pierwszego terminu najwcześniejszego terminu , znajduje optymalne rozwiązanie dla nieważonego planowania z pojedynczym przedziałem czasowym:

1. Wybierz interwał, x , z najwcześniejszym czasem zakończenia .
2. Usuń x i wszystkie przedziały przecinające x ze zbioru przedziałów kandydujących.
3. Powtarzaj, aż zestaw przedziałów kandydujących będzie pusty.

Ilekroć wybierzemy interwał w kroku 1, być może będziemy musieli usunąć wiele interwałów w kroku 2. Jednak wszystkie te interwały koniecznie przecinają czas końcowy x , a zatem wszystkie przecinają się ze sobą (patrz rysunek). Dlatego co najwyżej 1 z tych przedziałów może być rozwiązaniem optymalnym. Stąd dla każdego przedziału w rozwiązaniu optymalnym istnieje przedział w rozwiązaniu zachłannym. Dowodzi to, że algorytm zachłanny rzeczywiście znajduje rozwiązanie optymalne.

Bardziej formalne wyjaśnienie podaje argument ładowania .

Algorytm zachłanny może być wykonywany w czasie O( n log n ), gdzie n jest liczbą zadań, przy użyciu etapu przetwarzania wstępnego, w którym zadania są sortowane według czasu ich zakończenia.

Ważony

Gdy przedziały mają wagi, problem jest równoważny znalezieniu niezależnego zestawu o maksymalnej wadze na wykresie przedziałowym . Można go rozwiązać w czasie wielomianowym.

Aby znaleźć maksymalną wagę harmonogramu pojedynczego interwału w czasie Θ(n), wykonaj następujący pseudokod:

    
    
    
   
  // Wektory są już posortowane od najwcześniejszego do najpóźniejszego czasu zakończenia.  int  v  [  liczbaWektorów  +  1  ];  // lista wektorów przedziałów  int  w  [  numOfVectors  +  1  ];  // w[j] to waga dla v[j].  int  p  [  liczbaWektorów  +  1  ];  // p[j] to liczba wektorów, które kończą się przed początkiem v[j].  int  M  [  liczbaWektorów  +  1  ];  int  końcowy Harmonogram 


0  0 0  0 0  0

           
         [];  // v[0] nie istnieje. Pierwszy wektor interwału jest ustawiony na v[1].   w  [  ]  =  ;  p  [  ]  =  ;  M  [  ]  =  ;  for  (  int  i  =  1  ;  i  <  liczbaWektora  +  1  ;  i  ++  )  {  M  [  i  ]  =  max  (  w  [  ja  ]  +  M    




  
       0   
            [  p  [  ja  ]],  M  [  ja  -  1  ]);  }  // Maksymalna waga harmonogramu jest równa M[liczbaWektorów + 1].  harmonogram  (  j  )  {  jeśli  (  j  ==  )  {  powrót  ;  }  else  if  (  w  [  j  ]  +  M  [  p  [  j  ]]  >=  M  [  j  -  
          
        
          
 1  ]) {  przedstaw  (  v  [  j  ],  finalSchedule  );  // dołącza v[j] do harmonogramu.  harmonogram  (  p  [  j  ]);  }  else  {  harmonogram  (  j  -  1  );  }  } 

Decyzja o harmonogramie grupowym

NP-zupełne, gdy niektóre grupy zawierają 3 lub więcej przedziałów

GISDPk jest NP-zupełny, gdy ${\ Displaystyle k \ geq 3}$ , nawet jeśli wszystkie przedziały mają tę samą długość. Można to wykazać poprzez redukcję z następującej wersji problemu spełnialności Boole'a , który okazał się NP-zupełny, podobnie jak wersja nieograniczona.

Niech ${\ Displaystyle X = \ {x_ {1}, x_ {2}, \ kropki, x_ {p} \}}$ będzie zbiorem zmiennych boolowskich. Niech ${\ Displaystyle C = \ {c_ {1}, c_ {2}, \ kropki, c_ {q} \}}$ będzie zbiorem klauzul nad X takimi że (1) każda klauzula w C ma co najwyżej trzy literały i (2) każda zmienna jest ograniczona do jednego lub dwóch wystąpień dodatnich i raz negatywnych ogólnie w C . Zdecyduj, czy istnieje takie przypisanie do zmiennych X , że każda klauzula w C ma co najmniej jeden prawdziwy literał.

Biorąc pod uwagę wystąpienie tego problemu spełnialności, skonstruuj następujące wystąpienie GISDP. Wszystkie interwały mają długość 3, więc wystarczy przedstawić każdy interwał przez czas jego rozpoczęcia:

• Dla każdej zmiennej $($ i = 1 , ..., ) $p$ grupę z dwoma przedziałami: jeden reprezentujący przypisanie $\ Displaystyle x_ {i} = \ operatorname {fałsz}} )$ i inne zaczynające się od ${\ Displaystyle 50i + 10}$ (reprezentujące zadanie ${\ Displaystyle x_ {i} = \ operatorname {prawda}}$ ).
• Dla każdej klauzuli $\ displaystyle c_ {j}$ dla } = 1, ..., q ) utwórz grupę z następującymi przedziałami: do jot {
  • $50$ zmiennej , która pojawia się dodatnio po raz pierwszy w C - przedział zaczynający się od $\ displaystyle 50i-12}$ .
  • Dla każdej zmiennej $50$ pojawia się dodatnio po raz drugi w C - przedział zaczynający się od $\ displaystyle 50i-8}$ . Zauważ, że oba te przedziały $\ operatorname$ przedział związany z $false$ }
  • Dla każdej zmiennej $50$ która pojawia się ujemnie - przedział zaczynający się od $\ displaystyle 50i + 8$ . Ten $}}$$}$ \ displaystyle .

Należy zauważyć, że interwały w grupach powiązanych z różnymi klauzulami nie zachodzą na siebie. Jest to zapewnione, ponieważ zmienna pojawia się najwyżej dwa razy pozytywnie i raz negatywnie.

Skonstruowany GISDP ma wykonalne rozwiązanie (tj. szeregowanie, w którym każda grupa jest reprezentowana), wtedy i tylko wtedy, gdy dany zestaw klauzul boolowskich ma satysfakcjonujące przypisanie. Stąd GISDP3 jest NP-zupełny, podobnie jak GISDPk dla każdego ${\ displaystyle k \ geq 3}$ .

Wielomian, gdy wszystkie grupy zawierają co najwyżej 2 przedziały

GISDP2 można rozwiązać w czasie wielomianowym poprzez następującą redukcję do problemu spełnialności 2 :

• $y_ {i}}$ każdej grupy tworzę dwie zmienne reprezentujące jej dwa przedziały: $ja$ displaystyle .
• ${x_ {i}} \$ każdej grupy ja utwórz klauzule: $ja$ { , które reprezentują stwierdzenie, że należy wybrać dokładnie jeden z tych dwóch przedziałów.
• Dla każdych dwóch przecinających się przedziałów (tj. ${\ Displaystyle \ neg {x_ {i} }\cup \neg {y_{j}}}$$Displaystyle y_$${j}}$ \ ) utwórz klauzulę: , które reprezentują stwierdzenie, że należy wybrać co najwyżej jeden z tych dwóch przedziałów.

Ta konstrukcja zawiera co najwyżej klauzule O( n ² ) (po jednej dla każdego przecięcia przedziałów plus dwa dla każdej grupy). Każda klauzula zawiera 2 literały. O spełnialności takich formuł można zdecydować w czasie liniowo względem liczby klauzul (patrz 2-SAT ). Dlatego GISDP2 można rozwiązać w czasie wielomianowym.

Maksymalizacja planowania interwałów grupowych

MaxSNP-complete, gdy niektóre grupy zawierają 2 lub więcej interwałów

GISMPk jest NP-zupełny nawet wtedy, gdy ${\ Displaystyle k \ geq 2}$ .

Co więcej, GISMPk jest MaxSNP -kompletny, tj. nie ma PTAS, chyba że P=NP. Można to udowodnić, pokazując redukcję zachowującą przybliżenie z MAX 3-SAT-3 do GISMP2.

Wielomian 2-aproksymacja

Poniższy algorytm zachłanny znajduje rozwiązanie, które zawiera co najmniej 1/2 optymalnej liczby przedziałów:

1. Wybierz interwał, x , z najwcześniejszym czasem zakończenia .
2. Usuń x i wszystkie przedziały przecinające x oraz wszystkie przedziały w tej samej grupie x ze zbioru przedziałów kandydujących.
3. Kontynuuj, aż zestaw przedziałów kandydujących będzie pusty.

Formalne wyjaśnienie podaje argument ładowania .

Współczynnik przybliżenia równy 2 jest ciasny. Na przykład w następującej instancji GISMP2:

• Grupa nr 1: {[0..2], [4..6]}
• Grupa nr 2: {[1..3]}

Algorytm zachłanny wybiera tylko 1 interwał [0..2] z grupy 1, podczas gdy optymalne szeregowanie polega na wybraniu [1..3] z grupy 2, a następnie [4..6] z grupy 1.

Bardziej ogólny algorytm aproksymacji osiąga aproksymację dwuczynnikową dla przypadku ważonego.

Algorytmy aproksymacji oparte na LP

Wykorzystując technikę relaksacji programowania liniowego , możliwe jest przybliżenie optymalnego szeregowania z nieco lepszymi współczynnikami aproksymacji. Współczynnik aproksymacji pierwszego takiego algorytmu wynosi asymptotycznie 2, gdy k jest duże, ale gdy k=2 algorytm osiąga współczynnik aproksymacji 5/3. Współczynnik aproksymacji dla dowolnego k został później poprawiony do 1,582.

Powiązane problemy

Problem planowania interwałów można opisać za pomocą wykresu przecięcia , gdzie każdy wierzchołek jest przedziałem, a między dwoma wierzchołkami istnieje krawędź wtedy i tylko wtedy, gdy ich przedziały się pokrywają. W tej reprezentacji problem planowania interwałowego jest równoważny znalezieniu maksymalnego niezależnego zestawu na tym wykresie przecięcia. Znalezienie maksymalnego zbioru niezależnego jest NP-trudne na ogólnych grafach, ale można to zrobić w czasie wielomianowym w szczególnym przypadku grafów przecięcia (ISMP).

Problem szeregowania przedziałów grupowych (GISMPk) można opisać za pomocą podobnego wykresu przecięć przedziałów, z dodatkowymi krawędziami między każdymi dwoma przedziałami tej samej grupy, tj. kliki wielkości k .

Wariacje

Ważną klasą algorytmów szeregowania jest klasa dynamicznych algorytmów priorytetów. Gdy żaden z przedziałów się nie pokrywa, optymalne rozwiązanie jest trywialne. Optymalne dla wersji nieważonej można znaleźć przy najwcześniejszym terminie pierwszego planowania . Planowanie z ważonymi interwałami to uogólnienie, w którym każdemu wykonywanemu zadaniu przypisywana jest wartość, a celem jest maksymalizacja całkowitej wartości. Rozwiązanie nie musi być unikalne.

Problem planowania interwałowego jest jednowymiarowy – istotny jest tylko wymiar czasowy. Problem maksymalnego zbioru rozłącznego jest uogólnieniem na 2 lub więcej wymiarów. To uogólnienie również jest NP-zupełne.

Inną odmianą jest alokacja zasobów, w której zestaw interwałów s jest planowany przy użyciu zasobów k tak, że k jest zminimalizowane. Oznacza to, że wszystkie interwały muszą być zaplanowane, ale celem jest zminimalizowanie zużycia zasobów.

Inną odmianą jest sytuacja, gdy jest m procesorów zamiast jednego procesora. Oznacza to, że m różnych zadań może działać równolegle. Zobacz planowanie identycznych maszyn .

Bardzo podobnym problemem jest również planowanie dla pojedynczej maszyny .