Examkin

Soru

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

Bir elektronik bileşen üreticisinde, beş farklı özel devre kartı siparişinin (K1,K2,K3,K4,K5K_1, K_2, K_3, K_4, K_5) sırasıyla "Dizgi" (Makine 1) ve "Test" (Makine 2) aşamalarından geçmesi gerekmektedir. İşlerin her bir makinedeki işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

İş (Sipariş)Dizgi Süresi (Makine 1)Test Süresi (Makine 2)
K1K_164
K2K_227
K3K_385
K4K_431
K5K_596

İşletme, tüm siparişlerin tamamlanma süresini (makespan) en aza indirmek için Johnson Algoritması'nı kullanmaya karar vermiştir.

Buna göre, optimum iş sıralaması uygulandığında Test (Makine 2) aşamasının toplam boş kalma süresi ve tüm işlerin tamamlanma süresi sırasıyla aşağıdakilerden hangisidir?

  1. 7 saat / 30 saatCevap
  2. B
    16 saat / 39 saat
  3. C
    11 saat / 34 saat
  4. D
    5 saat / 30 saat
  5. E
    9 saat / 32 saat

Cevap

Optimum sıralama sonucunda Makine 2'nin boş kalma süresi 7 saat ve toplam tamamlanma süresi 30 saattir.
Johnson Algoritması doğru uygulandığında (en küçük değerler bulundukça Makine 1 ise başa, Makine 2 ise sona eklenerek) elde edilen sıralama K2−K5−K3−K1−K4K_2 - K_5 - K_3 - K_1 - K_4 şeklindedir. Bu sıralamaya göre bir zaman çizelgesi çıkarıldığında Makine 2 sırasıyla [0-2], [9-11], [17-19] ve [24-25] saatleri arasında toplam 7 saat boş kalır. Son iş olan K4K_4'ün Makine 2'den çıkış anı ise tüm operasyonun tamamlanma süresi olan 30 saati verir.

Adım Adım Çözüm

1
Johnson Algoritmasına göre tablodaki en kısa işlem süresini bul.
Tüm tablodaki en kısa süre Makine 2'de (Test) K4K_4 işi için 1 saattir.
Algoritmanın ilk adımı tüm işler ve makineler arasındaki en küçük değeri tespit etmektir.
2
En kısa sürenin ait olduğu işi sıralamaya yerleştir ve tablodan çıkar.
En kısa süre (1 saat) Makine 2'de olduğu için K4K_4 işi sıralamanın EN SONUNA yerleştirilir. Sıralama: [_, _, _, _, K4K_4]. K4K_4 elendi.
Kurala göre en kısa süre 1. makinede ise iş en başa, 2. makinede ise en sona atanır.
3
Kalan işler (K1,K2,K3,K5K_1, K_2, K_3, K_5) için aynı mantığı tekrar et.
Kalanlar içindeki en kısa süre Makine 1'de K2K_2 için 2 saattir. Makine 1'de olduğu için EN BAŞA yerleşir. Sıralama: [K2K_2, _, _, _, K4K_4].
Algoritma tüm işler sıralanana kadar kalan işler üzerinden iteratif olarak devam eder.
4
Kalan işler (K1,K3,K5K_1, K_3, K_5) için adımları sürdürerek tam dizilimi oluştur.
Sıradaki en kısa süre Makine 2'de K1K_1 (4 saat) -> Sona (boş olan en son yere) atılır: [K2K_2, _, _, K1K_1, K4K_4].
Sonraki en kısa süre Makine 2'de K3K_3 (5 saat) -> Sona atılır: [K2K_2, _, K3K_3, K1K_1, K4K_4].
Kalan son iş K5K_5 ortaya yerleşir. Nihai sıralama: K2−K5−K3−K1−K4K_2 - K_5 - K_3 - K_1 - K_4.
Tüm işler Johnson kuralına uygun bir şekilde yerleştirilmiştir.
5
Bulunan sıralamaya göre işlerin başlangıç ve bitiş zamanlarını (Gantt şeması mantığıyla) hesapla.
K2K_2: M1'de (0-2), M2'de (2-9). (M2 baştaki bekleme boşluğu: 2)
K5K_5: M1'de (2-11), M2'de (11-17). (M2'nin K2K_2 sonrası beklemesi: 11-9 = 2)
K3K_3: M1'de (11-19), M2'de (19-24). (M2 beklemesi: 19-17 = 2)
K1K_1: M1'de (19-25), M2'de (25-29). (M2 beklemesi: 25-24 = 1)
K4K_4: M1'de (25-28), M2'de (29-30). (M2 beklemesi: 29-29 = 0)
Her iş, birinci makinedeki işlemi bittiğinde ve aynı zamanda ikinci makine boş olduğunda ikinci makinede işleme başlayabilir.
6
Tamamlanma süresini ve M2'nin boş kalma süresini topla.
Tamamlanma Süresi (Makespan) = En son işin M2'den çıkış anı = 30 saat.
M2 Toplam Boş Kalma Süresi = 2 + 2 + 2 + 1 + 0 = 7 saat.
Test aşamasındaki (Makine 2) toplam işlem süresi 23 saattir. Tamamlanma süresi 30 saat olduğuna göre formül gereği boş zaman (30 - 23) 7 saattir.

Anahtar Kavram

Johnson Algoritması, iki makine veya iş istasyonundan belirli bir sırayla geçmesi gereken n adet işin toplam tamamlanma süresini (makespan) minimize eden matematiksel sıralama kuralıdır.
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru