Examkin

Soru

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

Bir mobilya fabrikasında üretilecek olan K, L, M ve N özel siparişlerinin her biri sırasıyla önce 'Kesim' (1. Aşama) daha sonra 'Montaj' (2. Aşama) işlemlerinden geçmektedir. Siparişlerin her bir aşamadaki işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

SiparişKesim (1. Aşama)Montaj (2. Aşama)
K63
L27
M85
N49

Buna göre, tüm siparişlerin toplam tamamlanma süresini (makespan) en aza indirmek için bu işler Johnson Algoritması'na göre hangi sırayla atölyeye üretime verilmelidir?

  1. A
    K - M - N - L
  2. B
    L - N - K - M
  3. L - N - M - KCevap
  4. D
    K - M - L - N
  5. E
    M - K - N - L

Cevap

Siparişler L - N - M - K sırasıyla üretime verilmelidir.
Johnson Algoritması kuralına göre; tüm süreler arasından en küçük olan seçilir. Bu süre 1. makinede ise iş öne, 2. makinede ise iş sona yerleştirilir ve o iş tablodan çıkarılır. Bu işlem tekrarlanır. Önce en küçük süre olan 2 (L, Kesim) bulunur ve L başa alınır. Sonra kalanlar arasından en küçük süre 3 (K, Montaj) bulunur ve K sona alınır. Kalanlar arasından en küçük 4 (N, Kesim) bulunur, 1. makine olduğu için baştan sıradaki boşluğa alınır. Kalan M ise araya girer. Doğru dizilim L - N - M - K şeklinde oluşur.

Adım Adım Çözüm

1
Tüm siparişlerin her iki aşamadaki işlem süreleri arasından en küçük değeri bulun.
Tablodaki en küçük değer 2 saattir (L siparişi, Kesim aşaması).
Johnson Algoritması, her adımda henüz atanmamış işler içindeki mutlak en kısa süreyi bularak işlemeye başlar.
2
Bulunan en kısa sürenin hangi aşamaya ait olduğuna göre siparişin sırasını belirleyin.
Süre 1. aşamada (Kesim) olduğu için L siparişi sıralamada ilk boşluğa (en başa) yerleştirilir ve tablodan çıkarılır. (Mevcut sıralama: L - _ - _ - _ )
Birinci makinedeki süresi kısa olan işleri öne almak, ikinci makinenin boş bekleme süresini azaltır.
3
Kalan siparişler (K, M, N) için en küçük değeri bulup yerleştirme kuralını uygulayın.
Kalan süreler içindeki en küçük değer 3 saattir (K siparişi, Montaj aşaması). Süre 2. aşamada olduğu için K siparişi sıralamada son boşluğa yerleştirilir. (Mevcut sıralama: L - _ - _ - K )
İkinci makinedeki süresi kısa olan işleri sona bırakmak, sistemdeki iş birikiminin hızla eritilmesini sağlar.
4
Geriye kalan siparişleri (M ve N) kalan boşluklara kurala uygun şekilde yerleştirin.
M ve N arasındaki en küçük süre 4 saattir (N siparişi, Kesim aşaması). 1. aşamada olduğu için baştan ilk boş sıraya konur. Kalan tek iş olan M, kalan son boşluğa yerleştirilir. (Nihai sıralama: L - N - M - K )
Tüm işler sıralanana kadar algoritma adımları aynı mantıkla tekrar edilir.

Anahtar Kavram

İki makineli sistemlerde n adet işin toplam tamamlanma süresini (makespan) minimize eden Johnson Algoritması'nın uygulanması.
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru