Büyük bir yetkili araç servis merkezinde, kazalı olarak gelen 5 farklı aracın (A, B, C, D ve E) onarım süreci iki temel aşamadan oluşmaktadır. Araçlar sırasıyla önce Kaporta atölyesine, ardından Boya atölyesine girmek zorundadır. Her bir aracın bu atölyelerdeki tahmini işlem süreleri (gün cinsinden) aşağıdaki tabloda verilmiştir:
| Araç | Kaporta Süresi (Gün) | Boya Süresi (Gün) |
|---|---|---|
| A | 4 | 5 |
| B | 8 | 3 |
| C | 2 | 6 |
| D | 7 | 8 |
| E | 5 | 4 |
Tüm araçların toplam tamamlanma süresini (makespan) en aza indirmek isteyen servis müdürü, iş sıralamasını belirlemek için Johnson Algoritması'nı kullanmaya karar vermiştir.
Buna göre, araçların atölyelere giriş sırası aşağıdakilerden hangisi olmalıdır?
- AC - A - E - D - B
- BB - E - D - A - C
- C - A - D - E - BCevap
- DA - B - C - D - E
- EB - E - A - C - D
Cevap
Johnson algoritmasının kuralları adım adım uygulandığında, toplam tamamlanma süresini en aza indirecek doğru sıralama C - A - D - E - B olmalıdır.
Johnson algoritması, iki aşamalı üretim süreçlerinde 'makespan'i minimize etmek için kullanılır. Temel kural; 1. makinedeki en kısa süreleri en başa, 2. makinedeki en kısa süreleri ise en sona atamaktır. Tablo incelendiğinde sırasıyla şu adımlar izlenir: 1) Tüm sürelerin en küçüğü C'nin 1. aşama (kaporta) süresidir (2), bu yüzden C ilk sıraya yazılır. 2) Kalanlardan en küçüğü B'nin 2. aşama (boya) süresidir (3), bu yüzden B son sıraya (5.) yazılır. 3) Kalan A, D, E araçlarından en küçük süreler A'nın 1. aşama süresi (4) ve E'nin 2. aşama süresidir (4). A öne (2. sıraya), E ise sona doğru (4. sıraya) yerleştirilir. 4) Kalan tek araç D, ortadaki 3. boşluğa konulur. Elde edilen nihai optimum sıra C - A - D - E - B'dir.
Adım Adım Çözüm
Anahtar Kavram
Johnson Algoritması