Examkin

Soru

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

Bir kamu kurumunun bilgi işlem merkezinde, 5 farklı genel müdürlükten gelen büyük veri analizi talepleri (D1D_1, D2D_2, D3D_3, D4D_4, D5D_5) işleme alınacaktır. Her bir veri seti sırasıyla önce 'Veri Hazırlama' (Sunucu 1), ardından 'Model Eğitimi' (Sunucu 2) aşamalarından geçmek zorundadır. Veri setlerinin her bir sunucudaki tahmini işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

Veri SetiVeri Hazırlama (Sunucu 1)Model Eğitimi (Sunucu 2)
D1D_186
D2D_237
D3D_392
D4D_458
D5D_574

Tüm işlerin toplam tamamlanma süresini (makespan) en aza indirmek isteyen sistem yöneticisi, Johnson Algoritması'nı kullanarak işleri sıralamak istemektedir.

Buna göre, veri setlerinin doğru işlenme sırası aşağıdakilerden hangisidir?

  1. D2−D4−D1−D5−D3D_2 - D_4 - D_1 - D_5 - D_3Cevap
  2. B
    D3−D5−D1−D4−D2D_3 - D_5 - D_1 - D_4 - D_2
  3. C
    D2−D4−D5−D1−D3D_2 - D_4 - D_5 - D_1 - D_3
  4. D
    D2−D3−D5−D4−D1D_2 - D_3 - D_5 - D_4 - D_1
  5. E
    D3−D5−D1−D2−D4D_3 - D_5 - D_1 - D_2 - D_4

Cevap

Veri setlerinin işlenme sırası sırasıyla D2−D4−D1−D5−D3D_2 - D_4 - D_1 - D_5 - D_3 olmalıdır.
Johnson Algoritması kuralına göre; tüm işlem süreleri içinde en küçük değer bulunur. Bu değer 1. aşamadaysa iş sıranın en başına, 2. aşamadaysa en sonuna yazılır. İşlem listeden silinir ve süreç kalan işler için tekrarlanır. En küçük değer D3D_3'ün 2. aşamasındaki 2 saattir, bu yüzden en sona D3D_3 konur. Kalanlar içindeki en küçük değer D2D_2'nin 1. aşamasındaki 3 saattir, en başa D2D_2 konur. Sonrakilerde D5D_5'in 2. aşamasındaki 4 saat bulunur ve sondaki boşluğa konur. Daha sonra D4D_4'ün 1. aşamasındaki 5 saat sebebiyle baştaki boşluğa konur. En son ortada kalan yere D1D_1 yazılır. Böylece sıralama D2−D4−D1−D5−D3D_2 - D_4 - D_1 - D_5 - D_3 olur.

Adım Adım Çözüm

1
Tüm süreler içindeki en küçük değeri bulma
En küçük süre 2 saattir (D3D_3, Sunucu 2).
Johnson algoritması, kalan en kısa sürenin ait olduğu makineye göre işi başa veya sona yerleştirerek ilerler.
2
En küçük sürenin konumuna göre işi yerleştirme
2 saatlik süre 2. makinede olduğu için D3D_3 işi en SONA yerleştirilir. Sıralama: [_, _, _, _, D3D_3]
Kural gereği, en kısa süre 2. aşamadaysa iş listenin sonundaki boşluğa yerleştirilir.
3
Kalan işler (D1,D2,D4,D5D_1, D_2, D_4, D_5) arasından en küçük süreyi bulma
En küçük süre 3 saattir (D2D_2, Sunucu 1). Süre 1. makinede olduğu için EN BAŞA yerleştirilir. Sıralama: [D2D_2, _, _, _, D3D_3]
Kural gereği, en kısa süre 1. aşamadaysa iş listenin başındaki ilk boşluğa yerleştirilir.
4
Kalan işler (D1,D4,D5D_1, D_4, D_5) arasından en küçük süreyi bulma
En küçük süre 4 saattir (D5D_5, Sunucu 2). Süre 2. makinede olduğu için sondaki ilk boşluğa yerleştirilir. Sıralama: [D2D_2, _, _, D5D_5, D3D_3]
İkinci makine kuralı gereğince boş alanların en sonuna doğru yerleşim yapılır.
5
Kalan işler (D1,D4D_1, D_4) arasından en küçük süreyi bulma
En küçük süre 5 saattir (D4D_4, Sunucu 1). Süre 1. makinede olduğu için baştaki ilk boşluğa yerleştirilir. Sıralama: [D2D_2, D4D_4, _, D5D_5, D3D_3]
Birinci makine kuralı gereğince boş alanların en başına doğru yerleşim yapılır.
6
Son kalan işi (D1D_1) yerleştirme
D1D_1 işi kalan tek boşluğa yerleşir ve nihai sıralama elde edilir: [D2D_2, D4D_4, D1D_1, D5D_5, D3D_3].
Algoritma tüm işler yerleştirildiğinde son bulur.

Anahtar Kavram

İki makineden/aşamadan oluşan süreçlerde, toplam tamamlanma zamanını (makespan) minimize etmek için ardışık iş sıralama yöntemidir.
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru