Johnson algoritması

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

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

Algoritma şu şekildedir

1. Adım 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. Adım 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. Adım A listesi tamamen boşalana kadar 2. adım tekrar edilir

4. Adım L1 ve L2 listeleri birleştirilir


Örnek

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


1. Adım: A={P1,P2,P3,P4} L1={} L2={}
2. Adım:
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 L1'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. Adım:
iki liste birleştirlir

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