52
Karakteristik dasar penjadwalan flow shop adalah sebagai berikut:
a. Terdapat n job yang tersedia dan siap diproses pada waktu t = 0
b. Waktu set up independent terhadap urutan pengerjaan.
c. Terdapat m mesin berbeda, yang tersedia secara kontinu.
d. Operasi-operasi individual tidak dapat dipecah-pecah.
Teorema-teorema yang dapat digunakan untuk penjadwalan flow shop dengan
m mesin adalah:
a. Penjadwalan heuristic Campbell, Dudek and Smith (CDS).
Dalam prakteknya,
masalah
penjadwalan
sering
kali
melibatkan
sejumlah
besar
pekerjaan
yang
harus
diproses
oleh
banyak
mesin.
Penjadwalan heuristic
CDS
adalah sebuah metode penjadwalan pada
mesin
seri
yang
merupakan
pendekatan
dari
Johnson’s
rule.
Johnson’s
rule
atau
aturan
Johnson
merupakan
algoritma
yang digunakan untuk menjadwalkan sejumlah pekerjaan pada dua mesin seri.
Algoritma
ini bertujuan
untuk
meminimasikan
nilai makespannya. Johnson’s rule
telah
dikembangkan
oleh
Campbell,
Dudek,
and
Smith dan
digunakan
untuk
menjadwalkan
sejumlah pekerjaan (n job)
yang dikerjakan pada
mesin
(m
mesin)
yang memungkinkan untuk menghasilkan alternatif penjadwalan sebanyak jumlah
mesin -
1 penjadwalan, dan memilih yang terbaik untuk diimplementasikan.
Heuristic CDS dikembangkan sejak tahun 1970. Heuristic
ini
menghasilkan
urutan
m
–
1
dan
pilihan
dengan
makespan
terkecil
[1,
hlm 443].
Dalam
prakteknya,
masalah
penjadwalan
seringkali
melibatkan
sejumlah
besar job
yang
harus diproses oleh banyak
mesin. Untuk kasus
seperti
ini, aturan
Johnson
tidak
 |