The 2nd International Conference on Computer Application and System Modeling (2012)

Evolved Discrete Harmony Search Algorithm for Multi-objective No-wait Flow

Shop Scheduling Problem
Xie Guang

Li Junqing

Hainan University Sanya College

Sanya, China,572022
[email protected]

School of Computer Science

Liaocheng University
Liaocheng ,China, 252059
[email protected]

AbstractIn this paper, an evolved discrete harmony search

(EDHS) is proposed. Firstly, a job-permutation-based
encoding scheme is applied to enable the continuous harmony
search algorithm to be used in all sequencing problems.
Additional, a new method is proposed to generate new
solutions, while an efficient approach is developed to update
the archive set of the non-dominated solutions during the
search process. Finally, computational simulation results based
on the well-known benchmarks show that the proposed EDHS
algorithm is superior to hybrid differential evolution algorithm
in terms of searching quality, diversity level and efficiency.
Keywords- Harmony search, No-wait flow shop, Multi-object
optimization

I.

INTRODUCTION

MULTI-OBJECT NO-WAIT FLOW SHOP SCHEDULING

PROBLEM

The problem considered in this research is described as

follows. Each job j J = {1,2,..., n} will be through each
machine i M = {1,2,..., m} in a sequence. Suppose that a job
permutation = { ..., } represents a schedule of
1

j 1

delay on the first machine between the start of jobs j 1 and

j
and due date respectively.The formula is given as
follows
(1)
e( , ) = p( ,1) + max 0, max p( , h) p( , h)
j 1

j 1

k 1

j 1

2k m h=2

h=1

}]

The completion time of job j on machine m can be

computed by the following formula :
C ( , m) = p ( , k )
(2)
m

k =1

C ( j , m) = e( i 1 , i ) + p ( j , k ) j = 2,3,..., n

The no-wait flow shop scheduling problem is one of the

most typical problems with strong engineering background.
In the no-wait flow shop scheduling problem, each of n jobs
consists of m operations and each one will be processed on
m machines in the sequence continuously. Thus, in order to
meet the no-wait requirement the start of a job on the first
machine must be delayed. In the past decades, efforts have
been dedicated to solving the problems with single objective.
However, the multi-objective no-wait flow shop scheduling
problem has a wider practical application. Therefore, it is
more important to develop the technologies and approaches
for this problem. With the advent of just in time, we find
Pareto optimal solutions for no-wait flow shop scheduling
problems with the minimize the maximum completion time,
the total flow time and the maximum tardiness criteria.
Harmony Search (HS) is a heuristic optimization method
for complex continuous nonlinear functions which is musicinspired.The harmony in music is analogous to the solution
vector.The musicians improvisations are looked as local and
global search schemes . Due to its simplicity, easy
implementation and quick convergence, the HS algorithm
has gained much attention and a wide range of successful
applications.
II.

jobs to be processed. Let the processing time of job j on

p ( , k )
e( , ) d ( )
machine i be
.Let
,
be the minimum

i=2

k =1

(3)

C ( )
, maximum tardiness T ( ) and
The makespan
total flow time TF ( ) can be computed by the following
formula :
max

max

f1 ( ) = Cmax ( ) = C( n , m) = e( j1 , j ) + p( n , k )
n

j =2

k =1

f 2 ( ) = Tmax( ) = max
(max(0, C( j , m) d( j )))
j =1

(4)
(5)

f 3 ( ) = TF ( ) = C ( j , m)
j =1

= (n + 1 j )e( j 1 , j ) + p ( j , k )
j =2

III.

j =1 k =1

(6)

THE EVOLVED DISCRETE HS(EDHS)

A EDHS algorithm which is evolved in the discrete space

is proposed . Let HMS , HMCR , PAR represent harmony
memory size ,harmony memory considering rate, pitch
X i = [x i , x i ,.., x i ]

n
1
2
, denote the ith
adjusting rate respectively.
harmony solution. The detail of the EDHS algorithm is
explained as follows.

A. update solution
The initial solutions are generated based on jobpermutation. According to the method, the solutions can be
updated as follows:
g (x r , x b ) Rnd < HMCR
x ' = HMCR g ( x r , x b ) =
r
otherwise
x

(7)

x b is one of the pareto solutions. g () represents twor

point crossover with the probability of HMCR. The x
denotes the temporary solution which is generated by

Published by Atlantis Press, Paris, France.

the authors
0791

The 2nd International Conference on Computer Application and System Modeling (2012)

learning harmony solutions. The h() represents insert

operation.
The disturbance operation as follows:
h ( x ' )
x ' = PAR h ( x ' ) = '
x

Rnd < PAR

otherwise

(8)

(1) Two-point crossover

b

In the two-point crossover, a block of jobs from x is

determined by two-cut points randomly. This block is either
moved to the right or left corner of the solution. Then the
offspring permutation is filled out with the remaining jobs
r
from x . This procedure will always produce two distinctive
offspring from the same two parents. In this paper, the better
offspring is chosen.
(2) The procedure of generate x r
r
The x is a temporary solution which is generated by
learning all the harmony individuals. One of the solutions in
b
the non-dominated solutions is selected to be x .The detail
of the procedure is shown in the fig 1:

IV.

COMPUTATIONAL RESULTS

A. Comparison Setup
In order to test the algorithm proposed in this paper, 31
well-known flow shop benchmark instances [1-3] are
modified for the problems. The related data is given as
follows: HMCR = 0.95 , PAR = 0.1 , HMS = n . Maximum
iterating times t = 10 * m * n .The EDHS algorithm is coded
in C++ .All experiments are conducted on a Intel(R)
Core(TM) i3 CPU, 2GHZ PC with 2GB memory. For each
instance, we carried out 20 independent replications and
calculate average distance (

Dl R

), Number of non-dominated

N NDS ( S j )

), Ratio of non-dominated solutions

solutions (
RNDS ( S j )
d ( )
S
(
),due date(
)[4]. Let j ( j = 1,2 ) to be the
non-dominated solution set, which obtained by algorithm j ,

s * denote the reference solution set, which obtained by the

S * = s j

. Dl can be used to evaluate the spread

*
S
N (S )
and distribution of
to s .
is the total number of
Sj
that are not dominated by any other
those solutions in

formula

NDS

*
R (S )
can be used to evaluate the quality
solution in S .
Sj
.
of the solutions in
NDS

Figure 1. generate

xr

B. The Procedure of EDHS

The HS algorithm generates one solution once. In order
to improve its efficiency, the algorithm generates ten
solutions once .Based on the above design, the procedure of
the EDHS algorithm is summarized as follows.
Step
1:
Set
the
parameters
such
as
HMS , HMCR , PAR and Initialize solutions.
Step 2: Evaluate each solution. Initialize AS.
Step 3: i = 0
Step 4: Generate new solution using the method of
Section 3.1.
Step 5: if i < 10 , go back to step 4.
Step 6: Update AS and the first ten solutions with new
solution.
Step 7: Update solutions which is dominated by new
solution.
Step 8: If a stopping criterion is met, output AS ,
otherwise go back to Step 3.

B. Computational Results
We compare our EDHS algorithm with HDE [5]. The
HDE algorithm is applied to the problems under
consideration by modifying its objective evaluation and its
parameters were fixed at the same ones as given in their
papers. The average value (AVG), minimum value (MIN),
maximum value (MAX), and the standard deviation (SD) of
these metrics in 20 replications are also calculated as the
statistics for the performance measures.The results are shown
in Tab. 1,Tab.2 and Tab.3.
(1) It is clear from Table 1 that the EDHS algorithm is
the better one in terms of the overall mean average, min, max
and tandard deviation of D1R In comparison to HDE. For all
instances, EDHS algorithm yields significantly better results.
SO, we can say that the EDHS algorithm can nearly find all
the reference solutions for these instances.
(2) The EDHS algorithm has the advantage of the HDE
algorithm in that the EDHS algorithm produces much better
overall mean AVG, MIN ,MAX and SD of N NDS and
RNDS than the HDE algorithm from table2 and table3. The
two metrics generated by the EDHS algorithm is much
higher than the HDE algorithm. This means that for these
instances, almost every solution of the HDE algorithm is
dominated by some solutions of the EDHS algorithm. So it is
concluded that the EDHS algorithm can produce much more
non-dominated solutions with good performances than the
HDE

Published by Atlantis Press, Paris, France.

the authors
0792

The 2nd International Conference on Computer Application and System Modeling (2012)

V.

CONCLUTION

REFERENCES

This paper addresses to solve multi-object no-wait flow shop

scheduling problem to minimize the maximum completion
time, the total flowtime and the maximum tardiness .We
presented a discrete harmony search optimization algorithm
which worked in the discrete domain by employing a jobpermutation-based encoding scheme. a new method of
producing new solutions. In order to obtain a good
approximate Pareto-optimal set, the EDHS algorithm
dynamically updated an archive set of the non-dominated
solutions during the search process. Computational
simulations and comparisons demonstrated the superiority of
the proposed algorithms in terms of solution quality.

TABLE I.
instance
Name
nm
Car01
115
Car02
134
Car03
125
Car04
144
Car05
104
Car06
89
Car07
77
Car08
88
Hel1
10010
Hel2
2010
Rec01
205
Rec03
205
Rec05
205
Rec07
2010
Rec09
2010
Rec11
2010
Rec13
2015
Rec15
2015
Rec17
2015
Rec19
3010
Rec21
3010
Rec23
3010
Rec25
3015
Rec27
3015
Rec29
3015
Rec31
5010
Rec33
5010
Rec35
5010
Rec37
7520
Rec39
7520
Rec41
7520
Mean

TABLE II.
instance
Name
nm
Car01
115
Car02
134
Car03
125
Car04
144

AVG
25.77
20.59
17.42
40.77
15.81
6.95
6.94
9.75
224.75
37.89
34.34
39.41
51.56
50.29
55.88
50.27
103.84
90.20
56.36
98.82
67.22
67.93
78.32
39.97
454.94
151.05
104.06
88.61
219.53
177.77
96.26
83.33

AVERAGE DISTANCE
HDE
MIN
MAX
15.89
38.36
14.45
26.27
12.00
26.51
25.86
53.21
10.04
24.96
3.40
18.66
0.90
19.05
4.31
17.75
196.61
259.67
23.34
49.13
23.78
49.97
24.06
51.98
28.24
73.97
26.62
74.76
41.11
83.77
21.10
75.93
58.79
137.57
26.09
128.24
33.20
73.54
57.63
141.87
42.05
85.63
30.08
94.79
35.17
116.48
29.27
51.97
248.83
702.10
108.52
205.02
48.57
146.47
61.63
113.63
141.76
274.89
134.25
223.09
72.05
119.69
51.60
114.80

[1]
[2]
[3]
[4]

[5]

Carlier J. Ordonnancements a contraintes disjonctives. RAIRO

Recherche Operationelle[J] 1978;12:333-51.
Reeves C. A genetic algorithm for flowshop sequencing. Computers
and Operations Research[J], 1995,22:5-13.
Heller J. Some numerical experiments for an MJ flow shop and its
decision-theoretical aspects. Operations Research[J], 1960;8:178-84.
PAN Quan-ke, WANG Ling, QIAN Bin. A novel differential
evolution algorithm for bi-criteria no-wait flow shop scheduling
problems. Computers & Operations Research[J], 2009, 36(8): 2498 2511.
QIAN Bin, WANG Ling, HUANG De-xian, WANG Wan-liang,
WANG Xiong, An effective hybrid DE-based algorithm for multiobjective flowshop scheduling with limited buffers. Computers &
Operations Research[J] 36 (2009) 209 233.

Dl R OF THE EDHS AND HDE ALGORITHMS

SD
5.66
3.52
4.06
6.67
3.54
3.68
4.27
3.39
18.39
6.56
7.51
7.58
11.28
14.13
11.69
15.63
21.70
28.57
11.36
24.11
11.63
17.54
16.96
5.73
126.09
25.81
24.00
14.67
35.89
25.99
14.28
17.16

NUMBER OF NON-DOMINATED SOLUTIONS

AVG
9.97
9.33
9.21
14.89
7.90
1.33
0.92
1.54
7.65
15.25
12.20
7.33
15.59
9.37
7.77
7.30
12.21
14.36
7.61
11.43
12.59
8.99
10.62
15.46
96.43
10.79
13.36
12.26
13.00
12.51
13.10
12.98

N NDS

EDHS
MIN
MAX
5.37
22.49
5.00
22.02
5.65
20.12
4.77
38.16
5.42
20.56
0.00
7.38
0.00
9.97
0.22
9.07
0.00
38.93
10.03
28.75
5.73
29.21
0.31
20.91
9.16
33.08
3.24
22.30
0.00
28.09
1.41
16.99
0.00
31.74
9.16
20.28
0.00
26.80
0.00
39.47
4.66
30.79
1.89
20.98
0.28
29.05
9.51
27.36
0.00
166.24
0.00
36.61
0.00
27.83
0.00
25.09
0.00
28.56
0.00
38.73
3.46
27.80
2.75
30.50

OF THE EDHS AND HDE ALGORITHMS

HDE
AVG
2.05
3.20
5.45
0.90

MIN
0.00
0.00
0.00
0.00

MAX
8.00
11.00
24.00
4.00

SD
2.65
3.21
5.99
1.17

AVG
19.45
20.50
26.00
15.60

SD
4.76
3.77
3.41
7.71
3.69
1.89
2.78
2.29
10.35
4.74
5.55
5.60
6.41
5.41
6.66
4.39
9.68
3.34
7.57
11.52
7.98
5.55
7.73
5.79
59.86
8.99
6.56
8.83
7.10
10.05
6.16
7.94

MIN
5.00
9.00
6.00
7.00

Published by Atlantis Press, Paris, France.

the authors
0793

EDHS
MAX
27.00
27.00
40.00
19.00

SD
5.11
5.30
8.49
2.91

The 2nd International Conference on Computer Application and System Modeling (2012)

Car05
Car06
Car07
Car08
Hel1
Hel2
Rec01
Rec03
Rec05
Rec07
Rec09
Rec11
Rec13
Rec15
Rec17
Rec19
Rec21
Rec23
Rec25
Rec27
Rec29
Rec31
Rec33
Rec35
Rec37
Rec39
Rec41
Mean

104
89
77
88
10010
2010
205
205
205
2010
2010
2010
2015
2015
2015
3010
3010
3010
3015
3015
3015
5010
5010
5010
7520
7520
7520

6.00
10.65
13.80
16.60
0.00
0.75
0.40
0.50
0.25
0.80
0.00
0.25
0.05
0.25
0.25
0.00
0.05
0.20
0.05
0.45
0.15
0.10
0.15
0.60
0.00
0.00
0.10
2.06

TABLE III.
instance
Name
nm
Car01
115
Car02
134
Car03
125
Car04
144
Car05
104
Car06
89
Car07
77
Car08
88
Hel1
10010
Hel2
2010
Rec01
205
Rec03
205
Rec05
205
Rec07
2010
Rec09
2010
Rec11
2010
Rec13
2015
Rec15
2015
Rec17
2015
Rec19
3010
Rec21
3010
Rec23
3010
Rec25
3015
Rec27
3015
Rec29
3015
Rec31
5010
Rec33
5010
Rec35
5010
Rec37
7520
Rec39
7520
Rec41
7520
Mean

1.00
3.00
8.00
10.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.71

13.00
14.00
19.00
25.00
0.00
6.00
2.00
2.00
3.00
10.00
0.00
2.00
1.00
4.00
3.00
0.00
1.00
2.00
1.00
6.00
2.00
2.00
3.00
4.00
0.00
0.00
2.00
5.61

3.96
2.66
2.95
3.98
0.00
1.77
0.75
0.76
0.72
2.35
0.00
0.64
0.22
0.91
0.72
0.00
0.22
0.62
0.22
1.36
0.49
0.45
0.67
1.35
0.00
0.00
0.45
1.33

RATIO OF NON-DOMINATED SOLUTIONS

25.85
16.85
19.15
32.70
16.25
18.25
19.00
31.05
9.95
18.15
18.60
22.20
14.05
9.10
22.80
18.55
11.60
17.20
18.35
23.95
13.55
15.10
18.70
22.20
12.00
25.45
20.50
19.12

RNDS

9.00
9.00
9.00
16.00
9.00
11.00
7.00
16.00
8.00
9.00
5.00
10.00
9.00
6.00
13.00
8.00
8.00
13.00
7.00
8.00
7.00
8.00
14.00
10.00
7.00
13.00
15.00
9.39

MIN
0.00
0.00
0.00
0.00
0.04
0.19
0.56
0.58
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.04

MAX
1.00
0.58
0.83
0.29
0.60
0.93
1.00
0.94
0.00
0.50
0.20
0.14
0.23
0.53
0.00
0.40
0.04
0.44
0.14
0.00
0.05
0.22
0.06
0.46
0.33
0.10
0.20
0.27
0.00
0.00
0.15
0.34

SD
0.27
0.15
0.28
0.08
0.17
0.16
0.11
0.11
0.00
0.13
0.05
0.05
0.05
0.12
0.00
0.10
0.01
0.10
0.03
0.00
0.01
0.06
0.01
0.10
0.08
0.02
0.04
0.09
0.00
0.00
0.03
0.08

AVG
0.96
0.95
0.87
0.98
0.93
0.99
0.93
0.99
1.00
0.99
0.99
0.99
0.99
0.99
1.00
1.00
1.00
1.00
0.99
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.99

5.99
2.11
2.76
4.74
3.60
3.74
3.96
8.03
1.99
3.53
5.18
4.75
2.67
1.71
4.47
5.19
2.66
2.14
5.26
5.38
4.73
3.68
2.74
5.20
1.95
6.11
4.75
4.22

OF THE EDHS AND HDE ALGORITHMS

HDE
AVG
0.16
0.17
0.27
0.06
0.28
0.70
0.87
0.78
0.00
0.05
0.03
0.03
0.02
0.04
0.00
0.03
0.00
0.03
0.01
0.00
0.00
0.02
0.00
0.03
0.02
0.01
0.01
0.04
0.00
0.00
0.01
0.12

31.00
18.00
21.00
36.00
19.00
25.00
25.00
40.00
17.00
24.00
25.00
30.00
17.00
11.00
30.00
26.00
17.00
20.00
26.00
30.00
20.00
21.00
24.00
30.00
16.00
35.00
33.00
25.16

MIN
0.56
0.76
0.40
0.83
0.69
0.82
0.64
0.89
1.00
0.93
0.88
0.91
0.82
0.75
1.00
0.95
1.00
1.00
0.90
1.00
1.00
1.00
0.92
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.89

Published by Atlantis Press, Paris, France.

the authors
0794

EDHS
MAX
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00

SD
0.12
0.07
0.19
0.05
0.08
0.04
0.08
0.03
0.00
0.02
0.03
0.02
0.04
0.06
0.00
0.01
0.00
0.00
0.03
0.00
0.00
0.00
0.02
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.03