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.