Planowanie przepływowe

Planowanie Flow-shop to problem optymalizacyjny w informatyce i badaniach operacyjnych . Jest to wariant optymalnego planowania pracy . W ogólnym problemie szeregowania zadań mamy n zadań J ₁ , J ₂ , ..., J _n o różnych czasach przetwarzania, które należy zaplanować na m maszynach o różnej mocy obliczeniowej, starając się jednocześnie zminimalizować makepan – całkowitą długość harmonogramu (to znaczy, kiedy wszystkie zadania zostały zakończone). W specyficznym wariancie znanym jako harmonogramowanie przepływowe każde zlecenie zawiera dokładnie m operacji. I ta operacja zadania musi zostać wykonana na i -tej maszynie. Żadna maszyna nie może wykonywać jednocześnie więcej niż jednej operacji. Dla każdej operacji każdego zadania określony jest czas wykonania.

Planowanie typu flow-shop jest szczególnym przypadkiem planowania typu job-shop , w którym istnieje ścisła kolejność wykonywania wszystkich operacji na wszystkich zadaniach. Harmonogramowanie przepływowe może dotyczyć zarówno zakładów produkcyjnych , jak i projektów komputerowych . Szczególnym typem problemu szeregowania przepływowego jest permutacyjny problem szeregowania przepływowego, w którym kolejność przetwarzania zadań na zasobach jest taka sama dla każdego kolejnego kroku przetwarzania.

W standardowej trójpolowej notacji dla problemów z optymalnym planowaniem zadań wariant flow-shop jest oznaczony przez F w pierwszym polu. Na przykład problem oznaczony przez „ F3 | ${\ displaystyle p_ {ij}}$ | ${\ displaystyle C _ {\ max}}$ " to problem z przepływem 3 maszyn z jednostkowymi czasami przetwarzania, gdzie celem jest zminimalizowanie maksymalnego czasu realizacji.

Definicja formalna

Jest m maszyn i n miejsc pracy. Każde zadanie zawiera dokładnie m operacji. I ta operacja zadania musi zostać wykonana na i -tej maszynie. Żadna maszyna nie może wykonywać jednocześnie więcej niż jednej operacji. Dla każdej operacji każdego zadania określony jest czas wykonania.

Operacje w ramach jednego zadania muszą być wykonywane w określonej kolejności. Pierwsza operacja jest wykonywana na pierwszej maszynie, następnie (po zakończeniu pierwszej operacji) druga operacja na drugiej i tak dalej, aż do n-tej operacji . Zadania można jednak wykonywać w dowolnej kolejności. Z definicji problemu wynika, że ​​ta kolejność zadań jest dokładnie taka sama dla każdej maszyny. Problem polega na określeniu optymalnego takiego układu, czyli takiego, który zapewnia możliwie najkrótszy całkowity czas wykonania zadania.

Pomiary wydajności sekwencjonowania (γ)

Problem sekwencjonowania można określić jako określenie sekwencji S takiej, że jeden lub kilka celów sekwencjonowania jest zoptymalizowanych.

1. (Średni) czas przepływu ${\ Displaystyle \ suma (w_ {i}) F_ {i}}$
2. . rozpiętość, C _maks
3. (Średnia) spóźnienie, ${\ Displaystyle \ suma (w_ {i}) T_ {i}}$
4. ....

szczegółowe omówienie pomiaru wydajności można znaleźć w Malakooti (2013).

Złożoność planowania flow-shop

Jak przedstawili Garey i in. (1976), większość rozszerzeń problemów harmonogramowania przepływów jest NP-trudnych i niewiele z nich można optymalnie rozwiązać w O(nlogn); na przykład F2|prmu|C _max można optymalnie rozwiązać za pomocą reguły Johnsona .

Taillard zapewnia istotne problemy wzorcowe do planowania sklepów przepływowych, otwartych sklepów i sklepów z ofertami pracy.

Metody rozwiązania

Proponowane metody rozwiązywania problemów typu flow-shop-scheduling można sklasyfikować jako algorytm dokładny , taki jak algorytm rozgałęziony i związany , oraz algorytm heurystyczny, taki jak algorytm genetyczny .

Minimalizacja rozpiętości, C _max

F2|prmu|C _max i F3|prmu|C _max można optymalnie rozwiązać za pomocą reguły Johnsona, ale dla ogólnego przypadku nie ma algorytmu gwarantującego optymalność rozwiązania.

Przepływomierz zawiera n zadań jednocześnie dostępnych w czasie zero i do przetworzenia przez dwie maszyny ustawione szeregowo z nieograniczoną pamięcią między nimi. Czas przetwarzania wszystkich zadań jest znany z całą pewnością. Wymagane jest zaplanowanie n zadań na maszynach tak, aby zminimalizować makepan. Reguła Johnsona dotycząca planowania zadań w warsztacie przepływowym z dwoma maszynami jest podana poniżej.

W optymalnym harmonogramie praca i poprzedza pracę j, jeśli min{p _1i ,p _2j } < min{p _1j ,p _2i } . Gdzie as, p _1i to czas przetwarzania zadania i na maszynie 1, a p _2i to czas przetwarzania zadania i na maszynie 2. Podobnie p _1j i p _2j to odpowiednio czasy przetwarzania zadania j na maszynie 1 i maszynie 2.

Dla algorytmu Johnsona:

Niech p _1j będzie czasem przetwarzania zadania j na maszynie 1

, a p _2j czasem przetwarzania zadania j na maszynie 2

Algorytm Johnsona:

1. Zestaw formularzy 1 zawierający wszystkie prace z p _1j < p _2j
2. Zestaw formularzy 2 zawierający wszystkie prace z p _1j > p _2j , prace z p _1j = p _2j można umieścić w dowolnym zestawie.
3. Utwórz sekwencję w następujący sposób:

   (i) Zadanie w zbiorze 1 jest pierwsze w sekwencji i następuje w porządku rosnącym p _1j (SPT)

   (ii) Zadania w zestawie 2 następują w porządku malejącym p _2j (LPT). Więzy są zrywane arbitralnie.

Ten typ harmonogramu jest określany jako harmonogram SPT(1)–LPT(2).

Szczegółowe omówienie dostępnych metod rozwiązania zawiera Malakooti (2013).

Zobacz też

• Planowanie otwartego sklepu
• Planowanie pracy w sklepie