Planowanie pracy w sklepie

Planowanie w warsztacie , problem w warsztacie ( JSP ) lub problem w warsztacie ( JSSP ) to problem optymalizacji w informatyce i badaniach operacyjnych . Jest to wariant optymalnego planowania pracy . W ogólnym problemie szeregowania zadań mamy dane n zadań J ₁ , J ₂ , ..., J _n o różnym czasie przetwarzania, które należy zaplanować na m maszyny o różnej mocy obliczeniowej, starając się jednocześnie zminimalizować makespan – całkowitą długość harmonogramu (czyli kiedy wszystkie zadania zakończą przetwarzanie). W specyficznym wariancie znanym jako szeregowanie w warsztacie , każde zadanie składa się z zestawu operacji O ₁ , O ₂ , ..., O _n , które muszą być przetwarzane w określonej kolejności (znanej jako ograniczenia pierwszeństwa ). Każda operacja ma określoną maszynę że musi być przetwarzane, a tylko jedna operacja w zadaniu może być przetwarzana w danym czasie. Powszechnym relaksem jest elastyczny warsztat pracy, w którym każdą operację można wykonać na dowolnej maszynie danego zestawu (maszyny w każdym zestawie są identyczne).

Nazwa pierwotnie pochodziła od planowania zadań w sklepie z ofertami pracy , ale motyw ma szerokie zastosowania poza tego typu instancjami. Ten problem jest jednym z najbardziej znanych optymalizacji kombinatorycznej i był pierwszym problemem, dla którego analiza konkurencyjności została przedstawiona przez Grahama w 1966 roku. Najlepsze przykłady problemów dla modelu podstawowego z celem makespan pochodzą od Taillarda.

W standardowej trójpolowej notacji dla problemów z optymalnym planowaniem zadań wariant warsztatowy jest oznaczony przez J w pierwszym polu. Na przykład problem oznaczony przez „ J3 | ${\ displaystyle p_ {ij}}$ | ${\ displaystyle C _ {\ max}}$ " to problem warsztatu z 3 maszynami z jednostkowymi czasami przetwarzania, gdzie celem jest zminimalizowanie maksymalnego czasu realizacji.

Odmiany problemu

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

• Maszyny mogą mieć duplikaty (warsztat elastyczny ze zduplikowanymi maszynami) lub należeć do grup identycznych maszyn (warsztat elastyczny).
• Maszyny mogą wymagać pewnej przerwy między zadaniami lub braku przestoju.
• Maszyny mogą mieć konfiguracje zależne od sekwencji.
• Funkcją celu może być minimalizacja rozpiętości, normy Lp , spóźnienia, maksymalnego spóźnienia itp. Może _to być również wielokryterialny problem optymalizacji.
• Zadania mogą mieć ograniczenia, na przykład zadanie i musi zostać zakończone przed rozpoczęciem zadania j (patrz przepływ pracy ). Ponadto funkcja celu może być wielokryterialna.
• Zestaw zadań może odnosić się do różnych zestawów maszyn.
• Deterministyczne (stałe) czasy przetwarzania lub probabilistyczne czasy przetwarzania.

NP-twardość

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

Reprezentacja problemu

Graf rozłączny jest jednym z popularnych modeli używanych do opisywania przypadków problemów z harmonogramowaniem w warsztacie.

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

Niech ${\ Displaystyle M = \ {M_ {1}, M_ {2}, \ kropki, M_ {m} \}}$ i ${\ Displaystyle J = \ {J_ {1}, J_ {2}, \ kropki, J_ {n} \}}$ będą dwoma skończonymi zbiorami . Ze względu na przemysłowe pochodzenie problemu, ${\ displaystyle \ displaystyle M_ {i}}$ nazywane są maszynami , a zadania nazywane są $\ displaystyle \ displaystyle J_ {j}}$ .

Niech oznacza zbiór wszystkich kolejnych przypisań zadań do maszyn, tak że każda praca jest wykonywana przez każdą maszynę dokładnie $raz$ elementy można zapisać jako macierze ${\ displaystyle n \ razy m}$$w$ których kolumna zawodów, które ${\ displaystyle \ displaystyle i}$ maszyna $.$ po kolei Na przykład macierz

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

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

Załóżmy również, że istnieje jakaś funkcja kosztów ${\ Displaystyle C: {\ mathcal {X}} \ do [0, + \ infty ]}$ . Funkcja kosztu może być $\ Displaystyle C_ {ij}: M \ razy J \ do [0,+\infty ]}$ jako „całkowity czas przetwarzania” i może mieć pewne wyrażenie w kategoriach czasów do ja , koszt/czas dla maszyny ${\ Displaystyle \ Displaystyle M_ {i}}$ wykonywać pracę ${\ Displaystyle \ Displaystyle J_ {j}}$ .

Problem warsztatu polega na znalezieniu przydziału zadań takiego, że jest $\ Displaystyle$ minimum, $x \ w {\ mathcal {X}}$ to znaczy, że nie ma takiego, że do ${\ Displaystyle y \ w {\ mathcal {X}}} .$${\ Displaystyle \ displaystyle C (x)> C (y)$ }

Efektywność planowania

Efektywność planowania 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} \ ponad \ suma _ {j, k} p_ {jk}} = {Cm \ ponad \ suma _ {j,k}p_{jk}}}$

Tutaj $jest$ czas bezczynności maszyny , makespan i $m}$$liczbą$$jest$ maszyn Zauważ, że przy powyższej definicji efektywność planowania to po prostu rozpiętość znormalizowana do liczby maszyn i całkowitego czasu przetwarzania. Dzięki temu możliwe jest porównanie wykorzystania zasobów między instancjami JSP o różnej wielkości.

Problem nieskończonych kosztów

Jednym z pierwszych problemów, z którymi należy się uporać w JSP, jest to, że wiele proponowanych rozwiązań ma nieskończony koszt: tj. istnieje takie, że x $\ Displaystyle x _ {\ infty}$${\ Displaystyle C (x _ {\ infty}) = + \ infty}$ . W rzeczywistości dość łatwo jest wymyślić przykłady takich, $się,$ że dwie maszyny utkną w martwym punkcie , tak że każdy czeka na wynik następnego kroku drugiego.

Główne wyniki

Graham już w 1966 roku dostarczył algorytm szeregowania list, który jest (2 − 1/ m ) -konkurencyjny, gdzie m jest liczbą maszyn. Udowodniono również, że harmonogramowanie listowe jest optymalnym algorytmem online dla 2 i 3 maszyn. Coffmana -Grahama (1972) dla zadań o jednakowej długości jest również optymalny dla dwóch maszyn i jest (2-2/ m ) -konkurencyjny. W 1992 roku Bartal, Fiat, Karloff i Vohra przedstawili algorytm, który jest 1,986 konkurencyjny. Algorytm konkurencyjny 1,945 został przedstawiony przez Kargera, Philipsa i Tornga w 1994 r. W 1992 r. Albers dostarczył inny algorytm, konkurencyjny 1,923. Obecnie najbardziej znanym wynikiem jest algorytm podany przez Fleischera i Wahla, który osiąga konkurencyjny współczynnik 1,9201.

Dolną granicę 1,852 przedstawił Albers. Instancje Taillarda odgrywają ważną rolę w opracowywaniu harmonogramów zadań w warsztatach z uwzględnieniem celu.

W 1976 roku Garey udowodnił, że ten problem jest NP-zupełny dla m>2, to znaczy, że nie można obliczyć optymalnego rozwiązania w deterministycznym 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 wcześniejsze wyniki.

Offline minimalizuje rozpiętość

Zadania atomowe

Zobacz też: Szeregowanie wieloprocesorowe

Najprostsza postać problemu minimalizacji sprawia, że ​​rozpiętość offline dotyczy zadań atomowych, to znaczy zadań, które nie są podzielone na wiele operacji. Jest to równoważne pakowaniu wielu przedmiotów o różnych rozmiarach do określonej liczby pojemników, tak aby maksymalny potrzebny 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 pakowania pojemników ).

Dorit S. Hochbaum i David Shmoys przedstawili w 1987 r. Schemat aproksymacji czasu wielomianowego , który znajduje przybliżone rozwiązanie problemu minimalizacji zakresu w trybie offline z zadaniami atomowymi z dowolnym pożądanym stopniem dokładności.

Zadania składające się z wielu operacji

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

Algorytm Johnsona

Zobacz także: reguła Johnsona

Algorytm heurystyczny autorstwa SM Johnsona może być wykorzystany do rozwiązania problemu zadania 2 maszyn N, gdy wszystkie zadania mają być przetwarzane w tej samej kolejności. Kroki algorytmu są następujące:

Zadanie P _i ma dwie operacje o czasie trwania P _i1 , P _i2 , które należy wykonać na maszynie M1, M2 w tej kolejności.

• Krok 1. Lista A = { 1, 2, …, N }, Lista L1 = {}, Lista L2 = {}.
• Krok 2. Spośród wszystkich dostępnych czasów trwania operacji wybierz minimalny.

Jeżeli minimum należy do P _k1 ,

Usuń K z listy A; Dodaj K na końcu 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 kolejność.

Metoda Johnsona działa optymalnie tylko dla dwóch maszyn. Ponieważ jednak jest optymalny i łatwy do obliczenia, niektórzy badacze próbowali go zaadaptować 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 m /2 w (wyimaginowane) Centrum Obróbcze MC1, a pozostałe Maszyny w Centrum Obróbcze MC2. Wtedy całkowity czas przetwarzania Zadania P na MC1 = suma (czasy operacji na pierwszych m /2 maszynach) i czas przetwarzania Zadania P na MC2 = suma (czasy operacji na ostatnich m /2 maszynach).

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

Przewidywanie rozpiętości

Uczenie maszynowe było ostatnio wykorzystywane do przewidywania optymalnego czasu wykonania instancji JSP bez tworzenia optymalnego harmonogramu. Wstępne wyniki pokazują dokładność około 80%, gdy zastosowano nadzorowane metody uczenia maszynowego 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 pracy w warsztacie sformułowanego w AMPL jako problem programowania liczb całkowitych mieszanych z ograniczeniami wskaźnikowymi:

 
 

    
    

    0

       
    parametr  N_JOBS  ;  parametr  N_MASZYNY  ;  ustaw  zamówione  ZADANIA  =  1  ..  N_ZADANIA  ;  ustaw  MASZYNY  zamówione  =  1  ..  N_MASZYNY  ;  parametr Czas  przetwarzania  {  ZADANIA  ,  MASZYNY  }  >  ;  parametr  CumulativeTime  {  i  w  PRACACH  ,  j  w  MASZYNACH  }  =  suma        

          
      
      {  jj  w  MASZYNACH  :  ord  (  jj  )  <=  ord  (  j  )}  Czas przetwarzania  [  i  ,  jj  ];  param  Przesunięcie Czasu  {  i1  w  ZADANIACH  ,  i2  w  ZADANIACH  :  i1  <>  i2  }  =  max  {  j  w  MASZYNACH  }  (  Łączny Czas  [  i1     

   0
   0
          ,  j  ]  -  Czas Skumulowany  [  i2  ,  j  ]  +  Czas Przetwarzania  [  i2  ,  j  ]);  var  koniec  >=  ;  var  start  {  PRACA  }  >=  ;  var  poprzedza  {  i1  w  JOBS  ,  i2  w  JOBS  :  ord  (  i1  )  <  ord  (  i2  

  

   
          

       )}  binarny  ;  zminimalizuj  makepan  :  koniec  ;  subj to  makepan_def  {  i  w  JOBS  }:  end  >=  start  [  i  ]  +  suma  {  j  w  MASZYNY  }  ProcessingTime  [  i  ,  j  ];  podlega  no12_conflict  {  i1  w  PRACACH  ,  i2  w  PRACACH  :    
         

        ord  (  i1  )  <  ord  (  i2  )}:  poprzedza  [  i1  ,  i2  ]  ==>  start  [  i2  ]  >=  start  [  i1  ]  +  Przesunięcie czasowe  [  i1  ,  i2  ];  podporządkowany  no21_conflict  {  i1  w  JOBS  ,  i2  w  JOBS  :  ord  (  i1  )   
         



   
   

  <  ord  (  i2  )}:  !  poprzedza  [  i1  ,  i2  ]  ==>  start  [  i1  ]  >=  start  [  i2  ]  +  Przesunięcie czasowe  [  i2  ,  i1  ];  dane  ;  parametr  N_JOBS  :  =  4  ;  parametr  N_MASZYNY  :  =  4  ;  parametr  Czas przetwarzania  : 
    
   
   
   
    1  2  3  4  :  =  1  4  2  1  2  3  6  2  3  7  2  3  4  1  5  8  ; 

Powiązane problemy

• Podobnym problemem jest planowanie flow-shop, ale bez ograniczenia, że ​​każda operacja musi być wykonana na określonej maszynie (zachowane jest tylko ograniczenie dotyczące kolejności).
• planowanie otwartego sklepu , ale również bez ograniczeń związanych z zamówieniami.

Zobacz też

• Wykres rozłączny
• Programowanie dynamiczne
• Planowanie algorytmów genetycznych
• Lista problemów NP-zupełnych
• Optymalna kontrola
• Harmonogramowanie (procesy produkcyjne)

Linki zewnętrzne

• University of Vienna Katalog metodologii, systemów i oprogramowania do dynamicznej optymalizacji.
• Instancje Taillarda
•   Brucker P. Algorytmy planowania . Heidelberg, Springer. wyd. piąte. ISBN 978-3-540-24804-0