IEEE International Conference on Industrial Technology (ICIT ’96) Shanghai, China
DECEMBER 2 - 6, 1996 pp. 426–430

A Fusion of Crossover and Local SearchTakeshi Yamada and Ryohei Nakano

NTT Communication Science Laboratories
2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02 JAPAN
Abstract— It is well known that GAs are
not well suited for fine-tuning structures thatare very close to optimal solutions and that
it is essential to incorporate local searchmethods, such as neighborhood search, into
GAs. This paper explores the use of a new
GA operator called multi-step crossover fusion (MSXF), which combines a crossover
operator with a neighborhood search algorithm. MSXF performs a local search essentially in the region within the search
space between parent solutions to find a locally optimal solution that inherits the parents’ characteristics. GA/MSXF was applied
to job-shop scheduling problem (JSSP). Experiments using benchmark problems showpromising GA/MSXF performance even witha small population.

I. Introduction
In solving combinatorial optimization problems such as job-shop scheduling problems(JSSP), it is often more difficult to define acrossover operator that recombines solutions andmakes global changes to them than it is to define
a transition operator of a neighborhood searchalgorithm that only modifies a solution locally.
Reeves proposed a neighborhood search crossoverfor Simple GA based on an extended neighboorhood and Hamming distance[8]. In fact, it israther easy to construct an example of neighborhood search for JSSP by using naturally introduced job permutations, and this can be further
enhanced by limiting the permutations on thecritical path and using active schedules. Unfortunately, the same method provides no help inbuilding an effective crossover operator, which
prevents us from applying GAs.
A GA using a binary encoding scheme was
first proposed by the authors in [7]. Although
this approach is simple and straightforward, it is
not robust enough because some members in thebinary neighborhood cannot be mapped backto job sequences or feasible schedules. Limiting the search to the set of all active schedules has proved to be more efficient. The

GT crossover based on Giffler and Thompson’s
active scheduler algorithm was proposed as ahigh-level crossover in this higher-level solution
space[12]. A still higher-level solution space isobtained by focusing on the critical path of aschedule and limiting the search to the critical path level. Simulated Annealing (SA) using
the Critical Block (CB) neighborhood has beenshown experimentally to be very powerful compared with other GA methods and SA methods
using other neighborhoods[15, 14].
Therefore it is quite natural to expect that
GA’s population-based search strategies and thefine tuning mechanism of local neighborhood
search could be unified to produce a very powerful optimization algorithm for JSSP. In thispaper, Multi-Step Crossover Fusion (MSXF) is
proposed as a new high-level crossover fusedwith a local search method. In MSXF, a solution initially set to be one of the parents is
stochastically replaced by a relatively good solution from the neighborhood, where the replacement is biased toward the other parent. The biased stochastic replacement is described briefly
as follows:
1. All members in the neighborhood are indexed
in ascending order according to their distancefrom the other parent.
2. A member is randomly selected from theneighborhood, but a smaller index is preferred.
It is then probabilistically accepted according
to its evaluation value.
3. If it is rejected, its index is changed to thelargest one in the neighborhood and the process returns to step 2.
4. Otherwise the current solution is replaced by
the selected one.
After a certain number of iterations of this process, the best one among the generated solutions is selected as an offspring. MSXF canbe viewed as a recombination operator in which
local search functionality is built in. In otherwords, it acts as a single operator unifying
crossover and local search.
MSXF has been applied to JSSP, employ-hood search, into GAs. The result of such incorporation is often called Genetic Local Search(GLS) [10]. In this framework, an offspring obtained by a recombination operator, such as acrossover, is not included in the next generation
directly but is used as a “seed” for the subsequent local search. The local search moves theoffspring from its initial point to the nearest loII. Backgroundcally optimal point, which is included in the next
generation.
A. Neighborhood Search
For more complicated problems to which
Neighborhood search is a widely used local
crossover operators are difficult to apply, this pasearch technique to solve combinatorial optiper proposes a different approach called Multimization problems. A solution x is represented
Step Crossover Fusion (MSXF): a new crossover
as a point in the search space, and a set of sooperator in which local search functionality islutions associated with x is defined as neighborbuilt in. A stochastic local neighborhood searchhood N (x). N (x) is a set of feasible solutions
algorithm is used for the base algorithm ofcapable of being reached from x by exactly one
MSXF. Although SA is a well-known stochastransition, a single perturbation of x.
tic method and has been successfully applied to
An outline of a neighborhood search for minimany problems as well as to JSSP, it would be
mizing V (x) is described in Algorithm 1, where
unrealistic to apply a full SA to our purpose bex denotes a point in the search space and V (x)cause it is too time consuming to run SA many
denotes its evaluation value.
times in a GA run. A restricted method witha fixed temperature parameter T = c might be
Algorithm 1 Neighborhood searcha good alternative. Accordingly, the acceptance• Select a starting point: x = x0 = xbest .
probability used in Algorithm 1 is rewritten as:do
1. Select a point y ∈ N (x) according to the
∆V
(y)
=
exp
−
, ∆V = V (y)−V (x), c : const.
Pcgiven criterion based on the value V (y). Setcx = y.
(2)
2. If V (x) < V (xbest ) then set xbest = x.
A crossover functionality can be incorporated
until some termination condition is satisfied.
into Algorithm 1 by adding more acceptance bias
in favor of y ∈ N (x) with a small d(y, p2 ). The
The criterion used in Step 1 in Algorithm 1 is acceptance bias in MSXF is controlled by sorting
called the choice criterion, by which the neigh- N (x) members in ascending order of d(yi , p2 ) soborhood search can be categorized. For exam- that yi with a smaller index i has a smaller disple, a descent method selects a point y ∈ N (x) tance d(yi , p2 ). Here d(yi , p2 ) can be estimatedsuch that V (y) < V (x). A stochastic method easily if d(x, p2 ) and the direction of the transiprobabilistically selects a point according to the tion from x to yi are known, and it is not necMetropolis Criterion, i.e. y ∈ N (x) is selected essary to generate and evaluate yi . Then yi iswith probability 1 if V (y) < V (x); otherwise, selected from N (x) randomly, but with a bias infavor of yi with a small index i. The outline ofwith probability:
MSXF is described in Algorithm 2.
P (y) = exp(−∆V /T ), where ∆V = V (y)−V (x) . In place of d(yi , p2 ), one can also use(1) σ(d(yi , p2 ) − d(x, p2 )) + r to sort N (x) memHere P is called the acceptance probability. Sim- bers in Algorithm 2. Here σ(x) denotes the signulated Annealing (SA) is a method in which pa- of x: σ(x) = 1 if x > 0, σ(x) = 0 if x = 0,
rameter T (called the temperature) decreases to σ(x) = −1 otherwise. A small random fraction
zero following an annealing schedule as the iter- r is added to randomize the order of members
ation step increases.
with the same sign.
The termination condition can be given, forB. Multi-Step Crossover Fusion
example, as the fixed number of iterations in
It is well known that GAs are not well suited the outer loop. MSXF is not applicable if thefor fine-tuning structures that are very close to distance between p1 and p2 is too small comoptimal solutions and that it is essential to incor- pared to the number of iterations. In such a case,porate local search methods, such as neighbor- a mutation operator called Multi-Step Mutation
ing a critical path-based neighborhood called
the CB neighborhood. Extensive experimental
studies have established the CB neighborhood
as one of the most powerful neighborhoods for
JSSP [15]. A GA with such a tailored high-level
MSXF (GA/MSXF) was evaluated with wellknown benchmark problems.

Algorithm 2 Multi-Step Crossover Fusion(MSXF)• Let p1 , p2 be parent solutions.
• Set x = p1 = q.
do • For each member yi ∈ N (x), calculated(yi , p2 ).
• Sort yi ∈ N (x) in ascending order ofd(yi , p2 ).
do 1. Select yi from N (x) randomly, butwith a bias in favor of yi with a small
index i.
2. Calculate V (yi ) if yi has not yet been
visited.
3. Accept yi with probability one if
V (yi ) ≤ V (x), and with Pc (yi ) otherwise.
4. Change the index of yi from i to n, andthe induces of yk (k ∈ {i + 1, i + 2, . . . , n})from k to k − 1.
until yi is accepted.
• Set x = yi .
• If V (x) < V (q) then set q = x.
until some termination condition is satisfied.
• q is used for the next generation.

Fusion (MSMF) is applied instead. MSMF canbe defined in the same manner as MSXF except
for one point: the bias is reversed, i.e. sort theN (x) members in descending order of d(yi , p2 )in Algorithm 2.
III. Job Shop Scheduling and GA/MSXF

of operations that must be performed on thesame machine.
The processing time for each operation is theweighted value attached to the corresponding
nodes.
conjunctive arc (technological sequences)disjunctive arc (pair of operations on the same machine)

P11
O11

source

0

P12
O12

P13
O13
P22
O22

P23
O23

P21
O21

O32
P32

O31
P31

sink

*

O33
P33

Oij : an operation of job i on machine j
Pij : processing time of Oij

Figure 1: Disjunctive graph G of a 3×3 problem
Scheduling defines the ordering between all
operations that must be processed on the samemachine, i.e. to fix precedences between operations. In the disjunctive graph model, this isdone by turning all undirected (disjunctive) arcs
into directed ones. The set of all directed arcs
selected from disjunctive arcs is called a selection.
A selection S defines a feasible schedule if andonly if the resulting directed graph is acyclic.
In such a case, S is called a complete selection.
A complete selection and its corresponding feasible schedule can be used interchangeably andrepresented by the same symbol S.
Makespan is given by the length of the longest
weighted path from source to sink in this graph.
This path P is called the critical path and iscomposed of a sequence of critical operations.
A sequence of consecutive critical operations on
the same machine is called a critical block.
The distance between two schedules S and T
can be measured by the number of differences in
the processing order of operations on each machine [7]. In other words, it can be calculated bysumming the disjunctive arcs whose directions
are different between S and T . We call this distance the disjunctive graph (DG) distance.

The general n×m minimum-makespan jobshop scheduling problem can be described by aset of n jobs that is to be processed on a setof m machines. Each job follows a technologicalsequence of the machines in processing. Each operation requires the exclusive use of one machine
for an uninterrupted duration called processing
time. The time required to complete all jobs iscalled makespan. The objective when solving or
optimizing this general problem is to determine
the processing order of each machine’s operations that minimizes the makespan.
Job-shop scheduling problems are often described by a disjunctive graph G = (V, C ∪ D), A. Active schedules
where
A schedule’s makespan may often be reduced• V is a set of nodes representing the operations by shifting an operation to the left without deof all jobs together with two special nodes, a laying other jobs. When no such shifting can besource (0) and a sink ?, representing the begin- applied to a schedule, it is called an active schedning and the end of the schedule, respectively. ule. An optimal schedule is clearly active, so it• C is a set of conjunctive arcs representing the is safe and efficient to limit search space to thetechnological sequences of operations.
set of all active schedules. An active schedule is• D is a set of disjunctive arcs representing pairs generated by the GT algorithm proposed in [5].

An extension of the CB neighborhood using the B. GA/MSXF for Job-shop Scheduling
GT algorithm is proposed in [13], which is called
The MSXF is applied to JSSP by using thethe active CB neighborhood. It was experimenactive CB neighborhood and the DG distancetally shown in [14] that SA using the active CB
previously defined. Algorithm 3 describes theneighborhood is very robust.
outline of the GA/MSXF routine for JSSP using the steady state model proposed in [11, 9].
To avoid premature convergence even under asmall-population condition, an individual whose
Algorithm 3 GA/MSXF for JSSP
fitness value is equal to someone in the popula• Initialize population: randomly generate a settion is not inserted into the population in stepof left and right active schedules in equal num4.
ber and apply the local search to each of them.
A mechanism to search in the space of both
do 1. Randomly select two schedules p1 , p2 fromleft
and right active schedules is introduced in
the population with some bias depending on
the
GA/MSXF
as follows. First, there are equal
their makespan values.
numbersofleft
and right active schedules in
2. Change the direction (left or right) of p1 by
theinitialpopulation.
The schedule q generreversing the job sequences with probability
ated
from
p
and
p
by
MSXF
ought to be left
1
2
Pr .
is
left
(or
right) active,(orright)
activeifp1
3. Do step (3a) with probability Pc , or otherbut
with
some
probability(0.1
forexample)thiswise do step (3b).
propertyisreversed.
(a) If the DG distance between p , p is1

2

shorter than some predefined smallvalue, apply MSMF to p1 and generate q.
Otherwise, apply MSXF to p1 , p2 using the active CB neighborhood N (p1 )and the DG distance and generate a
new schedule q.
(b) apply Algorithm 1 with accepting probability given by Equation 2 and active
CB neighborhood.
4. If q’s makespan is shorter than the worst in
the population, and no one in the population has the same fitness value as q, replace
the worst individual with q.
until some termination condition is satisfied.
• Output the best schedule in the population.

A given problem of JSSP can be converted toanother problem by reversing all the technological sequences. The new problem is equivalent
to the old one in the sense that reversing thejob sequences of any feasible solution from theoriginal problem results in a feasible solution for
the reversed problem with the same critical pathand makespan. It can be seen, however, that an
active schedule from the original problem is notnecessarily active in the reversed problem. wecall a schedule left active if it is an active schedule for the original problem and right active if it
is an active schedule for the reversed problem.
Searching only in the set of left (or right) active
schedules may bias the search toward the wrong
direction and result in poor local minima.

IV. Experimental Results
The performance of GA/MSXF was tested
by running several simulation trials using
well-known benchmark problems of Muth andThompson (MT)[6].
Table 1 summarizes the makespan performance of the GA/MSXF method together witha simulated annealing method using the CBneighborhood structure (CBSA) [15], and performances of other GA methods publishedso far in the literature for MT10×10 and
MT20×5 problems. The GA methods include
GA/GT+ECO [2], PGA+SBP [3], GVOT [4]and GA/MSX[13]. For GA/MSXF, population
size = 10, constant temperature c = 10 andnumber of iterations for each MSXF = 1000,
Pr = 0.1 and Pc = 0.5 are used. The GA/MSXF
experiments were performed on a DEC Alpha
600 5/226 which is about four times faster thana Sparc Station 10, and the programs were written in C language. It should be noted that all of
the GA/MSXF experiments successfully foundoptimal solutions in about one and a half minutes for each problem.
Figure 2 shows all of the solutions (in small
dots) generated by an application of (a) MSXF
and (b) a stochastic local search computationally equivalent to (a) for comparison. Both (a)and (b) started from the same solution (the same
parent p1 ), but in (a) transitions were biased
toward the other solution p2 . The x-axis represents the number of disjunctive arcs whose directions are different from those of p2 on machineswith odd numbers, i.e. the DG distance wasTable 1: Performance comparisons using MT benchmark problems
Prob
MT10×10

MethodBest Avg
Var Pop cpu time machine
CBSA
930
930.8
2.4
44m36sSS2
GA/GT+ECO
930
963
14 20255m
SS2
Opt. 930
PGA+SBP
930
947
8.2
100
2.3m
SS10
GVOT
949
977
?
500
25m
SUN4
GA/MSX
930
934.5
5.1
500
11m39sSS10
GA/MSXF
930
930
0
10
3m44s
SS10
MT20×5
CBSA
1178 1178
038m18sSS2
GA/GT+ECO 1181 1213
16 504130m
SS2
Opt. 1165
PGA+SBP1165 1188
10.3
100
2.3m
SS10
GVOT
1189 1215
?
500
25m
SUN4
GA/MSX
1165 1177.3
4.2
100
10m54sSS10
GA/MSXF
1165 1165
0
10
55s
DECα
Pop: population size; cpu time: average cpu time; machine: machine used
for the experiments; runs: number of runs; SS2(SS10): SUN SPARC Station 2(10); DECα: DEC Alpha 600 5/266(a) Multi-Step Crossover Fusion

50(b) Stochastic Local Search

50

Best (957)
40

40

30

30

p1

20

p1

20

Start (961)Start (961)10Target (951)10Best (935)

Target (951)

p2

0
0

10

p2

0
20

30

40

50

60

runs
10
200
200
?
10
10
5
200
200
?
10
10

0

10

20

30

40

50

60

Figure 2: Distribution of solutions generated by
an application of (a) MSXF and (b) a short-term
stochastic local search

restricted to the odd machines. Similarly, the yaxis representing the DG distance was restricted
to the even machines.
Table 2 shows the makespan performancesof GA/MSXF for the ten difficult benchmark
JSSPs[1]. The parameters used here are thesame as those of the MT benchmark except for
population size = 20. The algorithm was terminated when an optimal solution was found orafter 40 minutes of cpu time on the DEC Alpha
600 5/266. In the table, the column named lb
shows the known lower bound or known optimalvalue (for la40) of makespan, and the columns
named bst, avg and wst show the best, average,
variance and worst makespan values obtained,
respectively. The columns named nopt and topt
show the number of runs in which the optimalschedules are obtained and their average cpu
times.
The optimal solutions were found for half ofthe ten problems, and four of them were foundvery quickly. The small variances in the solution
qualities indicate the stableness of GA/MSXF as
an approximation method.

Table 2: Results of 10 touch JSSPs
prob lb
bst avg var wst nopt topt
abz7 655
678 692.5 0.94 703 ––abz8 638
686 703.1 1.54 724 ––abz9 656
697 719.6 1.53 732 ––la21 – ? 1046 1049.9 0.57 1055 9 687.7?
935 938.8 0.34 941 4 864.1
la24 –?
977 979.6 0.40 984 9 765.6
la25 –
la27 – ? 1235 1253.6 1.56 1269 1 2364.75
la29 1130 1166 1181.9 1.31 1195 ––la38 – ? 1196 1198.4 0.71 1208 21 1051.3–
la40 ? 1222 1224 1227.9 0.43 1233 –V. Conclusion
The multi-step crossover fusion (MSXF) is
proposed as a unified operator of a local searchmethod and a recombination operator in GLS.
MSXF uses a neighborhood structure and a distance measure in the problem space. Startingfrom one parent, MSXF carries out a local neighborhood search with a limited number of iterations, where the search direction is navigated by
the other parent. MSXF searches for a good solution in the problem space by concentrating its
attention on the area between the parents.
We applied GA/MSXF to the job-shop
scheduling problem. Experiments using Muth
and Thompson’s benchmark demonstrated that
GA/MSXF outperforms other GA methods described in the literature. GA/MSXF could findnear-optimal solutions for ten difficult benchmark problems, including optimal solutions forfive problems.
Further research, including the application of
GA/MSXF to other kinds of combinatorial prob-

lems, is necessary to show the full capabilities of
MSXF.
References[1] D. Applegate and W. Cook. A computational study of the job-shop scheduling problem. ORSA J. on Comput., 3(2):149–156,
1991.
[2] Y. Davidor, T. Yamada, and R. Nakano.
The ecological framework II: Improving ga
performance at virtually zero cost. In 5th
ICGA, pages 171–176, 1993.
[3] H. Kopfer, D.C. Mattfeld and C. Bierwirth.
Control of parallel population dynamics bysocial-like behavior of ga-individuals. In 3rd
PPSN, 1994.
[4] P. Ross Fang, H.L. and D. Corne. A promising genetic algorithm approach to jobshop scheduling, rescheduling, and openshop scheduling problems. In 5th ICGA,
pages 375–382, 1993.
[5] B. Giffler and G.L. Thompson. Algorithms
for solving production scheduling problems.
Oper. Res., 8:487–503, 1960.
[6] J.F. Muth and G.L. Thompson. Industrial
Scheduling. Prentice-Hall, Englewood Cliffs,
N.J., 1963.
[7] R. Nakano and T. Yamada. Conventional
genetic algorithm for job shop problems. In
4th ICGA, pages 474–479, 1991.
[8] C. R. Reeves. Genetic algorithms and neighbourhood search. In Evolutionary Computing, AISB Workshop (Leeds, U.K.), pages
115–130, 1994.
[9] G. Syswerda. Uniform crossover in genetic
algorithms. In 3rd ICGA, pages 2–9, 1989.
[10] N.L.J. Ulder, E. Pesch, P.J.M. van
Laarhoven, J. Bandelt, H, and E.H.L. Aarts.
Genetic local search algorithm for the traveling salesman problem. In 1st PPSN, pages
109–116, 1994.
[11] D. Whitley. The genitor algorithm and selection pressure: why rank-based allocationof reproductive trials is best. In 3rd ICGA,
pages 116–121, 1989.
[12] T. Yamada and R. Nakano. A genetic algorithm applicable to large-scale job-shop
problems. In 2nd PPSN, pages 281–290,
1992.
[13] T. Yamada and R. Nakano. A genetic algorithm with multi-step crossover for job-shop
scheduling problems. In Proc. of Int. Conf.
on GAs in Eng. Sys. (GALESIA) ’95, pages
146–151, 1995.
[14] T. Yamada and R. Nakano.
Job-Shop
Scheduling by Simulated Annealing Com-

bined with Deterministic Local Search.
Kluwer academic publishers, MA, USA,1996.
[15] T. Yamada, B.E. Rosen, and R. Nakano. A
simulated annealing approach to job shop
scheduling using critical block transition operators. In Proc. IEEE Int. Conf. on Neural
Networks (Orlando, Florida.), pages 4687–
4692, 1994.