Examkin

Soru

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

Özel tasarım mücevherat üreten butik bir atölye, aldığı beş farklı pırlanta set siparişinin (S1,S2,S3,S4,S5S_1, S_2, S_3, S_4, S_5) üretimini planlamaktadır. Üretim süreci ardışık iki aşamadan oluşmaktadır: Birinci aşamada döküm ve sadekar işçiliği (1. İş Merkezi), ikinci aşamada ise taş mıhlama ve cilalama (2. İş Merkezi) işlemleri yapılmaktadır. Siparişlerin her iki iş merkezindeki tahmini işlem süreleri (gün olarak) aşağıdaki tabloda verilmiştir:

Sipariş1. İş Merkezi (Gün)2. İş Merkezi (Gün)
S1S_163
S2S_225
S3S_387
S4S_449
S5S_574

Tüm siparişlerin önce 1. İş Merkezi'nde, ardından 2. İş Merkezi'nde işlem görmesi zorunludur.

Buna göre, atölyenin tüm siparişleri en kısa sürede tamamlayabilmesi (toplam tamamlanma süresini en küçüklemesi) için Johnson Algoritması'na göre uygulaması gereken optimal iş sıralaması aşağıdakilerden hangisidir?

  1. S2−S4−S3−S5−S1S_2 - S_4 - S_3 - S_5 - S_1Cevap
  2. B
    S1−S5−S3−S4−S2S_1 - S_5 - S_3 - S_4 - S_2
  3. C
    S2−S4−S1−S5−S3S_2 - S_4 - S_1 - S_5 - S_3
  4. D
    S1−S5−S2−S3−S4S_1 - S_5 - S_2 - S_3 - S_4
  5. E
    S2−S1−S5−S4−S3S_2 - S_1 - S_5 - S_4 - S_3

Cevap

Optimal sıralama, S2S_2 ile başlayıp araya S4S_4 ve S3S_3 siparişlerinin alındığı, S5S_5 ve S1S_1 ile sonlanan dizilimdir.
Johnson Algoritması kuralları eksiksiz işletildiğinde, işlem sürelerinden en kısası 1. makinede ise en başa, 2. makinede ise en sona yerleştirilir. Bu bağlamda, S2S_2 (2 gün, M1) en başa alınır. Sonrasında kalan en kısa iş S1S_1'dir (3 gün, M2) ve en sona yerleştirilir. Kalanlarda en kısa süre 4 gündür (S4S_4 M1'de olduğu için başa doğru, S5S_5 M2'de olduğu için sona doğru yerleştirilir). Kalan son sipariş S3S_3 ise ortaya konur. Doğru dizilim bu şekilde elde edilir.

Adım Adım Çözüm

1
Tüm süreler içindeki en küçük değeri bulun ve ait olduğu iş merkezini belirleyin.
En küçük süre 2 gündür. Bu süre 1. İş Merkezi'nde S2S_2 siparişine aittir.
Algoritma en kısa işlemi bulup duruma göre başa veya sona yerleştirerek başlar.
2
Bulunan işi sıralamaya yerleştirin ve tablodan çıkarın.
S2S_2, 1. İş Merkezi'nde olduğu için sıralamanın en başına yerleştirilir. Sıralama: [S2S_2, _, _, _, _]
Birinci makinedeki en kısa işlem süresi, makine boş kalmasın diye sıralamanın başına konur.
3
Kalan süreler içindeki en küçük değeri bulup yerleştirin.
Kalanlar içindeki en küçük süre 3 gündür (S1S_1, 2. İş Merkezi). 2. İş Merkezi'nde olduğu için sıralamanın en sonuna yerleştirilir. Sıralama: [S2S_2, _, _, _, S1S_1]
İkinci makinedeki en kısa işlemler, sürecin son kısmında birikmeyi önlemek için sona atılır.
4
Sıradaki en küçük değerleri tespit edip aynı kuralla yerleştirin.
Sıradaki en küçük süre 4 gündür. (S4S_4, 1. İş Merkezi ve S5S_5, 2. İş Merkezi). S4S_4 başa (boş olan 2. sıraya), S5S_5 sona (boş olan 4. sıraya) yerleştirilir. Sıralama: [S2S_2, S4S_4, _, S5S_5, S1S_1]
Algoritma iteratif olarak içe doğru işler; kalan en baştaki ve en sondaki boşluklar doldurulur.
5
Kalan son işi boş kalan yere yerleştirin.
Sadece S3S_3 kalmıştır ve ortadaki tek boşluğa yerleşir. Final sıralama: [S2S_2, S4S_4, S3S_3, S5S_5, S1S_1]
Tüm siparişlerin ataması tamamlanmıştır.

Anahtar Kavram

İki makineli sistemlerde toplam tamamlanma süresini en küçüklemek için Johnson Algoritması'nın uygulanması.
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru