Planowanie niepowiązanych maszyn

Planowanie niepowiązanych maszyn jest problemem optymalizacji w informatyce i badaniach operacyjnych . Jest to wariant optymalnego planowania pracy . Musimy zaplanować n zadań J ₁ , J ₂ , ..., J _n na m różnych maszynach, tak aby pewna funkcja celu była zoptymalizowana (zwykle należy zminimalizować rozpiętość ). Czas, w którym maszyna I potrzeb do wykonania zadania j oznaczamy pi _,j . Termin niezwiązany podkreśla, że ​​nie ma związku między wartościami p _i,j dla różnych i oraz j . Kontrastuje to z dwoma szczególnymi przypadkami tego problemu: szeregowaniem jednostajnych maszyn — w którym p _i,j = p _i / s _j (gdzie s _j jest prędkością maszyny j ) oraz szeregowaniem maszyn identycznych - w którym p _i,j = p _i (ten sam czas pracy na wszystkich maszynach).

W standardowej trójpolowej notacji dla problemów z optymalnym planowaniem zadań wariant niepowiązanych maszyn jest oznaczony przez R w pierwszym polu. Na przykład problem oznaczony przez „ to problem z planowaniem niepowiązanych maszyn bez ograniczeń, w którym celem jest zminimalizowanie $maksymalnego$ czasu

W niektórych wariantach problemu, zamiast minimalizowania maksymalnego czasu realizacji, pożądana jest minimalizacja średniego czasu realizacji (uśrednionego dla wszystkich n zadań); jest oznaczony przez R|| ${\ Displaystyle \ suma C_ {i}}$ . Bardziej ogólnie, gdy niektóre prace są ważniejsze od innych, może być pożądane zminimalizowanie średniej ważonej czasu ukończenia, gdzie każda praca ma inną wagę. Jest to oznaczone przez R|| ${\ Displaystyle \ suma w_ {i} C_ {i}}$ .

$wariancie$ trzecim celem jest maksymalizacja minimalnego czasu ukończenia Wariant ten odpowiada problemowi egalitarnej alokacji przedmiotów .

Algorytmy

Minimalizacja maksymalnego czasu realizacji (makespan)

Minimalizacja maksymalnego czasu ukończenia jest NP-trudna nawet dla identycznych maszyn, poprzez redukcję problemu partycji .

Horowitz i Sahni przedstawili:

• Dokładne algorytmy programowania dynamicznego w celu zminimalizowania maksymalnego czasu realizacji zarówno na jednolitych, jak i niezwiązanych ze sobą maszynach. Algorytmy te działają w czasie wykładniczym (przypomnijmy, że wszystkie te problemy są NP-trudne).
• Schematy aproksymacji w czasie wielomianowym , które dla dowolnego ε > 0 osiągają co najwyżej (1+ε)OPT. Aby zminimalizować maksymalny czas ukończenia na dwóch jednorodnych maszynach, ich algorytm działa w czasie , gdzie jest najmniejszą liczbą całkowitą, dla której jest . $^ {2l} n)}$$Displaystyle O ($${\ Displaystyle \ epsilon \ geq 2 \ cdot 10 ^ {- l}}$ . $_$ czas wykonywania to FPTAS Aby zminimalizować maksymalny czas ukończenia na dwóch niepowiązanych ze sobą komputerach, czas wykonania wynosi ${\ Displaystyle O (10 ^ {l} n ^ {2})}$ = ${\ styl wyświetlania O(n^{2}/\epsilon )}$ . Twierdzą, że ich algorytmy można łatwo rozszerzyć na dowolną liczbę jednorodnych maszyn, ale nie analizują w tym przypadku czasu wykonania.

Lenstra, Shmoys i Tardos przedstawili dwuczynnikowy algorytm aproksymacji wieloczasowej i udowodnili, że żaden algorytm policzasowy ze współczynnikiem aproksymacji mniejszym niż 3/2 nie jest możliwy, chyba że P=NP. Zamknięcie luki między 2 a 3/2 jest od dawna otwartym problemem.

Versache i Wiese przedstawili inny algorytm aproksymacji dwuczynnikowej.

Glass, Potts i Shade porównują różne lokalne techniki wyszukiwania w celu zminimalizowania czasu oczekiwania na niepowiązanych komputerach. Wykorzystując komputerowe symulacje odkryli, że wyszukiwanie tabu i symulowane wyżarzanie działają znacznie lepiej niż algorytmy genetyczne .

Minimalizacja średniego czasu realizacji

Bruno, Coffman i Sethi przedstawiają algorytm działający w czasie $^ {2}, n ^ {3}))}$ mn średni czas wykonania zadania na niepowiązanych maszynach, R|| ${\ displaystyle \ suma C_ {j}}$ (średnia czasu potrzebnego na wykonanie zadań dla wszystkich zadań ).

Minimalizowanie średniego ważonego czasu ukończenia, R|| ${\ Displaystyle \ suma w_ {j} C_ {j}}$ (gdzie w _j wagą zadania j ), jest NP-trudne nawet na identycznych maszynach, poprzez redukcję problemu plecakowego . Jest NP-trudny, nawet jeśli liczba maszyn jest ustalona i wynosi co najmniej 2, poprzez redukcję problemu partycji .

Schulz i Skutella przedstawiają algorytm aproksymacji (3/2+ε) wykorzystujący zaokrąglanie losowe . Ich algorytm jest przybliżeniem (2+ε) problemu z czasami zwalniania zadań, R| ${\ displaystyle r_ {j}}$ | $\ Displaystyle \ suma w_ {j} C_ {j}}$ .

Maksymalizacja zysku

Bar-Noy, Bar-Yehuda, Freund, Naor i Schieber rozważają ustawienie, w którym dla każdej pracy i maszyny istnieje zysk z wykonywania tej pracy na tej maszynie. Przedstawiają przybliżenie 1/2 dla wejścia dyskretnego i przybliżenie (1- ε )/2 dla wejścia ciągłego.

Maksymalizacja minimalnego czasu realizacji

Główny artykuł: Egalitarny przydział przedmiotów

Załóżmy, że zamiast „prac” mamy wartościowe przedmioty, a zamiast „maszyn” mamy ludzi. Osoba i ocenia przedmiot j na p _i,j . Chcielibyśmy przydzielać przedmioty ludziom tak, aby najmniej zadowolona osoba była jak najbardziej zadowolona. Ten problem jest odpowiednikiem planowania niepowiązanych maszyn, w którym celem jest maksymalizacja minimalnego czasu realizacji. Jest lepiej znany pod nazwą egalitarny lub alokacja przedmiotów max-min .

Formuła programowania liniowego

Naturalny sposób sformułowania problemu jako programu liniowego nazywa się programem liniowym Lenstra – Shmoys – Tardos (LST LP) . Dla każdej maszyny i i zadania j _, zdefiniuj zmienną , która jest równa 1 jeśli maszyna $razie$ przetwarza zadanie 0 w przeciwnym . Zatem ograniczenia LP to:

• ${\ Displaystyle \ suma _ {i = 1} ^ {m} z_ {i, j} = 1}$ dla każdej pracy j w 1, ..., n;
• $p_ {i, j} \ równoważnik T}$ cdot każda maszyna i w 1,..., m;
• ${\ Displaystyle z_ {i, j} \ in \ {0,1 \}}$ dla każdego ja , jot .

Złagodzenie ograniczeń całkowitoliczbowych daje program liniowy z wielomianem wielkości na wejściu. Rozwiązanie problemu zrelaksowanego można zaokrąglić, aby uzyskać przybliżenie problemu do 2.

Innym sformułowaniem LP jest konfiguracja programu liniowego . Dla każdej maszyny i istnieje skończenie wiele podzbiorów zadań, które maszyna i może wykonać w czasie co najwyżej T. Każdy taki podzbiór nazywany jest konfiguracją dla maszyny i . Oznaczmy przez C _i ( T ) zbiór wszystkich konfiguracji dla maszyny i . Dla każdej maszyny i i konfiguracji c w C _i ( T , zdefiniuj zmienną $a$ jeśli rzeczywista konfiguracja używana w maszynie to c , 0 w przeciwnym razie Zatem ograniczenia LP to:

• ${\ Displaystyle \ suma _ {c \ w C_ {i} (T)} x_ {i, c} = 1}$ dla każdej maszyny ja w 1, .. ., m;
• ${\ Displaystyle \ suma _ {i = 1} ^ {m} \ suma _ {c \ ni j, c \ in C_{i}(T)}x_{i,c}=1}$ dla każdego zadania j w 1,..., n;
• ${\ Displaystyle x_ {i, j} \ w \ {0,1 \}}$ dla każdego ja , jot .

Należy zauważyć, że liczba konfiguracji jest zwykle wykładnicza w stosunku do rozmiaru problemu, więc rozmiar konfiguracji LP jest wykładniczy. Jednak w niektórych przypadkach możliwe jest ograniczenie liczby możliwych konfiguracji, a tym samym znalezienie przybliżonego rozwiązania w czasie wielomianowym.

Przypadki specjalne

Istnieje szczególny przypadek, w którym p _i,j wynosi albo 1, albo nieskończoność. Innymi słowy, każde zadanie może być przetwarzane na podzbiorze dozwolonych maszyn , a jego czas wykonania na każdej z tych maszyn wynosi 1. Wariant ten jest czasami oznaczany przez „ P|p _j =1,M _j | ${\ styl wyświetlania C_{\max}}$ ". Można go rozwiązać w czasie wielomianowym.

Rozszerzenia

Kim, Kim, Jang i Chen rozszerzają ten problem, umożliwiając każdemu zadaniu ustawienie czasu, który zależy od zadania, ale nie od maszyny. Przedstawiają rozwiązanie wykorzystujące symulowane wyżarzanie . Vallada i Ruiz przedstawiają rozwiązanie wykorzystujące algorytm genetyczny .

Caragiannis rozszerza problem w inny sposób, zakładając, że prace są własnością samolubnych agentów (patrz Prawdziwe planowanie pracy ).

Linki zewnętrzne

• Podsumowanie problemów z maszynami równoległymi bez uprzedzenia