Examkin

Question

Difficulty: Mediumİş Sıralama Kuralları ve Johnson Algoritması

Bir endüstriyel ambalaj tesisinde, alınan beş farklı siparişin (S1, S2, S3, S4, S5) üretim süreci sırasıyla "Kesim" ve "Baskı" olmak üzere iki aşamadan oluşmaktadır. Bu aşamaların her birinde yalnızca birer makine bulunmaktadır. Siparişlerin ilgili makinelerdeki işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

SiparişKesim Süresi (Saat)Baskı Süresi (Saat)
S186
S237
S392
S458
S574

Tüm siparişlerin toplam tamamlanma süresini (makespan) minimize etmek isteyen tesis yönetimi, iş sıralamasını belirlerken Johnson Algoritması'nı kullanmaya karar vermiştir.

Buna göre, elde edilecek optimal iş sıralaması aşağıdakilerden hangisidir?

  1. S2 - S4 - S1 - S5 - S3Answer
  2. B
    S3 - S5 - S1 - S4 - S2
  3. C
    S2 - S4 - S5 - S1 - S3
  4. D
    S3 - S5 - S1 - S2 - S4
  5. E
    S2 - S3 - S5 - S4 - S1

Answer

S2 - S4 - S1 - S5 - S3
Optimal iş sıralaması Johnson Algoritması kullanılarak elde edilir. Algoritmada temel amaç, her iki makinedeki en küçük işlem süresini bularak, bu süre 1. makinedeyse işi olabildiğince başa; 2. makinedeyse olabildiğince sona planlamaktır. En kısa işlem S3'te 2. makinede (S3 en sonda). Sonra S2'de 1. makinede (S2 en başta). Sonra S5'te 2. makinede (S5 sondan ikinci). Sonra S4'te 1. makinede (S4 baştan ikinci). Son kalan S1 ise ortaya gelir. Doğru sıralama S2 - S4 - S1 - S5 - S3 şeklindedir.

Step-by-Step Solution

1
Tüm matris üzerindeki en kısa işlem süresini bul ve kuralı uygula.
En kısa süre S3'ün Baskı süresidir (2 saat). Baskı işlemi 2. aşama olduğu için S3 sıralamada en sona (5. sıraya) yerleştirilir. Sıralama: [ _ , _ , _ , _ , S3 ]
Johnson Algoritması'na göre en kısa süre 2. makinede ise, o iş kalan boşluklar içinde en sona alınır.
2
S3 dışındaki işler (S1, S2, S4, S5) arasından en kısa süreyi bul.
Kalanlar içindeki en kısa süre S2'nin Kesim süresidir (3 saat). Kesim işlemi 1. aşama olduğu için S2 sıralamada en başa (1. sıraya) yerleştirilir. Sıralama: [ S2 , _ , _ , _ , S3 ]
En kısa süre 1. makinede ise, o iş kalan boşluklar içinde en başa alınır.
3
S2 ve S3 dışındaki işler (S1, S4, S5) arasından en kısa süreyi bul.
Kalanlar içindeki en kısa süre S5'in Baskı süresidir (4 saat). 2. aşama olduğu için sağdan ilk boşluğa (S3'ün soluna) yerleştirilir. Sıralama: [ S2 , _ , _ , S5 , S3 ]
2. makinede olduğu için iş, mevcut sıralamada arkadan öne doğru ilk uygun boşluğa konur.
4
S1 ve S4 arasından en kısa süreyi bul.
Kalanlar içindeki en kısa süre S4'ün Kesim süresidir (5 saat). 1. aşama olduğu için soldan ilk boşluğa (S2'nin sağına) yerleştirilir. Sıralama: [ S2 , S4 , _ , S5 , S3 ]
1. makinede olduğu için iş, önden arkaya doğru ilk uygun boşluğa yerleştirilir.
5
Kalan son işi tek boş kalan yere yerleştir.
Kalan son iş S1'dir ve boş kalan ortadaki 3. sıraya yerleştirilir. Nihai sıralama: [ S2 , S4 , S1 , S5 , S3 ]
Sıralama matrisi tamamlanmıştır.

Key Concept

Johnson Algoritması
Estimated Time:1m 30s
Rate this question

Topics

İş Sıralama Kuralları ve Johnson Algoritması

More questions from this topic