Examkin

Soru

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

Bir kamu kurumunun matbaa tesisinde, kurum içi eğitimlerde kullanılacak 4 farklı kılavuz kitabın (K1,K2,K3,K4K_1, K_2, K_3, K_4) basım ve ciltleme işlemleri yapılacaktır. İşlemler önce 'Baskı' (1. Makine), ardından 'Ciltleme' (2. Makine) merkezinde gerçekleştirilmektedir.

Her bir kılavuz için baskı ve ciltleme süreleri (saat cinsinden) aşağıdaki tabloda verilmiştir:

KılavuzBaskı Süresi (Saat)Ciltleme Süresi (Saat)
K1K_163
K2K_225
K3K_384
K4K_457

Johnson Algoritması dikkate alındığında, bu dört işin toplam tamamlanma süresini (makespan) en aza indirecek optimal iş sıralaması aşağıdakilerden hangisidir?

  1. K2−K4−K3−K1K_2 - K_4 - K_3 - K_1Cevap
  2. B
    K1−K3−K4−K2K_1 - K_3 - K_4 - K_2
  3. C
    K2−K4−K1−K3K_2 - K_4 - K_1 - K_3
  4. D
    K2−K1−K4−K3K_2 - K_1 - K_4 - K_3
  5. E
    K3−K1−K4−K2K_3 - K_1 - K_4 - K_2

Cevap

Johnson algoritmasının kuralları adım adım uygulandığında optimal sıralama K2−K4−K3−K1K_2 - K_4 - K_3 - K_1 olarak bulunur.
Johnson algoritması adım adım uygulandığında en kısa süreli işlem K2K_2'nin birinci makine süresidir (2). Bu yüzden K2K_2 en başa yerleşir. Kalan işler (K1,K3,K4K_1, K_3, K_4) içinde en kısa süre K1K_1'in ikinci makine süresidir (3), bu nedenle K1K_1 en sona yerleşir. Geriye kalan K3K_3 ve K4K_4 arasında en kısa süre K3K_3'ün ikinci makine süresidir (4), bu yüzden K3K_3 geriye kalan boşluklardan sondan bir öncekine konur. Son kalan K4K_4 ise aradaki boşluğa yerleştirilir. Sonuç itibarıyla sıralama K2−K4−K3−K1K_2 - K_4 - K_3 - K_1 şeklinde hatasız olarak oluşur.

Adım Adım Çözüm

1
Tüm süreler içindeki en küçük değeri bulun.
En küçük değer 2 saattir ve K2K_2 işinin 1. makine (Baskı) işlemine aittir.
Johnson algoritmasına göre en kısa işlem süresi 1. makinede ise o iş sıralamanın en başına yerleştirilir.
2
K2K_2 işini dizilime yerleştirin ve tablodan çıkarın.
Sıralama durumu: [ K2K_2, _ , _ , _ ]
K2K_2 işi ilk sıraya atandı, geriye kalan işler (K1,K3,K4K_1, K_3, K_4) için işlem tekrarlanır.
3
Kalan süreler içindeki en küçük değeri bulun.
Kalanlar arasındaki en küçük değer 3 saattir ve K1K_1 işinin 2. makine (Ciltleme) işlemine aittir.
En kısa süre 2. makinede olduğu için bu iş sıralamada mümkün olan en son sıraya konulur.
4
K1K_1 işini dizilime yerleştirin ve tablodan çıkarın.
Sıralama durumu: [ K2K_2, _ , _ , K1K_1 ]
K1K_1 işi sona atandı, geriye K3K_3 ve K4K_4 işleri kaldı.
5
Kalan (K3,K4K_3, K_4) süreler içindeki en küçük değeri bulun.
En küçük değer 4 saattir ve K3K_3 işinin 2. makine işlemine aittir.
İşlem 2. makinede olduğu için K3K_3 işi mevcut boşluklardan en sondakine yerleştirilir.
6
K3K_3 işini dizilime yerleştirin ve kalan K4K_4 işini son boşluğa koyun.
Sıralama durumu: [ K2K_2, _ , K3K_3, K1K_1 ] -> Son olarak K4K_4 eklendiğinde [ K2K_2, K4K_4, K3K_3, K1K_1 ]
Tüm işler kurallara uygun şekilde dizilmiş ve algoritma tamamlanmıştır.

Anahtar Kavram

Johnson algoritması, iki iş merkezli ardışık üretim sistemlerinde tüm işlerin tamamlanma süresini (makespan) minimize eden iş sıralama kuralıdır.
Bu soruyu puanla

Konular

İş Sıralama Kuralları ve Johnson Algoritması

Bu konudan daha fazla soru