Planowanie listy

Planowanie listy to zachłanny algorytm planowania identycznych maszyn . Dane wejściowe do tego algorytmu to lista zadań, które powinny zostać wykonane na zbiorze m maszyn. Lista jest uporządkowana w ustalonej kolejności, którą można określić np. priorytetem wykonywania zadań lub kolejnością ich nadejścia. Algorytm wielokrotnie wykonuje następujące kroki, aż do uzyskania prawidłowego harmonogramu:

• Zajmij się pierwszą pracą z listy (tą o najwyższym priorytecie).
• Znajdź maszynę, która jest dostępna do wykonania tego zadania.
  • Jeśli zostanie znaleziona maszyna, zaplanuj to zadanie na tej maszynie.
  • W przeciwnym razie (brak odpowiedniej maszyny) wybierz następne zlecenie z listy.

Przykład

Załóżmy, że istnieje pięć zadań o czasach przetwarzania {4,5,6,7,8} i m = 2 procesorach. Wtedy wynikowy harmonogram to {4,6,8}, {5,7}, a makespan to max(18,12)=18; jeśli m =3, to wynikowy harmonogram to {4,7}, {5,8}, {6}, a makespan to max(11,13,6)=13.

Gwarancja wydajności

Algorytm działa w $n$ , gdzie liczba Algorytm zawsze zwraca podział zadań, których przedział czasowy jest co najwyżej ${\ displaystyle 2-1/m}$ razy większy od optymalnego przedziału czasowego. Wynika to z faktu, że zarówno długość najdłuższej pracy, jak i średnia długość wszystkich prac są dolnymi granicami optymalnego rozpiętości. Algorytm może być używany jako algorytm online , gdy nie można kontrolować kolejności nadejścia przedmiotów.

Strategie zamawiania

Zamiast korzystać z arbitralnego zamówienia, można wstępnie zamówić zadania, aby uzyskać lepsze gwarancje. Niektóre znane strategie planowania list to:

• Algorytm pierwszego poziomu najwyższego poziomu lub HLF;
• najdłuższej ścieżki lub LP;
• Planowanie z najdłuższym czasem przetwarzania lub LPT; ten wariant zmniejsza współczynnik aproksymacji do ${\ Displaystyle {\ Frac {4} {3}} - {\ Frac {1} {3k}}}$ .
• Metoda ścieżki krytycznej .
• Heterogeniczny najwcześniejszy czas zakończenia lub HEFT. W przypadku pracowników heterogenicznych.

Anomalie

Algorytm planowania listy ma kilka anomalii. Załóżmy, że jest m = 3 maszyn, a długość pracy to:

3, 2, 2, 2, 4, 4, 4, 4, 9

Załóżmy ponadto, że wszystkie zadania „4” muszą zostać wykonane po czwartym zadaniu „2”. Następnie planowanie listy zwraca następujący harmonogram:

• 3, 9
• 2, 2, 4, 4
• 2, [2 bezczynny], 4, 4

a rozpiętość wynosi 12.

Anomalia 1 . Jeśli zadania „4” nie zależą już od poprzednich zadań, harmonogram listy wygląda następująco:

• 3, 4, 9
• 2, 2, 4
• 2, 4, 4

a makespan wynosi 16. Usunięcie zależności powiększyło makespan.

Anomalia 2 . Załóżmy, że długość zadania zmniejsza się o 1, do 2, 1, 1, 1, 3, 3, 3, 3, 8 (z oryginalnymi zależnościami). Następnie harmonogram listy jest następujący:

• 2, 3, 3
• 1, 1, 3, 8
• 1, [1 bezczynny], 3

a makespan wynosi 13. Skrócenie wszystkich zadań zwiększyło makespan.

Anomalia 3 . Załóżmy, że istnieje jeszcze jedna maszyna (z oryginalnymi długościami, z zależnościami lub bez). Następnie harmonogram listy jest następujący:

• 3, 4
• 2, 4, 9
• 2, 4
• 2, 4

a makespan wynosi 15. Dodanie maszyny zwiększyło makespan.

Anomalie są ograniczone w następujący sposób. Załóżmy, że początkowo mieliśmy m ₁ maszyn, a rozpiętość wynosiła t ₁ . Teraz mamy m ₂ maszyn, zależności są takie same lub złagodzone, długości zadań są takie same lub krótsze, lista jest taka sama lub inna, a makespan to t 2. _Wtedy :

${\ Displaystyle {\ Frac {t_ {2}} {t_ {1}}} \ równoważnik 1 + {\ Frac {k_ {1} -1} {k_ { 2}}}}$ .

W szczególności przy tej samej liczbie maszyn stosunek ten wynosi ${\ displaystyle 2- {\ frac {1} {m}}}$ . Szczególnym przypadkiem jest sytuacja, gdy pierwotny harmonogram jest optymalny; $_$ ograniczenie .