10. CDS HEURISTIC

10. CDS HEURISTICUntuk problem-problem besar, akan sulit untuk mendapatkan solusi optimal dalam waktu terbatas, karena penjadwalan flow shop adalah masalah yang sifatnya kombinasi. Ini berarti kompleksitas fungsi waktu dari problem flow shop adalah eksponensial yang natural. Oleh karenanya, kita harus menggunakan heuristik yang efisien untuk masalah yang berukuran besar.
CDS (Campbell, Dudek dan Smith) heuristik adalah salah satu heuristik yang dipakai untuk flow shop scheduling.
The heuristik CDS sesuai dengan multistage menggunakan aturan Johnson yang diterapkan pada masalah baru yang terbentuk dari processing time yang asli.

Pada  stage 1

Dengan kata lain, aturan Johnson diterapkan pada operasi pertama dan mth dan operasi intermediate diabaikan.

Pada  stage 2

Artinya, aturan Johnson diterapkan dengan jumlah processing time dari dua operasi pertama dan dua operasi terakhir. Secara umum pada stage i,

Untuk setiap tahap i (i = 1, 2, ... m - 1), job order yang diperoleh digunakan untuk menghitung makespan untuk problem asli. Setelah stage m - 1, yang jadwal makespan terbaik di antara m - 1 terdentifikasi.
(Beberapa dari urutan m - 1 bisa jadi identik).

ILUSTRASI 6: Cari makespan menggunakan CDS heuristic untuk problem flow shop berikut :

SOLUTION

Urutan optimal untuk problem di atas adalah seperti di bawah ini:

3-2-1-4
Perhitungan makespan untuk jadwal di atas adalah sebagai berikut:

Makespan problem ini = 31.
Stage 2

Setelah menerapkan algoritma Johnson untuk problem di atas, kita mendapatkan urutan, 3-1-2-4. Perhitungan makespan diringkas dalam tabel berikut:

Urutan terbaik adalah 3-1-2-4, yang memiliki makespan dari 30.

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.