Examkin

Question

Difficulty: Mediumİş Sıralama Kuralları ve Johnson Algoritması

Ulusal bir referans laboratuvarında, 5 farklı hastaneden gelen kan numunesi partilerinin (N1,N2,N3,N4,N5N_1, N_2, N_3, N_4, N_5) analizi yapılacaktır.

Her bir numune partisi sırasıyla önce "Santrifüj ve Hazırlık" (1. İş Merkezi), ardından "Biyokimyasal Analiz" (2. İş Merkezi) aşamalarından geçmek zorundadır. Numune partilerinin her bir iş merkezindeki işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

Numune Partisi1. İş Merkezi (Saat)2. İş Merkezi (Saat)
N1N_163
N2N_225
N3N_389
N4N_447
N5N_552

Laboratuvar yöneticisi, tüm numune partilerinin analizinin en kısa sürede tamamlanması (toplam tamamlanma süresinin en küçüklenmesi) için Johnson Algoritmasını kullanacaktır.

Buna göre, numune partilerinin işleme alınma sırası aşağıdakilerden hangisi olmalıdır?

  1. A
    N5−N1−N3−N4−N2N_5 - N_1 - N_3 - N_4 - N_2
  2. B
    N2−N4−N5−N1−N3N_2 - N_4 - N_5 - N_1 - N_3
  3. C
    N5−N2−N1−N4−N3N_5 - N_2 - N_1 - N_4 - N_3
  4. N2−N4−N3−N1−N5N_2 - N_4 - N_3 - N_1 - N_5Answer
  5. E
    N3−N4−N2−N1−N5N_3 - N_4 - N_2 - N_1 - N_5

Answer

Doğru sıralama N2−N4−N3−N1−N5N_2 - N_4 - N_3 - N_1 - N_5 şeklinde olmalıdır.
Johnson Algoritması adımları sırasıyla uygulandığında; tablodaki en kısa süreler 2 saattir (N2N_2 için 1. Merkez, N5N_5 için 2. Merkez). Kural gereği N2N_2 ilk sıraya, N5N_5 son sıraya konur. Kalan numuneler arasında en kısa süre 3 saattir (N1N_1 için 2. Merkez) ve sona doğru kalan boşluğa alınır. Daha sonra kalanlar arasında en kısa süre 4 saattir (N4N_4 için 1. Merkez) ve başa doğru kalan boşluğa alınır. Kalan son numune olan N3N_3 ise ortaya yerleştirilir. Böylece N2−N4−N3−N1−N5N_2 - N_4 - N_3 - N_1 - N_5 sıralaması elde edilir.

Step-by-Step Solution

1
Tüm işlem süreleri arasından en küçük olanı (2 saat) belirle.
N2N_2'nin 1. iş merkezinde ve N5N_5'in 2. iş merkezinde en kısa süreye (2 saat) sahip olduğu görülür.
Johnson algoritmasının ilk kuralı, matristeki en küçük işlem süresini bulmaktır.
2
Bulunan en kısa sürelere göre ilgili işleri sıralamanın başına veya sonuna yerleştir.
N2N_2 1. iş merkezinde olduğu için sıralamanın en başına, N5N_5 2. iş merkezinde olduğu için sıralamanın en sonuna yerleştirilir. Yeni durum: N2N_2 - _ - _ - _ - N5N_5
Algoritma gereği, en kısa süre 1. makinedeyse iş başa, 2. makinedeyse sona atanır.
3
Kalan işler (N1,N3,N4N_1, N_3, N_4) arasından en küçük işlem süresini bul ve atama yap.
Kalanlar içindeki en küçük süre N1N_1'in 2. iş merkezindeki 3 saatlik süresidir. N1N_1 kalan boşlukların en sonuna atanır. Yeni durum: N2N_2 - _ - _ - N1N_1 - N5N_5
Atanan işler tablodan çıkarıldıktan sonra aynı kural kalan işler için tekrarlanır.
4
Son kalan işler (N3,N4N_3, N_4) için aynı adımı tekrarla ve sıralamayı tamamla.
Kalanlardan en küçük süre N4N_4'ün 1. iş merkezindeki 4 saatlik süresidir. N4N_4 başa atanır. Geriye kalan N3N_3 de boş kalan tek yere (ortaya) yazılır. Nihai sıralama: N2−N4−N3−N1−N5N_2 - N_4 - N_3 - N_1 - N_5
Tüm işler bitene kadar algoritma kuralları işletilir.

Key Concept

Johnson Algoritması (İki Makineli n İş Sıralaması)
Rate this question

Topics

İş Sıralama Kuralları ve Johnson Algoritması

More questions from this topic