Examkin

Question

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

Bir kamu kurumunun lokomotif bakım-onarım tesisinde, 5 farklı lokomotifin (L1,L2,L3,L4,L5L_1, L_2, L_3, L_4, L_5) periyodik bakım işlemleri yapılacaktır. Bakım süreci sırasıyla "Söküm ve Temizlik" (1. Aşama) ve "Motor Revizyonu" (2. Aşama) olmak üzere iki temel aşamadan oluşmaktadır. Lokomotiflerin her bir aşamadaki işlem süreleri (gün olarak) aşağıdaki tabloda verilmiştir:

LokomotifSöküm ve Temizlik (1. Aşama)Motor Revizyonu (2. Aşama)
L1L_146
L2L_273
L3L_325
L4L_458
L5L_584

Tüm lokomotiflerin bakım işlemlerinin en kısa sürede (minimum toplam tamamlanma süresi) bitirilmesi hedeflenmektedir.

Buna göre, atölye şefinin Johnson Algoritması'nı kullanarak belirlemesi gereken optimum iş sıralaması aşağıdakilerden hangisidir?

  1. A
    L2L_2 - L5L_5 - L4L_4 - L1L_1 - L3L_3
  2. B
    L3L_3 - L1L_1 - L2L_2 - L5L_5 - L4L_4
  3. L3L_3 - L1L_1 - L4L_4 - L5L_5 - L2L_2Answer
  4. D
    L3L_3 - L1L_1 - L4L_4 - L2L_2 - L5L_5
  5. E
    L2L_2 - L5L_5 - L3L_3 - L1L_1 - L4L_4

Answer

Doğru sıralama L3L_3 - L1L_1 - L4L_4 - L5L_5 - L2L_2 şeklinde olmalıdır.
Johnson Algoritması kuralına göre, tüm aşamalardaki süreler incelenerek en küçük değere sahip olan işlem bulunur. Eğer bu değer 1. aşamada ise söz konusu iş öne (başa), 2. aşamada ise arkaya (sona) atılır ve listeden çıkarılır. İşlem, geriye iş kalmayana dek tekrarlanır. En küçük değer L3L_3'ün 1. aşamasındaki '2'dir (L3L_3 1. sırada). Sonraki en küçük değer L2L_2'nin 2. aşamasındaki '3'tür (L2L_2 5. sırada). Sonraki en küçük değer 4 olup hem L1L_1 (1. aşama) hem L5L_5 (2. aşama) için geçerlidir (L1L_1 2. sıraya, L5L_5 4. sıraya). Geriye kalan L4L_4 ise 3. sıraya yerleşir. Böylece doğru dizilim L3L_3 - L1L_1 - L4L_4 - L5L_5 - L2L_2 olarak belirlenir.

Step-by-Step Solution

1
Tablodaki tüm süreler içinden en küçük değeri bulmak.
En küçük değer 2 gündür ve bu süre L3L_3 lokomotifinin 1. aşama (Söküm ve Temizlik) süresidir.
Johnson algoritması, kalan tüm işler içindeki mutlak en küçük işlem süresini bulmakla başlar.
2
L3L_3 lokomotifini sıralamaya yerleştirmek ve tablodan çıkarmak.
L3L_3 süresi 1. aşamada olduğu için sıralamanın en başına (1. sıraya) yerleştirilir. Sıralama: [L3L_3, _, _, _, _].
Kural gereği, en küçük süre 1. makinede/aşamada ise iş en başa, 2. aşamada ise en sona yerleştirilir.
3
Kalan işler (L1,L2,L4,L5L_1, L_2, L_4, L_5) arasındaki en küçük değeri bulup yerleştirmek.
Kalan işlerdeki en küçük değer 3 gündür (L2L_2'nin 2. aşama süresi). 2. aşamada olduğu için sıralamanın en sonuna yerleştirilir. Sıralama: [L3L_3, _, _, _, L2L_2].
Tablodan çıkanlar haricindeki en küçük değer 2. aşamaya ait olduğu için kalan boşlukların en sonuna eklenir.
4
Kalan işler (L1,L4,L5L_1, L_4, L_5) arasındaki en küçük değeri bulup yerleştirmek.
En küçük değer 4 gündür. Bu değer hem L1L_1'in 1. aşamasında hem de L5L_5'in 2. aşamasında vardır. L1L_1 1. aşamada olduğundan başa yakın ilk boşluğa (2. sıra), L5L_5 ise 2. aşamada olduğundan sona yakın boşluğa (4. sıra) konulur. Sıralama: [L3L_3, L1L_1, _, L5L_5, L2L_2].
Eşitlik durumunda kurallar aynı şekilde uygulanmaya devam eder; 1. aşamadakiler öne, 2. aşamadakiler arkaya yerleşir.
5
Geriye kalan son işi ortadaki boşluğa yerleştirmek.
Geriye sadece L4L_4 işi kaldığı için ortadaki tek boş yer olan 3. sıraya yazılır. Nihai sıralama: [L3L_3, L1L_1, L4L_4, L5L_5, L2L_2] olur.
Tüm işler bitene kadar algoritma tekrarlanır.

Key Concept

Johnson Algoritması (İki Makineli Üretim Sistemlerinde N İşin Sıralanması)
Rate this question

Topics

İş Sıralama Kuralları ve Johnson Algoritması

More questions from this topic