Algorytm Johnsona

 

Wariant dla dwóch maszyn

 

• Algorytm ten dotyczy zagadnienia 

harmonogramowania pracy dwóch 
maszyn na „n” działkach roboczych 
(obiektach),

• Został sformułowany przy założeniu, 

że harmonogramowanie jest 
wieloetapowym procesem planowania,

• Algorytm Johnsona charakteryzuje się 

prostotą i małym zakresem obliczeń 
numerycznych.

Oznaczenia w algorytmie:
a – pierwsza maszyna,
b – druga maszyna,
aj – { } zbiór zawierający czasy trwania 

czynności wykonywanych przez pierwszą 

maszynę na kolejnych obiektach,

bj – { } zbiór zawierający czasy trwania 

czynności wykonywanych przez drugą 

maszynę na kolejnych obiektach,

i1, i2, ..., in - oznacza permutację (ustawienie 

w kolejności elementów zbioru 

skończonego), określającą optymalną 

kolejność obiektów.

Algorytm Johnsona jest następujący:

1. Przyjąć r = 1, s = n.
2. Znaleźć najmniejszą liczbę spośród 

czasów aj, bj (j = 1, 2, ..., n).

3. Jeżeli liczbą tą jest ak, to ir = k oraz r: 

= r +1, jeżeli zaś liczbą tą jest bl to is 

= l oraz s: = s - 1.

4. Usunąć ze zbioru czasów trwania parę 

(ak, bk) lub (al, bl). 

5. Powtórzyć postępowanie od punktu 2.

Przykład
• Dwie różne maszyny budowlane mają 

wykonywać prace na sześciu obiektach, 

• Czasy wykonania robót na kolejnych 

obiektach przez maszynę pierwszą  wynoszą 
odpowiednio: aj = { 2, 3, 5, 1, 7, 6 }, 

• Czasy wykonania robót na kolejnych 

obiektach przez maszynę drugą wynoszą 
odpowiednio: bj = { 3, 4, 4, 2, 5, 5 },

• Należy wyznaczyć kolejność realizacji 

obiektów budowlanych, której odpowiada 
minimalny cykl realizacji wszystkich robót 
łącznie.

Interacja 1

1. Przyjąć 

r = 1, s = 6.

2. Wyznaczyć

min{a1, a2, a3, a4, a5, a6, 
b1, b2, b3, b4, b5, b6} = a4 = 1

3. Ponieważ liczbą tą jest a4, 

to i1 = 4 oraz r = 1 + 1 = 2.

4. Usuwamy ze zbioru parę (a4, b4) = (1, 2).

5. Powtarzamy postępowanie od punktu 2. 

Interacja 2

1. Z poprzedniego kroku 

r = 2, s = 6.

2. Wyznaczyć

min{a1, a2, a3, a5, a6, 
b1, b2, b3, b5, b6} = a1 = 2

3. Ponieważ liczbą tą jest a4, 

to i2 = 1 oraz r = 2 + 1 = 3.

4. Usuwamy ze zbioru parę (a1, b1) = (2, 3).

5. Powtarzamy postępowanie od punktu 2. 

Interacja 3

1.

Z poprzedniego kroku 
r = 3, s = 6.

2.

Wyznaczyć
min{ a2, a3, a5, a6, b2, b3, b5, b6} = a2 

= 3

3.

Ponieważ liczbą tą jest a2, 
to i3 = 2 oraz r = 3 + 1 = 4.

4.

Usuwamy ze zbioru parę (a2, b2) = (3, 4).

5.

Powtarzamy postępowanie od punktu 2. 

Interacja 4

1. Z poprzedniego kroku 

r = 4, s = 6.

2. Wyznaczyć

min{ a3, a5, a6, b3, b5, b6} = b3 = 4

3. Ponieważ liczbą tą jest b3, 

to i6 = 3 oraz s = 6 – 1 = 5.

4. Usuwamy ze zbioru parę (a3, b3) = (5, 4).

5. Powtarzamy postępowanie od punktu 2. 

Interacja 5

1. Z poprzedniego kroku 

r = 4, s = 5.

2. Wyznaczyć

min{ a5, a6, b5, b6} = b5 = 5

3. Ponieważ liczbą tą jest b5, 

to i5 = 5 oraz s = 5 – 1 = 4.

4. Usuwamy ze zbioru parę (a5, b5) = (7, 5).

5. Powtarzamy postępowanie od punktu 2. 

Interacja 6

• Wykonanie iteracji 6 nie jest 

konieczne, ponieważ w 

sześcioelementowym zbiorze obiektów 

wyznaczyliśmy już kolejność realizacji 

pięciu obiektów, a mianowicie: 

• i1 = 4, i2 = 1, i3 = 2, i5 = 5, i6 = 3. 
• Widać więc, że obiekt 6, dla którego 

nie ustalono dotychczas kolejności, 

powinien być realizowany jako czwarty 

(po obiekcie 2, i4=6). 

Wynik algorytmu

Permutacją określającą optymalną 

kolejność realizacji obiektów jest 
permutacja:

i1=4, i2=1, i3=2, i4=6, i5=5, i6=3.

Wynik algorytmu