Examkin

Soru

Zorluk: Ortaİş Sıralama Kuralları ve Johnson Algoritması

Bir büyükşehir belediyesinin İmar ve Şehircilik Dairesi Başkanlığında, beş farklı büyük ölçekli konut projesinin (P1,P2,P3,P4,P5P_1, P_2, P_3, P_4, P_5) ruhsat onay süreci iki aşamadan oluşmaktadır. Projeler sırasıyla önce 'Mimari Proje İnceleme' (1. Aşama) ardından 'Statik Proje İnceleme' (2. Aşama) birimlerinden geçmek zorundadır.

Projelerin bu birimlerdeki tahmini inceleme süreleri (gün olarak) aşağıdaki tabloda verilmiştir:

ProjeMimari Proje İnceleme (Gün)Statik Proje İnceleme (Gün)
P1P_168
P2P_2116
P3P_373
P4P_497
P5P_5410

Buna göre, tüm projelerin toplam tamamlanma süresini (makespan) en aza indirmek amacıyla Johnson Algoritması uygulandığında, projelerin doğru incelenme sırası aşağıdakilerden hangisi olmalıdır?

  1. A
    P3−P5−P1−P4−P2P_3 - P_5 - P_1 - P_4 - P_2
  2. B
    P5−P1−P2−P4−P3P_5 - P_1 - P_2 - P_4 - P_3
  3. P5−P1−P4−P2−P3P_5 - P_1 - P_4 - P_2 - P_3Cevap
  4. D
    P5−P1−P3−P4−P2P_5 - P_1 - P_3 - P_4 - P_2
  5. E
    P3−P2−P4−P1−P5P_3 - P_2 - P_4 - P_1 - P_5

Cevap

Doğru sıralama P5−P1−P4−P2−P3P_5 - P_1 - P_4 - P_2 - P_3 şeklindedir.
Johnson algoritmasına göre tüm süreler içindeki en küçük değer bulunur. Bu değer 1. aşamadaysa iş dizinin en başına, 2. aşamadaysa en sonuna yerleştirilir. Tablodaki en küçük süre 3 gündür ve P3P_3'ün 2. aşamasına aittir; bu yüzden P3P_3 dizinin en sonuna konur. Kalan işler arasındaki en küçük süre 4 gündür (P5P_5, 1. aşama) ve P5P_5 en başa konur. Kalan P1,P2,P4P_1, P_2, P_4 için en küçük süre 6 gündür (P1P_1 1. aşamada, P2P_2 2. aşamada). 1. aşamada olan P1P_1 mevcut boşlukların en başına, 2. aşamada olan P2P_2 ise en sonuna konur. Geriye kalan P4P_4 ortaya yerleşir. Doğru sıralama P5−P1−P4−P2−P3P_5 - P_1 - P_4 - P_2 - P_3 olur.

Adım Adım Çözüm

1
Tablodaki en kısa işlem süresini tespit etme.
Tüm matristeki en kısa süre 3 gündür (P3P_3, Statik İnceleme - 2. Aşama).
Algoritma her zaman atanmamış işler içindeki en küçük sürenin bulunmasıyla başlar.
2
P3P_3 projesini sıralamaya yerleştirme.
P3P_3 dizinin en sonuna (5. sıraya) yerleştirilir.
En kısa süre 2. aşamada (Statik İnceleme) olduğu için iş, boş olan son pozisyona atanır.
3
Kalan işler (P1,P2,P4,P5P_1, P_2, P_4, P_5) içindeki en kısa süreyi bulma ve yerleştirme.
En kısa süre 4 gündür (P5P_5, Mimari İnceleme - 1. Aşama). P5P_5 dizinin en başına (1. sıraya) yerleştirilir.
En kısa süre 1. aşamada olduğu için iş mevcut dizinin en başına atanır.
4
Kalan işler (P1,P2,P4P_1, P_2, P_4) içindeki en kısa süreleri bulma ve yerleştirme.
En kısa süre 6 gündür (P1P_1 için 1. aşamada ve P2P_2 için 2. aşamada). P1P_1 baştaki ilk boşluğa (2. sıraya), P2P_2 sondaki ilk boşluğa (4. sıraya) yerleştirilir.
1. aşamadaki en kısa süreli iş boşlukların başına, 2. aşamadaki en kısa süreli iş ise boşlukların sonuna doğru yerleştirilir.
5
Son kalan işi (P4P_4) yerleştirme.
P4P_4 dizide kalan tek boşluğa (3. sıraya) yerleştirilir ve nihai dizi P5−P1−P4−P2−P3P_5 - P_1 - P_4 - P_2 - P_3 olarak elde edilir.
Atanmayan tek iş kaldığı için zorunlu olarak merkezdeki boş pozisyona yerleşir.

Anahtar Kavram

Johnson Algoritması (İki Makineli n İş Sıralaması)
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru