9.2. Extension of Johnson’s Rule

9.2. Extension of Johnson’s Rule

Pertimbangkan 'tiga mesin dan n job' flow shop scheduling problem seperti pada Tabel 10.1.

Orang dapat memperluas algoritma Johnson terhadap masalah pada Tabel 10.1 jika ada dari dua kondisi berikut dipenuhi.

               If  min ti1  ≤  max ti2
atau       if  min ti3  ≤  max ti2
Jika dari kondisi tersebut di atas terpenuhi maka, kita dapat memperpanjang algoritma Johnson dengan cara berikut.
Create a hypothetical problem with two machines and n jobs as shown in Table 10.2.
The objective is to obtain optimal sequence for the data given in the Table 10.2. Later, the makespan is to be determined for the optimal sequence by using the data of the original problem shown in table.
This concept of extending Johnson’s algorithm to this type of problem is demonstrated using an example problem.

Buat hipotetis masalah dengan dua mesin dan n job seperti yang pada Tabel 10.2.
Tujuannya untuk mendapatkan urutan yang optimal untuk data dalam Tabel 10.2. Kemudian, makespan ditentukan untuk urutan yang optimal dengan menggunakan data dari original problem yang ditunjukkan dalam tabel.
Konsep perluasan algoritma Johnson ini untuk type masalah seperti ini diperagakan dengan menggunakan contoh soal.

ILLUSTRATION 6 : Perhitungkan 3 mesin  and 5 job flow shop problem berikut ini :

dalam table di atas,
         Min (ti1)=6           Max (ti2)=6

Karena kondisi min (ti1) ≤ max (ti2) terpenuhi, kita dapat memperluas algoritma Johnson untuk masalah ini. Jadi masalah bisa dimodifikasi dapat diberikan sebagai berikut :

Berikut ini adalah sekuen yang optimal untuk problemdi atas :
3-2-5-1-4
Makespan sekuen diatas ditentukan sbb :

Makespan untuk problem  ini adalah 51 satuan waktu.