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 

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

Grafik algoritmaları