A pruning pattern list approach to the permutation flowshop
scheduling problem
Takeshi Yamada
NTT Communication Science Laboratories,
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02, JAPANE-mail : yamada@cslab.kecl.ntt.co.jp
Abstract
This paper investigates an approach to the permutation flowshop scheduling problem basedon Tabu Search with an additional memory structure called a ‘pruning pattern list’. The
pruning pattern list approach allows a better use of the critical block information. A solutionof the flowshop scheduling problem is represented by a permutation of job numbers. A pruning
pattern is generated from a solution by replacing job numbers inside a critical block with ‘wild
cards’ so that solutions that ‘match’ the pattern would be excluded from the search. A setof pruning patterns, which is called a ‘pruning pattern list’, is used to navigate the search by
avoiding solutions that would match any pattern on the list. Computational experiments using
benchmark problems demonstrate the effectiveness of the proposed approach.

1

Introduction

The scheduling problem investigated in this paper is called the permutation flowshop schedulingproblem (PFSP) and is conventionally designated as n/m/P/Cmax [1], where n jobs have to beprocessed on m machines in the same order. The processing of each job on each machine is anoperation, which requires the exclusive use of the machine for an uninterrupted duration called theprocessing time. P indicates that only the permutation schedules are considered, where the orderin which each machine processes the jobs is identical for all machines. Hence, a schedule is uniquely
represented by a permutation of jobs. The objective here is to find a schedule that minimizes the
makespan Cmax , the time at which the last job is completed on the last machine. The problem isstrongly N P-hard[1], therefore complete enumeration methods are not computationally practicalas the problem size increases. Approximation methods to solve the problem are categorized to two
types: one is constructive methods and another is iterative improvement methods. Constructive
methods have been proposed by Campbell et al.[2], Dannenbring[3] and Nawaz et al.[4]. As for
iterative improvement methods, Osman and Potts[8] and Ogbu and Smith[6] proposed simulated
annealing methods, and Widmer and Herz[7] and Taillard[10] proposed tabu search methods. Morerecently, Nowicki and Smutnicki proposed a very powerful approximation method based on tabu
search[5].
In this paper, an approximation method based on Tabu Search with an additional memory
structure called “pruning pattern list” is proposed. In short, the pruning pattern list approachallows a better use of the critical block information. A pruning pattern is constructed from asolution represented by a permutation of job numbers by replacing some of job numbers inside
a critical block by wild cards (?-s) so that solutions that ‘match’ the pattern will be excluded
from the search hereafter. This means that any modification of a solution, regardless of inside oroutside the critical block, is discouraged if the resulting sequence would match the pattern. A listof pruning patterns generated from good schedules collected in the course of a search process isused to prevent the search from visiting already searched and no longer interesting region again
and again.
1

2

Basic concepts

A critical path is a sequence of operations starting from the first operation on the first machine M1
and ending with the last operation on the last machine Mm . The starting time of each operation on
the path, except for the first one, is equal to the completion time of its preceding operation—that
is, there is no idle time along the path. Thus, the length of the critical path is the sum of theprocessing times of all the operations on the path and equals to Cmax . There can be more than
one critical path in a schedule.
The operations on a critical path can be partitioned into subsequences, called critical blocks,
according to their associated machines. A critical block consists of maximal consecutive operations
on the same machine, or to put it more simply, a subsequence of associated jobs. Most of thefollowing notations have previously been used by Nowicki and Smutnicki[5]. Consider a schedule
represented by a permutation π. Let B1 , . . . Bk be a set of all critical blocks that contains morethan one job and let ml be the index of the machine associated with Bl . Let π(ul ) be the first jobof Bl (and the last job of Bl−1 ). Then the ‘inside’ of Bl , denoted by B̂l , is defined as follows: Bl \ {π(ul+1 )}B̂l =if l = 1 and ml = 1
Bl \ {π(ul )}if l = k and ml = n B \ {π(u ), π(u )} otherwise.
lll+1

Figure 1 shows an example of schedule π = 4, 5, 6, 1, 2, 3, 8, 7 for a problem with n = 8 jobs andm = 6 machines represented by a grid graph, that is taken from [5]. In the figure, the verticalaxis corresponds to machines and the horizontal axis to jobs. Each circle represents an operation,
and arrows precedence relation between operations. A critical path is marked by thin lines. In
this example, there are four critical blocks B1 , B2 , B3 , B4 that contain more than one job. B2 onmachine 3, for example, consists of four jobs 5, 6, 1 and 2, and B̂2 consists of jobs 6 and 1. LikewiseB̂4 on machine 6 consists of jobs 8 and 7.
A neighborhood N (x) of a point x in a search space can be defined as a set of new points that canbe reached from x by exactly one transition or move (a single perturbation of x). One of the wellknown transition operators for PFSP is the shift move which takes a job from its current position
and re-inserts it in another position. Let v = (a, b) be a pair of positions in π. Here, v defines a movethat removes the job π(a) from a position a and re-inserts it in a position b. If a < b, the resulting
schedule is represented by πv = π(1), . . . , π(a − 1)π(a + 1), . . . , π(b), π(a), π(b + 1), . . . , π(n), and if
a > b, πv = π(1), . . . , π(b), π(a), π(b + 1), . . . , π(a − 1)π(a + 1), . . . , π(n). A neighborhood N (V, π)
is defined as the set of all schedules obtained by shift moves in V = {(a, b) : b 6∈ {a − 1, a}, a, b ∈{1, . . . , n}}.
Let Wl (π) be a set of moves restricted to the inside of Bl , namely Wl (π) = {(a, b) ∈ V |a, b ∈ B̂l }S
and W (π) = kl=1 Wl (π), then the so-called ‘block property’ is formulated as follows:
Property A (block property):

For any schedule β, β ∈ N (W (π), π) =⇒ Cmax (β) ≥ Cmax (π).

According to property A above, no move in W (π) can directly improve schedule π. Therefore,
it is reasonable, for computational efficiency, to reduce the size of the neighborhood N (V, π) byeliminating moves in W (π), and to use a new neighborhood N (V \ W (π), π), which we call here a“critical block neighborhood”.

3

Tabu search

Nowicki and Smutnicki [5] proposed a Tabu Search (TS) method for the PFSP. The tabu list
used in their approach is described as follows: when v = (a, b) is performed on π, a pair of jobs
(π(a), π(a + 1)) (if a < b) or (π(a − 1), π(a)) (if a > b) is stored as ‘tabu’ in the tabu list T oflength tl. Then, a move v = (a, b) cannot be performed on β if a < b and {(β(j), β(a)) | j =a + 1, . . . , b} ∩ T 6= φ or if a > b and {(β(a), β(j)) | j = b, . . . , a − 1} ∩ T 6= φ. The neighborhood2

job 4block machine
1
1

2

2

3

5

6

1

2

3

8

7

4
3

5

4

6

Figure 1: A grid graph representation of a solution to a problem of 8 jobs and 6 machines.
N (V \ W (π), π), which is a subset of N (V, π), is still too big for problems of even moderate size.
Thus, it is impracticable to evaluate all the neighbors in N (V \ W (π), π), so Nowicki and Smutnicki
use a subset of N (V \ W (π), π) as a neighborhood structure. Alternatively, one can make theevaluation probabilistic: a member α from N (V \ W (π), π) is selected at random and accepted if
Cmax (α) < Cmax (π), otherwise probabilistically accepted according to the Metropolis probability
Pc (α) = exp (−∆Cmax /c), where ∆Cmax = Cmax (α) − Cmax (π).

4Pruning pattern

A pruning pattern [π]l associated with π and its critical block Bl is derived from π by replacing
the jobs that belong to B̂l by ? as follows:([π]l (j) =?
if j ∈ B̂l ,π(j) otherwise.

For example, the pruning pattern corresponding to π = 4, 5, 6, 1, 2, 3, 8, 7 and B2 in Figure 1 is [π]2 =4, 5, ?, ?, 2, 3, 8, 7. The makespan of [π]l is defined as the makespan of π, namely, Cmax ([π]l ) :=Cmax (π). The ? means a wild card, and a permutation β ‘matches’ [π]l if β(j) = [π]l (j) at all but? positions. For example 4, 5, 6, 1, 2, 3, 8, 7 and 4, 5, 1, 6, 2, 3, 8, 7 both match [π]2 . [π]l and a setof all permutations that match [π]l are identified. It is clear that N (Wl (π), π) ⊂ [π]l . The blockproperty can be reformulated using [π]l as follows:
Property B: For any schedule β and any pruning pattern [π]l , β ∈ [π]l =⇒ Cmax (β) ≥ Cmax ([π]l ).
Property C below is a corollary of Property B:
Property C: For any two pruning patterns [π]i and [φ]j , [π]i ⊂ [φ]j =⇒ Cmax ([π]i ) ≥ Cmax ([φ]j ).
Property B suggests that when a new, possibly good, solution π is found during the search, [π]lidentifies a region where no solutions are better than π, and that excluding [π]l from the search
space can reduce the size of the search space without eliminating the global optima.

5

Pruning pattern list approach

The basic idea of the pruning pattern list approach is to reduce the size of the search space effectively
through storing the ‘important’ pruning patterns that correspond to a long critical block of a goodsolution. Let [π] (without suffix) be the pruning pattern that corresponds to the longest critical
block of schedule π. The pruning pattern list P L with length pl is maintained and updated asshown in Figure 2. In the figure, N (π) represents the neighborhood of π. N (V \ W (π), π) or its
subset is normally used as N (π). There is no good reason to keep patterns that are rarely accessedin the list. Therefore such patterns are replaced by new patterns. According to property C, it is3

1. At the beginning of the search, P L is initialized as a list of empty pl elements.
2. After N (π) is calculated from π, N P (π) is initialized as N (π). For each α ∈ N P (π), if
α matches any pattern [β] ∈ P L, then α is removed from N P (π), resulting N P (π) :=N P (π) \ α, and the ‘access count’ of [β] is incremented. N P (π) is used as the newneighborhood of π.
3. When a cost-decreasing solution α is selected from the neighborhood N P (π) of thecurrent solution π (Cmax (α) < Cmax (π)), then its longest pruning pattern [α] isstored in the list.
4. All the existing patterns [β] in the list that are subsets of a newly stored pattern [α]([β] ⊂ [α]) are removed and substituted by empty patterns.
5. If the number of non-empty patterns on P L exceeds pl, then the least accessed
pattern [γ] is removed from the list.

Figure 2: The pruning pattern list approach to the PFSP.
also not necessary to keep pruning patterns in the list that are subsets of other patterns. Thus
they are removed.
Starting from an initial solution, the local search iteratively replaces the current solution with
one of its neighbors. In advanced local search strategies, such as Simulated Annealing (SA) and TS,
cost-increasing neighbors can be accepted as well as cost-decreasing ones. Accepting cost-increasing
moves enables the search to escape from the local optima, but this may also cause revisiting ofpreviously evaluated points in the search space – something that is wasteful of computing resourcesin itself, and which also means the search is not adequately diversified. One of the main aims of tabu
search is to discourage such revisiting. This can be accomplished by means of an explicit ‘tabu list’of points previously visited, but normally it is easier, and more efficient, to record specific attributesof such points, or of moves that would lead towards them. Nevertheless, recording attributes ofthe points, and not the points themselves, can risk treating even moves that are better than any
solution obtained so far as tabu. This is one of the main reasons why aspiration criteria should be
introduced into TS.
In the case of the pruning pattern list approach, property B guarantees that a move thatmatches a pruning pattern is never better than the best solution obtained so far. This means thatan aspiration criterion is not necessary, and it also means that the pruning pattern list can serve
as a longer-term memory to prevent the search getting stuck in an already searched and no longer
interesting region. Unlike the tabu list, an old pattern can remain in the pruning list as long as itis accessed frequently. If N (V \ W (π), π) or its subset is used as the neighborhood of the current
solution π, it does not contain any solution that matches [π]l , even without P L. However, it is still
possible that the region [π]l would be revisited in some later stages without any better solutions
than π being found. The size of P L is fixed to pl mainly for computational efficiency. Theoretically,
N P (π) may not satisfy the connectivity property that N (V \ W (π), π) does. It should be notedthat the pruning pattern list is treated in a similar way that the population is treated in Genetic
Algorithms (GAs), especially in the steady state model [12]. The access count of the pruning
pattern corresponds to the fitness function of the individual in GAs.

4

6

Experimental results

The pruning pattern list approach described in the previous section can be embedded into any local
search method, including TS, SA, and even GAs [13, 9]. Here a simple probabilistic version of theTS described in Section 3 is used as a test case. The programs are coded in C.
The graph on the left side of Figure 3 shows the time evolution of the makespan averaged over
30 runs of the TS with and without the pruning pattern list. This uses the ta041 problem, which
is one of Taillard’s benchmarks for size 50×20 (50 jobs and 10 machines) [11]. The parameters
used are c = 3.0, tl = 7 and pl = 10. The pruning pattern list is updated after every 10000 TS
evaluations for 700 times (thus total 10000×700 TS evaluations). One run takes about 10 minutes
on an HP 700 workstation. The best and worst makespans obtained among 30 runs are 3000 and
3016 respectively when TS with the pruning pattern list is used, and 3010 and 3025 when TS
without the pruning pattern list is used. It can be seen that the pruning pattern list approach
improves both the solution quality and the speed. Without the pruning pattern list 12 runs out of
30 were trapped at a local minimum of makespan = 3025, which Nowicki and Smutnicki reported
as the new reference makespan for this problem[5]. This suggests that their TS method can also
be improved by incorporating the pruning pattern list approach.
The pruning pattern list approach is also applied to 50×20 (50 jobs and 20 machines) problemsof Taillard’s benchmarks (ta051 - ta060). The parameters used are the same as in the ta041
case and the results are averaged over 10 replications instead of 30. The results are summarizedin Table 1, where the columns labeled TS+PL and TS show the average performance with andwithout the pruning pattern list respectively. The column labeled NOW shows the best makespanreported in[5]. The results of TS with the pruning pattern list generally outperform the results of
TS without the pruning pattern list, except for the ta057 problem. As typical examples, the graphon the right side of Figure 3 shows the time evolution of the average makespan for ta051 problem.
It also includes the computationally equivalent MSXF-GA results reported in [9] for comparison.
Figure 4 shows the time evolution for other 50×20 problems.
prob
051
052
053
054
055
056
057
058
059
060

TS+PL
3859.43708.03653.93734.03617.13689.33712.83701.43756.93765.7TS
3866.03713.43657.43737.23625.73691.73712.43706.83762.33767.3

NOW (best)
3875
3715
3668
3752
3635
3698
3716
3709
3765
3777

Table 1: Comparison with and without the pruning pattern list for problems size 50×20.
To see how the proposed approach behaves with growing problem sizes, the experiments areextended to Taillard’s 100×20 (ta081 - ta090), 200×20 (ta101 - ta110) and 500×20 (ta111 - ta120)
problems. For 100×20 (ta081 - ta090), 200×20 (ta101 - ta110) problems, the results are summarizedin Table 2. Here, the pruning pattern list is updated after every 10000 TS evaluations for 160
times, which resulted in comparable and slightly better performances than those reported in [5].
The parameters used are are c = 3.0, tl = 7 and pl = 5. and the results are averaged over 10
replications. One run for each 100×20 and 200×20 problems takes about 6 and 12 minutes on an
HP 700 workstation respectively. It is observed that the computational overhead of the pruning
pattern calculation is about 8 % when pl = 5 and increases linearly as the size of P L. According tosome preliminary experiments, the performance of the algorithm seems not sensitive to the length5

of the pruning pattern list as long as pl ≥ 5. It can be seen that the results of TS with the pruning
pattern list generally outperform the results of TS without the pruning pattern list with some
exceptions, whereas the gaps between TS+PL and TS become decreasing and less significant (lessthan 0.1 %).
prob
081
082
083
084
085
086
087
088
089
090

TS+PL
6270.66228.96309.86302.56358.16420.86328.26470.16327.06469.3

TS
6270.26233.06314.86306.66362.16431.16333.66471.56332.26476.9NOW (best)
6286
6241
6329
6306
6377
6437
6346
6481
6358
6465

prob
101
102
103
104
105
106
107
108
109
110

TS+PL
11285.5
11358.5
11428.3
11357.7
11301.511269.7
11463.8
11413.5
11302.811404.6

TS11305.011349.6
11430.3
11366.911310.3
11275.011459.911420.9
11313.2
11418.3

NOW (best)
11294
11420
11446
11347
11311
11282
11456
11415
11343
11422

Table 2: Comparison with and without the pruning pattern list for problems size 100×20 and
200×20.
Table 2 shows the results for Taillard’s 500×20 (ta111 - ta120) problems. In the columns
TS+PL and TS, the average, best and worst results over 10 replications are reported respectively.
To keep the results comparable with those reported in [5], the number of iterations is doubled
and the pruning pattern list is updated after every 10000 TS evaluations for 320 times with theother parameters same as 100×20 and 200×20 problems. Due to the increase both in the problem
size and the number of iterations, one run now takes about 60 minuts. The same tendencies areobserved here again: TS+PL runs are generally better than TS runs with some exceptions whereas
the gaps between TS+PL and TS become decreasing.
Finally, to see the maximal performace of the TS+PL method, the number of iterations aredoubled again for TS+PL runs only, resulting in best, worst and average makespans shown in thecolumns under the label “TS+PL (long)” in Table 2.
prob
111
112
113
114
115
116
117
118
119
120

average26324.026687.6
26465.6
26547.2
26371.426589.2
26432.4
26678.826149.826600.0

TS+PL[best worst][26198 26398][26633 26735][26435 26522][26522 26590][26354 26412][26535 26621][26412 26481][26619 26748][26097 26196][26546 26669]

average
26321.0
26717.026483.626555.6
26399.626584.026438.4
26659.4
26151.026608.6

TS[best worst][26263 26403][26629 26805][26466 26512][26533 26584][26383 26413][26564 26621][26412 26463][26619 26736][26101 26235][26572 26684]

TS+PL (long)
average[best worst]
26159.6 [26139 26182]
26625.5 [26600 26642]
26431.4 [26417 26435]
26525.0 [26520 26541]
26356.2 [26354 26366]
26516.3 [26498 26543]
26413.0 [26412 26422]
26615.9 [26615 26619]
26078.8 [26050 26103]
26526.4 [26497 26552]

NOW (best)
26189
26629
26458
26549
26404
26581
26461
26615
26083
26527

Table 3: Computational results for problems size 500×20.

7Conclusion

The pruning pattern list approach to the makespan-minimizing permutation flowshop scheduling problem is proposed and embedded into a Tabu Search method. The experimental results
6

ta041

makespanta051

makespan
3930

3052
3048

3920

3044
3910

3040
3036

3900
3032

TS without pruning pattern list

3028

TS without pruning pattern list

3890

3024

MSXF-GA
3880

3020

TS with pruning pattern list

TS with pruning pattern list

3016

3870

3012
3860

3008
0

100

200

300

400

500

600

0

700

iterations

100

200

300

400

500

600

700

iterations

Figure 3: The time evolutions of makespans for the ta041 (50 jobs and 10 machines) and ta051 (50jobs and 20 machines) problems
demonstrate the effectiveness of the proposed approach especially for medium-size problems. Good
performances are also observed for large-size problems, however the gap between with and without
the pruning pattern list approach seems to be decreasing, which would be left for future research.
Future research will also aim to implement more efficient ways to scan the pruning pattern list andfind a match more quickly. The proposed approach can also be embedded into GAs. However,
the implementation details including whether each individual should have its own pruning patternlist and should occasionally exchange it with others, or a single list should be shared by all themembers in the population are yet to be investigated.

7

Cmax
3760

ta052

ta053

Cmax
3705

Cmax
3785

3750

3695

3775

3740

3685

3765

3730

TS
TS+PL

3720
3710
0

Cmax
3685
3675
3665
3655
3645
3635
3625
3615

0

Cmax
3770
3760
3750
3740
3730
3720
3710
3700

0

3675

TS

3665

3655
200 400 600
0iterations

ta055

3755
TS+PL

3750

Cmax
3770

3740

3760

3730

3750

3720
TS
3710
TS+PL
3700

3740

200 400 600
iterations

ta058

Cmax

TS

0

3825
3815
3805
3795
3785
TS
TS+PL 3775
3765
3755
200 400 600
0iterations

3730

TS+PL

200 400 600
iterations

ta057

TS+PL
TS

3720

200 400 600 3710 0
iterations

ta059

TS
TS+PL

3745

3735
0
200 400 600
iterations

ta056

Cmax

3690

ta054

Cmax
3815

200 400 600
iterations

ta060

3805
3795
TS

TS+PL

3785
3775

3765
0
200 400 600
iterations

TS

TS+PL

200 400 600
iterations

Figure 4: The time evolutions for the other nine Taillard problems of 50 jobs and 20 machines(ta052 – ta060)

8References[1] A.H.G. Rinnooy Kan. Machine Scheduling Problems: Classification, Complexity and Computations. Freeman, San Francisco, 1979.
[2] H.G. Campbell, R.A. Dudek and M.L. Smith. A heuristic algorithm for the n job m machinesequencing problem. Management Science 16, 630–637, 1970.
[3] D.G. Dannenbring. An evaluation of flow shop sequencing heuristics. Management Science,
23(11), 1174–1182, 1977.
[4] M. Nawaz, E.E. Enscore Jr. and I. Ham. A heuristic algorithm for the m-machine, n-job
flow-shop sequencing problem. OMEGA, 11(1), 91–95, 1983.
[5] E. Nowicki and C. Smutnicki. A fast tabu search algorithm for the permutation flow-shop
problem. European Journal of Operational Research, 91, 160–175, 1996.
[6] F.A. Ogbu and D.K. Smith.
OMEGA, 19(1), 64–67, 1990.

Simulated annealing for the permutation flowshop problem.

[7] M. Widmer and A. Hertz. A new heuristic method for the flow shop sequencing problem.
European Journal of Operational Research, 41, 186–193, 1989.
[8] I.H. Osman and C.N. Potts. Simulated annealing for permutation flow-shop scheduling.
OMEGA, 17(6), 551–557, 1989.
[9] C.R. Reeves and T. Yamada. Genetic algorithms, path relinking and the flowshop sequencing
problem. Evolutionary Computation journal, 6(1), 45–60, 1998.
[10] E. Taillard. Some efficient heuristic methods for flow shop sequencing. European Journal ofOperational Research, 47, 65–74, 1990.
[11] E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational
Research, 64, 278–285, 1993.
[12] D. Whitley, T. Starkweather, and D. Fuquay. Scheduling problems and traveling salesman:
The genetic edge recombination operator. In Proceedings of the 3rd International Conference
on Genetic Algorithms, 133–140, 1989.
[13] T. Yamada and C.R. Reeves. Permutation flowshop scheduling by genetic local search. In
Proceedings of the 2nd IEE/IEEE Int. Conf. on Genetic ALgorithms in Engineering Systems(GALESIA ’97), 232–238, 1997.

9