Examkin

Question

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

Bir tıbbi tahlil laboratuvarına gelen beş farklı numune grubunun (N1,N2,N3,N4,N5N_1, N_2, N_3, N_4, N_5), laboratuvardaki iki farklı cihazda sırasıyla işlem görmesi gerekmektedir. Numuneler önce "Santrifüj" (Makine 1), ardından "Analiz" (Makine 2) cihazından geçmek zorundadır. Numunelerin cihazlardaki işlem süreleri (dakika cinsinden) aşağıdaki tabloda verilmiştir:

NumuneSantrifüj (Makine 1)Analiz (Makine 2)
N1N_186
N2N_235
N3N_372
N4N_458
N5N_594

Johnson Algoritması kullanılarak, numunelerin işlemden geçme süresini (toplam tamamlanma süresi) en aza indirecek optimal iş sıralaması ve bu sıralamaya göre tüm işlemlerin tamamlanacağı toplam süre (makespan) aşağıdakilerden hangisinde doğru verilmiştir?

  1. Sıralama: N2−N4−N1−N5−N3N_2 - N_4 - N_1 - N_5 - N_3 | Toplam Süre: 34 dakikaAnswer
  2. B
    Sıralama: N3−N5−N1−N4−N2N_3 - N_5 - N_1 - N_4 - N_2 | Toplam Süre: 43 dakika
  3. C
    Sıralama: N2−N4−N3−N1−N5N_2 - N_4 - N_3 - N_1 - N_5 | Toplam Süre: 36 dakika
  4. D
    Sıralama: N2−N3−N4−N5−N1N_2 - N_3 - N_4 - N_5 - N_1 | Toplam Süre: 38 dakika
  5. E
    Sıralama: N3−N5−N2−N1−N4N_3 - N_5 - N_2 - N_1 - N_4 | Toplam Süre: 41 dakika

Answer

Optimal sıralama N2−N4−N1−N5−N3N_2 - N_4 - N_1 - N_5 - N_3 şeklindedir ve bu sıralamaya göre toplam tamamlanma süresi 34 dakikadır.
Johnson algoritmasına göre iş sıralaması yapılırken, tüm işler için her iki makinedeki işlem sürelerine bakılır. En kısa süre Makine 1'de ise ilgili iş sıralamada öne, Makine 2'de ise sona alınır ve bu işlem kalan işler için tekrarlanır. En kısa süre 2 dakika ile Makine 2'de (N3N_3) olduğu için sona yazılır. Sonraki en kısa süre 3 dakika ile Makine 1'de (N2N_2) olduğundan başa yazılır. Ardından 4 dakika ile Makine 2'de yer alan N5N_5 sondan bir önceye yazılır. Kalan iki iş arasından 5 dakika ile Makine 1'de yer alan N4N_4 baştan ikinciye yazılır. Geriye kalan N1N_1 de ortaya yerleşir. Böylece optimal sıralama N2−N4−N1−N5−N3N_2 - N_4 - N_1 - N_5 - N_3 olur. Bu sıralamayla makinelerin çalışma ve bekleme süreleri çizelgelendiğinde (Gantt şeması) son iş olan N3N_3'ün ikinci makineden çıkış süresinin (toplam tamamlanma süresi) 34 dakika olduğu görülür.

Step-by-Step Solution

1
Tablodaki tüm işlem süreleri arasında en küçük değeri bul.
En küçük değer 2 dakikadır (N3N_3 numunesi, Analiz makinesi).
Johnson algoritması, kalan işler içindeki en kısa süreyi arayarak yerleştirme yapar.
2
Bulunan en küçük değerin hangi makinede olduğuna bakarak işin sırasını belirle.
2 dakika Makine 2'de olduğu için N3N_3 sıralamanın en sonuna yerleştirilir. Sıralama: _ - _ - _ - _ - N3N_3
Kurala göre en küçük süre 1. makinede ise iş boş olan ilk sıraya, 2. makinede ise boş olan son sıraya alınır.
3
Kalan numuneler (N1,N2,N4,N5N_1, N_2, N_4, N_5) arasında en küçük işlem süresini bul ve aynı kuralı uygula.
Kalanlar içindeki en küçük süre 3 dakikadır (N2N_2 numunesi, Makine 1). Makine 1'de olduğu için en başa yerleştirilir. Sıralama: N2N_2 - _ - _ - _ - N3N_3
Sıraya alınan iş tablodan çıkarılır ve kalan işler üzerinden algoritma sürdürülür.
4
Kalan numuneler (N1,N4,N5N_1, N_4, N_5) arasından sıradaki en küçük değeri bul ve yerleştir.
En küçük süre 4 dakikadır (N5N_5 numunesi, Makine 2). Makine 2'de olduğu için sondan bir önceki boşluğa yerleştirilir. Sıralama: N2N_2 - _ - _ - N5N_5 - N3N_3
Boş olan son sıraya yerleştirme kuralı devam ettirilir.
5
Son kalan numuneler (N1,N4N_1, N_4) arasından en küçük olanı bul, yerleştir ve geriye kalan son numuneyi de boşta kalan sıraya yaz.
Kalanlar içinde en küçük süre 5 dakikadır (N4N_4 numunesi, Makine 1). Baştan ikinci boşluğa yerleşir. Geriye kalan N1N_1 tam ortaya yerleşir. Nihai sıralama: N2N_2 - N4N_4 - N1N_1 - N5N_5 - N3N_3
Tüm işlerin sıralaması tamamlanmıştır.
6
Bulunan sıralamaya göre her işin makinelere giriş-çıkış sürelerini (Gantt tablosu mantığıyla) hesaplayarak makespan'i bul.
N2 (M1: 0-3, M2: 3-8), N4 (M1: 3-8, M2: 8-16), N1 (M1: 8-16, M2: 16-22), N5 (M1: 16-25, M2: 25-29), N3 (M1: 25-32, M2: 32-34). Tüm işlemler 34. dakikada biter.
İkinci makine, birinci makinede işi bitmeyen bir numuneyi işlemeye başlayamaz. Beklemeler dikkate alınarak toplam süre hesaplanmalıdır.

Key Concept

İki Makineli Sistemlerde İş Sıralama ve Johnson Algoritması
Rate this question

Topics

İş Sıralama Kuralları ve Johnson Algoritması

More questions from this topic