Lee, Yuan-Shin et al "Soft Computing for Optimal Planning and Sequencing of Parallel Machining Operations"
Computational Intelligence in Manufacturing Handbook
Edited by Jun Wang et al
Boca Raton: CRC Press LLC,2001

©2001 CRC Press LLC

8

Soft Computing for
Optimal Planning and
Sequencing of Parallel

Machining Operations

8.1 Introduction

8.2 A Mixed Integer Program

8.3 A Genetic-Based Algorithm

8.4 Tabu Search for Sequencing Parallel Machining
Operations

8.5 Two Reported Examples Solved
by the Proposed GA

8.6 Two Reported Examples Solved by the Proposed
Tabu Search

8.7 Random Problem Generator and Further Tests


Shu-Cherng Fang

North Carolina State University

ء

Dr. Lee’s work was partially supported by the National Science Foundation (NSF) CAREER Award (DMI-
9702374). E-mail:

©2001 CRC Press LLC

One characterization of parallel machines is based on the location of the cutting tools and workpiece.
As shown in Figure 8.1, a typical parallel machine is equipped with a main spindle, a subspindle (or
work locations), and two or more turrets (or machining units), each containing several cutting tools.
For a given workpiece to be machined on parallel machines, the output of the CAPP generates a set of
precedent operations needed for each particular workpiece to be completed. A major issue to be resolved
is the sequencing of these precedent operations.
The objective is to find a feasible operation sequence with an associated parallel machining schedule
to minimize the total machining cycle time. Because of the relatively new trend of applying parallel
machines in industrial manufacturing, only a handful of papers are found on sequencing machining
operations for parallel machines [3, 22]. The combinatorial nature of sequencing and the complication
of having precedence constraints make the problem difficult to solve.
A definition of such parallel machines can be found in [11, 22]:

D

EFINITION

1


P

(

I, L

)

is a machine tool with

I

(

Ͼ

1) MUs and

L

(

Ն

1) WLs with
the capability of activating

i



l

Ͼ

1)
being held on distinct WLs.
The necessary and sufficient condition for a machine tool to be parallel is

I

Ͼ

1. However, for a parallel
machine to perform machining in sequential operations, we can simply set

i

ϭ

1 and

l

ϭ

1.

duced and further testing results are reported in Section 8.7. Concluding remarks are given in Section 8.8.

8.2 A Mixed Integer Program

The problem of sequencing parallel machining operations was originated from the manufacturing prac-
tice of using parallel machines, and so far there is no formal mathematical model for it. In this section,
we propose a mixed integer program to model the process of sequencing parallel operations on parallel
machines.
The proposed mixed integer program seeks the minimum cycle time (completion time) of the corre-
sponding operation sequence for a given workpiece. The model is formulated under the assumptions that
each live tool is equipped with only one spindle and the automated tool change time is negligibly small.
Consider a general parallel machine with

⌱

MUs and

L

WLs. The completion of a workpiece requires a
sequence of

J

operations which follows a prescribed precedence relation. Let

K

denote the number of time
slots needed to complete the job. Under the parallel setting,

as follows:ϭ

starting time of operation

j

performed by MU

i

on WL

l

in the

k

th time slot. Define , if

k

ϭ

1; for infeasible

i


, i.e., for any
particular operation

j

on WL

l

in the

k

th time slot, if no MU is available then the starting time
is set to be ,

ϭ

completion time of operation

j

performed by MU

i

on WL

l


1

on operation 6.
Denote as the Dirac delta function. For any particular operation

j

, with its corresponding starting
time and completion time , no other operation , at any other time slot , can
be scheduled between , i.e., either or , for , and or . Thus,
for a feasible schedule, the following conditions are required:
With the above definitions, a mixed integer program for sequencing parallel operations is formulated as
Equation (8.1)
Equation (8.2)
x
ijl
k
1 if operation
j is performed by MU
i
on
WL
l
in the kth time slot,
0 if not applicable,



ϭ

ϩϱ
f
ijl
k
f
ijl
k
ϭϩϱ
x
261
4
␦
()и
s
ijl
k
f
ijl
k
jЈ jЈ, j kЈ, kЈ k
s
ijl
k
f
ijl
k
,[] s
ijl
k
f

0Ͻ ,Ϫ



ϭ
␦
s
ijЈl
kЈЈ
f
ijl
k
Ϫ()
1ifs
ijЈl
kЈЈ
f
ijl
k
0,ՆϪ
0ifs
ijЈl
kЈЈ
f
ijl
k
0Ͻ .Ϫ




8.9 ensures the starting time of operation j cannot be initialized until both (i) an MU is available for operation
j and (ii) operation j’s precedent operations are completed. Constraint 8.10 ensures that no multiple operations
are performed by the same MU in the same time slot. Constraint 8.11 describes the variables assumption.
The combinatorial nature of the operation sequencing problem with precedence constraints indicates
the potential existence of multiple local optima in the search space. It is very likely that an algorithm
for solving the above mixed integer program will be trapped by a local optimum. The complexity of
the problem is also an issue that needs to be considered. Note that each of the variables , , and
has multiple indices. For a five-operation example performed on a 2-MU, 2-WL parallel machine,
given that both MUs and one WL are available for each operation, there are 50 ϫ 3 ϭ 150 variables
x
ijl
k
1Յ i,
lϭ1
L
Α
jϭ1
J
Α
ϭ 1 … Ik ,,,ϭ 1 … K,,,
x
ijl
k
1 k ,Յ
jϭ1
J
Α
iϭ1
I
Α

ihl
kЈ
kЈϭ1
kϪ1
Α
lϭ1
L
Α
iϭ1
I
Α



x
ijl
k
lϭ1
L
Α
iϭ1
I
Α



Ն khj,(),,᭙,
f
ijl
k

kϪ1
Α
iЈϭ1
I
Α
,




,
0 ϱи 0,ϭ
␦
s
ijl
k
f
ijЈl
kЈ
Ϫ()
␦
s
ijЈl
kЈЈ
f
ijl
k
Ϫ()ϩ 1 for feasible ,ϭ ijkl,, ,, with jЈ jkЈ kk k
ЈЈ
Ͻ,Ͻ, ,

5. Select a new population from .
6. Apply genetic operator on .
7. Generate .
8. Repeat steps 3 through 8 until termination conditions are met.
9. Output the best solutions found.
8.3.1 Applying GAs on the Parallel Operations Process
The proposed genetic algorithm utilizes Yip-Hoi and Dutta’s single parent precedence tree [22]. The
outline of this approach is illustrated in Figure 8.2. An initial population is generated with each chro-
mosome representing a feasible operation sequence satisfying the precedence constraints. The genetic
operators are then applied. After each generation, a subroutine to schedule the operations in parallel
FIGURE 8.2
Flow chart for parallel operations implementing GAs.
ijkϫ lϫϫ 2ϭ 15ϫ 5ϫϫ 50ϭ
Pt() x
1
t
… x
n
t
,,{}ϭ x
i
t
t 0ϭ
Pt()
Pt()
tt1ϩϭ
Pt() Pt 1Ϫ()
Pt()
Pt 1ϩ()
gen=1

A precedence constraint is represented by a precedence matrix P. For the example, with five operations
(Figure 8.3), the operations occupy three levels. A 5 ϫ 3 matrix (Table 8.1) P is constructed with each
row representing an operation and each column representing a level. Each element P
i,j
assigns a prede-
cessor of operation i which resides at level j, e.g., stands for ‘‘operation 3 at level 2 has a precedent
operation 1.’’ The operations at level 1 are assigned with a large value M. The initial population is then
generated based on the information provided by this precedence matrix.
8.3.1.3 Generating Initial Population
The initial population is generated by two different mechanisms and then the resulting individuals
are merged to form the initial population. We use the five-operation example to explain this work.
TABLE 8.1 The Precedence Constraint
Matrix P
FIGURE 8.3
A five-operation precedence tree.
level
123
→
P
op1
op2
op3
op4
op5
M 00
M 00
010
010
003


(if any) can be scheduled as early as possible and the overall operation time (cycle time) can be
reduced. To achieve this goal, the operations in the same level are scheduled as a cluster in the resulting
sequence.
8.3.1.4 Selection Method
The roulette wheel method is chosen for selection, where the average fitness (cycle time) of each chro-
mosome is calculated based on the total fitness of the whole population. The chromosomes are selected
randomly proportional to their average fitness.
8.3.2 Order-րPosition-Based Crossover Operators
A crossover operator combines the genes in two parental chromosomes to produce two new children.
For the order-based chromosomes, a number of crossover operators were specially designed for the
evolution process. Syswerda proposed the order-based and position-based crossovers for solving sched-
uling problem with GAs [17]. Another group of crossover operators that preserve orders/positions in
the parental chromosomes was originally designed for solving TSP. The group consists of a partially-
mapped crossover (PMX) [9], an order crossover (OX) [6], a cycle crossover (CX) [15] and a common-
ality-based crossover [1]. These crossovers all attempt to preserve the orders and/or positions of parental
chromosomes as the genetic algorithm evolves. But none of them is able to maintain the precedence
constraints required in our problem. To overcome the difficulty, a new crossover operator is proposed
in Section 8.3.3.
8.3.3 A New Crossover Operator
In the parallel machining operation sequencing problem, the ordering comes from the given precedence
constraints. To maintain the relative orders from parents, we propose a new crossover operator that will
produce an offspring that not only inherits the relative orders from both parents but also maintains the
feasibility of the precedence constraints.
The Proposed Crossover Operator

Given parent 1 and parent 2, the child is generated by the following steps:
Step 1. Randomly select an operation in parent 1. Find all its precedent operations.
Store all the operations in a set, say, branch .
Step 2. For those operations found in Step 1, store the locations of operations in parent 1 as location
1

1
and
location
c
location
1
), fill in remaining operations with the ordering of parent 1.
pos in,()n child i()ϪՅ


©2001 CRC Press LLC
Table 8.2 shows how the operator works for the eight-operation example (Figure 8.4). In step 1, operation
5 is randomly chosen and then traced back to all its precedent operations (operations 1 and 2), together
they form branch ϭ {1, 2, 5}. In step 2, find the locations of operations 1, 2, 5 in both parents, and store
them in location
1
ϭ {1, 3, 8} and location
2
ϭ {1, 5, 7}. In step 3, the earliest locations for each operation in
{1, 2, 5} to appear in both parents is stored as location
c
ϭ {1, 3, 7}. Fill in the child with {1, 2, 5} at the
locations given by location
c
ϭ {1, 3, 7} while at the same time keeping the precedence relation unchanged.
In step 4, fill in the remaining operations {3, 6, 4, 7, 8} following the ordering of parent 1. The crossover
process is now completed with a resulting child [1 3 2 6 4 7 5 8] that not only inherits the relative orderings
from both parents but also satisfies the precedence constraints.
To show that the proposed crossover operator always produces feasible offspring, a proof is given
as follows. Let T

(i
2
) Ͻ
…
Ͻ
location
2
(i
k
).
In step 3, location
c
(i
l
) ϭ {location
1
(i
l
), location
2
(i
l
)} is defined to allocate the location of chosen
operation i
l
in the child. We claim that the resulting child is always feasible. Otherwise, there exists a
precedent pair such that location
c
(i
1

), location
2
(i
l
)} Ͻ min {location
1
(i
m
),
location
2
(i
m
)}. Thus, if (i
l
, i
m
) D, then location
c
(i
l
) Ͻ location
c
(i
m
). This guarantees the child to be a
feasible sequence after applying the proposed crossover operator.
TABLE 8.2 The Proposed Crossover Process on the Eight-Operation Example
The Proposed Crossover
parent 1 [1 3 2 6 4 7 8 5]

ϭ
ij,(): i ՞ jij,() T
n
ʦ᭙,{}
i ՞ j
i
1
… i
k
,,{}
min
lϭ1
k
i
l
i
m
,()Dʦ lm, 1 … k,,ϭ
i
l
i
m
Ͻ
ʦ
©2001 CRC Press LLC
8.3.4 A New Mutation Operator
The mutation operators were designed to prevent GAs from being trapped by a local minimum.
Mutation operators carry out local modification of chromosomes. To maintain the feasible orders among
operations, some possible mutations may (i) mutate operations between two independent subtrees or
(ii) mutate operations residing in the same level. Under this consideration, we develop a new mutation

TABLE 8.3 The Proposed Mutation Process on the Eight-Operation Example
The Proposed Mutation
parent [1 3 2 6 4 7 8 5]
step 1: [1 3 |2 6 4| 7 8 5] operations 3, 7 chosen,
branch ϭ {3, 2, 6, 4, 7}
step 2, 3: [1 2 |3 6 4| 7 8 5] mutate operations 2 and 3
child [1 2 3 6 4 7 8 5]
m 3Ն


©2001 CRC Press LLC
record tabu moves. Each time a move is executed, it is recorded as a tabu move. The status of this tabu
move will last for a given number of iterations called tabu tenure. A tabu move is freed from the tabu list
when it reaches tabu tenure. A strategy called aspiration criteria is introduced to override the tabu status
of moves once a better solution is encountered. The above tabu conditions and aspiration criteria are the
backbone of the tabu search heuristic. Together they make up the bases of the short-term memory process.
The implementation of the short-term memory process is what differentiates tabu search from local search
(hill climbing/descending) techniques. Tabu search follows the greatest improvement move in the neigh-
borhood. If such a move is not available, the least nonimprovement move will be performed in order to
escape from the trap of a local optimum. Local search, on the other end of the spectrum, always searches
for the most improvement for each iteration.
A more refined tabu search may employ the intermediate-term and long-term memory structures in
the search procedure to reach regional intensification and global diversification. The intermediate-term
memory process is implemented by restricting the search within a set of potentially best solutions during
a particular period of search to intensify the search. The long-term memory process is invoked periodically
to direct the search to less explored regions of the solution space to diversify the search.
In this section, a tabu search with a short-term recency-based memory structure is employed to solve
the operations sequencing problem. The neighborhood structure, move mechanism, data structure of
tabu list, aspiration criteria, and the stopping rule in the tabu search are described as follows.
8.4.2 Neighborhood Structure

2. The precedence constraint: Even after an ‘‘admissible’’ exchange, a checkup procedure is needed to ensure
the precedence constraint is not violated. Consider the above operation sequence [1 2 3 4 5 6 7 8].
Operations 6 has possible locations between the third and the eighth in the sequence, i.e., [opE(6), opL(6)]
ϭ [3, 8]. Similarly, [opE(8), opL(8)] ϭ [4, 8]. Although both operations are in permissible locations for
exchange, the exchange of operations 6 and 8 incurs an infeasible operation sequence [1 2 3 4 5 8 7 6]
which violates the precedence constraint (Figure 8.4) of having operation 7 before operation 8.
8.4.4 Tabu List
The type of elements in the tabu list L
TABU
for the searching process is defined in this section. The data
structure of L
TABU
takes the form of an n ϫ n matrix, where n is the number of operations in the parallel
machining process. A move consists of a pair (i, j) which indicates that operations (i, j) are exchanged.
The element L
TABU
(i, j) keeps track of the number of times the two operations are exchanged and the
prohibition of a tabu move is thus recorded. A fixed tabu tenure is used in the proposed tabu search.
The status of a tabu move is removed when the value of L
TABU
(i, j) reaches the tabu tenure.
8.4.5 Aspiration Criterion and Stopping Rule
An aspiration criterion is used to override the tabu status of moves once better solutions are encountered.
The aspiration criterion together with the tabu conditions are the means used by a tabu search to escape
from the trap of local optima. A fixed aspiration level is adopted in the proposed tabu search. The stopping
rule used here is based on the maximum number of iterations. The search process terminates at a given
maximum number of iterations. The best solution found in the process is the output of the tabu search.
8.4.6 Proposed Tabu Search Algorithm
To outline the structure of the proposed tabu search algorithm, we denote
n as the number of operations,

O
nϫn
←
f
ء
f opseq()←
ʦ
f
ء
← f
ء
f opseq p()()←
©2001 CRC Press LLC
Else, check aspiration level.
if , update L
TABU
,
.
5. If , set and Go to step 3.
6. .

If k ϭ maxit , STOP.
Else k k ϩ 1 and p 1, Go to step 2.
The performance of the proposed tabu search will be investigated in Sections 8.6 and 8.7.
8.5 Two Reported Examples Solved by the Proposed GA
In this section, two examples are used to test our genetic algorithm with the proposed crossover and
mutation GA operators. The computation experiments were conducted on a Sun Ultra1 workstation,
and all programs were written in MATLAB environment.
In both examples, there are three machining constraints [22]:
1. The precedence constraints. All the scheduled operations must follow a prescribed precedence

M ( opseq(p) )
Tabu Move?
Criteria
Satisfied?
f ( opseq(p) ) < f * ?
NO
NO
YES
YES
YES
NO
opbest opseq(p)
f * f ( opseq(p) )
Update
TABU
L
Aspiration
f opseq p()()f
ء
Ͻ
opbest opseq p()← f
ء
, f opseq p()()←
pnn1Ϫ()Ͻ /2 pp1ϩ←
opseq opbest←
←←