Algorytm Johnsona

Algorytm ten dotyczy zagadnienia harmonogramowania pracy dwóch maszyn (m=2) na n działkach roboczych (obiektach). Został sformułowany przy założeniu, że harmonogramowanie jest wieloetapowym procesem planowania. Algorytm S. Johnsona charakteryzuje się prostotą i małym zakresem obliczeń numerycznych.

Oznaczmy przez a_j oraz b_j (j=1,2,…,n) czasy wykonania robót na obiekcie j odpowiednio: przez pierwszą i drugą maszynę (i=1,2) oraz niech i₁, i₂,…, i_n oznacza permutację, określającą optymalną kolejność

1. Przyjąć r=1, s=n.

2. Znaleźć najmniejszą liczbę spośród czasów a_j, b_j (j=1,2,…,n).

3. Jeżeli liczbą tą jest a_k, to i_k=k oraz r=r+1, jeżeli zaś liczbą tą jest b_l, to i_s=1 oraz s=s-1.

4. Usunąć ze zbiorów czasu trwania parę (a_k, b_k) lub (a_l, b_l).

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

j i	1	2	3	4	5	6	7
a	8	4	1	6	3	7	5
b	5	6	4	3	5	2	1

Iteracja 1

1. Przyjmujemy r=1, s=7

2. Wyznaczamy:

min{a₁, a₂, a₃, a₄, a₅, a₆, a₇, b₁, b₂, b₃, b₄, b₅, b₆, b₇}= a₃=1

3. Ponieważ liczbą tą jest a₃ to i₁=3 oraz r=1+1=2

4. Usuwamy ze zbioru parę (a₃, b₃)=(1,4)

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

Iteracja 2

1. Przyjmujemy r=2, s=7

2. Wyznaczamy:

min{a₁, a₂, a₄, a₅, a₆, a₇, b₁, b₂, b₄, b₅, b₆, b₇}= b₇=1

3. Ponieważ liczbą tą jest b₇ to i₂=7 oraz s=7-1=6

4. Usuwamy ze zbioru parę (a₇, b₇)=(5,1)

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

Iteracja 3

1. Przyjmujemy r=2, s=6

2. Wyznaczamy:

min{a₁, a₂, a₄, a₅, a₆, b₁, b₂, , b₄, b₅, b₆}= b₆=2

3. Ponieważ liczbą tą jest b₆ to i₃=6 oraz s=6-1=5

4. Usuwamy ze zbioru parę (a₆, b₆)=(7,2)

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

Iteracja 4

1. Przyjmujemy r=2, s=5

2. Wyznaczamy:

min{a₁, a₂, a₄, a₅, b₁, b₂, b₄, b₅}= a₅=3

3. Ponieważ liczbą tą jest a₅ to i₄=5 oraz r=2+1=3

4. Usuwamy ze zbioru parę (a₅, b₅)=(3,5)

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

Iteracja 5

1. Przyjmujemy r=3, s=5

2. Wyznaczamy:

min{ a₁, a₂, a₄, b₁, b₂, b₄,}= b₄=3

3. Ponieważ liczbą tą jest b₄ to i₅=4 oraz s=5-1=4

4. Usuwamy ze zbioru parę (a₄, b₄)=(6,3)

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

Iteracja 6

1. Przyjmujemy r=3, s=4

2. Wyznaczamy:

min{a₁, a₂, b₁, b₂}= a₂=4

3. Ponieważ liczbą tą jest a₂ to i₃=2 oraz r=3+1=4

4. Usuwamy ze zbioru parę (a₂, b₂)=(4,6)

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

Iteracja 7

1. Przyjmujemy r=4, s=4

2. Wyznaczamy:

min{a₁, b₁ }= b₁=5

3. Ponieważ liczbą tą jest a₁ to i₇=1 oraz s=4-1=3

4. Usuwamy ze zbioru parę (a₁, b₁)=(8,5)

i1	i2	i3	i4	i5	i6	i7
3	7	6	5	4	2	1