Johnson algoritması
Johnson algoritması (Johnson sıralama algoritması veya Johnson kuralı olarak da bilinir) bir grup işin, iki makinede sırasıyla çalışması sistemini planlama yöntemidir.[1][2] Birincil amacı yapım süresini (tüm işleri tamamlamak için gereken toplam süreyi) azaltmak için uygun iş sırasını bulmaktır. Ayrıca iki iş merkezi arasındaki boşta kalma süresini de azaltır.
Algoritma değiştir
Teknik birkaç ön koşul gerektirir:
- Her işin süresi sabit olmalıdır.
- İş süreleri, iş sırasından bağımsız olmalıdır.
- Tüm işlerin ikinci iş makinesine girmeden önce birinci iş makinesinde işlenmesi gerekir.
- Tüm işlerin önceliği eşit olmalıdır.
Johnson kuralı şu şekildedir:
- Her iş merkezindeki işleri ve zamanları listeleyin.
- En kısa süreye sahip iş parçasını seçin. Bu iş parçası ilk makine içinse, bu işi en önceye planlayın; ikinci makine içinse, bu işi en sona planlayın.
- En kısa iş parçasına sahip işi düşünme sırasından çıkarın.
- Tüm işleri planlayana kadar iş sırasının merkezine doğru çalışarak 2. ve 3. adımları tekrarlayın.
Örnek değiştir
Beş işin her birinin M1 ve M2 makinelerinde sırasıyla işlenmesi gerekiyor. Johnson kuralını kullanarak optimum iş sırasını bulun.
| İş | Birinci çalışma merkezi (M1) | İkinci çalışma merkezi (M2) |
|---|---|---|
| A | 3 | 1 |
| B | 9 | 10 |
| C | 8 | 7 |
| D | 4 | 5 |
| E | 2 | 6 |
1. En küçük süreye sahip iş parçası A'da (1 saat) bulunmaktadır. Bu iş parçası M2'de olduğundan, bu işi en sona planlayın.
| ? | ? | ? | ? | A |
A işini değerlendirmeden çıkarın.
2. Bir sonraki en küçük süreye sahip iş parçası E'de (2 saat) bulunmaktadır. Bu iş parçası M1'de olduğundan, bu işi en önceye planlayın.
| E | ? | ? | ? | A |
E işini değerlendirmeden çıkarın.
3. Bir sonraki en küçük süreye sahip iş parçası D'de (4 saat) bulunmaktadır. Bu iş parçası M1'de olduğundan, bu işi en önceye planlayın.
| E | D | ? | ? | A |
D işini değerlendirmeden çıkarın.
4. Bir sonraki en küçük süreye sahip iş parçası C'de (7 saat) bulunmaktadır. Bu iş parçası M2'de olduğundan, bu işi en sona planlayın.
| E | D | ? | C | A |
C işini değerlendirmeden çıkarın.
5. Yalnızca B işi kaldığı için, bu işi, iş sırasının merkezine ekleyin.
| E | D | B | C | A |
Sonuç olarak, işlerin E → D → B → C → A sırasıyla işlenmesi ve her iki makinede de aynı sırada işlenmesi gerekir.
Kaynakça değiştir
- ^ "Johnson's Rule in Sequencing Problems". 30 Ocak 2024 tarihinde kaynağından arşivlendi. Erişim tarihi: 30 Ocak 2024.
- ^ "Johnson Algoritması" (PDF). 14 Şubat 2019 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 30 Ocak 2024.