Examkin

Soru

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

Bir çelik konstrüksiyon fabrikasında, beş farklı özel proje siparişinin (P1,P2,P3,P4,P5P_1, P_2, P_3, P_4, P_5) sırasıyla 'Kesim' (Makine 1) ve 'Kaynak' (Makine 2) atölyelerinden geçerek tamamlanması gerekmektedir. Projelerin her bir atölyedeki işlem süreleri (gün) aşağıdaki tabloda verilmiştir:

ProjeKesim (Makine 1) SüresiKaynak (Makine 2) Süresi
P1P_186
P2P_237
P3P_395
P4P_448
P5P_572

İşletme, bu beş projenin tamamlanma süresini (makespan) en aza indirmek istemektedir.

Buna göre, Johnson Algoritması kullanıldığında projelerin atölyelerdeki işlem sırası aşağıdakilerden hangisi olmalıdır?

  1. P2−P4−P1−P3−P5P_2 - P_4 - P_1 - P_3 - P_5Cevap
  2. B
    P5−P3−P1−P4−P2P_5 - P_3 - P_1 - P_4 - P_2
  3. C
    P2−P4−P5−P1−P3P_2 - P_4 - P_5 - P_1 - P_3
  4. D
    P5−P2−P4−P1−P3P_5 - P_2 - P_4 - P_1 - P_3
  5. E
    P5−P3−P1−P2−P4P_5 - P_3 - P_1 - P_2 - P_4

Cevap

Doğru sıralama P2−P4−P1−P3−P5P_2 - P_4 - P_1 - P_3 - P_5 şeklindedir.
Doğru seçenek, Johnson Algoritması'nın adımlarının harfiyen uygulanmasıyla elde edilmiştir. Algoritmaya göre tüm matris içindeki en küçük süre bulunur (M2'de 2 gün olan P5P_5) ve M2'de olduğu için en sona konur. Ardından kalanlar içinde en küçük süre (M1'de 3 gün olan P2P_2) bulunur ve M1'de olduğu için en başa konur. Bu eleme usulü devam ettirildiğinde kesin sıralama P2−P4−P1−P3−P5P_2 - P_4 - P_1 - P_3 - P_5 şeklinde çıkar.

Adım Adım Çözüm

1
Tüm süreler içindeki en küçük işlem zamanını bulmak ve kuralı uygulamak.
Tablodaki en kısa süre 2 gün ile P5P_5 projesinin Kaynak (Makine 2) işlemindedir. İkinci makinede olduğu için dizilimin en sonuna (5. sıraya) yerleştirilir. Geçici dizilim: [ _, _, _, _, P5P_5 ]
Johnson kuralına göre, tespit edilen en kısa süre ikinci makinede ise ilgili iş sıralamanın boş olan en sonuna atılır.
2
Kalan işler (P1,P2,P3,P4P_1, P_2, P_3, P_4) arasında en kısa işlem zamanını bulmak.
Kalanlar arasındaki en kısa süre 3 gün ile P2P_2'nin Kesim (Makine 1) işlemindedir. Birinci makinede olduğu için başa (1. sıraya) yerleştirilir. Geçici dizilim: [ P2P_2, _, _, _, P5P_5 ]
Tespit edilen en kısa süre birinci makinede ise, ilgili iş sıralamanın boş olan en başına atılır.
3
Kalan işler (P1,P3,P4P_1, P_3, P_4) arasında bir sonraki en kısa süreyi değerlendirmek.
Kalanlar arasındaki en kısa süre 4 gün ile P4P_4'ün Kesim (Makine 1) işlemindedir. Birinci makinede olduğu için baştaki ilk boş yere (2. sıraya) yerleştirilir. Geçici dizilim: [ P2P_2, P4P_4, _, _, P5P_5 ]
Birinci makine süresi küçük olan işler mümkün olduğunca öne doğru sıralanmalıdır.
4
Kalan son iki işi (P1,P3P_1, P_3) değerlendirmek.
Kalanlar arasındaki en kısa süre 5 gün ile P3P_3'ün Kaynak (Makine 2) işlemindedir. İkinci makinede olduğu için sondaki ilk boş yere (4. sıraya) yerleştirilir. Geçici dizilim: [ P2P_2, P4P_4, _, P3P_3, P5P_5 ]
İkinci makine süresi küçük olan işler mümkün olduğunca sona doğru sıralanmalıdır.
5
Kalan son işi yerleştirmek.
Kalan son iş olan P1P_1, dizilimdeki tek boş yer olan 3. sıraya (ortaya) yerleştirilir. Nihai dizilim: P2−P4−P1−P3−P5P_2 - P_4 - P_1 - P_3 - P_5
Algoritma tamamlanmış ve tüm işler kurallara uygun dizilmiştir.

Anahtar Kavram

İş Sıralama Kuralları ve Johnson Algoritması
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru