TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.5, May 2014, pp
. 4024 ~ 40
2
9
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i5.5093
4024
Re
cei
v
ed
No
vem
ber 2, 20
13; Re
vised
De
cem
ber 2
6
,
2013; Accep
t
ed Jan
uary 1
6
, 2014
The Hybrid Flow Shop Scheduling with Special Time
Constraints
Xiaobing Ch
eng*
1
, Mingping Xia
2
, Xiuy
ing Wang
3
Yongjun Xiao
4
1,2,
3
Colle
ge of Automatio
n
, Beiji
ng U
n
io
n Un
iversit
y
, Be
iji
ng
, P.R.China, 10
010
1
4
Chin
a Electro
n
ic Informatio
n
Industr
y
D
e
vel
opm
e
n
t Rese
a
r
ch Institute, Beiji
ng, 10
00
36
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: xia
o
b
i
ngc
he
n
g
@sin
a.com
1
, zdhtmin
gpi
ng
@bu
u
.edu.c
n
2
,
zdht
xiu
y
i
n
g
@
b
uu.ed
u.cn
3
, yxi
ao1
97
9@1
26.c
o
m
4
A
b
st
r
a
ct
A constraint s
a
tisfaction
opti
m
i
z
at
io
n mod
e
l is
esta
blis
h
ed for just-i
n-
time
HF
S schedu
lin
g
prob
le
m w
i
th
li
mite
d w
a
iti
n
g
time. C
onsi
deri
ng th
e
pro
b
le
m’
s
co
mplic
ate
d
ch
aracteristi
c
of h
a
vi
ng
bi
na
r
y
varia
b
les, this
pap
er deco
m
p
o
ses it into a Mult
ipl
e
Ca
pac
itated F
l
ow
Shop Sche
dul
in
g
(MCF
S
) probl
em
and
a machi
n
e all
o
cati
on pr
obl
e
m
. Durin
g
the proc
ess of
solvin
g the M
C
F
S
probl
e
m
, a loca
l searc
h
is
embe
dde
d
into
the
proc
edur
e
of co
nstrai
nt s
a
tisfaction
o
p
ti
mi
z
a
t
i
o
n
so
as
to i
m
prove
th
e co
nverg
enc
e
of
the alg
o
rith
m. Data exp
e
ri
me
nts s
how
that both the mod
e
l
and a
l
g
o
rith
m are feasi
b
le
an
d effective.
Ke
y
w
ords
:
hy
brid flow
shop (
H
F
S
), just in time, li
mited w
a
i
t
ing time, const
r
aint satisfactio
n
opti
m
i
z
at
ion
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Ju
st-in
-
time
HFS sch
edul
ing problem
with
limited waiting
time exists widely
in
the
metallurgical, petrochemi
c
al and pha
rmace
u
tica
l p
r
ocess ind
u
stry produ
ctio
n manag
em
ent
pra
c
tice. F
o
r
example, in t
he ste
e
l-m
a
ki
ng an
d
c
ontin
uou
s castin
g
pro
c
e
s
s of th
e iro
n
an
d st
eel
enterp
r
i
s
e
s
the castin
g
machi
ne h
a
s the stri
ct re
quire
ment
s o
n
the ste
e
l
comp
ositio
n
and
temperature,
and the
r
efore
it is
not allowed that the m
o
lten steel
i
n
high temp
era
t
ure ha
s a lo
ng
waiting
time i
n
the
process, in o
r
de
r to
a
v
oid
the
de
creased te
mpe
r
ature affe
cting the
qu
ality of
the molten st
eel. In additi
on, contin
uo
us
cast
con
s
traints of
con
t
inuou
s ca
sti
ng ma
chin
e has
pun
ctual re
q
u
irem
ents to arrival of the
furnace,
na
mely the refined molten
steel must on time
arrive co
ntin
uou
s
castin
g
machi
ne when contin
uo
us ca
sting machi
ne co
mplete
a ca
sting
furna
c
e, in order to avoid casti
ng b
r
ea
k
and lo
ss of th
e heat waitin
g.
In theory, HFS sch
eduli
n
g probl
em is NP-p
roble
m
, so just-i
n-ti
me HFS sch
edulin
g
probl
em
with
limited
waiti
ng time
is al
so
NP-pro
ble
m
. Some
rel
a
ted i
s
sue
s
were di
scu
s
sed in
literature: literature [1-3]
explore
d
diff
erent
metho
d
s fo
r
solvin
g gen
eral HFS sche
duli
ng,
inclu
d
ing o
p
e
r
ation
s
resea
r
ch
metho
d
s based o
n
a
c
curate
math
ematical
mo
del an
d artifi
cial
intelligenc
e
methods
to obtain a satis
f
ac
tory
so
lutio
n
for the
pu
rpose; literatu
r
e [4]
overvie
w
ed
the co
mputati
onal
compl
e
xity of the no
waiti
ng and b
l
ocking sche
duling pro
b
le
m;
literature
[5]
explore
d
the
perfo
rma
n
ce of the
no
-wait flo
w
sh
op sched
ulin
g
alg
o
rithm; literature
[6] put
forwa
r
d the
minimum d
e
v
iation algori
t
hm for two-stage n
o
-wai
t HFS sche
duling p
r
obl
e
m
;
literature [7] establi
s
h
ed
mathemati
c
al
model to
mi
nimize
waitin
g time and e
a
rline
s
s/tardi
ness
puni
shme
nt
for the
opti
m
ization
go
a
l
for the
st
eel-m
aki
ng-continuo
us ca
sting pro
d
u
c
tion
sched
uling problem, and p
u
t forward practical
algo
rithm based on
genetic alg
o
r
ithm and lin
ear
prog
ram
m
ing
.
In this
pape
r,
usi
ng
con
s
traint satisfa
c
tion o
p
timizati
on meth
od [
8
] solve
s
ju
st
-in-time
HFS
sch
eduli
ng p
r
obl
em
with limited
waiting tim
e
. First,
we b
u
il
d a
con
s
trai
n
t
s of the
pro
b
lem
meet the opti
m
ization
mod
e
l; then the o
r
iginal
pr
o
b
le
m is de
com
p
ose
d
into mul
t
i-cap
a
city flo
w
sho
p
sche
du
ling co
nstrai
nts to meet the
optimization pro
b
le
m and ma
chine a
ssig
n
m
ent
con
s
trai
nt sa
tisfies p
r
obl
e
m
; then we
put
forward a method
ba
sed
on nei
g
hborhoo
d se
arch
con
s
trai
nts t
o
meet o
p
timization
alg
o
rithm; at
la
st we
use d
a
ta experi
m
e
n
ts to verify
the
effectivene
ss
of the model and alg
o
rithm
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
The Hyb
r
id Fl
ow Shop S
c
h
edulin
g with
Special Tim
e
Con
s
trai
nts (Xiaobing
Che
ng)
4025
2. Problem Descriptio
n
a
nd Model
Ju
st-in
-
time HFS sched
ul
ing
p
r
obl
em with
limited
waiting
time refers
to
the
N wo
rk
perfo
rming
proce
s
s alon
g the sa
me di
re
cti
on throug
h s sta
ges, a
n
d
each
stag
e h
a
s l
j
≥
1
(j=1, 2,
... , s)
with t
he
same
speed parall
el m
a
chi
ne,
wherein at l
e
ast
one
phase exists the parallel
machi
ne. It is kno
w
n
that the relea
s
ed
time of ea
ch
j
ob i i
s
rd
i
an
d the d
e
livery
time is
dd
i
, the
pro
c
e
ssi
ng time of the j-th
stage proce
ss (ope
ration
) o
ij
is p
ij
, as well as to all
o
w the maxi
mum
time w
j
in th
e
adja
c
e
n
t ph
a
s
e
waitin
g, a
nd
requi
rem
e
nts d
e
termi
n
e
sta
r
ting time
and
pro
c
e
s
si
ng
machi
n
e
r
y of the wo
rk at
variou
s
sta
ges
und
er
m
eeting
the a
s
sumption
s and con
s
trai
nts,
makin
g
the sum of job co
mpletion time
earline
s
s/tardine
ss p
enalti
es minimi
ze. If the start time of
the ope
ration
and processing m
a
chine
mappin
g
is
variable V, the option
a
l starting time
of
operation an
d
processin
g
machi
ne map
p
ing
i
s
th
e
ra
nge
of varia
b
l
e
D, th
e
con
s
traints
map
p
i
n
g
is the con
s
tra
i
nts set C, an
d the goal
of probl
em
is
expre
s
sed a
s
a
function F,
so
the sched
uli
n
g
probl
em can
be tran
sformed into the
con
s
trai
nt
satis
f
ac
tion optimiz
a
ti
on p
r
o
b
lem (Con
straint
Satis
f
ac
tion
Optimiz
a
tion Problem, CS
OP)
Θ
=(V, D,
C, F).
To e
s
tabli
s
h
con
s
trai
nt satisfactio
n
o
p
timization
mod
e
l for
co
nven
ience, we int
r
odu
ce
symbol
s a
nd
variable
s
: i i
s
the
work
nu
mber, i
∈
I
=
{1, 2, ..., n}; j
is
the procedure
number, j
∈
J
=
{1, 2, ..., s
}
; o
ij
is the j-th pro
c
e
ss of jo
b
i, also kn
own as op
eratin
g o
ij
; p
ij
is the pro
c
e
ssi
ng time
of ope
ration
o
ij
; c
ij
i
s
com
p
letion time
of
the m
anip
u
l
a
te o
ij
; rd
i
i
s
t
he
relea
s
e
p
e
riod
of th
e j
ob i;
dd
i
is the deli
v
ery time of job i; w
j
is ma
ximum wait time of work b
e
twee
n the j and j +1
pha
se;
C1
i
i
s
pe
r u
n
i
t time pe
nalt
y
of complet
ed a
hea
d of
sched
ule
of the jo
b i;
C2
i
is
the tardines
s
compl
e
tion p
e
r unit
time
puni
shme
nt of
wo
rk
i; s
ij
is start
tim
e
of
the ope
rat
i
on
o
ij
; m
ij
is
th
e
pro
c
e
ssi
ng m
a
chi
ne of the operation o
ij
.
CSOP model
of con
s
traint
satisfa
c
tion o
p
timization m
odel is:
)
0
),
(
2
max
)
(
1
max
min(
]
1
[
I
i
i
is
i
I
i
is
i
i
dd
c
c
c
dd
c
M
(1)
S.T.
J
j
I
i
p
s
c
ij
ij
ij
,
,
(2)
}
1
,...,
2
,
1
{
,
,
1
s
j
I
i
c
s
ij
ij
(3)
J
j
i
i
I
i
i
c
s
c
s
m
m
i
i
j
i
j
i
j
i
j
i
j
i
,
,
,
),
(
)
(
2
1
2
1
1
2
2
1
2
1
(4)
}
1
,...,
2
,
1
{
,
,
1
s
j
I
i
w
c
s
j
ij
ij
(5)
J
j
I
i
rd
s
i
ij
,
,
(6)
I
i
J
j
r
r
r
R
m
j
jl
j
j
j
ij
},
|
,...,
,
{
2
1
(7)
Among them,
the objectiv
e
function fo
rmula (1
) sho
w
s the
earli
n
e
ss/tardin
ess penalty
sum
of mini
mizing
work;
the fo
rmula
(2) sho
w
s on
ce yo
u
start
pro
c
e
ssi
ng th
e work, it is
not
allowed to be
interru
pted; the formula
(3
) is the
timing
con
s
traint
s o
f
the operatio
n, which mea
n
s
whe
n
the l
a
st
stag
e en
ds , we
ca
n
start
the p
r
o
c
e
ssi
ng of the
nex
t stage; th
e formul
a (4) i
s
the
disju
n
ctio
n co
nstrai
nt of the ope
ration,
whi
c
h me
ans
it is impossi
ble that the two work pe
rform
s
pro
c
e
ssi
ng in
any one ma
chine at the
sa
me time;
the formul
a (5
) sh
ows the work
can
not exce
e
d
the upp
er limi
t
in the waitin
g time of the
adja
c
ent
stag
e; the formula
(6), (7) d
enot
e the sta
r
t time
variable
s
of the ope
ration
and the varia
b
les rang
e of pro
c
e
ssi
ng m
a
chi
ne.
3. Method fo
r Solv
ing
Becau
s
e
the
pa
rallel
exist in the
HFS env
ironme
n
t,
the CSOP model
of sch
edulin
g
probl
em exi
s
ts with
ope
rati
ng o
ij
dete
r
mi
ning the
bina
ry variabl
es:
starting tim
e
variable
s
ij
a
nd
pro
c
e
ssi
ng m
a
chi
ne va
riab
le m
ij
. Aiming
at this
cha
r
a
c
teri
stic, the
HFS Sched
ul
ing p
r
oble
m
i
s
decompo
se
d
into two
sub
-
probl
em
s to
solve: (1
) i
gno
re th
e a
s
sign
ed p
r
o
c
e
s
s of
the m
a
chine
of
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 4024 – 40
29
4026
the work in e
a
ch ph
ase, and just-i
n-tim
e
HFS
sched
uling problem
with limited waiting time is
simplified
to the
corre
s
po
nding
mo
re ability
flow shop
S
c
he
duli
ng (Multiple
Cap
a
citate
d Flow
Shop S
c
hed
uling, M
C
FS) pro
b
lem, a
n
d
u
s
e
con
s
tr
aint satisfa
c
tion optimi
z
ati
on alg
o
rithm
to
obtain M
C
FS
schem
e; (2) by solving
machi
ne
assi
gnment
probl
em to d
e
termine p
r
o
c
e
ssing
machi
ne
of the o
peration,
to en
su
re
o
peratio
ns
of
assign
ed to
the
same
ma
chin
e
satisfy
the
corre
s
p
ondin
g
disju
n
ctive
con
s
trai
nts.
3.1. MCFS Problem
Learn from th
e literatu
r
e
[9
] we
get the
definit
ion
of the multi
abilit
y to Jo
b Sh
o
p
, MCFS
probl
em ca
n be con
s
id
ere
d
to be a spe
c
ial kin
d
of
flow sh
op
sch
edulin
g
p
r
obl
em.
It
is
diffe
ren
t
from the assu
mption of any machin
e at most processing a work at the same tim
e
in the gene
ral
flow
shop
scheduli
ng p
r
o
b
lem, an
d th
e ma
chin
es
in the M
C
FS
probl
em
withi
n
the
cap
a
cit
y
of
the machi
ne (resou
rce) p
r
o
c
e
ss
several works at the same time.
In ord
e
r to a
c
curately
est
ablish ju
st-in
-
ti
me MCFS
problem model with limited waiting
time, we intro
duce the discrete time t and the Boolea
n variable
ijt
B
:
ijt
B
=
0
|}
,
|
{
,
,
1
J
j
I
i
s
t
c
t
s
ij
ij
ij
CSOP model
of MCFS pro
b
lem is:
[M2] (1)
S.T. (2), (3), (5), (6
)
}
,
|
{
,
|,
|
J
j
I
i
s
t
J
j
R
B
ij
j
I
i
ijt
(8)
In the ab
ove
model, the l
e
ft item of the form
ul
a (8) m
ean
s resource load
of sta
ge j at
a
time t phase,
and the ri
gh
t term rep
r
e
s
ents the
re
so
urce capa
bility of stage j. The style is
a
machi
ne reso
urce capa
city con
s
trai
nts, whi
c
h mea
n
s that at any time in stag
e j pro
c
e
ssi
ng work
numbe
r do
es
not excee
d
its availabl
e re
sou
r
ces |R
j
|.
The p
ape
r re
fers to
rem
a
i
n
ing resou
r
ce
cap
a
city an
a
l
ysis m
e
thod
that the litera
t
ure [9]
use
s
, and t
he combin
ed
model i
s
for the
cha
r
a
c
teri
stics of
the target to
minimize th
e
earlin
ess/tard
iness p
uni
sh
ment, first th
e structu
r
e
fe
asibl
e
initial
sched
uling
o
n
the time
by the
relaxation
resource
capa
cit
y
con
s
traint;
Then
u
s
e th
e
co
nst
r
aint
co
nsi
s
ten
c
y techniqu
e to
re
p
a
ir
the resou
r
ce confli
cts, and
get compl
e
tel
y
feasible
sch
edulin
g; in order to get a b
e
tter solutio
n
in
a short
pe
rio
d
of time,
e
m
bed
neig
h
b
o
rho
od
se
ar
ch in
re
startin
g
the
se
arch
me
chani
sm
of
con
s
trai
nt sat
i
sfactio
n
opti
m
ization to
m
a
ke u
p
f
o
r it
s
lac
k
in co
nv
er
gen
ce.
3.1.1. Gener
a
te Fe
asible
Solution
(1) Initialization schedulin
g
The i
n
itializat
ion
sched
ulin
g with
out
co
nsid
er
in
g
the
re
so
urce ca
pacity con
s
traints (8
),
according to
delivery time
of the wo
rk
a
nd the ti
ming
con
s
trai
nts o
f
the operatio
n, cal
c
ulate t
he
optimal sta
r
t time of each o
peratio
n:
J
j
I
i
p
dd
s
s
j
k
ik
i
ij
,
,
(9)
We call that the time is the
relaxation (reso
ur
ce
capa
city con
s
trai
n
t
s) optimal
st
art time,
and this tim
e
sched
uling i
s
said fea
s
ibly i
n
itia
l sched
uli
ng on the tim
e
. If the sche
duling m
eets
all
of
re
sou
r
ce
cap
a
cit
y
con
s
t
r
aint
s,
it
i
s
a n
o
e
a
rlin
ess / ta
rdin
e
s
s optimal
fi
nal
sched
uli
ng;
otherwise, according to th
e re
sou
r
ce capa
city
con
s
traints
of prob
lem, based o
n
satisfying t
h
e
timing con
s
traints, adju
s
t the startin
g
time to the ope
ration.
(2) Co
nstraint
consistency
Con
s
trai
nt consi
s
ten
c
y impleme
n
tatio
n
in
clud
es constraint
c
h
e
cki
ng and
constraint
prop
agatio
n and it is the
core technolo
g
y of the
CSP solving pro
c
e
ss. Con
s
traint con
s
i
s
te
ncy
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
The Hyb
r
id Fl
ow Shop S
c
h
edulin
g with
Special Tim
e
Con
s
trai
nts (Xiaobing
Che
ng)
4027
impleme
n
tation aim
s
at
discove
r
ing
and
elimin
ates
confli
ct
s d
ue to i
m
pro
per vari
able
assignm
ent i
n
MCFS
pro
b
lem solving
pro
c
e
ss:
(1
) the timing
conflict du
e to the op
erati
on
starting tim
e
violating timin
g
co
ns
traints;
(2) re
sou
r
ce load
ex
ceed
s
the re
sou
r
ce
confli
ct that the
resou
r
ce abili
ty cause
s
. Ti
ming conflict
is examin
ed
by the con
s
traint E
quation
(3) a
nd di
re
ctly
according to
the Equatio
n
(3) trim the
startin
g
time
of the op
eration an
d be
can
c
ell
ed. T
he
resource conflict is chec
ked by the remain
ing resource ability function (10):
I
i
ij
ijt
j
J
j
I
i
s
t
J
j
B
R
t
j
RC
}
,
|
{
,
,
|
|
)
,
(
(10)
If the RC (j, t)
<0, it means that the reso
urce
load exceed
s the resour
ce capa
cit
y
at
the
stage j time t
,
it is need to
trim the sta
r
ting time of th
e ope
ration t
o
red
u
ce the
resou
r
ce loa
d
.
The ba
si
c id
ea to trim o
peratio
n\tartin
g time is th
a
t
we ad
d tim
i
ng con
s
train
t
s between t
he
operation
s
at
occupi
ed t t
i
me re
so
urce
, and
sele
ct
the ope
ratio
n
by the forward
-
loo
k
ing
a
nd
backtra
cking
and trim the start time. Base
d on t
he con
s
trai
nt co
nsi
s
ten
c
y technical re
sou
r
ce
colli
sion repai
r pro
c
e
s
s is a
s
follows:
Step 1: Add operatio
n of t(t=S
ij
) time to the co
nflict op
eration
set
jt
cos
:
|}
,
|
{
cos
ij
pj
pj
pj
jt
s
t
c
t
s
o
,
supp
ose :
;
cos
:
cos
0
jt
jt
Step 2: If
,
cos
jt
, turn to
step
5; ot
herwise, a
c
co
rdin
g to
th
e fo
llo
w
i
ng
for
m
u
l
a
s
e
lec
t
the earli
est starti
ng time in
confli
ct operation
set
jt
cos
:
{|
m
i
n
{
}
,
c
o
s
}
pj
p
j
pj
p
j
p
j
j
t
oo
s
s
o
, if it exi
s
ts several
pj
o
, select
any one,
cos
:
co
s
j
tj
t
p
j
o
;
Step 3: Trimming the ea
rli
e
st sta
r
ting time of operation
pj
o
,
pj
i
j
pj
ss
p
;
Step 4: Con
s
t
r
aint p
r
opa
ga
tion, to all 1<k<j, if
1
pk
k
sc
(or
pk
sr
d
(k
=
1
) ), trimmi
ng
the earlie
st starting time
11
pk
pk
p
k
j
ss
p
w
of operation
pk
o
, turn to step 8;
otherwi
se,
back to step
3 and turn to
step 2;
Step 5: acco
rding to the formul
a we se
lect the mini
mum ope
rati
on that the completion
time an
d time t has in confli
ct operation set
jt
cos
:
}
,
cos
},
min{
|
{
0
'
'
ij
jt
pj
pj
j
p
pj
j
p
s
t
o
t
c
s
o
o
, if there
exist several
j
p
o
'
, we can
sel
e
ct
any
one;
Step 6: trimming the startin
g
time
j
p
ij
c
s
'
of operation
ij
o
;
Step 7: co
nstrai
nt pro
pagatio
n, tri
mming the
startin
g
ti
me to all
s
k
j
1
1
ik
ik
ik
p
s
s
;
Step 8: outpu
t current sche
duling a
nd en
d the pro
c
e
s
s.
3.1.2. Neigh
borhood Sea
r
ch
Re
starting
se
arch m
e
chan
ism
wa
s u
s
e
d
to optimi
z
e
the obj
ectiv
e
fun
c
tion to
MCFS
sched
uling p
r
oble
m
u
s
ing
optimizatio
n
con
s
trai
nt
satisfactio
n
, a
nd the results sho
w
that
the
optimizatio
n
pro
c
e
ss i
s
fa
st, easy to im
plement, but
the co
nverg
e
n
ce i
s
le
ss th
an ideal. So,
we
embed
Lo
cal Search (LS) repla
c
ing
th
e neigh
borho
o
d
sea
r
ch b
a
se
on fo
rwa
r
d i
n
the
con
s
trai
nt
satisfa
c
tion o
p
timization p
r
oce
s
s, and th
e pse
udo
-cod
e is:
Procedu
re LS
(sch,
sch
=s
ch)
{
gene
rate a n
e
ighb
or of
is
o
:
)
(
is
o
N
;
while
)
(
is
o
N
do {
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 4024 – 40
29
4028
sele
ct
ks
o
)
(
is
o
N
,
)
(
is
o
N
:=
)
(
is
o
N
-
ks
o
;
excha
nging p
o
sition
s
of
is
o
and
ks
o
;
gene
rate a n
e
ighb
or
k
sch
through con
s
train
t
propag
ation;
If a feasible solution
k
sch
exis
ts
& F(
k
sch
)<F
(
sch
) then{
sch
:=
k
sch
;
}
}
Return: =
sch
;
}
3.2. Machine
Assignmen
t Problem
Machi
ne a
ssi
gnment
sho
w
s that the op
erati
on in the
MCFS pro
b
l
e
m sched
ulin
g re
sults
is a
s
signe
d t
o
the
parallel
machine
in t
he
corre
s
po
n
d
ing
HFS. T
he p
r
obl
em i
s
the
con
s
tra
i
nt
satisfa
c
tion
probl
em, co
nsi
s
ted by the ope
ratio
n
of pro
c
e
ssi
ng ma
chin
e
variable m
ij
and
con
s
trai
nt (4)
and (7
).
In solving p
r
oce
s
s of the
machi
ne a
s
signm
ent
pro
b
lem, the ch
oice of vari
a
b
les a
n
d
values u
s
e th
e first com
e
first service rul
e
s (F
CFS
)
an
d the first idle
machin
e pri
o
rity rule (FAM
)
[10], and it can quickly get a solutio
n
of a con
s
trai
nt satisfactio
n
problem.
4. Simulation Experimen
t
Usi
ng
DELP
HI a
s
the
p
r
o
g
rammi
ng l
a
n
guag
e to
re
al
ize th
e al
go
rithm in
the
pa
per, th
e
experim
ental
environ
ment i
s
de
skto
p
of Pentium4/CP
U
3.00G
Hz
/RAM 1GB. The experim
ent
al
data set the
work
numb
e
r
n={
10,20,5
0
},
the num
be
r
of stage
s
s={
2
,3,5}, the m
a
chi
ne n
u
mb
er of
each stag
e |R
j
|=3, the work p
r
o
c
e
s
si
ng time p
ij
follows the u
n
iform di
strib
u
tion intege
rs of
U[10,30],
the relea
s
e
d
perio
d
rd
i
=0,
the delivery time dd
i
=
s
j
j
n
i
s
j
ij
s
j
ij
i
R
p
U
p
dd
1
11
1
/
1
,
0
, rou
nded,
the
work wa
iting time li
mit w
j
={5,10
}
betwe
en adja
c
ent pha
se
s, and
th
e work
in
a
d
va
n
c
e,
t
a
rdin
ess pen
alties co
effici
ent
C1
i
, C2
i
ar
e
taken
5 an
d
10, 20 g
r
ou
p
s
of qu
estio
n
instan
ce
s a
r
e ran
domly
gene
rated fo
r each p
r
oble
m
st
ru
ct
ur
e.
Table 1. Data
Experimental
Results
Work×stage Waiting
time
ω
j
Termination c
y
cl
e number
CPU/s
Improvement r
a
t
e
η
/(
％
)
CSO LSBCSO
CSO
LSBCSO
10×2 5
10
80.38
106.45
53.85
56.01
3.37
2.46
0.81
0.85
2.97
4.53
10×3 5
10
139.93
171.05
80.51
88.31
6.89
5.95
1.82
2.00
4.25
6.63
10×5 5
10
248.41
208.32
98.53
105.67
14.33
12.02
3.71
3.98
5.37
7.23
20×2 5
10
402.23
416.91
228.70
213.50
18.57
25.29
6.90
6.44
6.14
8.08
20×3 5
10
778.85
733.71
339.15
335.08
53.93
64.41
15.34
16.47
7.76
9.70
20×5 5
10
833.75
688.97
377.80
354.02
111.33
79.51
28.48
31.14
11.48
15.56
50×2 5
10
958.15
882.68
265.51
247.76
110.57
101.86
20.02
18.68
13.66
22.05
50×3 5
10
1217.24
1264.28
421.95
385.66
244.72
218.85
47.72
43.62
21.04
31.14
50×5 5
10
1029.16
1169.88
538.43
500.89
378.19
337.51
101.49
94.41
25.61
32.99
The
experi
m
ental
re
sults
are
sho
w
n i
n
Tabl
e 1, th
e termi
nated
cycl
e n
u
mb
er i
s
th
e
obje
c
tive fun
c
tion valu
e i
m
provem
ent
rate n
o
t more than 0.5%
of the cy
cle
numbe
r
within
contin
uou
s
2
0
cy
cle
s
; CP
U time
is the
prog
ram
con
s
ume
d
time
whe
n
it
rea
c
h
e
s th
e te
rmin
ation
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
The Hyb
r
id Fl
ow Shop S
c
h
edulin
g with
Special Tim
e
Con
s
trai
nts (Xiaobing
Che
ng)
4029
cycle
num
ber; improvem
en
t rate
η
=(
F
LSBCSOFCS
O
)-F
CSO
)/F
CSO
, F
LSBC
S
O
and F
CSO
re
spe
c
tiv
e
ly
ref
e
r
to the optim
al sol
u
tion o
f
con
s
trai
nt satisfa
c
tion
a
l
gorithm
L
SBCSO
embedd
e
d
neig
hbo
rho
o
d
sea
r
ch con
s
traint and the
optimal soluti
on of co
ns
t
r
a
i
nt satisfa
c
tio
n
algo
rithm CSO without t
he
neigh
borhoo
d
search.
Table 1 li
sts
the re
sults of
two different
algorith
m
s
which
are
CS
O and
LSBCSO, and
we can see:
(1) Two al
go
rithms obtai
n
a
satisfa
c
tory sc
hed
uling
re
sult
within
an
accepta
b
l
e time
rang
e.
(2) F
r
om th
e
algorith
m
efficien
cy, we
ca
n
se
e that to
stru
cture of th
e sam
e
p
r
obl
em, the
comp
utationa
l efficiency o
f
LSBCSO is better
than
that of the CSO,
whi
c
h
sho
w
s that the
embed
ded
n
e
ighb
orh
ood
sea
r
ch can g
r
eatly improve
the efficie
n
c
y of co
nst
r
a
i
nt satisfa
c
tio
n
optimization algorithm. The bigge
r scal
e of the probl
em the more
obvious effici
ency will be.
(3) F
r
om the
experim
ental
effect, neighb
or
ho
od sea
r
ch for the targ
et value improvement
rate of co
nstraint satisfa
c
ti
on optimization al
go
rithm
CSO and the
probl
em scal
e and the wai
t
ing
limit time are related. Th
e reason
is that
the greate
r
problem si
ze i
s
the greate
r
fe
asibl
e
sol
u
tion
spa
c
e a
nd th
e more o
b
vio
u
s imp
r
ovem
ent effect of the sol
u
tion wi
ll be, the grea
ter waiting ti
me
con
s
trai
nts li
mit is, the more rel
a
xed problem co
n
s
traint and the g
r
eate
r
feasi
b
l
e
solutio
n
sp
ace
will be, so the more obvious improv
ement effect of solution will be.
5. Conclusio
n
Ju
st-in
-
time
HFS
sched
u
ling p
r
obl
em
with limite
d
waiting ti
me in th
e i
ndu
strial
prod
uctio
n
sy
stem exist
s
many exampl
es. HFS
sche
duling p
r
obl
e
m
with limite
d
waiting tim
e
on
minimizi
ng th
e ea
rline
s
s/tardine
s
s p
enal
ty for the o
p
timization
obj
e
c
tive were
stu
d
ied.
Con
s
tra
i
nt
satisfa
c
tion
tech
nolo
g
y was
used to
e
s
tabli
s
h th
e o
p
timization
m
odel; b
a
se
d
on the
co
mpl
e
xity
characteri
stics of the
model with two v
a
riabl
es
, we decompose
the
probl
em i
n
to several
ability
flow sh
op
scheduli
ng p
r
o
b
lem an
d the
machi
ne a
s
signment p
r
ob
lem. We fo
cu
s on the fo
rmer
and present con
s
trai
nt sat
i
sfactio
n
opti
m
izat
ion al
go
rithm ba
sed
on neig
hbo
rh
ood search.
The
experim
ental
re
sults sho
w
that, n
e
ig
hborhoo
d
se
arch in
opti
m
ization
rest
arting th
e
se
arch
mech
ani
sm o
f
the embe
dd
ed con
s
traint
satisfa
c
ti
on
can imp
r
ove t
he conve
r
gen
ce of
con
s
trai
nt
satisfa
c
tion
optimizatio
n method
s; the algorithm
p
u
t forwa
r
d in the pape
r is feasible
and
effec
t
ive.
Referen
ces
[1]
Brah SA, Loo
LL. Heur
istics for sched
uli
ng i
n
a flo
w
s
h
o
p
w
i
t
h
multip
le pr
ocessors.
Euro
pea
n Journ
a
l
of Operation
a
l
Rese
arch
. 19
9
9
; 113(1): 1
13-
122.
[2]
Moursli O, Poc
het Y. A bra
n
c
h
-an
d
-bo
u
n
d
al
gorithm for th
e
h
y
bri
d
flo
w
s
h
op.
Intern
ation
a
l Jo
urna
l o
f
Producti
on Eco
n
o
m
ics
. 20
00; 64(1/3): 11
3-1
25.
[3]
W
a
rdon
o B, Fathi Y. A tabu search al
gorit
hm fo
r multi-stage p
a
ral
l
el m
a
chi
ne pro
b
l
e
m
w
i
th l
i
mite
d
buffer capac
itie
s.
Europea
n Jo
urna
l of Operat
ion
a
l Res
earc
h
.
2004; 15
5(2): 380-
401.
[4]
Hall
n G, Sriskand
araj
ah C. A surve
y
of m
a
chi
ne sche
d
u
ling
prob
lems
w
i
t
h
block
i
n
g
and n
o
-
w
a
i
t in
process.
Oper
ations R
e
se
arch
. 1996; 4
4
(3): 510-
525.
[5]
Sriskan
dara
j
a
h
C.
T
he performance of sch
edu
lin
g al
gorit
hms for no
w
a
i
t
flo
w
sho
p
s
w
i
t
h
par
all
e
l
machi
nes.
Eur
ope
an Jo
urna
l of Operation
a
l
Rese
arch
. 19
9
3
; 70(3): 36
5-3
78.
[6]
Xi
e Jin
x
i
ng,
Xing W
e
n
x
un, Liu Z
h
i
x
i
n
, et al. Minimum
deviati
on al
g
o
rithm for t
w
o
-
stage no-
w
a
it
flo
w
sh
ops w
i
th
para
lle
l
machi
n
es.
Computers
& Mathe
m
atics
w
i
th Applicatio
ns
. 2004; 4
7
: 1857-
186
3.
[7]
Li T
i
eke, Z
hou
Jian, Su
n Li
n.
Steelmak
i
ng c
ont
in
uo
us casti
ng a
nd ro
lli
ng
and c
o
ld-m
ou
n
t
ed hot-ro
lle
d
side-
b
y
-s
id
e e
n
viro
nment-C
o
n
tinu
ous
Casti
ng Pro
ducti
on
Sched
uli
ng M
o
del
an
d Al
gorit
hm.
System
eng
ine
e
ri
ng th
eory an
d Practi
ce
. 2006; 6: 11
7-12
3.
[8]
Dorn
dorf U, P
e
sch E, Pha
n
-
H
u
y
T
.
Constraint
pr
opa
gati
o
n techn
i
qu
es f
o
r the d
i
sju
n
cti
v
e sche
dul
in
g
prob
lem.
Artificial Intelligence
. 2000; 1
22: 18
9-24
0.
[9]
Nuijte
n
W
,
Aar
t
s E. A comput
ation
a
l stu
d
y
o
f
cons
trai
nt sat
i
sfaction
for m
u
ltipl
e
c
apac
ita
t
ed j
ob s
h
o
p
sched
uli
ng.
Eu
rope
an Jo
urna
l
of Operation
a
l
Researc
h
. 199
6; 90(2): 26
9-2
84.
[10]
Valeri
e BG. Hybr
id flo
w
sh
o
p
sched
uli
ng
w
i
t
h
prece
d
e
n
c
e constrai
nts and time lag
s
to minimize
maximum lat
e
ness.
Internatio
nal Jo
urna
l of Producti
on Eco
n
o
m
ics
. 20
00; 64: 101-
11
1.
Evaluation Warning : The document was created with Spire.PDF for Python.