Examkin

Soru

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

Uluslararası bir yayınevi, yabancı dildeki beş farklı eserin (K1,K2,K3,K4,K5K_1, K_2, K_3, K_4, K_5) Türkçe yayın hazırlıklarını yapmaktadır. Bu eserlerin basıma hazır hale gelebilmesi için sırasıyla 'Çeviri' ve 'Redaksiyon' aşamalarından geçmesi gerekmektedir. İşlemler, her bir eser için çeviri tamamlandıktan sonra redaksiyona geçilecek şekilde iki aşamalı olarak yürütülmektedir. Eserlerin çeviri ve redaksiyon süreleri (gün olarak) aşağıdaki tabloda verilmiştir:

KitapÇeviri Süresi (Gün)Redaksiyon Süresi (Gün)
K1K_11214
K2K_285
K3K_31518
K4K_469
K5K_51011

Bu yayınevinin, beş kitabın tüm yayın hazırlık sürecini (toplam tamamlanma süresini) en aza indirmek için Johnson Algoritması'na göre uygulaması gereken iş sıralaması aşağıdakilerden hangisidir?

  1. A
    K2−K4−K5−K1−K3K_2 - K_4 - K_5 - K_1 - K_3
  2. B
    K4−K2−K5−K1−K3K_4 - K_2 - K_5 - K_1 - K_3
  3. C
    K2−K3−K1−K5−K4K_2 - K_3 - K_1 - K_5 - K_4
  4. K4−K5−K1−K3−K2K_4 - K_5 - K_1 - K_3 - K_2Cevap
  5. E
    K3−K1−K5−K4−K2K_3 - K_1 - K_5 - K_4 - K_2

Cevap

Doğru iş sıralaması K4−K5−K1−K3−K2K_4 - K_5 - K_1 - K_3 - K_2 şeklindedir.
Johnson algoritmasına göre; en kısa süre 2. makinede ise iş sona, 1. makinede ise başa yerleştirilerek listeden çıkarılır. İşlemler sırasıyla uygulandığında önce K2 sona yerleştirilir. Sonra kalanlarda K4'ün 1. aşama süresi en kısa (6) olduğu için en başa yerleşir. Ardından K5'in 1. aşama süresi (10) K1 ve K3'ten kısa olduğu için K4'ün yanına geçer. Sonraki en kısa süre K1'in 1. aşamasındadır (12) ve boş olan 3. sıraya geçer. Sona kalan K3 mecburen 4. sıraya yerleşir.

Adım Adım Çözüm

1
Tüm kitaplar ve aşamalar için en kısa sürenin tespit edilmesi.
Tüm tablo içindeki en küçük değer 5 gündür (K2K_2 kitabının redaksiyon süresi).
Johnson Algoritması, her adımda henüz sıralanmamış işler içindeki mutlak minimum işlem süresini arar.
2
En kısa süreye sahip olan K2K_2 kitabının sıralamaya yerleştirilmesi.
K2K_2 kitabı sıralamanın en sonuna (5. sıraya) yerleştirilir. Güncel sıralama: [_, _, _, _, K2K_2]
Algoritma kuralı gereği, tespit edilen en kısa süre 2. makinede/aşamada ise o iş sıralamanın en sonuna konur.
3
Kalan işler (K1,K3,K4,K5K_1, K_3, K_4, K_5) içinde en kısa sürenin bulunup yerleştirilmesi.
Kalanlarda en küçük değer 6 gündür (K4K_4, çeviri). Birinci aşama olduğu için başa yazılır. Güncel sıralama: [K4K_4, _, _, _, K2K_2]
Tespit edilen en kısa süre 1. makinede/aşamada ise o iş sıralamanın en başına (önden ilk boşluğa) konur.
4
Kalan işler (K1,K3,K5K_1, K_3, K_5) içinde işleme devam edilmesi.
Kalanlarda en küçük değer 10 gündür (K5K_5, çeviri). Önden ilk boşluğa (2. sıraya) yazılır. Güncel sıralama: [K4K_4, K5K_5, _, _, K2K_2]
Kalan işler içinde 1. makineye ait en küçük değer bulunduğu için baştan geriye doğru boş olan ilk yere yerleştirilir.
5
Kalan son iki işin (K1K_1 ve K3K_3) sıralanması.
Kalanlarda en küçük değer 12 gündür (K1K_1, çeviri). 3. sıraya yazılır. Kalan tek boşluğa (4. sıra) ise mecburen K3K_3 yazılır. Nihai sıralama: K4−K5−K1−K3−K2K_4 - K_5 - K_1 - K_3 - K_2
Algoritma adımları tüm işler bir sıraya yerleşene kadar periyodik olarak devam ettirilir.

Anahtar Kavram

Johnson Algoritması ile n İşin 2 Makinede Sıralanması
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru