Examkin

Soru

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

Bağımsız bir film yapım şirketinin post-prodüksiyon stüdyosunda, beş farklı reklam filmi projesinin (P1,P2,P3,P4,P5P_1, P_2, P_3, P_4, P_5) işlemleri gerçekleştirilecektir. Her proje sırasıyla önce 'Kurgu' (1. Aşama) daha sonra 'Renk ve Ses Miksajı' (2. Aşama) departmanından geçmek zorundadır. Projelerin bu iki departmandaki işlem süreleri (gün olarak) aşağıdaki tabloda verilmiştir:

ProjeKurgu (1. Aşama)Renk ve Ses (2. Aşama)
P1P_162
P2P_235
P3P_387
P4P_449
P5P_554

Stüdyo yöneticisi, tüm projelerin tamamlanma süresini (maksimum akış süresi) en aza indirmek istemektedir.

Buna göre, yöneticinin Johnson Algoritması'nı kullanarak belirleyeceği optimal işlenme sırası aşağıdakilerden hangisidir?

  1. P2−P4−P3−P5−P1P_2 - P_4 - P_3 - P_5 - P_1Cevap
  2. B
    P2−P4−P5−P1−P3P_2 - P_4 - P_5 - P_1 - P_3
  3. C
    P1−P2−P5−P4−P3P_1 - P_2 - P_5 - P_4 - P_3
  4. D
    P1−P5−P3−P4−P2P_1 - P_5 - P_3 - P_4 - P_2
  5. E
    P3−P1−P5−P4−P2P_3 - P_1 - P_5 - P_4 - P_2

Cevap

Johnson Algoritmasına göre doğru sıralama P2−P4−P3−P5−P1P_2 - P_4 - P_3 - P_5 - P_1 olmalıdır.
Johnson Algoritması, iki iş istasyonundan belirli bir sırayla geçmek zorunda olan n adet işin toplam tamamlanma süresini minimize etmek için kullanılır. Kurala göre tüm matristeki en küçük işlem süresi bulunur; bu süre birinci makinedeyse iş mümkün olan en öne, ikinci makinedeyse mümkün olan en sona yerleştirilir. Bu mantıkla sırasıyla P1P_1 en sona, P2P_2 en başa, P4P_4 önden ikinciye, P5P_5 sondan ikinciye yerleştirildiğinde ve ortaya kalan P3P_3 konulduğunda P2−P4−P3−P5−P1P_2 - P_4 - P_3 - P_5 - P_1 sıralaması elde edilir.

Adım Adım Çözüm

1
Tüm projeler ve her iki aşama için tablodaki en kısa işlem süresi bulunur.
En kısa süre 22 gün ile P1P_1 projesinin 2. Aşamasındadır (Renk ve Ses).
Algoritmanın ilk adımı tüm matris içindeki minimum değeri tespit etmektir.
2
P1P_1 projesi sıralamadaki yerine yerleştirilir ve tablodan çıkarılır.
P1P_1 projesi en kısa süresi 2. Aşama'da olduğu için sıralamanın en sonuna (5.5. sıraya) yerleştirilir. Sıralama: [_,_,_,_,P1][\_, \_, \_, \_, P_1]
Johnson algoritmasında en kısa süre 2. makinede/aşamada ise o iş mevcut olan en son sıraya atanır.
3
Kalan projeler (P2,P3,P4,P5P_2, P_3, P_4, P_5) arasında en kısa işlem süresi bulunur.
Kalanlar içindeki en kısa süre 33 gün ile P2P_2 projesinin 1. Aşamasındadır.
İşlem gören proje elenir ve kalanlar arasından yeni minimum değer aranır.
4
P2P_2 projesi sıralamadaki yerine yerleştirilir ve tablodan çıkarılır.
P2P_2 projesi en kısa süresi 1. Aşama'da olduğu için sıralamanın en başına (1.1. sıraya) yerleştirilir. Sıralama: [P2,_,_,_,P1][P_2, \_, \_, \_, P_1]
Johnson algoritmasında en kısa süre 1. makinede/aşamada ise o iş mevcut olan en baştaki sıraya atanır.
5
Kalan projeler (P3,P4,P5P_3, P_4, P_5) arasında en kısa işlem süresi bulunur.
En kısa süre 44 gündür. Bu değer hem P4P_4'ün 1. Aşamasında hem de P5P_5'in 2. Aşamasındadır.
Eşitlik durumunda her iki iş de ait oldukları aşama kuralına göre yerleştirilebilir.
6
P4P_4 ve P5P_5 projeleri sıralamadaki yerlerine yerleştirilir.
P4P_4 projesi 1. Aşamada kısa olduğu için baştan ilk boş yer olan 2.2. sıraya, P5P_5 projesi 2. Aşamada kısa olduğu için sondan ilk boş yer olan 4.4. sıraya konur. Sıralama: [P2,P4,_,P5,P1][P_2, P_4, \_, P_5, P_1]
Eşit sürelere sahip işler kendi aşama kurallarına (1. aşamaysa öne, 2. aşamaysa sona) sadık kalınarak eş zamanlı yerleştirilebilir.
7
Kalan son proje olan P3P_3 boşta kalan sıraya yerleştirilir.
P3P_3 projesi 3.3. sıraya yerleşir. Nihai sıralama: P2−P4−P3−P5−P1P_2 - P_4 - P_3 - P_5 - P_1 olarak bulunur.
Tüm işler bitene kadar süreç tekrarlanır ve boş kalan son yer son işe ayrılır.

Anahtar Kavram

İki makineli sistemlerde maksimum akış süresini (makespan) minimize eden Johnson Algoritmasının uygulanması.
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru