Examkin

Soru

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

Bir tekstil fabrikasının iş kıyafetleri üretim departmanında, dört farklı kurumsal müşteriden alınan özel dikim siparişleri (S1,S2,S3,S4S_1, S_2, S_3, S_4) sırasıyla Kesim ve Dikim atölyelerinde işlem görecektir.

Aşağıdaki tabloda her bir siparişin atölyelerdeki tahmini işlem süreleri (saat) verilmiştir:

SiparişKesim AtölyesiDikim Atölyesi
S1S_164
S2S_237
S3S_352
S4S_489

Tüm siparişlerin tamamlanma süresini (maksimum akış süresi) en aza indirmek isteyen üretim planlama uzmanının, Johnson Algoritması'nı kullanarak belirlemesi gereken en uygun işlem sırası aşağıdakilerden hangisidir?

  1. S2−S4−S1−S3S_2 - S_4 - S_1 - S_3Cevap
  2. B
    S3−S1−S4−S2S_3 - S_1 - S_4 - S_2
  3. C
    S2−S3−S1−S4S_2 - S_3 - S_1 - S_4
  4. D
    S3−S1−S2−S4S_3 - S_1 - S_2 - S_4
  5. E
    S4−S1−S3−S2S_4 - S_1 - S_3 - S_2

Cevap

Doğru sıralama S2−S4−S1−S3S_2 - S_4 - S_1 - S_3 şeklindedir.
Johnson Algoritması adım adım uygulandığında: Tablodaki en kısa süreli işlem 2 saat ile S3S_3 için 2. makinededir, bu yüzden S3S_3 sıralamada en sona konur. Geri kalan işler içinde en kısa işlem 3 saat ile S2S_2 için 1. makinededir, bu yüzden S2S_2 en başa konur. Geriye kalanlar içinde en kısa işlem 4 saat ile S1S_1 için 2. makinededir, bu yüzden S1S_1 boş olan en son sıraya (S3S_3'ün hemen önüne) konur. Geriye kalan tek iş olan S4S_4 ise boş kalan 2. sıraya yerleşir.

Adım Adım Çözüm

1
Tüm süreler içindeki en küçük değeri tespit edip, ilgili makineye göre yerleşim kuralını uygulayın.
Tablodaki en küçük değer, S3S_3 işinin Dikim Atölyesi'ndeki (2. makine) 2 saatlik süresidir. İkinci makinede olduğu için S3S_3 en sona (4. sıraya) yerleştirilir. Sıralama: [ _ , _ , _ , S3S_3 ]
Johnson Algoritması'na göre en kısa süre 2. makinede ise, o iş yapılabilecek en son sıraya atılarak 2. makinenin boş bekleme süresi azaltılır.
2
S3S_3'ü tablodan çıkarın ve kalan işler (S1,S2,S4S_1, S_2, S_4) arasındaki en küçük süreyi tespit edin.
Kalan süreler içindeki en küçük değer, S2S_2 işinin Kesim Atölyesi'ndeki (1. makine) 3 saatlik süresidir. Birinci makinede olduğu için S2S_2 en başa (1. sıraya) yerleştirilir. Sıralama: [ S2S_2 , _ , _ , S3S_3 ]
En kısa süre 1. makinede ise, o iş boş olan en ön sıraya yerleştirilir ki 2. makineye hızlıca iş aktarılabilsin.
3
S2S_2'yi tablodan çıkarın ve kalan işler (S1,S4S_1, S_4) arasındaki en küçük süreyi tespit edin.
Kalan işler arasında en küçük değer, S1S_1 işinin Dikim Atölyesi'ndeki (2. makine) 4 saatlik süresidir. İkinci makinede olduğu için S1S_1, boş olan en son sıraya (3. sıraya) yerleştirilir. Sıralama: [ S2S_2 , _ , S1S_1 , S3S_3 ]
İkinci makinede en kısa süreye sahip iş, sıralamadaki kalan boşlukların en sonuna eklenir.
4
Kalan son işi boş kalan sıraya yerleştirin.
Geriye sadece S4S_4 işi kalmıştır. Ortadaki son boşluğa (2. sıraya) yerleştirilir. Nihai sıralama: [ S2S_2 , S4S_4 , S1S_1 , S3S_3 ]
Tüm işler sıralanana kadar karşılıklı başa ve sona atma mantığı devam ettirilir.

Anahtar Kavram

İki makineli sistemlerde iş sıralamasının belirlenmesi ve toplam tamamlanma süresinin (makespan) minimizasyonu (Johnson Algoritması).
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru