Examkin

Soru

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

Bir büyükşehir belediyesinin itfaiye araçları bakım kademesinde, beş farklı itfaiye aracının (A1,A2,A3,A4,A5A_1, A_2, A_3, A_4, A_5) periyodik bakımı yapılacaktır. Her bir aracın bakım süreci sırasıyla "1. Aşama: Mekanik Bakım" ve ardından "2. Aşama: Pompa ve Hidrolik Testi" olmak üzere iki temel istasyondan geçmek zorundadır.

Araçların her bir istasyondaki tahmini işlem süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

Araç1. Aşama: Mekanik Bakım2. Aşama: Pompa ve Hidrolik Testi
A1A_154
A2A_232
A3A_3106
A4A_428
A5A_575

Buna göre, araçların bakım süreçlerinin toplam tamamlanma süresini en aza indirmek amacıyla Johnson Algoritması uygulandığında, 2. Aşama (Pompa ve Hidrolik Testi) istasyonunun toplam boş bekleme süresi (atıl zaman) kaç saat olur?

  1. A
    2
  2. B
    3
  3. 5Cevap
  4. D
    8
  5. E
    14

Cevap

Optimum çizelgeleme sonucunda 2. Aşama istasyonunun toplam atıl zamanı 5 saat olarak hesaplanır.
Johnson algoritması kurallarına uygun olarak optimum sıralama (A4−A3−A5−A1−A2A_4 - A_3 - A_5 - A_1 - A_2) bulunduktan sonra istasyonlardaki akış çizelgelendiğinde; başlangıçta 2 saat, A4A_4 ile A3A_3 arasında 2 saat ve A3A_3 ile A5A_5 arasında 1 saat olmak üzere 2. istasyonun toplam 5 saat atıl (boş) kaldığı tespit edilmektedir.

Adım Adım Çözüm

1
Tüm araçlar ve aşamalar için en kısa işlem süresini bulunuz.
En kısa süre A4A_4 aracının 1. Aşama süresi olan 2 saattir.
Johnson algoritmasının ilk adımı, tüm işlem süreleri matrisindeki minimum değeri tespit etmektir.
2
A4A_4 aracını sıralamaya yerleştiriniz ve tablodan çıkarınız.
A4A_4 aracı 1. aşamada minimum süreye sahip olduğu için dizilimin en başına (1. sıraya) alınır. Mevcut sıralama: [A4A_4, _, _, _, _]
Kural gereği, en kısa süre birinci makinede/aşamada ise o iş ilk sıraya atanır.
3
Kalan araçlar (A1,A2,A3,A5A_1, A_2, A_3, A_5) için süreci tekrarlayınız.
Kalanlar içindeki en küçük süre A2A_2 aracının 2. Aşamasındaki 2 saattir. 2. aşamada olduğu için en sona (5. sıraya) konur. Sıralama: [A4A_4, _, _, _, A2A_2]
En kısa süre ikinci makinede ise iş en sona atanır.
4
Kalan A1,A3,A5A_1, A_3, A_5 araçlarını aynı mantıkla sıralayınız.
Min süre A1A_1 (2. Aşama, 4 saat) -> 4. sıraya konur. Sonraki min süre A5A_5 (2. Aşama, 5 saat) -> 3. sıraya konur. Kalan A3A_3 mecbur 2. sıraya yerleşir. Kesin optimum sıralama: A4−A3−A5−A1−A2A_4 - A_3 - A_5 - A_1 - A_2
Tüm işler bitene kadar algoritma ardışık olarak uygulanır.
5
Optimum sıralamaya göre her iki istasyon için işlerin başlama ve bitiş zamanlarını çizelgeleyiniz.
A4A_4: 1. Aşama (0-2), 2. Aşama (2-10). (2. Aşama başlangıçta 2 saat bekler).
A3A_3: 1. Aşama (2-12), 2. Aşama (12-18). (2. Aşama 10'da bitmişti, 12'ye kadar 2 saat bekler).
A5A_5: 1. Aşama (12-19), 2. Aşama (19-24). (2. Aşama 18'de bitmişti, 19'a kadar 1 saat bekler).
A1A_1: 1. Aşama (19-24), 2. Aşama (24-28). (Bekleme yok).
A2A_2: 1. Aşama (24-27), 2. Aşama (28-30). (Bekleme yok).
Atıl zamanları doğru tespit etmek için iş akışının zaman doğrusu üzerinde kesintisiz simülasyonu yapılmalıdır.
6
2. Aşama istasyonundaki boş bekleme sürelerini toplayınız.
Başlangıçtaki bekleme (2 saat) + A3A_3 öncesi bekleme (2 saat) + A5A_5 öncesi bekleme (1 saat) = 5 saat.
Toplam atıl zaman, istasyonun işleyişe başladığı andan tüm işler bitene kadar boş kaldığı sürelerin bütünüdür.

Anahtar Kavram

Johnson Algoritması ve Makine Atıl Zaman Hesabı

Alternatif Yöntem

Toplam tamamlanma süresi (Makespan) mantığı kullanılarak da sağlama yapılabilir. Çizelgeden işlerin tümünün bitiş zamanı (toplam tamamlanma süresi) 30 saat olarak bulunur. 2. Aşama istasyonundaki toplam aktif çalışma süresi (Tablodaki 2. Aşama sürelerinin toplamı = 4+2+6+8+5 = 25 saat) bu değerden çıkarıldığında (30 - 25 = 5) istasyonun toplam atıl zamanı pratik şekilde de doğrulanabilir.
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru