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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.