Examkin

Soru

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

Uluslararası bir dijital medya ajansında, beş farklı reklam filmi projesinin (P1,P2,P3,P4,P5P_1, P_2, P_3, P_4, P_5) post-prodüksiyon süreçleri planlanmaktadır. Tüm projeler sırasıyla önce "Kurgu" (1. Aşama), ardından "Renklendirme ve Görsel Efekt" (2. Aşama) işlemlerinden geçmek zorundadır.

Projelerin her bir aşamadaki tahmini işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

ProjeKurgu Süresi (Saat)Renklendirme Süresi (Saat)
P1P_1146
P2P_2818
P3P_3512
P4P_4209
P5P_51115

Ajans yöneticisi, tüm projelerin tamamlanma süresini (makespan) en aza indirmek istemektedir.

Buna göre, Johnson Algoritması kullanılarak elde edilecek en uygun iş sıralaması ve tüm projelerin tamamlanması için geçecek toplam süre aşağıdakilerden hangisinde doğru verilmiştir?

  1. Sıralama: P3−P2−P5−P4−P1P_3 - P_2 - P_5 - P_4 - P_1 | Toplam Süre: 65 saatCevap
  2. B
    Sıralama: P3−P2−P5−P4−P1P_3 - P_2 - P_5 - P_4 - P_1 | Toplam Süre: 60 saat
  3. C
    Sıralama: P1−P4−P5−P2−P3P_1 - P_4 - P_5 - P_2 - P_3 | Toplam Süre: 90 saat
  4. D
    Sıralama: P3−P2−P5−P1−P4P_3 - P_2 - P_5 - P_1 - P_4 | Toplam Süre: 67 saat
  5. E
    Sıralama: P1−P4−P5−P2−P3P_1 - P_4 - P_5 - P_2 - P_3 | Toplam Süre: 65 saat

Cevap

Sıralama: P3−P2−P5−P4−P1P_3 - P_2 - P_5 - P_4 - P_1 | Toplam Süre: 65 saat olan seçenek doğrudur.
Johnson algoritması, 'n' adet işin 2 farklı ardışık makinede sıralanmasında toplam süreyi minimize eder. Kurala göre tüm süreler taranır; en küçük süre 1. makinedeyse o iş olabildiğince öne, 2. makinedeyse olabildiğince sona planlanır. Süreç P3P_3 (1. aşama=5) öne, P1P_1 (2. aşama=6) sona, P2P_2 (1. aşama=8) öne, P4P_4 (2. aşama=9) sona ve son kalan P5P_5'in ortaya alınmasıyla tamamlanır. Sıralama P3−P2−P5−P4−P1P_3 - P_2 - P_5 - P_4 - P_1 olur. Süre hesabı yapıldığında; 2. makine P3P_3 için 5. saatte başlar 17'de bitirir. P2P_2 17-35, P5P_5 35-50, P4P_4 50-59, P1P_1 ise 59-65 saatleri arasında işlenir. Tüm projeler 65. saatte biter.

Adım Adım Çözüm

1
Tüm süreler içindeki en küçük değeri bulma.
En kısa süre 5 saat ile P3P_3 projesinin 1. aşama (Kurgu) süresidir.
Johnson Algoritması, süresi en kısa olan işten başlar.
2
Bulunan en küçük süreli işi sıralamaya yerleştirme.
P3P_3 projesinin en kısa süresi 1. aşamada olduğu için sıralamanın en başına (P3P_3 - _ - _ - _ - _) yerleştirilir ve listeden çıkarılır.
1. aşamadaki en kısa süreli işler en erken, 2. aşamadaki en kısa süreli işler en geç yapılmalıdır.
3
Kalan işler (P1,P2,P4,P5P_1, P_2, P_4, P_5) arasından en küçük süreyi bulma.
Kalanlar içindeki en kısa süre 6 saat ile P1P_1 projesinin 2. aşama (Renklendirme) süresidir.
Aynı kural kalan işler kümesi için iteratif olarak tekrarlanır.
4
Bulunan işi sıralamaya yerleştirme.
Süre 2. aşamada olduğu için P1P_1 sıralamanın en sonuna (P3P_3 - _ - _ - _ - P1P_1) yerleştirilir ve listeden çıkarılır.
İkinci makinede işi çabuk bitenlerin sona bırakılması yığılmayı önler.
5
Kalan işler (P2,P4,P5P_2, P_4, P_5) için kuralı tekrarlama.
En kısa süre 8 saat (P2P_2, 1. aşama). Önden ilk boşluğa konur: (P3P_3 - P2P_2 - _ - _ - P1P_1). Kalanlar (P4,P5P_4, P_5) içinde en kısa süre 9 saat (P4P_4, 2. aşama). Sondan ilk boşluğa konur: (P3P_3 - P2P_2 - _ - P4P_4 - P1P_1). Kalan P5P_5 ortaya yerleşir. Nihai sıralama: P3−P2−P5−P4−P1P_3 - P_2 - P_5 - P_4 - P_1.
Tüm işler sıralanana kadar Johnson kuralı eksiksiz uygulanmış olur.
6
Elde edilen sıralamaya göre toplam tamamlanma süresini (Makespan) hesaplama.
1. Aşama bitişleri: P3=5P_3=5, P2=13P_2=13, P5=24P_5=24, P4=44P_4=44, P1=58P_1=58. 2. Aşama bitişleri: P3=5+12=17P_3=5+12=17, P2=17+18=35P_2=17+18=35, P5=35+15=50P_5=35+15=50, P4=50+9=59P_4=50+9=59, P1=59+6=65P_1=59+6=65. Toplam süre: 65 saattir.
Makespan, ikinci makinedeki (Renklendirme) son işin bitiş zamanıdır.

Anahtar Kavram

İki aşamalı üretim süreçlerinde toplam tamamlanma süresini (Makespan) minimize eden Johnson Algoritmasının uygulanması.

Alternatif Yöntem

Matematiksel takip yerine, her bir işi sırayla bir Gantt şemasına bloklar halinde çizerek bekleme sürelerini ve bitiş zamanını çok daha net bir şekilde görsel olarak hesaplayabilirsiniz.
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru