Examkin

Question

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

Endüstriyel unlu mamuller üreten bir tesiste, dört farklı büyük parti siparişin (S1,S2,S3,S4S_1, S_2, S_3, S_4) sırasıyla önce 'Hamur Hazırlama' (Makine 1) ve ardından 'Pişirme' (Makine 2) işlemlerinden geçmesi gerekmektedir. Siparişlerin her bir makinedeki işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

SiparişHamur Hazırlama (Makine 1)Pişirme (Makine 2)
S1S_136
S2S_284
S3S_375
S4S_421

Tüm siparişlerin tamamlanma süresini (maksimum akış süresi) en aza indirmek isteyen tesis yöneticisi, Johnson Algoritması'nı kullanarak bir üretim çizelgesi oluşturacaktır.

Buna göre, siparişlerin atölyedeki işlem sırası aşağıdakilerden hangisi olmalıdır?

  1. S1−S3−S2−S4S_1 - S_3 - S_2 - S_4Answer
  2. B
    S4−S2−S3−S1S_4 - S_2 - S_3 - S_1
  3. C
    S4−S1−S3−S2S_4 - S_1 - S_3 - S_2
  4. D
    S4−S1−S2−S3S_4 - S_1 - S_2 - S_3
  5. E
    S2−S3−S1−S4S_2 - S_3 - S_1 - S_4

Answer

İşlem sırası S1−S3−S2−S4S_1 - S_3 - S_2 - S_4 şeklinde olmalıdır.
Johnson Algoritması adım adım uygulandığında; tablodaki en küçük değer 1 saat ile S4S_4'ün ikinci makinedeki işlemidir, bu yüzden S4S_4 en sona konur. Kalanlar arasından en küçük değer 3 saat ile S1S_1'in birinci makinedeki işlemidir, S1S_1 en başa konur. Sonraki en küçük değer 4 saat ile S2S_2'nin ikinci makinedeki işlemidir, sondaki boşluğa (sağdan sola) yerleştirilir. Son kalan S3S_3 ise aradaki boşluğa yerleştirilir. Doğru sıralama S1−S3−S2−S4S_1 - S_3 - S_2 - S_4 olarak elde edilir.

Step-by-Step Solution

1
Tüm tablo içindeki en küçük işlem süresini belirle.
En küçük süre 1 saattir ve S4S_4 siparişinin Makine 2'deki (Pişirme) işlem süresidir.
Johnson algoritmasının ilk adımı, matristeki mutlak en küçük değeri bulmaktır.
2
S4S_4 siparişinin konumunu belirle.
En kısa süre Makine 2'de olduğu için S4S_4 sıralamanın en sonuna yerleştirilir. Sıralama: [ _ - _ - _ - S4S_4 ]
Kural gereği, en kısa süre birinci makinedeyse iş başa, ikinci makinedeyse iş sona atanır.
3
Kalan işler (S1,S2,S3S_1, S_2, S_3) arasından en küçük işlem süresini belirle.
Kalanlar içindeki en küçük süre 3 saattir ve S1S_1 siparişinin Makine 1'deki işlem süresidir.
Ataması yapılan iş tablodan çıkarılır ve kalanlar üzerinden aynı kural işletilir.
4
S1S_1 siparişinin konumunu belirle.
En kısa süre Makine 1'de olduğu için S1S_1 boş olan en ön sıraya yerleştirilir. Sıralama: [ S1S_1 - _ - _ - S4S_4 ]
Birinci makinedeki en kısa süreler her zaman baştan sağa doğru yerleştirilir.
5
Kalan işler (S2,S3S_2, S_3) arasından en küçük süreyi bul ve ata.
En küçük süre 4 saattir (S2S_2, Makine 2). Makine 2'de olduğu için S2S_2 boş olan en son sıraya yerleştirilir. Sıralama: [ S1S_1 - _ - S2S_2 - S4S_4 ]
İkinci makinedeki değerler sondan sola doğru boş yerlere yerleştirilir.
6
Son kalan işi boşluğa yerleştir.
Geriye sadece S3S_3 kalmıştır. Boş olan tek sıraya yerleşir. Nihai sıralama: [ S1S_1 - S3S_3 - S2S_2 - S4S_4 ]
Tüm işler sıralandığında algoritma tamamlanır.

Key Concept

Johnson Algoritması, ardışık iki makineden veya iş merkezinden geçen n adet işin sıralamasını yaparak toplam tamamlanma süresini (Makespan) minimize etmeye yarayan bir yöntemdir.
Estimated Time:1m 30s
Rate this question

Topics

İş Sıralama Kuralları ve Johnson Algoritması

More questions from this topic