Examkin

Soru

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

Bir dijital reklam ajansında dört farklı tanıtım kampanyasının (K1,K2,K3,K4K_1, K_2, K_3, K_4) sırasıyla 'Tasarım' ve 'Baskı' aşamalarından geçmesi gerekmektedir. İşlemlerin her bir aşamadaki tahmini tamamlanma süreleri (gün cinsinden) aşağıdaki tabloda verilmiştir:

KampanyaTasarım Süresi (Gün)Baskı Süresi (Gün)
K1K_185
K2K_2123
K3K_347
K4K_4910

Maksimum akış süresini (tüm işlerin bitiş süresini) en aza indirmek amacıyla Johnson Algoritması uygulandığında, işlerin sıralaması aşağıdakilerden hangisi olmalıdır?

  1. K3−K4−K1−K2K_3 - K_4 - K_1 - K_2Cevap
  2. B
    K2−K1−K4−K3K_2 - K_1 - K_4 - K_3
  3. C
    K3−K1−K4−K2K_3 - K_1 - K_4 - K_2
  4. D
    K3−K1−K2−K4K_3 - K_1 - K_2 - K_4
  5. E
    K2−K4−K1−K3K_2 - K_4 - K_1 - K_3

Cevap

Johnson algoritmasına göre optimum iş sıralaması K3−K4−K1−K2K_3 - K_4 - K_1 - K_2 şeklindedir.
Johnson Algoritması'na göre tablodaki en küçük değer aranır. Değer birinci makinede (Tasarım) ise iş öne, ikinci makinede (Baskı) ise iş sona yerleştirilir. Tablodaki en küçük değer 3 gün ile K2K_2'nin Baskı aşamasındadır; bu yüzden K2K_2 en sona konur. Kalan işlerde en küçük değer 4 gün ile K3K_3'ün Tasarım aşamasındadır; bu yüzden K3K_3 en başa konur. Kalan K1K_1 ve K4K_4 arasında en küçük değer 5 gün ile K1K_1'in Baskı aşamasındadır; K1K_1 sondan ikinciye yerleşir. Geriye kalan K4K_4 de kalan boşluğa yerleştirilir. Nihai doğru sıralama K3−K4−K1−K2K_3 - K_4 - K_1 - K_2 şeklindedir.

Adım Adım Çözüm

1
Tablodaki tüm süreler arasında en küçük değeri bulun.
En küçük süre 3 gündür (K2K_2 kampanyasının Baskı süresi).
Johnson algoritması her zaman tabloda kalan en küçük işlem süresini arayarak başlar.
2
En küçük süreye sahip olan K2K_2 işini yerleştirin ve tablodan çıkarın.
K2K_2 işi ikinci makinede (Baskı) olduğu için dizilimin en sonuna (4. sıraya) yerleştirilir: [ _ , _ , _ , K2K_2 ].
Kural gereği; en küçük süre birinci makinedeyse iş en başa, ikinci makinedeyse en sona konur.
3
Kalan işler (K1,K3,K4K_1, K_3, K_4) arasından en küçük süreyi bulun.
Kalanlar içindeki en küçük süre 4 gündür (K3K_3 kampanyasının Tasarım süresi).
Yerleştirilen işler tablodan çıkarılarak işleme devam edilir.
4
En küçük süreye sahip olan K3K_3 işini yerleştirin ve tablodan çıkarın.
K3K_3 işi birinci makinede (Tasarım) olduğu için dizilimin ilk sırasına (1. sıraya) yerleştirilir: [ K3K_3 , _ , _ , K2K_2 ].
Süre birinci aşamada olduğu için iş mevcut boşlukların en başına alınır.
5
Kalan iki iş (K1,K4K_1, K_4) arasından en küçük süreyi bulun.
En küçük süre 5 gündür (K1K_1 kampanyasının Baskı süresi).
Aynı algoritma döngüsü tekrar edilir.
6
K1K_1 işini yerleştirin ve geriye kalan son işi (K4K_4) boş kalan konuma ekleyin.
K1K_1 ikinci makinede olduğu için kalan boşlukların en sonuna (sondan ikinci sıraya) yerleşir. Geriye kalan K4K_4 ise aradaki tek boşluğa geçer. Nihai sıralama: [ K3K_3 , K4K_4 , K1K_1 , K2K_2 ] olur.
Tüm işler kurallara uygun biçimde dizilene kadar işleme devam edilir.

Anahtar Kavram

Johnson Algoritması Kuralları
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru