Planowanie warsztatów - Job-shop scheduling

Planowanie warsztatów pracy lub problem warsztatów pracy ( JSP ) to problem optymalizacji w informatyce i badaniach operacyjnych . Jest to wariant optymalnego planowania pracy . W ogólnym problemu harmonogramowania pracy, daje nam brak pracy J ₁ ,  J ₂ , ...,  J _n o różnym czasie przetwarzania, które muszą być zaplanowane na m maszynach o różnej mocy obliczeniowej, starając się zminimalizować makespan - w całkowita długość harmonogramu (czyli po zakończeniu przetwarzania wszystkich zadań). W konkretnym wariancie zwanym planowaniem warsztatów każde zadanie składa się ze zbioru operacji O ₁ ,  O ₂ , ...,  O _n, które muszą zostać przetworzone w określonej kolejności (tzw. ograniczenia pierwszeństwa ). Każda operacja ma określoną maszynę , na której musi zostać przetworzona i tylko jedna operacja w zadaniu może być przetwarzana w danym czasie. Powszechnym relaksem jest elastyczny warsztat pracy, gdzie każdą operację można wykonać na dowolnej maszynie z danego zestawu (maszyny w każdym zestawie są identyczne).

Nazwa pierwotnie wzięła się od planowania zadań w sklepie pracy , ale temat ma szerokie zastosowanie poza tego typu instancją. Problem ten jest jednym z najbardziej znanych problemów optymalizacji kombinatorycznej i był pierwszym problemem, dla którego analiza konkurencyjna została przedstawiona przez Grahama w 1966 roku. Najlepsze przykłady problemów dla modelu podstawowego z celem „maspan” są dziełem Taillarda.

W standardowym trójpolowym zapisie dla optymalnych problemów planowania zadań wariant warsztatowy jest oznaczony przez J w pierwszym polu. Na przykład, problem oznaczone „ J3 | |${\displaystyle p_{ij}}$ ” jest 3-maszyny praca-shop problem z czasów Processing Unit, gdzie celem jest zminimalizowanie czasu zakończenia maksimum. ${\displaystyle C_{\max}}$

Odmiany problemu

Istnieje wiele odmian problemu, w tym następujące:

• Maszyny mogą mieć duplikaty (elastyczny warsztat z duplikatami) lub należeć do grup identycznych maszyn (elastyczny warsztat pracy).
• Maszyny mogą wymagać pewnej przerwy między zadaniami lub braku przestojów.
• Maszyny mogą mieć konfiguracje zależne od sekwencji.
• Funkcją celu może być minimalizacja rozpiętości, normy L _p , opieszałości, maksymalnego opóźnienia itp. Może to być również problem optymalizacji wielokryterialnej.
• Zadania mogą mieć ograniczenia, na przykład zadanie i musi zostać zakończone przed rozpoczęciem zadania j (patrz przepływ pracy ). Również funkcja celu może być wielokryterialna.
• Zestaw zadań może dotyczyć innego zestawu maszyn.
• Deterministyczne (stałe) czasy przetwarzania lub probabilistyczne czasy przetwarzania.

NP-twardość

Ponieważ problem komiwojażera jest NP-trudny , problem warsztatu z konfiguracją zależną od sekwencji jest oczywiście również NP-trudny, ponieważ TSP jest szczególnym przypadkiem JSP z jednym zadaniem (miasta to maszyny, a sprzedawca jest Praca).

Reprezentacja problemu

Dysjunktywny wykres jest jednym z popularnych modeli używanych do opisywania praca-Shop wystąpienia problemu szeregowania zadań.

Matematyczne sformułowanie problemu można sformułować w następujący sposób:

Niech i będzie dwoma skończonymi zbiorami . Ze względu na pochodzenie przemysłowych problemu, nazywane są maszyny i nazywane są miejsca pracy . ${\ Displaystyle M = \ {M_ {1}, M_ {2}, \ kropki, M_ {m} \}}$${\ Displaystyle J = \ {J_ {1}, J_ {2}, \ kropki, J_ {n} \}}$ ${\displaystyle \displaystyle M_{i}}$${\displaystyle \displaystyle J_{j}}$

Niech oznacza zbiór wszystkich kolejnych zadań w pracy z maszynami tak, że każda praca jest wykonywana przez każdą maszyną dokładnie jeden raz; elementy mogą być zapisane jako macierze, w których kolumna zawiera listę zadań, które maszyna wykona w kolejności. Na przykład macierz ${\displaystyle \displaystyle \ {\mathcal {X}}}$${\displaystyle x\in {\mathcal {X}}}$${\displaystyle n\razy m}$${\displaystyle \displaystyle i}$${\displaystyle \displaystyle M_{i}}$

${\ Displaystyle x = {\ zacząć {pmatrix} 1 i 2 \ \ 2 i 3 \ \ 3 i 1 \ koniec {pmatrix}}}$

oznacza, że ​​maszyna wykona trzy zadania w zamówieniu , podczas gdy maszyna wykona zadania w zamówieniu . ${\displaystyle \displaystyle M_{1}}$${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$${\displaystyle \displaystyle M_{2}}$${\displaystyle \displaystyle J_{2},J_{3},J_{1}}$

Załóżmy również, że istnieje jakaś funkcja kosztu . Funkcja kosztu może być interpretowana jako „całkowity czas przetwarzania” i może mieć pewne wyrażenie w postaci czasu , kosztu/czasu wykonania zadania przez maszynę . ${\displaystyle C:{\mathcal {X}}\do [0,+\infty]}$${\ Displaystyle C_ {ij}: M \ razy J \ do [0, + \ infty]}$${\displaystyle \displaystyle M_{i}}$${\displaystyle \displaystyle J_{j}}$

Problem praca-sklep jest znalezienie przyporządkowanie zadań takich, że to minimum, to znaczy, nie ma tak, że . ${\displaystyle x\in {\mathcal {X}}}$${\displaystyle \displaystyle C(x)}$${\ Displaystyle y \ w {\ mathcal {X}}}$${\displaystyle \displaystyle C(x)>C(y)}$

Efektywność planowania

Wydajność harmonogramowania można zdefiniować dla harmonogramu poprzez stosunek całkowitego czasu bezczynności maszyny do całkowitego czasu przetwarzania, jak poniżej:

${\ Displaystyle C '=1 + {\ suma _ {i} l_ {i} \ nad \ suma _ {j, k} p_ {jk}} = {Cm \ nad \ suma _ {j, k} p_ {jk }}}$

Oto czas bezczynności maszyny , czas pracy i liczba maszyn. Zauważ, że przy powyższej definicji wydajność planowania to po prostu makepan znormalizowany do liczby maszyn i całkowitego czasu przetwarzania. Umożliwia to porównywanie wykorzystania zasobów w instancjach JSP o różnej wielkości. ${\displaystyle l_{i}}$${\displaystyle i}$${\ Displaystyle C}$${\ Displaystyle m}$

Problem nieskończonych kosztów

Jednym z pierwszych problemów, z którymi trzeba się uporać w JSP, jest to, że wiele proponowanych rozwiązań ma nieskończone koszty, tj. istnieją takie, że . W rzeczywistości dość łatwo jest wymyślić takie przykłady, zapewniając, że dwie maszyny ulegną zakleszczeniu , tak aby każda z nich czekała na wyjście następnego kroku drugiej. ${\displaystyle x_{\infty}\w {\mathcal {X}}}$${\ Displaystyle C (x_ {\ infty}) = + \ infty}$${\displaystyle x_{\infty}}$

Główne wyniki

Graham dostarczył już algorytm planowania List w 1966, który jest (2 − 1/ m ) -konkurencyjny, gdzie m jest liczbą maszyn. Udowodniono również, że planowanie list jest optymalnym algorytmem online dla 2 i 3 maszyn. Algorytm Coffman, Graham (1972) dla pracy jednolitej długości jest optymalne dla dwóch maszyn, i (2 - 2 / m ) konkurencji na rynkach. W 1992 roku Bartal, Fiat, Karloff i Vohra przedstawili algorytm, który jest konkurencyjny na poziomie 1,986. Algorytm 1.945-kompetycyjny został przedstawiony przez Kargera, Philipsa i Tornga w 1994 roku. W 1992 roku Albers dostarczył inny algorytm, który jest konkurencyjny dla 1.923. Obecnie najbardziej znanym wynikiem jest algorytm podany przez Fleischera i Wahla, który osiąga konkurencyjny współczynnik 1,9201.

Dolna granica 1,852 została przedstawiona przez Albersa. Instancje Taillarda odgrywają ważną rolę w opracowywaniu harmonogramów warsztatów z celem makepan.

W 1976 Garey dostarczył dowód, że problem ten jest NP-zupełny dla m>2, to znaczy, że nie można zweryfikować optymalnego rozwiązania w czasie wielomianowym dla trzech lub więcej maszyn (chyba że P=NP ).

W 2011 Xin Chen i in. dostarczył optymalne algorytmy do planowania online na dwóch powiązanych maszynach, poprawiając poprzednie wyniki.

Minimalizacja makepanu offline

Praca atomowa

Najprostsza forma problemu minimalizacji makepan w trybie offline dotyczy zadań atomowych, czyli zadań, które nie są podzielone na wiele operacji. Jest to równoważne pakowaniu wielu przedmiotów o różnych rozmiarach do stałej liczby pojemników, tak aby maksymalny wymagany rozmiar pojemnika był jak najmniejszy. (Jeśli zamiast tego liczba pojemników ma zostać zminimalizowana, a rozmiar pojemnika jest stały, problem staje się innym problemem, znanym jako problem z pakowaniem pojemnika .)

Dorit S. Hochbaum i David Shmoys przedstawili w 1987 r. schemat aproksymacji wielomianowej w czasie, który znajduje przybliżone rozwiązanie problemu minimalizacji makepanu w trybie offline z zadaniami atomowymi z dowolną żądaną dokładnością.

Zadania składające się z wielu operacji

Podstawowa forma problemu planowania zadań z wieloma (M) operacjami, na maszynach M tak, że wszystkie pierwsze operacje muszą być wykonane na pierwszej maszynie, wszystkie drugie operacje na drugiej itd. oraz pojedyncza zadanie nie może być wykonywane równolegle, jest znane jako problem z planowaniem przepływu-shopu . Istnieją różne algorytmy, w tym algorytmy genetyczne .

Algorytm Johnsona

Algorytm heurystyczny SM Johnson może być użyty do rozwiązania przypadku problemu z 2 maszynami N zadań, gdy wszystkie zadania mają być przetwarzane w tej samej kolejności. Kroki algorytmu są następujące:

Praca P _i ma dwie operacje, o czasie trwania P _i1 , P _i2 , które mają być wykonane na komputerze M1, M2 w tej sekwencji.

• Krok 1. Lista A = { 1, 2, …, N }, Lista L1 = {}, Lista L2 = {}.
• Krok 2. Ze wszystkich dostępnych czasów działania wybierz minimum.

Jeżeli minimum należy do P _k1 ,

Usuń K z listy A; Dodaj K na koniec listy L1.

Jeżeli minimum należy do P _k2 ,

Usuń K z listy A; Dodaj K na początku listy L2.

• Krok 3. Powtarzaj krok 2, aż lista A będzie pusta.
• Krok 4. Dołącz do listy L1, listy L2. To jest optymalna sekwencja.

Metoda Johnsona działa optymalnie tylko dla dwóch maszyn. Jednak ponieważ jest optymalna i łatwa do obliczenia, niektórzy badacze próbowali zaadaptować ją dla maszyn M ( M  > 2.)

Pomysł jest następujący: Wyobraź sobie, że każde zadanie wymaga m operacji w sekwencji, na M1, M2 … Mm. Łączymy pierwsze maszyny m /2 w (wyobrażone) centrum obróbkowe MC1, a pozostałe maszyny w centrum obróbkowe MC2. Następnie całkowity czas przetwarzania dla Zadania P na MC1 = suma (czasy operacji na pierwszych m /2 maszyn), a czas przetwarzania dla Zadania P na MC2 = suma (czasy operacji na ostatnich m /2 maszyn).

W ten sposób zredukowaliśmy problem m-Machine do problemu planowania dwóch centrów obróbkowych. Możemy to rozwiązać za pomocą metody Johnsona.

Prognozy Makespan

Uczenie maszynowe było ostatnio używane do przewidywania optymalnego stanu instancji JSP bez faktycznego tworzenia optymalnego harmonogramu. Wstępne wyniki wykazują dokładność około 80%, gdy nadzorowane metody uczenia maszynowego zostały zastosowane do klasyfikowania małych losowo generowanych instancji JSP na podstawie ich optymalnej wydajności planowania w porównaniu ze średnią.

Przykład

Oto przykład problemu planowania warsztatów sformułowanego w AMPL jako problem programowania mieszanych liczb całkowitych z ograniczeniami wskaźnikowymi:

param N_JOBS;
param N_MACHINES;

set JOBS ordered = 1..N_JOBS;
set MACHINES ordered = 1..N_MACHINES;

param ProcessingTime{JOBS, MACHINES} > 0;

param CumulativeTime{i in JOBS, j in MACHINES} =
   sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];

param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} =
   max {j in MACHINES}
     (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);

var end >= 0;
var start{JOBS} >= 0;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)} binary;

minimize makespan: end;

subj to makespan_def{i in JOBS}:
   end >= start[i] + sum{j in MACHINES} ProcessingTime[i,j];

subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   precedes[i1,i2] ==> start[i2] >= start[i1] + TimeOffset[i1,i2];

subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   !precedes[i1,i2] ==> start[i1] >= start[i2] + TimeOffset[i2,i1];

data;

param N_JOBS := 4;
param N_MACHINES := 4;

param ProcessingTime:
  1 2 3 4 :=
1 4 2 1
2 3 6 2
3 7 2 3
4 1 5 8;

Powiązane problemy

• Planowanie Flow-shop to podobny problem, ale bez ograniczenia, że ​​każda operacja musi być wykonana na określonej maszynie (zachowywane jest tylko ograniczenie kolejności).
• Podobnym problemem jest planowanie w otwartym sklepie, ale również bez ograniczenia zamówienia.

Zobacz też

Bibliografia

Zewnętrzne linki

• Uniwersytet Wiedeński Katalog metodologii, systemów i oprogramowania do optymalizacji dynamicznej.
• Instancje Taillarda
• Brucker P. Algorytmy planowania . Heidelberg, Springer. Piąte wydanie. ISBN  978-3-540-24804-0
• Harmonogram wizualny w sklepie pracy