Johnson algoritması

Johnson algoritması, Johnson Sıralama Algoritması olarak da bilinir. Bir grup işin iki makinede sırasıyla çalışması sisteminde en iyi çözümü verir.

İşleyişi

Algoritma şu şekilde işler:

1. Yapılacak işlerin alt işleri bir listeye konulur. Buna A listesi diyelim. Ve iki tane boş liste oluşturulur. Bunlara da L1 ve L2 diyelim.

2. Bütün alt işler arasında en az miktarlı olan iş bulunur.

Eğer bu iş 1. makineye aitse, bu iş L1 listesinin sonuna eklenir ve A listesinden çıkarılır

Eğer bu iş 2. makineye aitse, bu iş L2 listesinin başına eklenir ve A listesinden çıkarılır

3. A listesi tamamen boşalana kadar 2. adım tekrar edilir

4. L1 ve L2 listeleri birleştirilir

Örnek

Makineler	P1 İşi	P2 İşi	P3 İşi	P4 İşi
M1 makinesi	3	9	8	4
M2 Makinesi	1	10	7	5

1. A={P1,P2,P3,P4} L1={} L2={}

2. En düşük süreli iş, P12'dir. İkinci makineye ait olduğu için P1'i, L2'nin başına ekleyip, A listesinden çıkarırız

A={P2,P3,P4} L1={} L2={P1}

Kalanlar içindeki en düşük süreli iş, P41'dir. P4, A listesinden çıkarılır ve L1'in sonuna eklenir

A={P2,P3} L1={P4} L2={P1}

Kalanlar içindeki en düşük süreli iş, P32'dir. P3, A listesinden çıkarılır ve L2'in başına eklenir

A={P2} L1={P4} L2={P3,P1}

Kalan iş L1'in sonuna veya L2'nin başına eklenebilir

A={} L1={P4,P2} L2={P3,P1}

4. İki liste birleştirlir

Sonuç: iş sırası = {P4,P2,P3,P1} şeklinde oluşur