![](https://csdnimg.cn/release/download_crawler_static/15867825/bg3.jpg)
The objective is then to find a schedule with which the makespan
or maximum completion time is minimised.
To formulate a mathematical model according to the above
description, we first list the notation, as follows:
s
k;j
Starting time of job j at stage k.
U A very large positive number.
x
k;j;i
If job j is assigned to machine i at stage k, then x
k;j;i
¼ 1;
otherwise, x
k;j;i
¼ 0.
y
k;j;j
0
If job j is preceding charge j
0
to be processed at stage k,
then y
k;j;j
0
¼ 1; otherwise, y
k;j
1
;j
¼ 0.
With the above symbols, the HFS problem is formulated as
follows:
M inimise C
max
¼ max
j A J
ðs
m;j
þp
m;j
Þð1Þ
s.t.
∑
l
k
i ¼ 1
x
k;j;i
¼ 1; 8jA J; kA M; ð2Þ
s
1;j
Z 0; 8jA J ð3Þ
s
k þ 1;j
s
k;j
Z p
k;j
; 8 jA J; k; kþ1A M ð4Þ
y
k;j;j
0
þy
k;j
0
;j
r 1; 8 j; j
0
A J; kA M ð5Þ
s
k;j
0
ðs
k;j
þp
k;j
ÞþU ð3y
k;j;j
0
x
k;j;i
x
k;j
0
;i
ÞZ 0; 8 j; j
0
A J; kA M; iA f1; 2; :::; l
k
g
ð6Þ
x
k;j;i
A f0; 1g; jA J; kA M; iA f1; 2; :::; l
k
gð7Þ
y
k;j;j
0
A f0; 1g; j; j
0
A J; kA M ð8Þ
The objective function (1) is to minimise the maximum
completion time or makespan. Constraints (2) ensure that a job
passes through all stages and must be processed by exactly one
machine at every stage. Constraints (3) ensure that the starting
time of a job on the first stage is larger than or equal to zero.
Constraints (4) are the technological requirement, i.e., for two
consecutive operations of a job, the next operation can be started
only after the preceding operation has been finished. Constraints
(5) and (6) describe the machine capacity restriction. For two jobs
processed on the same machine, the next job can be started only
after the proceeding job has finished. Constraints (7) and (8) define
the value ranges for the decision variables.
3. The presented heuristics
Heuristics that explore the specific characteristics of problems
can find good solutions with a very limited computational effort.
In the recent scheduling literature, it has been a common trend to
construct a few initial individuals for metaheuristics by using
effective heuristics. For this purpose, we present a total of 24
simple rules and NEH-based heuristics. In the HFS, with poten-
tially more than one machine per stage, we must consider assign-
ing jobs to machines and sequencing jobs on each machine. As is
commonly performed in the literature [2,24], we address sequen-
cing and assignment separately. To be specific, we use the
heuristics to generate a simple permutation of the jobs, which
indicates the order in which the jobs are launched to the shop at
the first stage, and then, we allocate a job to the first machine that
becomes available, i.e., the machine that first finishes the job
(if any) that was previously assigned to it. The fi rst available
machine also results in the earliest completion time of the job.
This arrangement is consistent with the objective of minimising
the makespan. For the subsequent stage k (k ¼ 2; 3; :::; m), we take
the completion times of jobs in a previous stage k1 as their
release times, and we allocate them to the first available machine
according to the increasing order of the release times.
3.1. The simple heuristics
We first adapt simple dispatching rules, including the longest
processing time (LPT) and shortest processing time (SPT), to the
HFS problem. LPT generates a permutation by sorting the jobs
according to their non-increasing total processing times, i.e.,
∑
k ¼ 1;2:::m
p
k;j
, whereas SPT produces a permutation according to
the non-decreasing total processing times.
Intuitively, the processing time at the first stage has a larger
effect on the complete solution than at other stages. Therefore, we
generate a permutation of the jobs according to their processing
times at the first stage, and we obtain two simple rules: the
longest processing time at the first stage (LPTF) and the shortest
processing time at the first stage (SPTF). LPTF/SPTF is the same as
LPT/SPT but sorts jobs according to their processing times at the
first stage, i.e., p
1;j
, j ¼ 1; 2; :::; n.
Bottleneck is a phenomenon by which the performance or
capacity of an entire system is severely limited by a single
component [24]. According to [17], the bottleneck stage k
b
is
defined as the stage that has the largest flow ratio between the
workload and the total available capacity, i.e., ð1=l
k
Þ∑
n
j ¼ 1
p
k;j
,
k ¼ 1; 2; :::; m. We present two more heuristics: longest processing
times till bottleneck stage (LPTB) and shortest processing times till
bottleneck stage (SPTB). LPTB/SPTB is the same as LPT/SPT, but it
sorts jobs according to their total processing time from stage one
to the bottleneck stage k
b
, i.e., ∑
k ¼ 1;2:::k
b
p
k;j
.
3.2. The NEH-based heuristics
The NEH from Nawaz et al. [16] was recognised as the highest
performing heuristic for the permutation flowshop scheduling
problem to minimise the makespan [37]. This approach has been
successfully adapted to many other scheduling problems in the
literature [38,39]. Researchers also extended NEH to the HFS
problems and obtained good results [1,2]. NEH first yields a seed
sequence β ¼ðβ
1
; β
2
; :::; β
n
Þ by using LPT [40]. Then, the first job β
1
is extracted as the first job of the current sequence π, and the
remaining jobs, β
2
; :::; β
n
, are then taken out one by one and are
inserted into the best slot of the current sequence π. The procedure
of NEH is described as follows (see Fig. 1).
There are a total of ðnðn þ1Þ=2Þ1 insertions, and each inser-
tion generates a partial sequence. NEH must evaluate all of the
generated sequences, and its computational complexity is O ðn
3
mÞ.
It can be seen from Fig. 1 that LPT is only used to generate a
seed sequence for the NEH enumeration, and the specific char-
acteristics of the problem explored by LPT are not well-utilised in
Procedure NEH
Generate a seed sequence
),...,,(
21 n
β
β
= by using the LPT rule
)(:
1
βπ
=
for
:h = 2
to n do %(the NEH enumeration procedure)
Take job
h
β
from
β
and test it in all of the
h
possible slots of
Insert job
h
β
in
at the slot that results in the lowest objective value
endfor
return
π
Fig. 1. The NEH heuristic.
Q.-K. Pan et al. / Omega 45 (2014) 42–5644