9.1. Johnson’s Algorithm
Langkah 1:Cariminimum diantarati1 dan ti2.
Langkah 2a : Jika processing time minimum butuh mesin 1, tempatkan job terkait di posisi pertama yang tersedia secara berurutan. Lanjutkan ke Langkah 3.
Langkah 2b : Jika processing time minimum butuh mesin 2, tempatkan job terkait di posisi terakhir yang tersedia secara berurutan. Lanjutkan ke Langkah 3.
Langkah 2b : Jika processing time minimum butuh mesin 2, tempatkan job terkait di posisi terakhir yang tersedia secara berurutan. Lanjutkan ke Langkah 3.
Langkah 3 :Hilangkanjob yang dialokasikandari perhitungandan kembalike Langkah1sampai semuaposisidalam urutan bisa terisi.(Tiesmungkin rusaksecara acak.)
Algoritma di atas digambarkan dengan menggunakan problem berikut:
ILUSTRASI 5: Perhitungkan dua mesin berikut ini dan enam job flow shop-scheduling problem. Gunakan algoritma Johnson, dapatkan urutan yang optimal, yang bisa meminimalkan makespan.
SOLUSI : Cara kerja algoritma dirangkum dalam bentuk tabel, yang ditunjukkan di bawah ini:
The optimal sequence is 2-5-3-6-1-4. The makespan is determined as shown below. In the following table:
Urutan optimal adalah 2-5-3-6-1-4. Makespan ditentukan seperti ditunjukkan dalam tabel di bawah ini. :
[Time-in on M/c 2 = max [M!c 1 Time-out of the current job, M/c 2 Time-out of the previous job]
[Time-in on M/c 2 = max [M!c 1 Time-out of the current job, M/c 2 Time-out of the previous job]
Tidak ada komentar:
Posting Komentar