Information Technology Reference
In-Depth Information
performance of the proposed IDABC algorithm in solving the HFS problem un-
der the criterion of makespan minimization, the IDABC algorithm was compared
with a B&B method [4], an AIS [9], an ACO [10], a GA [8], a QIA [11], and a
PSO algorithm [12]. The maximum run time of the algorithm was set at 1600s or
until the lower bound (LB) [3], [4] was reached. If the LB was not found within
this time limit, the search was stopped and the best solution was accepted as
the final solution.
In order to establish more accurate and objective comparisons, the compu-
tational results of these compared algorithms are obtained from their original
papers. For each test problem, the proposed IDABC algorithm was run inde-
pendently twenty times and the performance of all the compared algorithms was
summarized in Table 1. In Table 1, Solved means the number of problems which
the algorithm can solve, and Deviation denotes the average relative percentage
error to LB.
Tabl e 1.
Comparison results on Carlier and Neron's benchmark problems
Easy problems Hard problems
Solved Deviation Solved Deviation
Algorithm
B&B
53
2
.
17%
24
6
.
88%
AIS
53
0
.
99%
24
3
.
13%
ACO
45
0
.
92%
18
3
.
88%
GA
53
0
.
95%
24
3
.
05%
5
.
04%
QIA
29
0
12
PSO
53
0
.
95%
24
2
.
85%
IDABC
55
0
.
94%
43
2
.
82%
As it can be noticed from Table 1, the machine layouts have an important
effect on the complexity of problems that affects solution quality. In the 55 easy
problems and 43 hard problems, B&B, AIS, GA, and PSO can solve 53 easy
problems and 24 hard problems, ACO can solve only 45 easy problems and 18
hard problems, QIA can solve only 29 easy problems and 12 hard problems,
while the proposed IDABC algorithm can solve all the 98 problems. The average
percentage deviation values of the easy and hard problems generated by IDABC
are equal to 0.94% and 2.82%. For the 55 easy problems, QIA has a zero deviation
value but it can solve only 29 of the 55 easy problems. The performance of PSO
is comparable with the proposed IDABC, but it still cannot solve problems as
many as the proposed IDABC. Thus, it is concluded that the IDABC algorithm
is more effective and e
cient in comparison with other algorithms for Carlier
and Neron's benchmark problems.
Comparison of Liao's Benchmarks.
For Liao's benchmark problems, two
meta-heuristics: AIS and PSO, have been applied to the problems in [12]. The
computational results are shown in Table 2, where the experimental data of AIS
and PSO were obtained from their original papers, and the IDABC algorithm
was run twenty independent replications for each problem. The execution time
Search WWH ::
Custom Search