28
TM2
i
Misalkan
n
job
(1,
2,
3
…
n)
dan
masing-masing job
diproses
pada
tiga
mesin, yaitu M1, M2, dan M3 pada urutan
yang sama. Lower bound dari
make-span untuk semua job dihitung sebagai berikut.
n
1.
L1
, M1
t , M1
i , M1
t
n
,
M2
t
n
,M
3
t
1
n
2.
L2
t1 , M1
, M2
t , M2
i , M2
t
n
,M
3
t
1
n
3.
L3
t1 , M1
t1 , M2
, M3
t , M3
i , M3
t
1
Untuk
menentukan lower bound tiap-tiap cabang, misalkan
untuk tiap-
tiap
cabang
terdapat
urutan
Jr,
yaitu
berisi
sub
set
tertentu
r
job
dari
n
job
yang ada.
Didefinisikan TM1
(Jr),
TM2
(Jr),
dan
TM3 (Jr)
sebagai
waktu
di
M1,
M2,
dan M3
untuk
penyelesaian job
terakhir
pada urutan Jr.
Maka lower
bound
make-span untuk
semua
jadwal
yang
dapat
dimulai
dengan
urutan
Jr
adalah :
TM1(Jr)
¹
t ¹
i ¹
min
t 2
i 2
t
i
3
LB (Jr)
max
(Jr )
jr
t
i
jr
2
min
t
TM3 (Jr )
³
t ³
i ³
jr
 |