Examkin

Soru

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

Bir otomotiv yetkili servisine hasar onarımı için dört farklı araç (A, B, C, D) gelmiştir. Bu araçlar sırasıyla önce 'Kaporta' bölümünde, ardından 'Boya' bölümünde işlem görecektir. Tüm araçların her iki bölümden de geçmesi zorunludur. Araçların bu bölümlerdeki tahmini işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

AraçKaporta İşlem SüresiBoya İşlem Süresi
A45
B83
C26
D79

Tüm araçların toplam onarım süresini (maksimum akış süresini) en aza indirmek isteyen servis müdürü, Johnson Algoritması'nı kullanarak işleri sıralamak istemektedir.

Buna göre, araçların atölyeye alınma sırası aşağıdakilerden hangisi olmalıdır?

  1. C - A - D - BCevap
  2. B
    B - D - A - C
  3. C
    C - A - B - D
  4. D
    C - B - A - D
  5. E
    D - C - A - B

Cevap

Araçların Johnson Algoritmasına göre atölyeye alınma sırası C - A - D - B şeklinde olmalıdır.
Johnson Algoritmasına göre sıralama yapılırken tablodaki en küçük değer aranır. Tablodaki en küçük değer C aracının 1. işlemindeki 2 saattir; 1. işlemde olduğu için C en başa alınır (Sıra: C - _ - _ - _). Kalanlar arasındaki en küçük değer B aracının 2. işlemindeki 3 saattir; 2. işlemde olduğu için B en sona alınır (Sıra: C - _ - _ - B). Geriye kalan A ve D araçlarından en kısa süre A'nın 1. işlemindeki 4 saattir; 1. işlemde olduğu için A, baştaki ilk boşluğa yerleştirilir (Sıra: C - A - _ - B). Son kalan D aracı da boş kalan 3. sıraya yerleştiğinde doğru sıralama C - A - D - B olarak elde edilir.

Adım Adım Çözüm

1
Tüm araçlar ve her iki işlem için tablodaki en kısa süre bulunur.
En kısa süre 2 saattir (C aracının Kaporta süresi).
Johnson algoritmasının ilk adımı, tüm matristeki en küçük işlem zamanını tespit etmektir.
2
Bulunan en kısa sürenin hangi bölüme (makineye) ait olduğuna bakılarak aracın sıralamadaki yeri belirlenir.
2 saatlik süre 1. bölüme (Kaporta) ait olduğu için C aracı sıralamada en başa (1. sıraya) yerleştirilir ve C aracı tablodan çıkarılır. Oluşan Sıralama: C - _ - _ - _
Kurala göre; en kısa süre 1. makinede ise iş en başa, 2. makinede ise en sona yerleştirilir.
3
Kalan araçlar (A, B, D) arasından en kısa süre tekrar bulunur.
Kalanlar içindeki en kısa süre 3 saattir (B aracının Boya süresi).
Listede kalan işler için aynı tespit işlemi tekrarlanır.
4
İkinci en kısa sürenin ait olduğu bölüme göre B aracının yeri belirlenir.
3 saatlik süre 2. bölüme (Boya) ait olduğu için B aracı sıralamanın en sonuna (4. sıraya) yerleştirilir ve tablodan çıkarılır. Oluşan Sıralama: C - _ - _ - B
En kısa süre 2. makinede olduğu için iş sona atılarak diğer işlemlerin önü açılır.
5
Kalan araçlar (A ve D) için en kısa süre tekrar bulunur ve son yerleşim yapılır.
Kalanlar içindeki en kısa süre 4 saattir (A aracının Kaporta süresi). Bu süre 1. bölüme ait olduğu için A aracı baştan boş olan ilk sıraya (2. sıraya) yerleştirilir. Sona kalan D aracı da doğal olarak 3. sıraya yazılır. Nihai Sıralama: C - A - D - B
Tüm işler sıralamaya yerleştirilene kadar döngü işletilir.

Anahtar Kavram

İş Sıralama Kuralları ve Johnson Algoritması
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru