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