Harmonogramowanie maszyn jednolitych

Jednolite planowanie maszyn (zwane również jednolicie powiązanym szeregowaniem maszyn lub powiązanym szeregowaniem maszyn ) jest problemem optymalizacyjnym w informatyce i badaniach operacyjnych . Jest to wariant optymalnego planowania pracy . Dano nam n zadań J ₁ , J ₂ , ..., J _n o różnym czasie przetwarzania, które należy zaplanować na m różnych maszynach. Celem jest zminimalizowanie tzw makepan - całkowity czas potrzebny do wykonania harmonogramu. Czas, jakiego potrzebuje maszyna i do wykonania zadania j, jest oznaczony przez pi _,j . W ogólnym przypadku czasy p _i,j nie są ze sobą powiązane i możliwa jest dowolna macierz dodatnich czasów przetwarzania. W konkretnym wariancie zwanym jednolitym harmonogramem maszyn niektóre maszyny są jednakowo szybsze niż inne. Oznacza to, że dla każdej maszyny i istnieje współczynnik szybkości _si i czas wykonywania zadania j na maszynie i jest p _i,j = p _j / s _i .

W standardowej trójpolowej notacji dla problemów z optymalnym harmonogramowaniem zadań wariant z jednolitą maszyną jest oznaczony przez Q w pierwszym polu. Na przykład problem oznaczony przez „ Q || ${\ displaystyle C _ {\ max}}$ " to jednolity problem z harmonogramem maszyny bez ograniczeń, w którym celem jest zminimalizowanie maksymalnego czasu ukończenia. Szczególnym przypadkiem jednolitego szeregowania maszyn jest identyczne szeregowanie maszyn , w którym wszystkie maszyny mają tę samą prędkość. Ten wariant jest oznaczony przez P w pierwszym polu.

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

Algorytmy

Minimalizacja średniego czasu realizacji

Minimalizację średniego czasu ukończenia można wykonać w czasie wielomianowym:

Algorytm SPT (Najpierw najkrótszy czas przetwarzania) sortuje zadania według ich długości, zaczynając od najkrótszego, a następnie przypisuje je do procesora o najwcześniejszym dotychczas czasie zakończenia. Działa w czasie O( n log n ) i minimalizuje średni czas ukończenia na identycznych maszynach, P|| ${\ Displaystyle \ suma C_ {i}}$ .
Horowitz i Sahni przedstawiają dokładny algorytm o czasie wykonywania O( n log mn ), służący do minimalizacji średniego czasu ukończenia na jednorodnych maszynach, Q|| ${\ Displaystyle \ suma C_ {i}}$ .
Bruno, Coffman i Sethi przedstawiają algorytm działający w czasie $^ {2}, n ^ {3}))}$ mn średni czas ukończenia na niepowiązanych maszynach, R|| ${\ Displaystyle \ suma C_ {i}}$ .

Minimalizacja średniego ważonego czasu realizacji

Minimalizowanie średniego ważonego czasu ukończenia 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 .

Sahni przedstawia algorytm czasu wykładniczego i algorytm aproksymacji czasu wielomianowego dla identycznych maszyn.

Horowitz i Sahni przedstawili:

Dokładne algorytmy programowania dynamicznego do minimalizacji czasu realizacji średniej ważonej na jednorodnych maszynach. Algorytmy te działają w czasie wykładniczym.
Schematy aproksymacji w czasie wielomianowym , które dla dowolnego ε > 0 osiągają co najwyżej (1+ε)OPT. Aby zminimalizować średni ważony czas ukończenia na dwóch jednorodnych maszynach, czas wykonania wynosi ${\ Displaystyle O (10 ^ {l} n ^ {2})}$ = $O(n^{2}/\epsilon)$ , więc jest to FPTAS. Twierdzą, że ich algorytmy można łatwo rozszerzyć na dowolną liczbę jednorodnych maszyn, ale nie analizują w tym przypadku czasu wykonania. Nie przedstawiają algorytmu dla średniego ważonego czasu ukończenia na niepowiązanych maszynach.

Minimalizacja maksymalnego czasu realizacji (makespan)

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

Przybliżenie ze stałym współczynnikiem uzyskuje się za pomocą algorytmu Longest-processing-time-first (LPT).

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.

Hochbaum i Shmoys przedstawili kilka algorytmów aproksymacyjnych dla dowolnej liczby identycznych maszyn . Później opracowali PTAS dla jednolitych maszyn.

Epstein i Sgall uogólnili PTAS dla jednolitych maszyn do obsługi bardziej ogólnych funkcji celu. Niech C _i (dla i między 1 a m ) będzie rozpiętością maszyny i w zadanym harmonogramie. Zamiast minimalizować funkcję celu max( C _i ), można zminimalizować funkcję celu max( f ( C _i )), gdzie f jest dowolną ustaloną funkcją. Podobnie można zminimalizować funkcję celu sum( f ( C _i )).

Monotoniczność i prawdomówność

W niektórych ustawieniach prędkość maszyny jest prywatną informacją o maszynie i chcemy zachęcić maszyny do ujawnienia swojej prawdziwej prędkości, czyli chcemy prawdziwego mechanizmu . Ważną kwestią dla osiągnięcia prawdomówności jest monotoniczność . Oznacza to, że jeśli maszyna zgłasza wyższą prędkość, a wszystkie inne dane wejściowe pozostają takie same, to całkowity czas przetwarzania przydzielony maszynie nieznacznie wzrasta. W przypadku tego problemu:

Auletta, De Prisco, Penna i Persiano przedstawili algorytm monotoniczny z 4 przybliżeniami, który działa w wieloczasie, gdy liczba maszyn jest ustalona.
Ambrosio i Auletta udowodnili, że algorytm najdłuższego czasu przetwarzania jest monotoniczny, gdy prędkości maszyny są potęgami niektórych c ≥ 2, ale nie wtedy, gdy c ≤ 1,78. W przeciwieństwie do tego, szeregowanie listy nie jest monotonne dla c > 2.
Andelman, Azar i Sorani przedstawili algorytm monotoniczny z 5 przybliżeniami, który działa w wieloczasie, nawet gdy liczba maszyn jest zmienna.
Kovacz przedstawił algorytm monotoniczny z 3 przybliżeniami.

Rozszerzenia

Zadania zależne : W niektórych przypadkach zadania mogą być zależne. Weźmy na przykład przypadek odczytu poświadczeń użytkownika z konsoli, a następnie użyj go do uwierzytelnienia, a następnie, jeśli uwierzytelnienie się powiedzie, wyświetl niektóre dane na konsoli. Oczywiście jedno zadanie jest zależne od drugiego. Jest to wyraźny przypadek, w którym istnieje pewien rodzaj uporządkowania między zadaniami. W rzeczywistości jest jasne, że można go modelować z częściowym uporządkowaniem . Wtedy z definicji zbiór zadań tworzy strukturę kratową . To dodatkowo komplikuje problem planowania wieloprocesorowego.

Statyczne kontra dynamiczne : algorytmy planowania maszyn są statyczne lub dynamiczne. Algorytm planowania jest statyczny , jeśli decyzje dotyczące planowania, które zadania obliczeniowe zostaną przydzielone do jakich procesorów, są podejmowane przed uruchomieniem programu. Algorytm jest dynamiczny , jeśli jest wykonywany w czasie wykonywania. W przypadku algorytmów planowania statycznego typowym podejściem jest uszeregowanie zadań zgodnie z ich relacjami pierwszeństwa i użycie techniki planowania listy w celu zaplanowania ich na procesorach.

Zadania wieloetapowe : w różnych ustawieniach każde zadanie może mieć kilka operacji, które muszą być wykonywane równolegle. Niektóre takie ustawienia są obsługiwane przez harmonogramy otwartego sklepu , harmonogramy przepływów i harmonogramy warsztatów .

Linki zewnętrzne

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

^ Horowitz, Ellis; Sahni, Sartadź (1976-04-01). „Dokładne i przybliżone algorytmy planowania procesorów nieidentycznych” . Dziennik ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .
^ ^abcd ^Horowitz ^,^Ellis ; Sahni, Sartadź (1976-04-01). „Dokładne i przybliżone algorytmy planowania procesorów nieidentycznych” . Dziennik ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .
Bibliografia _ Coffman, EG; Sethi, R. (1974-07-01). „Planowanie niezależnych zadań w celu skrócenia średniego czasu ukończenia” . Komunikaty ACM . 17 (7): 382–387. doi : 10.1145/361011.361064 . ISSN 0001-0782 .
^ ^a ^b Sahni, Sartadź K. (1976-01-01). „Algorytmy planowania niezależnych zadań” . Dziennik ACM . 23 (1): 116–127. doi : 10.1145/321921.321934 . ISSN 0004-5411 .
^ Hochbaum, Dorit S.; Szmojs, David B. (1987-01-01). „Wykorzystanie algorytmów podwójnej aproksymacji do planowania problemów teoretycznych i praktycznych wyników” . Dziennik ACM . 34 (1): 144–162. doi : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .
^ Hochbaum, Dorit S.; Szmojs, David B. (1988-06-01). „Schemat aproksymacji wielomianów do planowania na jednolitych procesorach: stosowanie podejścia z podwójnym przybliżeniem” . SIAM Journal o informatyce . 17 (3): 539–551. doi : 10.1137/0217033 . ISSN 0097-5397 .
Bibliografia _ Sgall, Jiri (2004-05-01). „Schematy aproksymacji dla jednolicie powiązanych i identycznych równoległych maszyn szeregowych” . Algorytmika . 39 (1): 43–57. doi : 10.1007/s00453-003-1077-7 . ISSN 1432-0541 . S2CID 12965369 .
Bibliografia _ Tardos, E. (2001-10-01). „Prawdziwe mechanizmy dla agentów jednoparametrowych” . Obrady 42. Sympozjum IEEE na temat podstaw informatyki : 482–491. doi : 10.1109/SFCS.2001.959924 . ISBN 0-7695-1390-5 . S2CID 11377808 .
Bibliografia _ De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). Diekert, Volker; Habib, Michel (red.). „Deterministyczne, zgodne z prawdą mechanizmy przybliżania do planowania maszyn powiązanych” . Stacs 2004 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 2996 : 608–619. doi : 10.1007/978-3-540-24749-4_53 . ISBN 978-3-540-24749-4 .
^ Ambrosio, Pasquale; Auletta, Vincenzo (2005). Persiano, Giuseppe; Solis-Oba, Roberto (red.). „Deterministyczne algorytmy monotoniczne do planowania na powiązanych maszynach” . Aproksymacja i algorytmy online . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 3351 : 267–280. doi : 10.1007/978-3-540-31833-0_22 . ISBN 978-3-540-31833-0 .
^ Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). Diekert, Volker; Durand, Bruno (red.). „Prawdziwe mechanizmy przybliżania do planowania samolubnych powiązanych maszyn” . Stac 2005 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 3404 : 69–82. doi : 10.1007/978-3-540-31856-9_6 . ISBN 978-3-540-31856-9 .
^ Kovács, Annamária (2005). Brodal, Gerth Stølting; Leonardi, Stefano (red.). „Szybki algorytm 3-przybliżenia monotonicznego do planowania powiązanych maszyn” . Algorytmy – ESA 2005 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 3669 : 616–627. doi : 10.1007/11561071_55 . ISBN 978-3-540-31951-1 .
^ Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). „Algorytmy planowania statycznego do przydzielania skierowanych grafów zadań do wieloprocesorów”. Ankiety komputerowe ACM . 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . doi : 10.1145/344588.344618 . ISSN 0360-0300 . S2CID 207614150 .

[1] Horowitz, Ellis; Sahni, Sartadź (1976-04-01). „Dokładne i przybliżone algorytmy planowania procesorów nieidentycznych” . Dziennik ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .

[:0-2] Horowitz ^,^Ellis ; Sahni, Sartadź (1976-04-01). „Dokładne i przybliżone algorytmy planowania procesorów nieidentycznych” . Dziennik ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .

[3] Bibliografia _ Coffman, EG; Sethi, R. (1974-07-01). „Planowanie niezależnych zadań w celu skrócenia średniego czasu ukończenia” . Komunikaty ACM . 17 (7): 382–387. doi : 10.1145/361011.361064 . ISSN 0001-0782 .

[:3-4] Sahni, Sartadź K. (1976-01-01). „Algorytmy planowania niezależnych zadań” . Dziennik ACM . 23 (1): 116–127. doi : 10.1145/321921.321934 . ISSN 0004-5411 .

[:02-5] Hochbaum, Dorit S.; Szmojs, David B. (1987-01-01). „Wykorzystanie algorytmów podwójnej aproksymacji do planowania problemów teoretycznych i praktycznych wyników” . Dziennik ACM . 34 (1): 144–162. doi : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .

[6] Hochbaum, Dorit S.; Szmojs, David B. (1988-06-01). „Schemat aproksymacji wielomianów do planowania na jednolitych procesorach: stosowanie podejścia z podwójnym przybliżeniem” . SIAM Journal o informatyce . 17 (3): 539–551. doi : 10.1137/0217033 . ISSN 0097-5397 .

[7] Bibliografia _ Sgall, Jiri (2004-05-01). „Schematy aproksymacji dla jednolicie powiązanych i identycznych równoległych maszyn szeregowych” . Algorytmika . 39 (1): 43–57. doi : 10.1007/s00453-003-1077-7 . ISSN 1432-0541 . S2CID 12965369 .

[8] Bibliografia _ Tardos, E. (2001-10-01). „Prawdziwe mechanizmy dla agentów jednoparametrowych” . Obrady 42. Sympozjum IEEE na temat podstaw informatyki : 482–491. doi : 10.1109/SFCS.2001.959924 . ISBN 0-7695-1390-5 . S2CID 11377808 .

[9] Bibliografia _ De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). Diekert, Volker; Habib, Michel (red.). „Deterministyczne, zgodne z prawdą mechanizmy przybliżania do planowania maszyn powiązanych” . Stacs 2004 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 2996 : 608–619. doi : 10.1007/978-3-540-24749-4_53 . ISBN 978-3-540-24749-4 .

[10] Ambrosio, Pasquale; Auletta, Vincenzo (2005). Persiano, Giuseppe; Solis-Oba, Roberto (red.). „Deterministyczne algorytmy monotoniczne do planowania na powiązanych maszynach” . Aproksymacja i algorytmy online . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 3351 : 267–280. doi : 10.1007/978-3-540-31833-0_22 . ISBN 978-3-540-31833-0 .

[11] Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). Diekert, Volker; Durand, Bruno (red.). „Prawdziwe mechanizmy przybliżania do planowania samolubnych powiązanych maszyn” . Stac 2005 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 3404 : 69–82. doi : 10.1007/978-3-540-31856-9_6 . ISBN 978-3-540-31856-9 .

[12] Kovács, Annamária (2005). Brodal, Gerth Stølting; Leonardi, Stefano (red.). „Szybki algorytm 3-przybliżenia monotonicznego do planowania powiązanych maszyn” . Algorytmy – ESA 2005 . Notatki z wykładów z informatyki. Berlin, Heidelberg: Springer. 3669 : 616–627. doi : 10.1007/11561071_55 . ISBN 978-3-540-31951-1 .

[13] Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). „Algorytmy planowania statycznego do przydzielania skierowanych grafów zadań do wieloprocesorów”. Ankiety komputerowe ACM . 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . doi : 10.1145/344588.344618 . ISSN 0360-0300 . S2CID 207614150 .

Problemy z optymalnym planowaniem zadań
Zadania jednoetapowe	Pojedyncza maszyna Identyczne maszyny Jednolite maszyny Niepowiązane maszyny
Zadania wieloetapowe	Zadania równoległe Otwarty sklep Sklep Flow Sklep z ofertami pracy
Cele optymalizacji	Rozpiętość wczesność Spóźnienie Opieszałość Wydajność
Inne wymagania	Planowanie interwałowe Prawdziwe planowanie pracy