Information Technology Reference
In-Depth Information
string from stage 1 through stage
s
and is processed by exactly one machine at
every stage. A machine can process at most one job at a time and a job can be
processed by at most one machine at a time. The processing time
p
i,j
is given
for each job at each stage. The scheduling problem is to choose a machine at
each stage for each job and determine the sequence of jobs on each machine so
as to minimize the makespan.
2.2 Mathematical Model
As we know, on the research of the HFS problem, there are two formats to repre-
sent a solution, namely the matrix representation and the vector representation.
In this paper, we employ the vector representation [16], which considers the se-
quence of jobs only at the stage one. This subset sequence should contain the
collection of all potentially good solutions for the problem and is a one-to-one
correspondence. Most importantly, it is very convenient to design and operate
by using this format. A subset sequence is decoded to a complete schedule by
employing a generalization of the List Scheduling (LS) algorithm to incorporate
the jobs at other stages [17], [18]. For scheduling jobs at each stage, the LS al-
gorithm is based on the first-come-first-service rule, in which the jobs with the
shortest completion time from the previous stage should be scheduled as early
as possible. It could result in a non-permutation schedule, that is, the sequence
of jobs at each stage may be different. The model of the HFS problem can be
formulated as follows in terms of this representation:
Minimize:
C
max
(
π
1
)= max
i
=1
,
2
,...n
{
C
π
s
(
i
)
,s
}
Subject to:
C
π
1
(
i
)
,
1
=
p
π
1
(
i
)
,
1
IM
i,
1
=
C
π
1
(
i
)
,
1
i
=1
,
2
,...m
1
⎧
⎨
C
π
1
(
i
)
,
1
=min
k
=1
,
2
,...m
1
{
IM
k,
1
}
+
p
π
1
(
i
)
,
1
NM
1
=arg min
k
=1
,
2
,...m
1
{
IM
k,
1
}
i
=
m
1
+1
,m
1
+2
,...n
⎩
IM
NM
1
,
1
=
C
π
1
(
i
)
,
1
π
j
(
i
)=
g
(
C
π
j−
1
(
i
)
,j−
1
)
i
=1
,
2
,...n
;
j
=2
,
3
,...s
C
π
j
(
i
)
,j
=
C
π
j
(
i
)
,j−
1
+
p
π
j
(
i
)
,j
IM
i,j
=
C
π
j
(
i
)
,j
i
=1
,
2
,...m
1
;
j
=2
,
3
,...s
⎧
⎨
C
π
j
(
i
)
,j
=max
{
C
π
j
(
i
)
,j−
1
,
min
k
=1
,
2
,...m
j
{
IM
k,j
}}
+
p
π
j
(
i
)
,j
NM
j
=arg min
k
=1
,
2
,...m
j
{
IM
k,j
}
⎩
IM
NM
j
,j
=
C
π
j
(
i
)
,j
i
=
m
j
+1
,m
j
+2
,...n
;
j
=2
,
3
,...s
where
π
j
is the job permutation at the stage
j
;
π
k
(
i
)isthe
i
th job in the
π
k
;
C
π
k
(
i
)
,j
is the completion time of job
π
k
(
i
) at the stage
j
;
IM
i,j
represents
the idle moment of machine
i
at the stage
j
;
NM
j
denotes the serial num-
ber of earliest available machine at the moment at the stage
j
; the function
Search WWH ::
Custom Search