An Empirical Performance Evaluation of a Parameter-free
Genetic Algorithm for Job-Shop Scheduling Problem
Shouichi Matsui and Seiji Yamada
Abstract— The Job-Shop Scheduling Problem (JSSP) is wellknown as one of the most difﬁcult NP-hard combinatorial
optimization problems. Several GA-based approaches have beenreported for the JSSP. Among them, there is a parameter-freegenetic algorithm (PfGA) for JSSP proposed by Matsui et al.,based on an extended version of PfGA, which uses random
keys for representing permutation of operations in jobs, anduses a hybrid scheduling for decoding a permutation into aschedule. They reported that their algorithm performs well for
typical benchmark problems, but the experiments were limited
to a small number of problem instances. This paper shows
the results of an empirical performance evaluation of the GA
for a wider range of problem instances. The results show that
the GA performs well for many problem instances, and theperformance can be improved greatly by increasing the numberof subpopulations in the parallel distributed version.

I. I NTRODUCTION
In the Job-Shop Scheduling Problem (JSSP), n jobs haveto be processed on m different machines. Each job Ji
consists of a sequence of tasks Ti,1 , · · · , Ti,m that have to
be completed during an uninterrupted time period of lengthpi,j ∈ IN on a given machine (M (Ti,j ) ∈ {1, · · · , m}).
A schedule is an allocation of tasks to time intervals on
machines. The goal in the job-shop scheduling problem is tofind the sequence of n jobs to be completed on m machines
such that the makespan (finish time of the last operation) is
minimized.
The job-shop scheduling problem is well known as oneof the most difficult NP-hard combinatorial optimization
problems. Several approaches have been reported to the JSSP
for a few decades. Among them work on Genetic Algorithms(GAs) for solving the JSSP has a history of only two decades,
but they perform well compared with other approaches.
Davis [7] was the first to use Genetic Algorithms to solve
the JSSP, and many GAs have been proposed and analyzed(e.g., [1], [4], [8], [11], [12], [14]–[16], [20], [23]–[26]).
Other heuristics such as Simulated Annealing (SA) andTabu Search (TS), and exact techniques as branch and boundhave also been developed for solving the JSSP. Jain and
Meeran provide a good description of these techniques [9].
However, the tuning of genetic parameters has to be
performed by trial and error, making optimization by GA
ad hoc. There have been many research projects for selfadaptive GA because such adaptation can tune the parameters
while solving a given problem. Nevertheless, it is a very timeconsuming task to design an optimal GA in an adaptive way

because we have to perform computation many times by trial
and error. To address this problem, Sawai et al. have proposed
the Parameter-free Genetic Algorithm (PfGA), for which nocontrol parameters for genetic operation need to be set inadvance [10], [17], [18]. The performance of the PfGA has
been reported to be high compared with other GAs [10], [17],[18].
Matsui et al. have proposed an extended parameter-free
GA for the JSSP [13], and reported that the GA performed well without tedious parameter-tuning. Their GA ispromising, but they only tested a small number of problem
instances.
This paper reports the results of an empirical evaluationof the GA to a wider range of problem instances. The
simulation results show that the GA performs well for many
problem instances, and the performance can be improved
greatly by increasing the number of subpopulations in theparallel distributed version.
II. T HE GA FOR E MPIRICAL E VALUATIONThis section gives a very brief overview of the GA [13]for the empirical evaluation. The proposed GA uses therandom keys [15] for permutation representation, and hybrid
scheduling for decoding the permutation.
A. Chromosome Representation
There are two ways of representing a schedule: indirect
and direct. In indirect representation, the chromosome contains an encoded schedule. A schedule builder is used totransform the chromosome into a feasible schedule. The
indirect representations range from traditional binary representations [14] to domain-specific knowledge representation[2].
In direct representation, the chromosome directly represents the production schedule. Bruns [6] shows many ways
to deal with direct representations. Direct representation
performs efficiently on production scheduling, incorporates
domain-specific operations easily, but also requires domainspecific recombination operators.
B. Types of Feasible Schedules
There are four types of feasible schedules in JSSP as
follows;(1) inadmissible: Inadmissible schedules contain
excess idle time, and they can be improved byforward-shifting operations until no excess idle
time exists.

S. Matsui is with System Engineering Research Laboratory (SERL), Central Research Institute of Electric Power Industry (CRIEPI), 2-11-1 Iwadokita, Komae-shi, Tokyo 201-8511, Japan; email: matsui@criepi.denken.or.jp.
S. Yamada is with National Institute of Informatics (NII), 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan; email: seiji@nii.ac.jp.

3796
c1-4244-1340-0/07/$25.00 2007
IEEE

(2) semi-active: Semi-active schedules contain noexcess idle time, but they can be improved by shifting some operations to the front without delaying
others.
(3) active: Active schedules contain no idle timeand no operation can be finished earlier without
delaying other operations. The optimal schedule isguaranteed to be an active schedule.
(4) non-delay: Non-delay schedules are active
schedules, in which operations are placed into theschedule such that the machine idle time is minimized. No machine is kept idle if some operation
can be processed.

D. Parameter-free Genetic Algorithm

The random keys representation [3], [15] encodes a solution with random numbers. These values are used as the sortkeys to decode the permutation.
C. Permutation Decoding
Permutations can be decoded into semi-active, active, or
non-delay schedules [5]. μi (k) = j (1 ≤ k ≤ mi ) specifies
that Mj is the machine that processes the k-th operation of
job Ji , where mi is the number of operations of Ji . The k-th
operation of job Ji processed on machine Mμi (k) is denotedas oik . The required processing time of oik is denoted bypik . Let tik be the starting time of operation oik , let thl andphl be the starting time and the required processing time ofthe operation of job Jh which precedes oik on its machine,thentik = max(ti,k−1 + pi,k−1 , thl + phl ).

(1)Hybrid schedules [5] can be produced in a flexible way
by introducing a parameter δ ∈ [0, 1]. The setting of δ canbe thought of as defining a bound on the length of time amachine is allowed to remain idle. At the extreme δ = 0
produces non-delay schedules while δ = 1 produces active
schedules. A schedule is constructed according to a given
permutation as follows.
step 1:Build the set of all beginning operations A :={oi1 | 1 ≤ i ≤ n}.
step 2:Find an operation o from A with the earliest
completion time t + p .
step 3:Determine the machine M  of o and build the set
B from all operations in A which are processed onM .
step 4:Find an operation o from B with the earliest
possible starting time t .
step 5:Delete operations in B in accordance with parameter δ such that
B := {oik ∈ B | tik ≤ t + δ((t + p ) − t )}.
step 6:Select operation o∗ik from B which occurs leftmost
in the permutation and delete it from A.
step 7:Append operation o∗ik to the schedule and calculate
its starting time.
step 8:If o∗ik has successor o∗i,k+1 , insert it into A.
step 9:If A is empty, terminate. Otherwise, go to step 2.

The Parameter-free Genetic Algorithm (PfGA) proposedby Sawai et al. [10], [17], [18] is a novel GA inspired by
the “disparity theory of evolution.” The idea of the theory
is based on different mutation rate in double strands ofDNA. The PfGA is a very compact and fast adaptive searchalgorithm based on the variable-size of population taking
a dynamic but delicate balance between exploration, andexploitation, i.e., global search and local search. The PfGA
is not only simple and robust, but also does not need to set
almost all genetic parameters in advance that need to be set
up in other GAs. The performance of PfGA is reported tobe very high for function optimization problems [10], [17],[18].
The PfGA procedure is as follows [17].
step 0:Let S be the whole population, and S  be thesubpopulation.
step 1:Select one individual randomly from S, and add it
to S  .
step 2:Select one individual randomly from S, and add it
to S  .
step 3:Select two individuals P1 , P2 randomly from S and perform multiple-point crossover to generate
two children C1 , C2 . In the crossover n crossover
points (n is a random integer 0 < n < L, where
L is the length of chromosome) are randomly
selected.
step 4:For one randomly selected child, perform mutation.
In the mutation, a randomly chosen portion ofchromosome is inverted, i.e., bit-flipped, at random.
step 5:Select one to three individuals among
P1 , P2 , C1 , C2 depending on the cases (describedlater), and feed them back to S  .
step 6:If the terminating condition is satisfied, then terminate.
step 7:If |S  | > 1 then go to step 3, otherwise go to step2.
For the selection operation in step 5, the fitness values fof P1 , P2 , C1 , C2 are compared, and the selection is done
according to the following rules.
case 1:If the fitness values of children f (C1 ) and f (C2 )are better than those of the parents, then C1 andC2 and argmax(f (P1 ), f (P2 )) are left in S  .
Picase 2:If the fitness values of children f (C1 ) andf (C2 ) are worse than those of parents, then only
argmax(f (P1 ), f (P2 )) is left in S  .
Picase 3:If the fitnessisorf (P2 )
children,thenvalues of either f (P1 )better
than
those
of
and
argmax(f (P1 ), f (P2 ))Piargmax(f (C1 ), f (C2 )) are left in S  .
Cicase 4:In all other situations, argmax(f (C1 ), f (C2 )) is
Ci

preserved and then one individual randomly chosenfrom S is added to S  .

2007 IEEE Congress on Evolutionary Computation (CEC 2007)

3797

E. Distributed Parallel PfGA
The distributed parallel processing of PfGA is as follows[17]. Let us assume that there are N subpopulations Si (i =1, 2, · · · , N ), and each subpopulation evolves as shown in theprevious section. Migration among the subpopulations occurs
when a better individual is produced in a subpopulation.
Sawai et al. proposed many migration methods, masterslave types and uniform-distributed types. The migration
method tested in this paper, which is named as UD1, is asfollows. If a better child is generated in a subpopulation, thebest child Ci is copied to other randomly chosen subpopulations as an emigrant. When other subpopulations receive
the immigrant, they add it as an individual and eliminate theworst individual among all individuals in the subpopulation.
F. Real-coded PfGA (Rc-PfGA)
Matsui et al. have extended the PfGA to a real codedversion. A gene of the original PfGA takes the value of 0 or
1, i.e., a chromosome is a bit-string. The real coded PfGA isan extension where a chromosome is a string of real numbers.
The mutation operator of Rc-PfGA replaces the value ofa gene by a random number uniformly distributed in thepredefined range.
The random keys representation of permutation can be
expressed naturally with the Rc-PfGA.
G. Chromosome
The chromosome of the GA is a sequence of real numbers,
and its length is 2 × n × m. The chromosome is divided into
two parts, the first part represents the random keys, and thesecond part represents the δs of the hybrid schedule.
III. C OMPUTATIONAL R ESULTS
The GA is tested by the benchmark problems from ORLib[22]. In the paper [13], as the problem instances, we onlyused the the same set that was used by Norman and Bean
[15]. The instances were limited to FT10, FT20, and LA01–
LA40, therefore we tested a wider range of instances, namely
10 tough problems, ORB01–ORB10, SWV01–SWV20, andTA01–TA30.
The GA was run for each problem instance using 50
different random seeds. The maximum number of fitness
evaluations was set to 1,000,000 as the base case.
A. 10 Tough Problems
1) Serial or Parallel: Matusi et al. showed that theperformance of the GA improved as they increased thenumber of subpopulations (N ) in distributed parallel version,
because the total number of fitness evaluations increased[13]. But they did not show whether the GA converged or not.
Therefore we tested the GA with different number of fitness
evaluations using the serial version and the parallel version.
We tested 10 tough problems as the problem instances,
ABZ7, ABZ8, ABZ9, LA21, LA24, LA25, LA27, LA29,
LA38, and LA40.

3798

The results are shown in Table I. In Table I, S2, S4, andS8 correspond to the cases where the number of fitness evaluations was multiplied by 2, 4, and 8, and D2, D4, and D8
correspond to the cases where the number of subpopulations(N ) was set to N = {2, 4, 8}. The μ, σ, and ‘best’ represents
the average, standard deviation, and best makespan over 50
runs respectively. The numbers in boldface shows the optimal
makespan.
Table I shows the followings.
• In most cases, as we increase the number of fitness
evaluations, the average makespan is reduced, and also
the standard deviation of makespan decreases in both theserial and the parallel version. But the best makespandoes not always shorten as we increase the number offitness evaluations.
• The difference of average makespan between the serial
and the parallel version is small. We can verify thatthe difference is not statistically significant by statisticaltests (t-test, Welch’s test, and non-parametric tests).
• The best makespan by the serial version is smaller thanthat by the parallel version in LA21, LA24, LA25,
and LA27 for all cases. In other problems, the best
makespan by the parallel version is smaller when wecompare S8 and D8, except for ABZ8 and ABZ9.
The average computation time of the serial version per run,for example, was 237 (sec.) for LA29 (20×10), 225 (sec.)
for LA40 (15×15) on a PC with an AMD Athlon MP 1800+(1.53GHz).
2) Number of Subpopulations: In the paper [13] they
only reported the cases where the number of subpopulations(N ) was set to N = {2, 4, 8}. We ran the cases N ={1, 4, 8, 16, 32, 64} to see the performance improvement by
increasing the number of subpopulations. Table II shows theresults. In Table II ‘blb’ represents the best lower bound [9],and n × m represents the problem size.
Fig.1 and 2 show the relative error of the best span tothe best upper bound and the average span to the best upperbound respectively. In the column ‘Best bounds’, the number
in parentheses denotes the best lower bound, the number
without parentheses denoted the best upper bound or the
optimal makespan.
From Tables II and Fig.1, 2, we can conclude the followings.
• As we increase the number of subpopulations, the average makespan is reduced, but the best makespan does
not always shorten. Except for the case that is relatively
easy (LA21, LA24, and LA25) the best span does not
shorten as we increase the number of populations.
• The relative error to the best upper bound is very small.
• The relative error of the best span to the best upperbound decreases roughly proportional to 1/N 1/8 . The
relative error of the average makespan to the best upperbound decreases in a similar way.

2007 IEEE Congress on Evolutionary Computation (CEC 2007)

TABLE IC OMPARISON OF SERIAL AND PARALLEL VERSION (10 TOUGH PROBLEMS )

μ
σ
best
μ
σ
best

μ
σ
best
μ
σ
best
μ
σ
best
μ
σ
best

ABZ7(20 × 15)
S2
S4
S8
692.7
688.2
685.7
5.24
5.64
6.1
681
677
672
D2
D4
D8
691.1
687.3
685.4
6.8
5.6
4.7
676
674
677
LA21(15 × 10)
S2
S4
S81069.0 1065.9 1069.4
12.0
9.2
11.5
1046
1047
1047
D2
D4
D8
1070.2 1066.5 1062.2
11.4
9.9
7.8
1047
1047
1050
LA29(20 × 10)
S2
S4
S81203.7 1199.0 1196.6
11.9
14.2
13.1
1184
1169
1167
D2
D4
D8
1203.5 1199.8 1191.0
12.8
13.6
10.0
1171
1175
1167

ABZ8(20 × 15)
ABZ9(20 × 15)
S2
S4
S8
S2
S4
S8
713.8
710.8
708.1
725.2
719.0
718.5
5.8
6.8
6.4
9.1
7.9
7.2
704
696
696
703
706
705
D2
D4
D8
D2
D4
D8
714.7
709.1
703.9
721.8
718.9
716.4
7.2
5.9
6.7
8.2
7.8
7.4
700
698
689
706
703
703
LA24(15 × 10)
LA25(15 × 10)
S2
S4
S8
S2
S4
S8
958.1
952.9
950.2
990.2
989.0
986.5
10.2
10.1
10.2
6.9
7.2
6.4
939
938
938
977
977
977
D2
D4
D8
D2
D4
D8
957.1
954.1
951.9
991.4
988.0
986.0
10.4
10.7
8.5
8.0
7.3
6.7
939
938
941
977
977
977
LA38(15 × 15)
LA40(15 × 15)
S2
S4
S8
S2
S4
S8
1251.0 1248.5 1244.3 1255.5 1253.1 1247.1
16.9
19.1
15.2
11.8
11.1
7.1
1220
1207
1212
1233
1233
1228
D2
D4
D8
D2
D4
D8
1251.3 1244.1 1237.7 1254.9 1249.7 1245.8
16.6
15.1
14.3
11.4
9.1
8.1
1219
1203
1216
1228
1228
1231

LA27(20 × 10)
S2
S4
S81267.7 1264.2 1263.2
7.0
7.2
6.4
1253
1240
1245
D2
D4
D8
1267.8 1265.2 1263.5
5.5
7.0
6.4
1255
1250
1250

Fig. 1. Relative error of the best span to the best upper bound (10 toughproblems)

Fig. 2. Relative error of the average span to the best upper bound (10tough problems)

3) Number of Migration: The number of migrations wasvery small for all problems, below 0.01% of the total numberof fitness evaluations. Therefore, the overhead of communication by MPI (Message Passing Interface) [19] among
subpopulations was negligible, and the computation time wasalmost equal to that of the serial version. Because there isno significant difference of average makespan between theserial and parallel version, we decided to test the parallelversion for other problem instances.

2007 IEEE Congress on Evolutionary Computation (CEC 2007)

3799

TABLE IIS IMULATION RESULTS FOR 10 TOUGH PROBLEMS

Prob.
ABZ7
ABZ8
ABZ9
LA21
LA24
LA25
LA27
LA29
LA38
LA40

n×m
20×15
20×15
20×15
15×10
15×10
15×10
20×10
20×10
15×15
15×15

blb [9]
656
645
661
1046
935
977
1235
1152
1196
1222

Prob.
ABZ7
ABZ8
ABZ9
LA21
LA24
LA25
LA27
LA29
LA38
LA40

n×m
20×15
20×15
20×15
15×10
15×10
15×10
20×10
20×10
15×15
15×15

blb [9]
656
645
661
1046
935
977
1235
1152
1196
1222

N =1
μ
696.1
716.4
730.0
1071.8959.8
996.8
1273.71207.61260.91258.5N = 16
best
μ
669
681.4
680
700.3
692
710.0
1047 1058.0
938
948.8
977
983.6
1244 1260.01164 1186.4
1205 1228.3
1224 1240.7
best
677
700
708
1053
938
978
1260
1184
1208
1240

σ
7.5
7.5
9.1
11.9
12.7
10.2
9.6
12.6
21.2
9.3
σ
4.2
7.0
6.3
6.9
7.5
4.9
6.7
10.4
10.6
7.1

N =2
μ
691.1
714.7
721.8
1070.2957.1
991.4
1267.81203.51251.31254.9N = 32
best
μ
669
677.6
688
696.9
696
707.2
1046 1054.8
937
943.1
977
982.6
1241 1256.01164 1185.01202 1223.9
1226 1240.6
best
676
700
706
1047
939
977
1255
1171
1219
1228

σ
6.8
7.2
8.2
11.4
10.4
8.0
5.5
12.8
16.6
11.4
σ
4.8
5.7
5.7
6.0
4.9
5.1
6.9
8.9
11.5
4.6

N =4
μ
σ
687.3
5.6
709.1
5.9
718.9
7.8
1066.59.9
954.1 10.7
988.0
7.3
1265.27.0
1199.8 13.6
1244.1 15.1
1249.7
9.1
N = 64
best
μ
σ
667
675.6
3.5
680
693.0
5.3
692
703.9
4.5
1046 1051.5
3.8
935
940.3
3.1
977
979.7
3.2
1241 1254.2
6.21163 1175.2
9.01202 1215.8
7.61228 1238.2
5.2
best
674
698
703
1047
938
977
1250
1175
1203
1228

best
677
689
703
1050
941
977
1250
1167
1216
1231

N =8
μ
σ
685.4
4.7
703.9
6.7
716.4
7.4
1062.2
7.8
951.9
8.5
986.0
6.7
1263.5
6.4
1191.0 10.0
1237.7 14.3
1245.88.1

B. ORB Problem Instances
Table III and Fig. 3 show the results for problem instances
ORB01–ORB10. Due to space limitation, we only show thecases for N = {1, 16, 32, 64} in Table III, but the relative
error to the optimal makespan is shown for all cases N ={1, 2, 4, 8, 16, 32, 64} in Fig. 3.
Table III and Fig. 3 show the followings.
• Because the size of the ORB problems is small, 10 ×
10, the GA can find the optimal makespan with N =1 except for ORB02, ORB05, and ORB06. The best
makespan can be found in all problem instances whenN ≥ 8.
• The relative error of the average makespan to the best
makespan decreases as we increase N . It is very small,
below 1.0%, when N ≥ 16. The relative error decreases
in a similar way as of the 10 tough problems.
• The GA can always find the optimal makespan whenN ≥ 2 in ORB10, when N ≥ 32 in ORB09, and when
N = 64 in ORB08.
C. TA and SWV Problem Instances
Table IV and Fig. 4 show the results for problem instances TA01–TA30, and Table V and Fig. 5 show theresults for problem instances SWV01–SWV15 (hard SWV
problems). Due to space limitation, we only show the cases
for N = {1, 16, 32, 64} in Table IV and Fig. 5, but therelative error to the best upper bound is shown for all cases
N = {1, 2, 4, 8, 16, 32, 64} in Fig. 4 and Fig. 5.

3800

Fig. 3.

Average relative error to the optimal makespan (ORB problems)

The GA can find the makespan that is equal to the
optimal or the best upper bound in TA02 and TA03
when we increase the number of subpopulations.
• As we increase the number of subpopulations, theaverage makespan is reduced, but the best makespandoes not always shorten. The relative error decreases ina similar way as of the 10 tough problems and ORB
problem instances.
• The average relative error to the best upper bound issmall enough in TA01–TA10, below 1.5%, when N =•2007 IEEE Congress on Evolutionary Computation (CEC 2007)

TABLE III
S IMULATION RESULTS FOR ORB PROBLEMS

Prob.
ORB01
ORB02
ORB03
ORB04
ORB05
ORB06
ORB07
ORB08
ORB09
ORB10

n×m
10×10
10×10
10×10
10×10
10×10
10×10
10×10
10×10
10×10
10×10

Opt [9]
1059
888
1005
1005
887
1010
397
899
934
944

N =1
Best
μ
1059 1087.0
889
892.7
1005 1027.7
1005 1016.8
889
893.0
1012 1029.3
397
401.2
899
920.3
934
939.9
944
944.5

N = 16Bestμ1059 1066.3
888
889.0
1005 1014.9
1005 1011.1
887
889.1
1010 1019.6
397
397.7
899
906.2
934
934.7
944
944.0

N = 32Bestμ1059 1062.3
888
889.0
1005 1011.4
1005 1009.9
887
888.8
1010 1016.7
397
397.2
899
902.8
934
934.0
944
944.0

N = 64Bestμ1059 1059.6
888
888.8
1005 1007.3
1005 1007.9
887
888.5
1010 1014.5
397
397.0
899
901.8
934
934.0
944
944.0

TABLE IVS IMULATION RESULTS FOR TA PROBLEMS

Prob.
TA01
TA02
TA03
TA04
TA05
TA06
TA07
TA08
TA09
TA10
TA11
TA12
TA13
TA14
TA15
TA16
TA17
TA18
TA19
TA20
TA21
TA22
TA23
TA24
TA25
TA26
TA27
TA28
TA29
TA30

n×m
15×15
15×15
15×15
15×15
15×15
15×15
15×15
15×15
15×15
15×15
20×15
20×15
20×15
20×15
20×15
20×15
20×15
20×15
20×15
20×15
20×20
20×20
20×20
20×20
20×20
20×20
20×20
20×20
20×20
20×20

Best
bounds [21]
1231
1244
1218
1175
1224
1238
1227
1217
1274
1241
1361(1323)
1367(1351)
1342(1282)
1345
1340(1304)
1360(1302)
1462
1396(1369)
1335(1297)
1351(1318)
1644(1539)
1600(1511)
1557(1472)
1647(1602)
1595(1504)
1645(1539)
1680(1616)
1614(1614)
1625(1514)
1584(1473)

N =1
Best
μ
1265 1288.2
1252 1280.9
1228 1256.8
1191 1222.6
1253 1272.4
1249 1286.8
1250 1264.0
1233 1266.8
1314 1342.9
1244 1299.0
1416 1464.0
1428 1471.6
1407 1443.1
1374 1405.5
1412 1461.3
1417 1462.8
1498 1546.5
1468 1519.1
1419 1454.2
1414 1453.3
1729 1773.6
1699 1736.2
1635 1683.9
1712 1767.8
1665 1715.6
1728 1766.3
1787 1827.3
1698 1739.4
1689 1730.5
1656 1717.8

64. But in TA11–TA30 it varies from 1.5% to 5.3%
even in N = 64. The best relative error to the best
upper bound is from 0.4% to 3.6% when N = 64.
• The relative error to the best upper bound is larger

N = 16Bestμ1249 1263.1
1244 1264.3
1219 1232.4
1181 1195.0
1236 1252.6
1248 1263.7
1236 1247.3
1221 1242.0
1296 1316.4
1244 1265.1
1395 1430.01406 1435.4
1378 1408.1
1352 1378.0
1388 1416.1
1397 1426.9
1496 1519.9
1461 1489.1
1398 1419.9
1399 1420.0
1687 1728.7
1677 1697.3
1595 1641.9
1695 1730.3
1651 1682.8
1700 1728.7
1737 1777.91658 1691.5
1655 1693.3
1639 1679.0

N = 32Bestμ1248 1259.6
1244 1261.0
1218 1229.3
1181 1191.3
1236 1246.4
1248 1258.6
1233 1242.6
1224 1238.2
1292 1310.2
1244 1256.3
1408 1426.8
1408 1430.8
1361 1399.6
1355 1373.6
1379 1412.6
1400 1420.2
1494 1514.1
1449 1477.6
1390 1415.2
1389 1414.1
1688 1723.1
1665 1689.7
1598 1636.9
1698 1722.0
1644 1671.3
1704 1724.7
1725 1761.3
1653 1685.9
1656 1685.9
1638 1667.7

N = 64Bestμ1241 1254.3
1244 1255.8
1218 1226.4
1181 1188.4
1228 1244.9
1246 1255.4
1228 1240.6
1223 1233.1
1284 1305.61244 1246.5
1398 1419.9
1396 1421.8
1371 1393.5
1351 1365.81384 1402.1
1380 1413.8
1490 1508.3
1443 1468.9
1382 1405.8
1380 1406.8
1685 1716.1
1646 1683.3
1589 1625.1
1693 1716.2
1650 1668.3
1699 1719.7
1741 1760.1
1654 1676.4
1653 1678.1
1638 1661.5

than that of ORB cases. This is due to the size of the
problems. The size of ORB problems is 10×10 and it is
15 × 15, 20 × 15, or 20 × 20 in TA problems. The lengthof the chromosomes used in the GA is proportional to2007 IEEE Congress on Evolutionary Computation (CEC 2007)

3801

Fig. 4.

Average relative error to the best upper bound (TA problems)
TABLE VS IMULATION RESULTS FOR HARD SWV PROBLEMS

Prob.
SWV01
SWV02
SWV03
SWV04
SWV05
SWV06
SWV07
SWV08
SWV09
SWV10
SWV11
SWV12
SWV13
SWV14
SWV15

n×m
20×10
20×10
20×10
20×10
20×10
20×15
20×15
20×15
20×15
20×15
50×10
50×10
50×10
50×10
50×10

Best
bounds [9]
1407
1475
1398(1396)
1483(1450)
1424
1678(1591)
1620(1446)
1763(1640)
1663(1604)
1767(1631)
2991(2983)
3003(2972)
3104
2968
2904(2885)

N =1
Best
μ
1489 1545.2
1549 1588.7
1480 1522.4
1559 1601.0
1532 1576.5
1817 1879.5
1737 1788.1
1939 2006.3
1809 1872.1
1902 1940.0
3327 3468.5
3429 3509.6
3462 3567.0
3274 3385.9
3327 3426.7

N = 16Bestμ1456 1490.5
1499 1551.9
1433 1475.6
1509 1555.0
1475 1523.7
1782 1825.6
1711 1742.1
1865 1934.7
1762 1812.1
1849 1886.1
3240 3355.3
3330 3397.0
3348 3450.1
3162 3259.9
3210 3318.0

N = 32Bestμ1442 1478.5
1496 1543.6
1436 1468.8
1519 1545.7
1469 1514.0
1778 1809.6
1688 1731.4
1881 1919.6
1741 1795.7
1830 1870.4
3241 3323.4
3297 3369.4
3374 3423.63150 3236.9
3190 3275.8

N = 64Bestμ1459 1479.9
1503 1537.8
1433 1465.2
1509 1535.4
1470 1506.7
1752 1797.9
1687 1720.3
1851 1904.3
1742 1783.8
1809 1862.4
3212 3300.53274 3349.8
3310 3386.5
3115 3189.0
3189 3254.9

the size of problems, 2 × n × m, therefore the length(L) is 200 in ORB problems, and 450, 600, or 800 in
TA problems. More detailed analysis is shown in thediscussion section.

Fig. 5.
Average relative error to the optimal makespan (Hard SWV
problems)

3802

D. Discussions
The relative error to the best upper bound varies amongproblem instances. The size of the problems is a reason of
the difference. The length of the chromosomes in the GA is
proportional to the size of problem instances, 2 × n × m,
therefore the length (L) varies from 200 (10 × 10 problems)
to 1000 (50 × 10 problems).
The size of search space is approximately proportional
to Z L where Z is a constant determined by the floatingpoint number representation format. Because we used theIEEE 32-bit representation of floating-point number format
in these experiments, Z = 224 . Therefore the size of search
space varies from (224 )200  101444 to (224 )1000  107224 .

2007 IEEE Congress on Evolutionary Computation (CEC 2007)

The difference of search space is huge, but the performancedoes not vary so greatly, and this supports the promising
applicability of the PfGA to wider class of JSSP instances.
As the experiments show, we can easily improve thesolution by just increasing the number of subpopulations.
This is also a good feature of the PfGA when applied to thereal-world applications. There are dual-/quad-core CPUs thatare not expensive, it is very easy to have PC-based cluster
system, and it is fairly easy to have a multi-processor system
today. Therefore it is very easy to increase the number of
subpopulations, and have a better solutions using distributed
version of PfGA.
IV. C ONCLUSIONS AND F UTURE W ORK
Our empirical performance evaluation showed that theparameter-free GA for JSSP can attain high quality solutions
for a wide range of benchmark problems without tediousparameter tuning. Though the decreasing rate of the averagerelative error to the best upper bound is not high, it is roughly
proportional to 1/N 1/8 (N is the number of subpopulations),
the parallel version can attain better results as we increase thenumber of subpopulations. The average makespan is reduced
as we increase the number of fitness evaluations. If the total
number of fitness evaluations is the same for the serial andparallel version, there is no statistically significant difference
in both versions, therefore we can speed-up by using theparallel version. The performance increases as we increase
the number of fitness evaluations in subpopulations, so wewill test it for a wider class of benchmark problems.
R EFERENCES[1] K.S. Amirthagadeswaran and V.P. Arunachalam: “Improved solutions
for job shop scheduling problems through genetic algorithm with adifferent method of schedule deduction,” The International Journal ofAdvanced Manufacturing Technology, vol.28, no.5-6, pp.1433–3015,
2006[2] S. Bagchi, S. Uckun, Y. Miyabe, and K. Kawarnura: “ Exploring
problem-specific recombination operators for job shop scheduling,”
International Conf. Genetic Algorithms (ICGA-91), pp.10–17, 1991.
[3] J.C. Bean: “Genetics and random keys for sequencing and optimization,” ORSA Journal of Computing, vol.6, no.2, pp.154–160, 1994.
[4] C. Bierwirth, D. Mattfeld, and H. Kopfer: “On permutation representations for scheduling problems,” Proc. 4th Parallel Problem Solvingfrom Nature – PPSN IV, pp.310–318, 1996.
[5] C. Bierwirth and D.C. Mattfeld: “Production scheduling and rescheduling with generic algorithms,” Evolutionary Computation, vol.7, no.1,
pp.1–17, 1999.
[6] R. Bruns: “Direct chromosome representation and advanced genetic
operations for production scheduling,” International Conf. Genetic
Algorithms (ICGA-93), pp.352–359, 1993.

[7] L. Davis: “Job shop scheduling with genetic algorithms,” International
Conf. Genetic Algorithms (ICGA-85), pp.136–140, 1985.
[8] P. Fenton and P. Walsh: “A comparison of messy GA and permutation based GA for job shop scheduling,” Genetic And Evolutionary
Computation Conference 2005, pp.1593–1594, 2005.
[9] A.S. Jain and S. Meeran: “Deterministic job-shop scheduling: past,present and future,” European Journal of Operational Research,
vol.113, pp.390–434, 1999.
[10] S. Kizu, H. Sawai and H. Endo: “Parameter-free genetic algorithm:
GA without setting genetic parameters,” Proc. 1997 International
Symposium on Nonlinear Theory and its Application, vol.2 of 2,
pp.1273–1276, 1997.
[11] S. Kobayashi,I. Ono and M. Yamamura: “An efficient genetic algorithm for job shop scheduling problems,” Proc. Sixth International
Conference on Genetic Algorithms, pp.506-511, 1995.
[12] T.-K. Liu, J.-T. Tsai, and J.-H. Chou: “Improved genetic algorithm
for the job-shop scheduling problem,” The International Journal ofAdvanced Manufacturing Technology, vol.27, no.9-10, pp.1021–1029,
2006.
[13] S. Matsui, I. Watanabe, and K. Tokoro: “Real-coded parameterfree genetic algorithm for job-shop scheduling problems,” Proc. 7th
Parallel Problem Solving from Nature – PPSN VII, pp.800–810, 2002.
[14] R. Nakano and T. Yamada: “Conventional genetic algorithm for job
shop scheduling,” Proc. 3rd International Conference on Genetic
Algorithms, pp.474–479, 1991.
[15] B. Norman and J.C. Bean: “Random keys genetic algorithm for job
shop scheduling,” Engineering Design & Automation, vol.3, no.2,
pp.145–156, 1997.
[16] B.M. Ombuki and M. Ventresca: “Local search genetic algorithms forthe job shop scheduling problem,” vol.21, no.1, pp.99–109, 2004.
[17] H. Sawai and S. Kizu: Parameter-free genetic algorithm inspired by“disparity theory “of evolution”,” Proc. 5th Parallel Problem Solvingfrom Nature – PPSN V, pp.702–711, 1998.
[18] H. Sawai, S. Kizu, and T. Endo: “Parameter-free genetic algorithm(PfGA),” Trans. IEICE, Japan, vol.J81-D-II, no.2, pp.450–452, 1998
(in Japanese).
[19] M. Snir, S.W. Otto, S. Huss-Lederman, D.W. Walker, and J. Dongarra:
MPI: The Complete Reference, The MIT Press (1997)[20] R. Storer, S. Wu, and R. Vaccari: “New search spaces for sequencing
problems with application to job shop scheduling,” Management
Science, vol.38, pp.1495–1509, 1992.
[21] É. Taillard: “Summary of best known lower and upperbound of Taillard’s instances,” http://ina.eivd.ch/collaborateurs/
etd/problemes.dir/ordonnancement.dir/ jobshop.dir/best lb up.txt, last
updated Nov. 17, 2005 (2005).
[22] R.J.M. Vaessens: “Operations Research Library of Problems,” Management School, Imperial College London, ftp://mscmga.ms.ic.ac.uk/
pub/jobshop1.txt, 1996.
[23] M. Vázquez and D. Whitley: “A comparison of genetic algorithms forthe static job shop scheduling problem,” Proc. 6th Parallel Problem
Solving from Nature – PPSN VI, pp.303–312, 2000.
[24] T. Yamada and R. Nakano: “A genetic algorithm applicable to largescale job-shop problems,” Proc. 2nd Parallel Problem Solving fromNature – PPSN II, pp.281–290, 1992.
[25] L. Wang and D.-Z. Zheng: “A modified genetic algorithm for job shop
scheduling,” The International Journal of Advanced Manufacturing
Technology, vol.20, no.1, 2002.
[26] C. Wu, W. Xiang, Y. Liang, H. Pueh Lee, and C. Zhou: “A modified
integer-coding genetic algorithm for job shop scheduling problem,”
PRICAI 2004: Trends in Artificial Intelligence, pp.373–380, 2004.

2007 IEEE Congress on Evolutionary Computation (CEC 2007)

3803