Examkin

Soru

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

Ulusal çapta faaliyet gösteren bir yayınevinin özel basım atölyesinde, beş farklı prestij kitabının (K1,K2,K3,K4,K5K_1, K_2, K_3, K_4, K_5) üretim süreci planlanmaktadır. Kitapların üretimi sırasıyla önce 'Baskı' (1. Makine) ve ardından 'Ciltleme' (2. Makine) aşamalarından geçmek zorundadır. Kitapların her bir aşamadaki tahmini işlem süreleri saat cinsinden aşağıdaki tabloda verilmiştir:

KitapBaskı (1. Makine)Ciltleme (2. Makine)
K1K_145
K2K_282
K3K_376
K4K_439
K5K_564

Buna göre, yayınevinin toplam tamamlanma süresini (makespan) en aza indirmek için Johnson Algoritması'nı uyguladığı varsayıldığında, elde edilecek optimal iş sıralaması aşağıdakilerden hangisidir?

  1. K4−K1−K3−K5−K2K_4 - K_1 - K_3 - K_5 - K_2Cevap
  2. B
    K2−K5−K3−K1−K4K_2 - K_5 - K_3 - K_1 - K_4
  3. C
    K4−K1−K5−K3−K2K_4 - K_1 - K_5 - K_3 - K_2
  4. D
    K1−K2−K5−K4−K3K_1 - K_2 - K_5 - K_4 - K_3
  5. E
    K3−K4−K2−K5−K1K_3 - K_4 - K_2 - K_5 - K_1

Cevap

Optimal sıralama K4−K1−K3−K5−K2K_4 - K_1 - K_3 - K_5 - K_2 şeklindedir.
Doğru yanıt olan sıralama, Johnson Algoritması adımlarının harfiyen uygulanmasıyla elde edilmiştir. Algoritmaya göre tüm tablo taranarak en kısa süreli iş bulunur; eğer süre birinci makinedeyse iş en başa, ikinci makinedeyse en sona atanır. İşlem süreleri sırasıyla: K2K_2 (Makine 2: 2sa) sona atanır. Sonra K4K_4 (Makine 1: 3sa) başa atanır. Sonra 4 saatlik bir eşitlik ortaya çıkar: K1K_1 (Makine 1: 4sa) atanabilecek en başa, K5K_5 (Makine 2: 4sa) atanabilecek en sona yerleştirilir. Sona kalan K3K_3 ise araya alınır. Bu durumda doğru sıralama K4−K1−K3−K5−K2K_4 - K_1 - K_3 - K_5 - K_2 olur.

Adım Adım Çözüm

1
Tüm süreler içindeki en küçük değeri bul ve ilgili işi sıraya yerleştir.
Tablodaki en küçük süre 2 saattir (K2K_2, Ciltleme).
Süre 2. makinede (Ciltleme) olduğu için, Johnson algoritmasına göre K2K_2 işi sıralamanın EN SONUNA yerleştirilir: [ _ - _ - _ - _ - K_2 ]. K2K_2 tablodan çıkarılır.
2
Kalan işler (K1,K3,K4,K5K_1, K_3, K_4, K_5) içindeki en küçük süreyi bul ve yerleştir.
Kalan en küçük süre 3 saattir (K4K_4, Baskı).
Süre 1. makinede (Baskı) olduğu için, K4K_4 işi sıralamanın EN BAŞINA yerleştirilir: [ K_4 - _ - _ - _ - K_2 ]. K4K_4 tablodan çıkarılır.
3
Kalan işler (K1,K3,K5K_1, K_3, K_5) içindeki en küçük süreyi bul ve eşitlik durumunu çöz.
Kalan en küçük süre 4 saattir. Hem K1K_1'in Baskı süresi hem de K5K_5'in Ciltleme süresi 4'tür.
Eşitlik durumunda kurallar aynen uygulanır: K1K_1 1. makinede olduğu için kalan boşlukların EN BAŞINA (2. sıraya), K5K_5 2. makinede olduğu için kalan boşlukların EN SONUNA (4. sıraya) yerleştirilir: [ K_4 - K_1 - _ - K_5 - K_2 ]. İki iş de çıkarılır.
4
Kalan son işi boş olan sıraya yerleştir.
Geriye sadece K3K_3 işi kalmıştır.
Boş kalan tek yer olan 3. sıraya K3K_3 yerleştirilir ve nihai sıralama belirlenir: [ K_4 - K_1 - K_3 - K_5 - K_2 ].

Anahtar Kavram

Johnson Algoritması
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru