Examkin

Soru

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

Bir seramik üretim atölyesinde, beş farklı özel siparişin (S1,S2,S3,S4,S5S_1, S_2, S_3, S_4, S_5) sırasıyla 'Şekillendirme' (Makine 1) ve 'Fırınlama' (Makine 2) işlemlerinden geçmesi gerekmektedir. Bu siparişlere ait işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

SiparişŞekillendirmeFırınlama
S1S_164
S2S_227
S3S_375
S4S_4410
S5S_583

Johnson algoritmasına göre, tüm siparişlerin en kısa sürede tamamlanabilmesi için işlerin sıralaması aşağıdakilerden hangisi olmalıdır?

  1. A
    S2−S4−S1−S3−S5S_2 - S_4 - S_1 - S_3 - S_5
  2. B
    S5−S1−S3−S4−S2S_5 - S_1 - S_3 - S_4 - S_2
  3. C
    S4−S2−S3−S1−S5S_4 - S_2 - S_3 - S_1 - S_5
  4. S2−S4−S3−S1−S5S_2 - S_4 - S_3 - S_1 - S_5Cevap
  5. E
    S2−S1−S5−S3−S4S_2 - S_1 - S_5 - S_3 - S_4

Cevap

Doğru sıralama S2−S4−S3−S1−S5S_2 - S_4 - S_3 - S_1 - S_5 şeklinde olmalıdır.
Johnson algoritmasına göre kurallar adım adım işletildiğinde; ilk olarak S2S_2 (1. makinede 2 saat) en başa, ardından S5S_5 (2. makinede 3 saat) en sona alınır. Kalanlar arasından S4S_4 (1. makinede 4 saat) başa, S1S_1 (2. makinede 4 saat) sona eklenir ve en son kalan S3S_3 araya yerleşir. Bu dizilim S2−S4−S3−S1−S5S_2 - S_4 - S_3 - S_1 - S_5 dizilimidir.

Adım Adım Çözüm

1
Tüm süreler içindeki en kısa işlem süresi belirlenir.
En kısa süre 2 saattir (S2S_2 siparişinin Şekillendirme süresi). Bu süre 1. makinede olduğu için S2S_2 sıralamanın en başına yerleştirilir. (Sıralama: S2S_2 - _ - _ - _ - _)
Johnson algoritması kuralına göre; en kısa işlem süresi 1. makinedeyse iş ilk sıraya alınır.
2
Kalan işler (S1,S3,S4,S5S_1, S_3, S_4, S_5) arasından en kısa süre bulunur.
En kısa süre 3 saattir (S5S_5 siparişinin Fırınlama süresi). Süre 2. makinede olduğu için S5S_5 sıralamanın en sonuna yerleştirilir. (Sıralama: S2S_2 - _ - _ - _ - S5S_5)
Kurala göre; en kısa işlem süresi 2. makinedeyse iş son sıraya alınır.
3
Geriye kalan işler (S1,S3,S4S_1, S_3, S_4) arasından yeni en kısa süreler bulunur ve atanır.
En kısa süre 4 saattir. Bu süre hem S1S_1 siparişinde (Fırınlama) hem de S4S_4 siparişinde (Şekillendirme) vardır. S4S_4 1. makinede olduğundan baştaki ilk boşluğa (2. sıraya), S1S_1 ise 2. makinede olduğundan sondaki ilk boşluğa (4. sıraya) yerleştirilir. (Sıralama: S2S_2 - S4S_4 - _ - S1S_1 - S5S_5)
Süreler eşit olsa da hangi makinede bulunduğuna bakılarak 1. makinedekiler başa, 2. makinedekiler sona doğru itilir.
4
Kalan son iş, boş kalan tek sıraya yerleştirilir.
Geriye kalan S3S_3 siparişi, boş kalan 3. sıraya yerleştirilir. Nihai sıralama: S2−S4−S3−S1−S5S_2 - S_4 - S_3 - S_1 - S_5
Tüm siparişler atandığında algoritma tamamlanmış olur.

Anahtar Kavram

Johnson Algoritması Kuralları
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru