Proceedings of Modern Heuristic for Decision Support, pp. 67–81,UNICOM seminar,
18–19 March 1997,London

Genetic Algorithms for Job-Shop
Scheduling Problems
Takeshi Yamada and Ryohei Nakano
NTT Communication Science Labs.
2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02 JAPANE-mail: {yamada,nakano}@cslab.kecl.ntt.co.jp

1

Introduction

The n×m minimum-makespan general job-shop scheduling problem, hereafter referred toas the JSSP, can be described by a set of n jobs {Ji }1≤j≤n which is to be processed on aset of m machines {Mr }1≤r≤m . Each job has a technological sequence of machines to beprocessed. The processing of job Jj on machine Mr is called the operation Ojr . Operation
Ojr requires the exclusive use of Mr for an uninterrupted duration pjr , its processing time.
A schedule is a set of completion times for each operation {cjr }1≤j≤n,1≤r≤m that satisfies
those constraints. The time required to complete all the jobs is called the makespanL. The objective when solving or optimizing this general problem is to determine theschedule which minimizes L. An example of a 3 × 3 JSSP is given in Table 1. The data
includes the routing of each job through each machine and the processing time for each
operation (in parentheses). Figure 1 shows a solution for the problem represented by“Gantt-Chart”.

job
1
2
3

Table 1: A 3 × 3 problem
Operations routing (processing time)
1 (3)
2 (3)
3 (3)
1 (2)
3 (3)
2 (4)
2 (3)
1 (2)
3 (1)

The JSSP is not only N P-hard , but it is one of the worst members in the class. An
indication of this is given by the fact that one 10 × 10 problem formulated by Muth andThompson [15] remained unsolved for over 20 years.

1.1

Disjunctive graph

The JSSP can be described by a disjunctive graph G = (V, C ∪ D), where (1) V is a setof nodes representing operations of the jobs together with two special nodes, a source (0)and a sink ?, representing the beginning and end of the schedule, respectively. (2) C isa set of conjunctive arcs representing technological sequences of the operations. (3) D is
1

,
,
,,
,, ,,
,,
,,
,,
,,,,,,,,,
,,,,
,,,,
,,,
,,,,,

M1

J1

J2

J3

M2

J3

J1

J2

,,,

J2

M3

0

2

4

6

J1

8

J3

10

12 timeFigure 1: A Gantt-Chart representation of a solution for a 3 × 3 problem
a set of disjunctive arcs representing pairs of operations that must be performed on thesame machines. The processing time for each operation is the weighted value attached tothe corresponding nodes. Figure 2 shows this in a graph representation for the problem
given in Table 1.
conjunctive arc (technological sequences)disjunctive arc (pair of operations on the same machine)

sourcep11= 3O11
p21 = 4

0

O21

O32
p32= 3p12= 3O12
p23= 3O23

O31
p31= 2

p13 = 3O13

sink

p22 = 2O22*

O33
p33= 1

Oij : an operation of job i on machine jp ij : processing time of Oij

Figure 2: A disjunctive graph of a 3 × 3 problem
Job-shop scheduling can also be viewed as defining the ordering between all operations
that must be processed on the same machine, i.e. to fix precedences between these operations. In the disjunctive graph model, this is done by turning all undirected (disjunctive)arcs into directed ones. A selection is a set of directed arcs selected from disjunctive arcs.
By definition, a selection is complete if all the disjunctions are selected. It is consistent if
the resulting directed graph is acyclic.

1.2

Semi-active schedules

A schedule uniquely obtained from a consistent complete selection by sequencing operations as early as possible is called a semi-active schedule. In a semi-active schedule, nooperation can be started earlier without altering the machining sequences. A consistentcomplete selection and the corresponding semi-active schedule can be represented by thesame symbol S without confusion. The makespan L is given by the length of the longest
weighted path from source to sink in this graph. This path P is called a critical pathalgorithm 1

GT algorithm

1. Let D be a set of all the earliest operations in a technological sequence not yetscheduled and Ojr be an operation with the minimum EC in D: Ojr = arg min{O ∈D | EC(O)}.
2. Assume i−1 operations have been scheduled on Mr . A conflict set C[Mr , i] is defined
as: C[Mr , i] = {Okr ∈ D | Okr on Mr , ES(Okr ) < EC(Ojr )}.
3. Select an operation O ∈ C[Mr , i] arbitrary.
4. Schedule O as the i-th operation on Mr with its completion time equal to EC(O).

and is composed of a sequence of critical operations. A sequence of consecutive criticaloperations on the same machine is called a critical block.
The distance between two schedules S and T can be measured by the number ofdifferences in the processing order of operations on each machine [16]. In other words, it
can be calculated by summing the disjunctive arcs whose directions are different between
S and T . We call this distance the disjunctive graph (DG) distance. Figure 3 shows the
DG distance between two schedules. The two disjunctive arcs drawn by thick lines inschedule (b) have directions that differ from those of schedule (a), and therefore the DG
distance between (a) and (b) is 2.
O11

(a)
0

O12

O22

O23

O21

O32

O31

(b)

O13

O33

*

0

O11

O12

O13

O22

O23

O21

O32

O31

*

O33

DG distance = 2
Figure 3: The DG distance between two schedules

1.3

Active schedules

The makespan of a semi-active schedule may often be reduced by shifting an operation
to the left without delaying other jobs. Such reassigning is called a permissible left shift
and a schedule with no more permissible left shifts is called an active schedule. An
optimal schedule is always active so the search space can be safely limited to the setof all active schedules. An active schedule is generated by the GT algorithm proposedby Giffler and Thompson [12], which is described in Algorithm 1. In the algorithm,
the earliest starting time ES(O) and earliest completion time EC(O) of an operation O
denote its starting and completion times when processed with the highest priority among
all currently schedulable operations on the same machine. An active schedule is obtainedby repeating the algorithm until all operations are processed. In Step 3, if all possible
choices are considered, all active schedules will be generated, but the total number will
still be very large.

2

Simple GAs with binary representation

As described in the previous section, a (semi-active) schedule is obtained by turning
all undirected disjunctive arcs into directed ones. Therefore, by labeling each directeddisjunctive arc of a schedule as 0 or 1 according to its direction, a schedule can be
represented by a binary string of length mn(n − 1)/2. Figure 4 shows a labeling example,
where an arc connecting Oij and Okj (i < k) is labeled as 1 if the arc is directed from Oij
to Okj (so Oij is processed prior to Okj ) or 0, otherwise. It should be noted that the DG
distance between schedules and the Hamming distance between the corresponding binary
strings can be identified through this binary mapping.
O11

O12

1 1
0

O21

1

O23

1
0
O32

0

0

O13

1
O22

1

O31

*

O33

Figure 4: Labeling disjunctive arcs
A conventional GA using this binary representation was proposed by Nakano and
Yamada [16]. An advantage of this approach is that conventional genetic operators,
such as 1-point, 2-point and uniform crossovers can be applied without any modification.
However, a resulting new bit string generated by crossover may not represent a scheduleand called illegal.
A repairing procedure that generates a feasible bit string, as similar to an illegal
one as possible, is called the harmonization algorithm [16]. The Hamming distance isused to assess the similarity between two bit strings. The harmonization algorithm goes
through two phases: local harmonization and global harmonization. The former removes
the ordering inconsistencies within each machine, while the latter removes the orderinginconsistencies between machines. An original (possibly illegal) bit string can be considered as a genotype, and a repaired feasible one as a phenotype and only used for thefitness evaluation.
The replacement of the original string with a repaired feasible one is called Forcing,which can be considered as the inheritance of an acquired character, although it is notwidely believed that such inheritance occurs in nature. Since frequent forcing may destroy
whatever potential and diversity of the population, it is limited to a small number of elites.
Such limited forcing brings about at least two merits: a significant improvement in theconvergence speed and the solution quality. Experiments have shown how it works [16].

3Permutation representation

The JSSP can be viewed as an ordering problem just like the Traveling Salesman Problem(TSP). For example, a schedule can be represented by the set of permutations of jobs oneach machine, in other words, m-partitioned permutations of operation numbers, whichis called a job sequence matrix. Table 5 shows a job sequence matrix of the same solution
as that given in Figure 1. The advantage of this representation is that the GA operators

used to solve the TSP can be applied without further modifications, because each job
sequence is equivalent to the path representation in the TSP.

1

M1
2 3

3

M2
1 2

M3
2 1 3

Figure 5: A job sequence matrix for a 3 × 3 problem

3.1

Subsequence exchange crossover

The Subsequence Exchange Crossover (SXX) was proposed by Kobayashi, Ono and Yamamura [14]. The SXX is a natural extension of the subtour exchange crossover for
TSPs presented by the same authors [13]. Let two job sequence matrices be p0 and p1 . A
pair of subsequences, one from p0 and the other from p1 on the same machine, is calledexchangeable if and only if they consist of the same set of jobs. The SXX searches forexchangeable subsequence pairs in p0 and p1 on each machine and interchanges each pair
to produce new job sequence matrices k0 and k1 . Figure 6 shows an example of the SXX
for a 6 × 3 problem. Because a valid job sequence matrix does not necessarily representa (valid) schedule, some repairing mechanism is also required. A small number of swap
operations designated by the GT algorithm are applied to repair a job sequence matrix.
M1

M2

M3

p0 123456 321564 235614
p1 621345 326451 635421
k0 213456 325164 263514
k1 612345 326415 356421
Figure 6: Subsequence Exchange Crossover (SXX)

3.2

Permutation with repetition

Instead of using an m-partitioned permutation of operation numbers like the job sequencematrix, another representation that uses an unpartitioned permutation with m-repetitionsof job numbers was employed by Bierwirth [6]. In this permutation, each job number
occurs m times. By scanning the permutation from left to right the k-th occurrenceof a job number refers to the k-th operation in the technological sequence of this job(see Figure 7). In this representation, any individual is decoded to a schedule without
repairing it, but still two or more different individuals can be decoded to an identicalschedule.
The well used Order Crossover and Partially Mapped Crossover for TSP are naturally
extended for this representation. A new Precedence Preservative Crossover (PPX) isalso proposed in [7]. The PPX perfectly respects the absolute order of genes in parental
chromosomes. A template bit string h of length mn is used to define the order in whichA job permutation
is decodedtoa schedule

1 3 2 1 3 2 2 1 3

M1 1
M2
M3

2
3

3
1

2
2

1 3

Figure 7: A job sequence (permutation with repetition) for a 3 × 3 problem is decoded
to a schedule, which is equivalent to the one in Figure 1.
genes are drawn from p0 and p1 . A gene is drawn from one parent and it is appended
to the offspring chromosome. The corresponding gene is deleted in the other parent(See Figure 8). This step is repeated until both parent chromosomes are empty andthe offspring contains all genes involved. The idea of forcing described in Section 2 iscombined with the permissible left shift described in Subsection 1.3: new chromosomes
are modified to active schedules by applying permissible left shifts.
p0 3 2 2 2 3 1 1 1 3h

0 0 1 1 1 1 0 0 0

p1 1 1 3 2 2 1 2 3 3k

3 2 1 1 2 1 2 3 3Figure 8: Precedence Preservative Crossover (PPX)

4

Heuristic crossover using an active schedule builder

The GT crossover proposed by Yamada and Nakano [24] is a problem dependent crossover
operator that directly utilizes the GT algorithm. In the crossover, parents cooperatively
give a series of decisions to the algorithm to build new offspring, namely active schedules.
An individual represents an active schedule, so there is no repairing scheme required.
Let H be a binary matrix of size n × m [24, 8]. Here Hir = 0 means that the i-th
operation on machine r should be determined by using the first parent and Hir = 1
by the second parent. The role of Hir is similar to that of h described in Section 3.2.
Let the parent schedules be p0 and p1 as always. The GT crossover can be defined bymodifying Step 3 of Algorithm 1 as shown in Algorithm 2. It tries to reflect the processingorder of the parent schedules to their offspring. It should be noted that if the parents
are identical to each other, the resulting new schedule is also identical to the parents’.
In general the new schedule inherits partial job sequences of both parents in different
ratios depending on the number of 0’s and 1’s contained in H. Mutation can be put in
Algorithm 2 by occasionally selecting the n-th (n > 1) earliest operation in C[Mr∗ , i] witha low probability inversely proportional to n in Step 3 of Algorithm 2.
The GT crossover generates only one schedule at once. Another schedule is generated
by using the same H but changing the roles of p0 and p1 . Thus two new schedules are
generated that complement each other. The outline of the GT crossover is described in
Figure 9.

algorithm 2

GT crossover

1. Same as Step 1. of Algorithm 1.
2. Same as Step 2. of Algorithm 1.
3. Select one of the parent schedules {p0 , p1 } according to the value of Hir as p = pHir .
Select O ∈ C[Mr , i] that has been the earliest scheduled operation in C[Mr , i] in p.
4. Same as Step 4. of Algorithm 1.

P0

Kid

,,,

1
2

earliest

Conflict

1

3
4
5
6

3

7

4

P1

Selected

,,,,
,,,,

5

6

Figure 9: GT crossover

5

Genetic enumeration

Genetic enumeration methods which utilize simple representations and operators, and at
the same time incorporate problem specific heuristics were proposed by Dorndorf andPesch [19, 11] . They interpret an individual solution as a sequence of decision rules fordomain specific heuristics such as the GT algorithm and the shifting bottleneck procedure.

5.1

Priority rule based GA

Priority rules [18] are the most popular and simplest heuristics for solving the JSSP. They
are rules used in Step 3 of Algorithm 1 to resolve a conflict by selecting an operation O
from the conflict set C[Mr , i]. For example, a priority rule called “SOT-rule” (shortest
operation time rule) selects the operation with the shortest processing time from theconflict set.
Each individual of the priority rule based GA (P-GA) [11, 19] is a string of lengthmn − 1, where the entry in the i-th position represents one of the twelve priority rules
to be used in the i-th iteration of the GT algorithm. The twelve rules are selected suchthat they are partially complementary in order to select each member in the conflict set.
A simple crossover that exchanges the substrings of two cut strings are applied.

5.2

Shifting bottleneck based GA

The Shifting bottleneck (SB) proposed by Adams et al. [2] is a powerful heuristic forsolving the JSSP. In the method, a one-machine scheduling problem (a relaxation of theoriginal JSSP) is solved for each machine not yet sequenced, and the outcome is used
to find a bottleneck machine; a machine having the longest makespan. Every time a
new machine has been sequenced, the sequence of each previously sequenced machine
is subject to reoptimization. The SB consists of two subroutines: the first one (SB I)
repeatedly solves one-machine scheduling problems; the second one (SB II) builds a partial
enumeration tree where each path from the root to a leaf is similar to an application of
SB I. Please refer to [2, 3, 27] as well as [11, 19] for more details.
The shifting bottleneck based genetic algorithm (SB-GA) [11, 19] controls the selectionof nodes in the enumeration tree of the shifting bottleneck heuristic. Here an individual
is represented by a permutation of machine numbers 1 . . . m, where the entry in the i-th
position represents the machine selected in SB I. A cycle crossover operator is used as
the crossover for this permutation representation.

6

Genetic local search and multi-step crossover fusion

It is well known that GAs can be enhanced by incorporating local search methods, suchas neighborhood search into themselves. The result of such an incorporation is often
referred as Genetic Local Search (GLS) [22]. In this framework, an offspring obtainedby a recombination operator, such as crossover, is not included in the next generation
directly but is used as a “seed” for the subsequent local search. The local search moves
the offspring from its initial point to the nearest locally optimal point, which is includedin the next generation. Mattfeld proposed an efficient GLS method called Difusion GA
for JSSP with good success[9].

6.1Neighborhood search crossover

Reeves has been exploring the possibility of integrating local optimization directly intoa Simple GA with bit string representations and has proposed the Neighborhood Search
Crossover (NSX) [20]. Let any two individuals be x and z. An individual y is calledintermediate between x and z, written as x  y  z, if and only if d(x, z) = d(x, y) + d(y, z)
holds, where x, y and z are represented in binary strings and d(x, y) is the Hamming
distance between x and y. Then the k th -order 2 neighborhood of x and z is defined as
the set of all intermediate individuals at a Hamming distance of k from either x or z.
Formally,
Nk (x, z) = {y | x  y  z and (d(x, y) = k or d(y, z) = k)}.
Given two parent bit strings p0 and p1 , the neighborhood search crossover of order k(NSXk ) will examine all individuals in Nk (p0 , p1 ), and pick the best as the new offspring.

6.2

Multi-step crossover fusion

Yamada and Nakano extended the idea of the NSX to make it applicable to more complicated problems such as job-shop scheduling and proposed the Multi-Step Crossover Fusion

algorithm 3 Multi-Step Crossover Fusion (MSXF)• Let p0 , p1 be parent solutions.
• Set x = p0 = q.
do

• For each member yi ∈ N(x), calculate d(yi, p1 ).
• Sort yi ∈ N(x) in ascending order of d(yi , p1 ).
do

1. Select yi from N(x) randomly, but with 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, and the indexes 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.

(MSXF): a new crossover operator with a built-in local search functionality [25, 28, 26].
The MSXF has the following characteristics compared to the NSX.
• It can handle more generalized representations and neighborhood structures.
• It is based on a stochastic local search algorithm.
• Instead of restricting the neighborhood by a condition of intermediateness, a biased
stochastic replacement is used.
A stochastic local search algorithm is used for the base algorithm of the MSXF.
Although the SA is a well-known stochastic method and has been successfully applied tomany problems as well as to the JSSP, it would be unrealistic to apply the full SA tosuit our purpose because it would consume too much time by being run many times ina GA run. A restricted method with a fixed temperature parameter is used as a goodalternative in MSXF.
Let the parent schedules be p0 and p1 , the neighborhood of an individual x be N(x)and the distance between any two individuals x and y in any representation be d(x, y).
If x and y are schedules, then d(x, y) is the DG distance. Crossover functionality can beincorporated into a local search algorithm by setting initial point: x0 = p0 and adding
a greater acceptance bias in favor of y ∈ N(x) having a small d(y, p1). The acceptancebias in the MSXF is controlled by sorting N(x) members in ascending order of d(yi, p1 )so that yi with a smaller index i has a smaller distance d(yi, p1 ). Here d(yi , p1 ) can be
estimated easily if d(x, p1 ) and the direction of the transition from x to yi are known; it
is not necessary to generate and evaluate yi. Then yi is selected from N(x) randomly,but with a bias in favor of yi with a small index i. The outline of the MSXF is describedin Algorithm 3.
In place of d(yi , p1 ), one can also use sign(d(yi, p1 )−d(x, p1 ))+r to sort N(x) members
in Algorithm 3. Here sign(x) denotes the sign of x: sign(x) = 1 if x > 0, sign(x) = 0
if x = 0, sign(x) = −1 otherwise. A small random fraction r is added to randomize
the order of members with the same sign. The termination condition can be given, forexample, as the fixed number of iterations in the outer loop.
The MSXF is not applicable if the distance between p0 and p1 is too small comparedto the number of iterations. In such a case, a mutation operator called the Multi-Step
Mutation Fusion (MSMF) is applied instead. The MSMF can be defined in the samemanner as the MSXF is except for one point: the bias is reversed, i.e. sort the N(x)members in descending order of d(yi, p1 ) in Algorithm 3.

6.3

MSXF-GA for Job-shop Scheduling

The MSXF is applied to the JSSP by using the active CB neighborhood [27] and the DG
distance previously defined. Algorithm 4 describes the outline of the MSXF-GA routine
for the JSSP using the steady state model proposed in [23, 21]. To avoid premature
convergence even under a small-population condition, an individual whose fitness value
is equal to someone’s in the population is not inserted into the population in Step 4.
The idea of schedule reversal and left/right active schedules are introduced in [28]. A
schedule is called left active if it is an active schedule for the original problem and rightactive if it is such for the reversed problem. A mechanism to search in the space of boththe left and right active schedules is introduced into the MSXF-GA as follows. First,
there are equal numbers of left and right active schedules in the initial population. The
schedule q generated from p0 and p1 by the MSXF ought to be left (or right) active if
p0 is left (or right) active, and with some probability (0.1 for example) the direction isreversed.
Figure 10 shows all of the solutions generated by an application of (a) the 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 p0 ), but in (a) transitions werebiased toward the other solution p1 . The x axis represents the number of disjunctive arcs
whose directions are different from those of p1 on machines with odd numbers, i.e. the
DG distance was restricted to odd machines. Similarly, the y axis representing the DG
distance was restricted to even machines.
(a) Multi-Step Crossover Fusion

50(b) Stochastic Local Search

50

Best (957)
40

40

30

30

20

P0
Start (961)10Target (951)
P1

0
0

10

20

P0
Start (961)10Best (935)

Target (951)
P1

0
20

30

40

50

60

0

10

20

30

40

50

60

Figure 10: Distribution of solutions generated by an application of (a) MSXF and (b) ashort-term stochastic local searchalgorithm 4 MSXF-GA for the JSSP
• Initialize population: randomly generate a set of left and right active schedules in equal
number and apply the local search to each of them.
do

1. Randomly select two schedules p0 , p1 from the population with some bias depending on their makespan values.
2. Change the direction (left or right) of p1 by reversing the job sequences withprobability Pr .
3. Do step (3a) with probability Pc , or otherwise do Step (3b).
(a) If the DG distance between p1 , p2 is shorter than some predefined smallvalue, apply MSMF to p1 and generate q.
Otherwise, apply MSXF to p1 , p2 using the active CB neighborhoodN(p1 ) and the DG distance and generate a new schedule q.
(b) Apply a short term stochastic local search using the 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 makespan as q, replace the worst individual with q.

until some termination condition is satisfied.
• Output the best schedule in the population.

7

Experimental results using benchmark problems

The two well-known benchmark problems with sizes of 10 × 10 and 20 × 5 (known as
mt10 and mt20) formulated by Muth and Thompson [15] are commonly used as test beds
to measure the effectiveness of a certain method. The mt10 problem used to be called
a “notorious” problem, because it remained unsolved for over 20 years; however it is nolonger a computational challenge.
Applegate and Cook proposed a set of benchmark problems called the “ten toughproblems” as a more difficult computational challenge than the mt10 problem, by collecting difficult problems from literature, some of which still remain unsolved [4].

7.1

Muth and Thompson benchmark

Table 2 summarizes the makespan performance of the methods described in this paper.
This table is partially cited from [6]. The Conventional GA has only limited success andis outdated. It would be improved by being combined with the GT algorithm and/or theschedule reversal. The other results excluding the MSXF-GA results are somewhat similar
to each other, although the SXX-GA is improved over the GT-GA in terms of speed andthe number of times needed to find optimal solutions for the mt10 problem. The SB-GA
produces better results using the very efficient and tailored shifting bottleneck procedure.
The MSXF-GA which combines a GA and local search obtains the best results.
For the MSXF-GA, the population size = 10, constant temperature c = 10, numberof iterations for each MSXF = 1000, Pr = 0.1 and Pc = 0.5 are used. The MSXF-GA
experiments were performed on a DEC Alpha 600 5/226 and the programs were written

Table 2: Performance comparison using the MT benchmark problems
1963
1991
1992

1994
1995
1995
1996

Muth-Thompson
Nakano/Yamada
Yamada/Nakano
Dorndorf/Pesch
Dorndorf/Pesch
Mattfeld/Kopfer
Kobayashi/Ono/Yamamura
Bierwirth
Yamada/Nakano

Test problems
Conventional GA[16]Giffler-Thompson GT-GA[24]Priority-Rule based P-GA[19, 11]
Shifting-Bottleneck SB-GA[19, 11]Diffusion GA [9]Subsequence Exchange Crossover
SXX-GA[14]Generalized-Permutation GP-GA[6]Multi-step Crossover Fusion MSXF-GA[28, 26]

10 × 10
965
930
960
938
930
930

20 × 5
1215
1184
1249
1178
1165
1178

936
930

1181
1165

in the C language. The MSXF-GA finds the optimal solutions for the mt10 and mt20
problems almost every time in less than five minutes on average.

7.2

The ten tough benchmark problems

Table 3 shows the makespan performance statistics of the MSXF-GA for the ten difficult
benchmark problems proposed in [4]. The parameters used here were the same as thosefor the MT benchmark except for the population size = 20. The algorithm was terminatedwhen an optimal solution was found or after 40 minutes of cpu time passed on the DEC
Alpha 600 5/266. In the table, the column named lb shows the known lower bound or
known optimal value (for la40) of the makespan, and the columns named bst, avg, var
and wst show the best, average, variance and worst makespan values obtained, over 30
runs respectively. The columns named nopt and topt show the number of runs in which the
optimal schedules are obtained and their average cpu times in seconds. The problem data
and lower bounds are taken from the OR-library [5]. Optimal solutions were found for halfof the ten problems, and four of them were found very quickly. The small variances in thesolution qualities indicate the stability of the MSXF-GA as an approximation method.
Table 4 shows comparison with various heuristic methods. In the table, MSXF represents MSXF-GA method proposed in[28, 26], Nowi and Dell are tabu search methods
proposed in [17] and [10] respectively, CBSA and Aarts are SA methods in [27] and [1].
Matt is the diffusion GA in [9], and Appl is from [4].

8Conclusions

The first serious application of GAs to solve the JSSP was proposed by Nakano and
Yamada using a bit string representation and conventional genetic operators. Although
this approach is simple and straightforward, it is not very powerful. The idea to use theGT algorithm as a basic schedule builder was first proposed by Yamada and Nakano [24]and by Dorndorf and Pesch [11, 19] independently. The approaches by both groups andother active schedule-based GAs are suitable for middle-size problems; however, it seems
necessary to combine each with other heuristics such as the shifting bottleneck or local
search to solve larger-size problems.
To solve larger-size problems effectively, it was crucial to incorporate local search

Table 3: Results of the 10 tough problems
prob sizelb
bst avg var wst nopt topt
abz7 20×15 655
678 692.5 0.94 703 ––abz8 20×15 638
686 703.1 1.54 724 ––abz9 20×15 656
697 719.6 1.53 732 ––?
la21 15×10 –1046 1049.9 0.57 1055 9
687.7?
la24 15×10 –935 938.8 0.34 941 4
864.1?
la25 20×10 –977 979.6 0.40 984 9765.6?
la27 20×10 –1235 1253.6 1.56 1269 1 2364.75
la29 20×10 1130 1166 1181.9 1.31 1195 ––?
la38 15×15 –1196 1198.4 0.71 1208 21 1051.3
la40 15×15 ? 1222 1224 1227.9 0.43 1233 ––Table 4: Comparison with various heuristic methods on the 10 tough problems
prob MSXF
abz7
678
abz8
686
abz9
697
la21 ? 1046
?
la24
935
?
la25
977
la27 ? 1235
la29
1166
?
la38
1196
la40
1224

Nowi
–
–
–
1047
939
?
977
1236
1160
?
1196
1229

Dell CBSA Aarts Matt
667
665
668
672
678
675
670
683
692
686
691
703
?
1048
1046 1053 1053?
941
935 ? 935
938
?
?
979
977
983
977
1242 ? 1235 1249 1236
1182
1154 1185 1184
1203
1198 1208 1201
1233
1228 1225 1228

Appl
668
687
707
1053
?
935
?
977
1269
1195
1209
?
1222

methods that use domain specific knowledge. The multi-step crossover fusion (MSXF)
was proposed by Yamada and Nakano as a unified operator of a local search method anda recombination operator in genetic local search. The MSXF-GA outperforms other GA
methods in terms of the MT benchmark and is able to find near-optimal solutions for theten difficult benchmark problems, including optimal solutions for five of them.

References[1] E.H.L. Aarts, P.J.M. van Laarhoven, J.K. Lenstra, and N.L.J. Ulder (1994). A
computational study of local search algorithms for job shop scheduling. ORSA J. on
Comput., 6(2):118–125.
[2] J. Adams, E. Balas, and D. Zawack (1988). The shifting bottleneck procedure forjob shop scheduling. Mgmt. Sci., 34(3):391–401.
[3] D. Applegate (1992). Jobshop benchmark problem set. Personal Communication.
[4] D. Applegate and W. Cook (1991). A computational study of the job-shop schedulingproblem. ORSA J. on Comput., 3(2):149–156.

[5] J.E. Beasley (1990). Or-library: distributing test problems by electronic mail. E. J.
of Oper. Res., 41:1069–1072.
[6] C. Bierwirth (1995). A generalized permutation approach to job shop schedulingwith genetic algorithms. OR Spektrum, 17:87–92.
[7] C. Bierwirth, D. Mattfeld, and H. Kopfer (1996). On permutation representations
for scheduling problems. In 4th PPSN, pages 310–318.
[8] Y. Davidor, T. Yamada, and R. Nakano (1993). The ecological framework II: Improving GA performance at virtually zero cost. In 5th ICGA, pages 171–176.
[9] H. Kopfer D.C. Mattfeld and C. Bierwirth (1994). Control of parallel population
dynamics by social-like behavior of GA-individuals. In 3rd PPSN.
[10] M. Dell’Amico and M. Trubian (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41:231–252.
[11] U. Dorndorf and E. Pesch (1995). Evolution based learning in a job shop schedulingenvironment. Computers Ops Res, 22:25–40.
[12] B. Giffler and G.L. Thompson (1960). Algorithms for solving production schedulingproblems. Oper. Res., 8:487–503.
[13] M. Kobayashi, T. Ono, and S. Kobayashi (1992). Character-preserving genetic algorithms for traveling salesman problem (in japanese). Journal of Japanese Society
for Artificial Intelligence, 7:1049–1059.
[14] S. Kobayashi, I. Ono, and M. Yamamura (1995). An efficient genetic algorithm forjob shop scheduling problems. In 6th ICGA, pages 506–511.
[15] J.F. Muth and G.L. Thompson (1963). Industrial Scheduling. Prentice-Hall, Englewood Cliffs, N.J..
[16] R. Nakano and T. Yamada (1991). Conventional genetic algorithm for job shop
problems. In 4th ICGA, pages 474–479.
[17] E. Nowicki and C. Smutnicki (1993). A fast taboo search algorithm for the job shop
problem. Institute of Engineering Cybernetics, Technical University of Wroclaw,
Wroclaw, Poland., Preprinty nr 8/93.
[18] S. S. Panwalkar and Wafix Iskander (1977). A survey of scheduling rules. Oper. Res.,25(1):45–61.
[19] E. Pesch (1994). Learning in Automated manufacturing: a local search approach.
Physica-Verlag, Heidelberg, Germany.
[20] C. R. Reeves (1994). Genetic algorithms and neighbourhood search. In Evolutionary
Computing, AISB Workshop (Leeds, U.K.), pages 115–130.
[21] G. Syswerda (1989). Uniform crossover in genetic algorithms. In 3rd ICGA, pages
2–9.

[22] N.L.J. Ulder, E. Pesch, P.J.M. van Laarhoven, J. Bandelt, H, and E.H.L. Aarts(1994). Genetic local search algorithm for the traveling salesman problem. In 1st
PPSN, pages 109–116.
[23] D. Whitley (1989). The genitor algorithm and selection pressure: why rank-based
allocation of reproductive trials is best. In 3rd ICGA, pages 116–121.
[24] T. Yamada and R. Nakano (1992). A genetic algorithm applicable to large-scale
job-shop problems. In 2nd PPSN, pages 281–290.
[25] T. Yamada and R. Nakano (1995). A genetic algorithm with multi-step crossover forjob-shop scheduling problems. In GALESIA ’95, pages 146–151.
[26] T. Yamada and R. Nakano (1996). A fusion of crossover and local search. In IEEE
International Conference on Industrial Technology (ICIT ’96).
[27] T. Yamada and R. Nakano (1996). Job-Shop Scheduling by Simulated Annealing
Combined with Deterministic Local Search. pages 237–248, Kluwer academic publishers, MA, USA.
[28] T. Yamada and R. Nakano (1996). Scheduling by genetic local search with multi-stepcrossover. In 4th PPSN, pages 960–969.