Reguła Johnsona

W badaniach operacyjnych reguła Johnsona jest metodą planowania zadań w dwóch centrach pracy. Jego głównym celem jest znalezienie optymalnej sekwencji zadań, aby zredukować makepan (całkowity czas potrzebny do wykonania wszystkich zadań). Zmniejsza również ilość bezczynności między dwoma centrami roboczymi. Metoda minimalizuje rozpiętość w przypadku dwóch stanowisk roboczych. Ponadto metoda znajduje najkrótszą rozpiętość w przypadku trzech stanowisk roboczych, jeśli spełnione są dodatkowe ograniczenia.

Algorytm

Technika wymaga kilku warunków wstępnych :

• Czas dla każdej pracy musi być stały.
• Czasy zadań muszą wzajemnie się wykluczać w sekwencji zadań .
• Wszystkie zadania muszą zostać przetworzone w pierwszym centrum roboczym przed przejściem przez drugie centrum robocze.
• Wszystkie zadania mają jednakowy priorytet.

Reguła Johnsona jest następująca:

1. Wypisz zadania i ich czas w każdym centrum roboczym.
2. Wybierz pracę o najkrótszym czasie aktywności. Jeśli ten czas działania dotyczy pierwszego centrum roboczego, najpierw zaplanuj zadanie. Jeśli ten czas działania dotyczy drugiego centrum roboczego, zaplanuj zadanie jako ostatnie. Zrywaj więzy arbitralnie .
3. Wyeliminuj najkrótszą pracę z dalszych rozważań.
4. Powtarzaj kroki 2 i 3, przesuwając się w kierunku środka harmonogramu zadań, aż wszystkie zadania zostaną zaplanowane.

Biorąc pod uwagę znaczny czas przestoju w drugim centrum roboczym (od oczekiwania na zakończenie pracy na pierwszym stanowisku), można zastosować podział pracy.

Przykład

Każde z pięciu zadań musi przejść przez centrum robocze A i B. Znajdź optymalną sekwencję zadań, korzystając z reguły Johnsona.

Czas pracy (godziny)

Stanowisko	Centrum pracy A	Centrum pracy B
A	3.2	4.2
B	4.7	1.5
C	2.2	5.0
D	5.8	4.0
mi	3.1	2.8

1. Najmniej czasu znajduje się w Job B (1,5 godziny). Ponieważ czas jest w Centrum roboczym B, zaplanuj to zadanie jako ostatnie.

   Wyeliminuj zadanie B z dalszych rozważań.

   ?

   ?

   ?

   ?

   B

2. Następny najmniejszy czas znajduje się w zadaniu C (2,2 godziny). Ponieważ czas jest w Centrum roboczym A, najpierw zaplanuj to zadanie.

   Wyeliminuj zadanie C z dalszych rozważań.

   C

   ?

   ?

   ?

   B

3. Następny najmniejszy czas po tym znajduje się w zadaniu E (2,8 godziny). Ponieważ czas jest w Centrum roboczym B, zaplanuj to zadanie jako ostatnie.

   Wyeliminuj zadanie E z dalszych rozważań.

   C

   ?

   ?

   mi

   B

4. Następny najmniejszy czas po znajduje się w zadaniu A (3,2 godziny). Ponieważ czas jest w Centrum roboczym A, najpierw zaplanuj to zadanie.

   Wyeliminuj zadanie A z dalszych rozważań.

   C

   A

   ?

   mi

   B

5. Jedyną pracą, która pozostała do rozważenia, jest praca D.

   C

   A

   D

   mi

   B

Zatem zadania muszą być przetwarzane w kolejności C → A → D → E → B i muszą być przetwarzane w tej samej kolejności na obu stanowiskach roboczych.

Notatki

•   Morton, Tomasz; Pentico, David W. (2001-07-20). Heurystyczne systemy planowania: z aplikacjami do systemów produkcyjnych i ... - Thomas Morton, David W. Pentico - Książki Google . ISBN 9780471578192 . Źródło 2012-09-26 . J

Dalsza lektura

• William J Stevenson, Zarządzanie operacyjne, wydanie 9 , McGraw-Hill/Irwin, 2007