Examkin

Soru

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

Bir ağır sanayi işletmesi, aldığı 5 farklı endüstriyel transformatör siparişinin (T1,T2,T3,T4,T5T_1, T_2, T_3, T_4, T_5) üretimini planlamaktadır. Üretim süreci, tüm transformatörler için sırasıyla 'Bobin Sarımı' (1. Aşama) ve 'Montaj ve Test' (2. Aşama) olmak üzere iki temel aşamadan oluşmaktadır. Siparişlerin her bir aşamadaki işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

Sipariş1. Aşama (Bobin Sarımı)2. Aşama (Montaj ve Test)
T1T_185
T2T_247
T3T_362
T4T_439
T5T_578

Tüm siparişlerin tamamlanma süresini (maksimum akış süresini) en aza indirmek isteyen işletme yönetiminin, Johnson Algoritmasına göre uygulaması gereken optimal iş sıralaması aşağıdakilerden hangisidir?

  1. T4−T2−T5−T1−T3T_4 - T_2 - T_5 - T_1 - T_3Cevap
  2. B
    T3−T1−T5−T2−T4T_3 - T_1 - T_5 - T_2 - T_4
  3. C
    T4−T2−T3−T5−T1T_4 - T_2 - T_3 - T_5 - T_1
  4. D
    T3−T1−T2−T5−T4T_3 - T_1 - T_2 - T_5 - T_4
  5. E
    T3−T2−T4−T1−T5T_3 - T_2 - T_4 - T_1 - T_5

Cevap

Optimal sıralama T4−T2−T5−T1−T3T_4 - T_2 - T_5 - T_1 - T_3 şeklindedir.
Johnson algoritmasına göre, tabloda eşzamanlı olarak aranılan en kısa işlem süreleri bulunduğunda; eğer süre 1. makinede/aşamada ise o iş sıralamanın en başına, eğer süre 2. makinede/aşamada ise o iş sıralamanın en sonuna yerleştirilir. Tablodaki en kısa süre T3T_3 işi için 2. aşamadadır (2 saat), bu nedenle T3T_3 en sona (5. sıraya) konur. Kalan işlerde en kısa süre T4T_4 işi için 1. aşamadadır (3 saat), bu nedenle T4T_4 en başa (1. sıraya) konur. Sonraki en kısa süre T2T_2 işi için 1. aşamadadır (4 saat), bu yüzden T4T_4'ün ardına (2. sıraya) yerleştirilir. Kalan iki iş (T1,T5T_1, T_5) arasından en kısa süre T1T_1'in 2. aşamasındadır (5 saat), bu yüzden sondaki ilk boşluğa (T3T_3'ün önüne, 4. sıraya) konur. Kalan T5T_5 işi ise ortadaki (3. sıradaki) boşluğa yerleşir. Böylece algoritma eksiksiz tamamlanarak optimal sonuç olan 'T4−T2−T5−T1−T3T_4 - T_2 - T_5 - T_1 - T_3' dizilimi elde edilir.

Adım Adım Çözüm

1
Tüm matristeki en kısa işlem süresini bulma
En küçük değer 2 saattir (2. Aşamada T3T_3 işi).
Johnson algoritması her iterasyonda en kısa süreyi arar.
2
T3T_3 işini sıralamaya yerleştirme
Süre 2. aşamada olduğu için T3T_3 en sona konur. Sıralama: [ _, _, _, _, T3T_3 ]
Kurala göre en kısa süre 2. makinede/aşamada ise iş sıralamanın sonuna yerleştirilir.
3
Kalan işler (T1,T2,T4,T5T_1, T_2, T_4, T_5) arasından en kısa süreyi bulma
En küçük değer 3 saattir (1. Aşamada T4T_4 işi).
Yerleştirilen iş listeden çıkarılır ve işlem tekrarlanır.
4
T4T_4 işini sıralamaya yerleştirme
Süre 1. aşamada olduğu için T4T_4 en başa konur. Sıralama: [ T4T_4, _, _, _, T3T_3 ]
Kurala göre en kısa süre 1. makinede/aşamada ise iş sıralamanın başına yerleştirilir.
5
Kalan işler (T1,T2,T5T_1, T_2, T_5) arasından en kısa süreyi bulma ve yerleştirme
En küçük değer 4 saattir (1. Aşamada T2T_2). 1. aşamada olduğu için baştan sıradaki boşluğa yerleştirilir. Sıralama: [ T4T_4, T2T_2, _, _, T3T_3 ]
Baştaki ilk boşluk T4T_4'ün hemen ardıdır.
6
Kalan işler (T1,T5T_1, T_5) arasından en kısa süreyi bulma ve yerleştirme
En küçük değer 5 saattir (2. Aşamada T1T_1). 2. aşamada olduğu için sondan sıradaki boşluğa yerleştirilir. Sıralama: [ T4T_4, T2T_2, _, T1T_1, T3T_3 ]
Sondaki ilk boşluk T3T_3'ün hemen öncesidir.
7
Son işi yerleştirme
Kalan tek iş olan T5T_5 ortadaki boşluğa yazılır. Nihai sıralama: T4−T2−T5−T1−T3T_4 - T_2 - T_5 - T_1 - T_3.
Tüm işler kurallara uygun biçimde dizilmiştir.

Anahtar Kavram

Johnson Algoritması (İki Makineli n İş Problemi)
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru