Examkin

Soru

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

Özel bir ahşap işleme atölyesinde, dört farklı mobilya siparişi (A1,A2,A3,A4A_1, A_2, A_3, A_4) üretim sürecinde sırasıyla "Kesim" (1. Aşama) ve "Cilalama" (2. Aşama) işlemlerinden geçmektedir. Siparişlerin her bir aşamadaki işlem süreleri (saat olarak) aşağıdaki tabloda verilmiştir:

SiparişKesim SüresiCilalama Süresi
A1A_186
A2A_235
A3A_372
A4A_449

Atölye şefi, tüm siparişlerin tamamlanma süresini en aza indirmek amacıyla Johnson Algoritması'nı kullanarak bir iş sıralaması yapacaktır.

Buna göre, siparişlerin işleme alınma sırası aşağıdakilerden hangisi olmalıdır?

  1. A2−A4−A1−A3A_2 - A_4 - A_1 - A_3Cevap
  2. B
    A3−A1−A4−A2A_3 - A_1 - A_4 - A_2
  3. C
    A2−A4−A3−A1A_2 - A_4 - A_3 - A_1
  4. D
    A2−A3−A4−A1A_2 - A_3 - A_4 - A_1
  5. E
    A3−A2−A1−A4A_3 - A_2 - A_1 - A_4

Cevap

Doğru sıralama A2−A4−A1−A3A_2 - A_4 - A_1 - A_3 şeklindedir.
Johnson Algoritması adımları uygulandığında; tablodaki en kısa süre 2 saat ile 2. makinedeki (Cilalama) A3A_3'e aittir, bu nedenle A3A_3 en sona yerleştirilir. Kalanlar içindeki en kısa süre 3 saat ile 1. makinedeki (Kesim) A2A_2'ye aittir, A2A_2 en başa konur. Kalan işlerden A4A_4'ün 1. makinedeki süresi (4 saat), A1A_1'in sürelerinden kısadır, bu yüzden A4A_4 baştan ikinci sıraya yerleştirilir. Geriye kalan A1A_1 ise üçüncü sıraya (sondan ikinci) yerleşir. Sonuç A2−A4−A1−A3A_2 - A_4 - A_1 - A_3 olur.

Adım Adım Çözüm

1
Tüm işlem süreleri arasındaki en küçük değeri bulun.
En küçük değer 2 saat ile A3A_3'ün Cilalama (2. makine) süresidir.
Johnson algoritması her zaman tablodaki en kısa süreyi bularak başlar.
2
A3A_3'ü sıralamaya yerleştirin ve tablodan çıkarın.
A3A_3 en sona yerleşir. Mevcut sıra: [_, _, _, A3A_3]
Bulunan en kısa süre 2. makinede olduğu için ilgili iş sıralamanın en sonuna konur.
3
Kalan süreler arasındaki en küçük değeri bulun.
Kalanlar arasında en küçük değer 3 saat ile A2A_2'nin Kesim (1. makine) süresidir.
Algoritma kalan işler arasında tekrar en kısa süreyi arar.
4
A2A_2'yi sıralamaya yerleştirin ve tablodan çıkarın.
A2A_2 en başa yerleşir. Mevcut sıra: [A2A_2, _, _, A3A_3]
Bulunan en kısa süre 1. makinede olduğu için ilgili iş sıralamanın en başına konur.
5
Kalan A1A_1 ve A4A_4 arasındaki en küçük değeri bulun.
En küçük değer 4 saat ile A4A_4'ün Kesim (1. makine) süresidir.
Kalan işler aynı kurala göre değerlendirilir.
6
A4A_4'ü yerleştirin ve kalan A1A_1'i son boşluğa koyun.
A4A_4 baştaki ilk boşluğa konur. Son boşluğa da A1A_1 konur. Nihai sıra: [A2A_2, A4A_4, A1A_1, A3A_3].
Tüm işler Johnson algoritmasının temel kurallarına uygun şekilde sıraya dizilmiş olur.

Anahtar Kavram

Johnson Algoritması
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru