INTRODUCTION
A review of the literature shows a trend in industry away from grandiose
schemes such as Flexible Manufacturing System (FMS) to much more focused,
smaller, manageable levels of factory automation (Kumar and Shankar, 2000).
Presently, because of changing market demands, manufacturing strategy
has switched from highvolume production of narrow product lines to mediumvolume
to lowvolume batches of various products. Consequently, the FMS which
offers the flexibility to produce economically in lots of any size is
becoming increasingly important in modern industrial settings (Pan and
Chen, 1997). An FMS, according to Saygin and Kilic (1999), consists of
a group of machine centers, interconnected via a set of automated material
handling and inprocess storage systems, which are all control by an integrated
computer system. The flexibility of FMS is achieved through the use of
versatile machine centers. Unlike the conventional assumption that only
one of each type of machine is available, some of the machines can perform
alternative operations in addition to their own primary ones.
Ahn et al. (1993) incorporated alternative operations into a scheduling
system to increase resource utilization and reduced the makespan of manufacturing
products. Liao et al. (1995) presented two integer programming
formulations for a permutation flowshop in which processors are flexible
to perform other operations besides their own. Gere (1996) investigated
several heuristic algorithms for traditional jobshop scheduling and concluded
that alternative operations improve productivity. They showed that the
production requirements can be completed earlier by employing alternative
machines. Jeong and Kim (1998) studied a realtime scheduling methodology
which uses simulation and dispatching rules for flexible manufacturing
systems. They developed a scheduling mechanism in which job dispatching
rules vary dynamically based on information from discrete event simulation
that is used for evaluating candidate dispatching rules. Pan and Chen
(1997) studied the problem of scheduling a set of jobs each of which consists
of two consecutive operations. The jobs are processed in a twomachine
flowshop in which either or both machines are versatile and the processing
times of the operations of each job are independent of job sequence. The
objective was to minimize the makespan. They showed that this scheduling
problem is NPcomplete and developed a branch and bound algorithm to solve
it. Guerrero et al. (1999) examined the influence of alternative
operations on FMS performance. They applied a linear programming model
to prescribe production plans and employed adaptive control mechanisms
to implement these plans. Shanker and Modi (1999) proposed a branch and
bound technique to determine an interdependent multipleproduct resourceconstrained
scheduling problem with the objective of makespan minimization in a flexible
manufacturing system with resource flexibility. For the same problems,
Cheng and Wang (1998) provided a general pseudopolynomial dynamic programming
scheme which solves the problems analytically.
The earlier studied consider scheduling with alternative operations,
but do not include machine setup times. Schaller et al. (2000)
considered the problem of scheduling part families and jobs within each
part family in a flow line manufacturing cell where the setup times for
each family were sequencedependent and it was desired to minimize the
makespan while processing parts (jobs) in each family together. Rajendran
and Ziegler (2003) presented efficient heuristics for scheduling jobs
in a static flowshop with sequencedependent setup times of jobs. The
objective is to minimize the sum of weighted flow time and weighted tardiness
of jobs. Kurz and Askin (2004) examined scheduling in flexible flow lines
with sequencedependent setup times to minimize makespan. Ruiz et al.
(2005) dealt with the permutation flowshop scheduling problem in which
there were sequencedependent setup times on each machine and the optimization
criterion considered was the minimization of the makespan. Chen and Pan
(2005) developed the development of a mixed Binary Integer Programming
(BIP) model for scheduling alternative operations in twomachine flowshop
problems with mean tardiness as the criterion.
The literature considering setup time on scheduling manufacturing systems
with alternative operations is scarce. Lee and Mirchandani (1988) were
the first to study a twomachine flexible flowshop problem and showed
that the problem could be reduced to three versions of zerosetup, onesetup
and twosetup problems. The zerosetup problem meant that there was no
operation shift on both machines, the onesetup problem meant that there
was just one operation shift on one of the machines and the twosetup
problem meant that there were two operation shifts with one on each machine.
Cheng and Wang (1999) derived a worstcase error bound for the heuristic
presented by Lee and Mirchandani (1988) for the NPcomplete onesetup
version of the twomachine flexible manufacturing cell scheduling problem
and proposed another heuristic with a worstcase error bound of 3/2.
This investigation examines the scheduling in a twomachine flowshop
in which both machines are versatile and where setup time is considered
such that alternative operations and machine setups can take place. This
study focuses on the twosetup problem presented by Lee and Mirchandani
(1988). A modified branch and bound algorithm based on the Pan and Chen`s
(1997) branch and bound technique is developed to find the optimal schedule.
A genetic algorithm is used to rapidly find the nearoptimal schedule
for larger problems. Computational experiments are conducted to illustrate
the effectiveness and efficiency of these algorithms.
PROBLEM DESCRIPTION
A scheduling problem can be described in terms of its job characteristics,
its shop characteristics and the optimality criterion with which the evaluation
of each schedule can be made (Pinedo, 2002). The specific twomachine
flexible flowshop that is considered in this study is described below:
Job characteristics
• 
Each job J_{i} has two operations, X and Y. 
• 
Each job requires the processing of firstly operation type X and
then operation type Y. 
• 
The processing time of the operations of each job are known and
fixed. 
• 
The operations are not preemptable. 
• 
All jobs are immediately available for processing once production
begins. 
Shop characteristics
• 
The shop consists of two machines, M_{1} and M_{2}. 
• 
Each machine can perform both operation types. M_{1} and
or M_{2} may be versatile. 
• 
Each machine can perform only one operation at a time. 
• 
The setup operation, S_{XY} (S_{YX}), changes the
toolset for operation type X (Y) with the toolset for operation
Y (X). Both setup operations are assumed to take the same amount of
time to perform. 
• 
A setup operation must be performed when the machine needs to perform
the other operation type. 
• 
The transfer or transport time of a job from one machine to the
other is negligible. 
• 
The objective is to schedule the operations and setups so as to
minimize the makespan. 
Optimality criterion
The plan for processing these n jobs requires two distinct operations performed
in the order operation type X followed by operation type Y, where M_{1}
has operation type X as its primary operation and M_{2} has operation
type Y as its primary operation. Therefore, all the jobs are loaded and processed
in the sequence M_{1} followed by M_{2}, if no alternative operations
occur. Although alternative operations may suffer from efficiency penalties,
they can be used to improve machine utilization and system performance when
one machine is overloaded and the alternative machine is idle.
Let p_{i1} and p_{i2} denote the processing times of
X of J_{i} on machines M_{1} and M_{2}, while
q_{i1} and q_{i2} are the processing times of Y of J_{i}
on M_{1} and M_{2}, respectively. For twomachine flowshop
scheduling with alternative operations, Pan and Chen (1997) investigated
the following three problems:
• 
The M_{1}→M_{2} problem. In this problem, M_{1}
is a versatile machine and M_{2} is dedicated to operation
Y and thus p_{[i]2} = ∞, i = 1, …, n. 
• 
The M_{2}→M_{1} problem. In this problem, M_{1}
is dedicated to operation X and M_{2} is a versatile machine
and thus q_{[i]1} = ∞, i = 1, …, n. 
• 
The M_{1}↔M_{2} problem. In this problem, both
M_{1} and M_{2} are versatile. 
This study builds upon the work of Pan and Chen (1997) and focuses on
the M_{1}↔M_{2} problem. This study also considers
setup time while the machine needs to perform the other operation type.
The objective is to sequence a set of jobs on the two machines to minimize
the maximum completion time, or makespan.
Modified branch and bound algorithm: Pan and Chen (1997) presented
a branch and bound algorithm to solve twomachine flexible scheduling
problems. However, they neglected the machine setup times. This study
considers setup times and extends the branch and bound approach of Pan
and Chen (1997).
Undoubtedly, for any feasible schedule for the twomachine flexible flowshop
with setup times problem, all jobs can be divided into four disjoint sets
E_{uv}, where u = 1, 2 and v = 1, 2, such that the X and Y operations
of all jobs in E_{uv} are scheduled on machines M_{u}
and M_{v}, respectively. Initially, all jobs are set to belong
to E_{12} and the optimal schedule is identified using Johnson`s
rule (Johnson 1954). If the operations of the jobs belong to E_{11}
or E_{22} or E_{21}, they are called alternative operations.
Pan and Chen (1997) proved this problem belongs to the class of difficult
problems known as NPcomplete. This study considers the scheduling problem
of minimizing makespan in a twomachine flexible flowshop with setup
times. Clearly, the proposed problem is NPcomplete since the problem
of scheduling alternative operations in twomachine flowshops is NPcomplete
(Pan and Chen, 1997).
Lemma 1: For the twomachine flexible flowshop with the setup
time scheduling problem, an optimal schedule exists with at most two setups,
of which at most one is in each machine and both are E_{XY} type.
Proof: The proof is straightforward.
Lemma 2: For the twomachine flexible flowshop with the setup
time scheduling problem, an optimal schedule s* exists in which there
is no idle time before any operations assigned to at least one of the
machines.

Fig. 1: 
A feasible schedule 
Proof: Similar to the proof of Lemma 3 by Cheng and Wang (1998).
According to Lemmas 1 and 2, E_{XY} and all jobs in each set
E_{uv} (u, v = 1, 2) can be scheduled as shown in Fig.
1.
Lemma 3: If alternative operations are known, the twomachine
flexible flowshop with the setup time scheduling problem can be solved
in polynomial time.
Proof: In situations involving predefined alternative operations,
the machine setup(s) and machine processes for each operation are known
and fixed, so the twomachine flexible flowshop with the setup time scheduling
problem reduces to n/2/G/C_{max} problem, which can be solved
in polynomial time by Johnson`s rule.
Let J_{[i]} denote the job scheduled at the ith position in a
particular processing sequence. Moreover, let p_{[i]1} and p_{[i]2}
be the processing times of X of J_{[i]} on machines M_{1}
and M_{2} and let q_{[i]1} and q_{[i]2 }represent
the processing times of Y of J_{[i]} on machines M_{1}
and M_{2}, respectively. According to Lemma 3, the C_{max}
of the twomachine flexible flowshop with the setup time scheduling problem
can be calculated as follows.
Procedure for calculating C_{max}
Step 1: 
Set TM_{1} = TM_{2} = 0, TM_{1} and TM_{2} as the current time when M_{1} and M_{2} finish the job processing, respectively.
Set CE_{12}[•] = CE_{21}[•] = 0, CE_{12}[•]
and CE_{21}[•] as the current time when M_{1} and
M_{2} finish processing the operations belonging to E_{12} and E_{21}, respectively.
Set NE_{uv} as the number of jobs belonging to type E_{uv},
where u = 1, 2 and v = 1, 2. 
Step 2: 
If NE_{12} ≠ 0, according to Johnson`s rule,
we obtain optimal schedule (J_{[1]}, J_{[2]}, …,J_{[NE12]}).
For (i = 1; i <= NE_{12}; i++) {TM_{1} = TM_{1} + p_{[i]1}; CE_{12}[J_{[i]}] = TM_{1}}. 
Step 3: 
If NE_{11} ≠ 0, the optimal schedule is arbitrarily,
e.g., (J_{[1]}, J_{[2]}, …,,J_{[NE11]}).
For (i = 1; i <= NE_{11}; i++) {TM_{1} = TM_{1} + p_{[i]1}}. 
Step 4: 
If NE_{21} ≠ 0, according to Johnson`s rule,
we obtain optimal schedule (J_{[1]}, J_{[2]}, …,,J_{[NE21]}).
For (i = 1; i <= NE_{21}; i++) {TM_{2} = TM_{2} + p_{[i]2}; CE_{21}[J_{[i]}] = TM_{2}}. 
Step 5: 
If NE_{22} ≠ 0, the optimal schedule is arbitrarily,
e.g., (J_{[1]}, J_{[2]}, …,,J_{[NE22]}).
For (i = 1; i <= NE_{22}; i++) {TM_{2} = TM_{2} + p_{[i]2}}. 
Step 6: 
Let t denote the setup time. If (NE_{21} ≠ 0
or NE_{22} ≠ 0), TM_{2} = TM_{2} + t. 
Step 7: 
If (NE_{11} ≠ 0 or NE_{21} ≠ 0),
TM_{1} = TM_{1} + t. 
Step 8: 
If NE_{11} ≠ 0, calculate TM_{1} according
to the schedule as step 3.
For (i = 1; i <= NE_{11}; i++) {TM_{1} = TM_{1} + q_{[i]1}}. 
Step 9: 
If NE_{21} ≠ 0, calculate TM_{1} according
to the schedule as step 4.
For (i = 1; i <= NE_{21}; i++) {TM_{1} = max(TM_{1},
CE_{21}[J_{[i]}]) + q_{[i]1}}. 
Step 10: 
If NE_{22} ≠ 0, calculate TM_{2} according
to the schedule as step 5.
For (i = 1; i <= NE_{22}; i++) {TM_{2} = TM_{2} + q_{[i]2};}. 
Step 11: 
If NE_{12} ≠ 0, calculate TM_{1} according
to the schedule as step 2.
For (i = 1; i <= NE_{12}; i++) {TM_{2} = max(TM_{2},
CE_{12}[J_{[i]}]) + q_{[i]2}}. 
Step 12: 
Set C_{max} = max(TM_{1}, TM_{2}). 
An illustrative example: To illustrate Lemma 3 and the procedure
for calculating C_{max}, consider the fivejob problem shown in
Table 1. First, all jobs are set to belong to E_{12}. The initial
schedule is obtained by Johnson`s rule as (J_{1}, J_{4},
J_{3}, J_{5}, J_{2}) with C_{max} = 47.
Finally, we set {J_{3}, J_{5}} ∈ E_{12},
J_{2} ∈ E_{11}, J_{1} ∈ E_{22}
and J_{4} ∈ E_{21}, then according to Lemma 3 and
the procedure for calculating C_{max}, we obtain new C_{max}
= 39. The Gantt chart of the example problem is shown in Fig.
2.
For any given schedule of the twomachine flexible flowshop with n jobs,
the total number of possible sequences when alternative operations are
considered is 2^{2n}. If no alternative operations are performed,
an optimal solution can be obtained by applying Johnson`s rule for the
n/2/G/C_{max} problem. Consequently, this solution can be used
as an initial feasible schedule and is designated by S_{0}. Figure
3 shows a typical branching tree with 16 nodes for scheduling the
twomachine flexible flowshop with two jobs. These nodes correspond to
the 16 possible sequences for a given initial schedule when both machines
are versatile. Node 0, representing the initial solution, is the initial
node and the remaining nodes are numbered in the order they are produced
by the following branching tree generation procedure. Let node s be a
node in the branching tree and let denote the unique parent node of s. Moreover, define o_{[i]j}
as the operation number j of job J_{[i]}, where i = 1, 2,. ..,
n and j = l, 2. At node s, let A_{s} represent the job whose second
operation is an alternative operation while its first operation is not;
and let B_{s} denote the job whose first operation is an alternative
operation and whose second operation is not. Similarly, C_{s}
denotes the job of which both operations are processed by alternative
machines. Finally, D_{s} is the job in which both operations are
performed by their respective primary machines. Clearly, A_{s},
B_{s}, C_{s} and D_{s} are mutually exclusive
and together they constitute the entire alternative operation type associated
with the job. The job number in Fig. 3 shows that node s has alternative operation
type x of job , where x = 1 denotes the job belongs to A_{s}, x = 2 represents that the job belongs
to B_{s} and x = 3 denotes that the job belongs to C_{s}.
Table 1: 
Data of the example problem 


Fig. 2: 
Gantt chart of the example problem 

Fig. 3: 
Branching tree of an M1↔M2 problem 
Let S_{s} denote the schedule represented by node s. Node s depicts
the introduction of an alternative operation for o_{[i]1} and
o_{[i]2} into the schedule represented by node
. For example, node 0 represents the initial schedule S_{0} which
contains no alternative operations. Moreover, node l indicates that o_{[1]2}
in S_{0} is an alternative operation performed by M_{1}.
Descending from o_{[1]2}, node 2 includes alternative operation
for o_{[2]2} in the schedule since its parent is node l in the
branching tree and so on. Therefore, given S_{0}, the set of all
the alternative operations performed at node s is the collection of all
the values by tracing node s upward until node 0 is reached in Fig.
3 and its schedule is determined by Johnson`s rule due to Lemma 3.
The branching tree in Fig. 3 can be produced by the
following procedure.
The branching tree generation procedure
Step 1 
: 
Set child node s = 0, parent node = 0, level L = 0 and job = 0. 
Step 2 
: 
Set x = 1 to denote the jobs in A_{s}. 
Step 3 
: 
Increase L by 1. Set , s = s+1 and generate a child of , node s. Set . 
Step 4 
: 
If = n, go to step 5. Otherwise, go to step 3. 
Step 5 
: 
Set x = 2 to denote the jobs in B_{s}. 
Step 6 
: 
Set s = s+1, =. 
Step 7 
: 
If = n, go to step 9. 
Step 8 
: 
Increase L by 1. Set = s, s = s+1 and generate a child of , node s. Set Go to step 7. 
Step 9 
: 
Set x = 3 to denote the jobs in C_{s}. 
Step 10 
: 
Set s = s + 1, . 
Step 11 
: 
If = n, go to step 13. 
Step 12 
: 
Increase L by 1. Set = s, s = s+1 and generate a child of , node s. Set . Go to step 11. 
Step 13 
: 
If L = 1, stop. Otherwise, go to step 14. 
Step 14 
: 
Decrease L by 1, set s = s+1 and generate node s. Set
x = 1 and .
Go to step 4. 
Define I_{s1} and I_{s2} as the idle times of M_{1}
and M_{2} in schedule S_{s}, respectively. In S_{s},
we then have
Where:
and
Where:
Define T_{sq} as the time when M_{q} finishes the processing
of all he jobs that are assigned to it in S_{s}, where q = 1,
2. Moreover, let I`_{sq} denote the idle time of M_{q}
based on its T_{sq}.
Then
Where:
and
Where:
The 2^{2n} number of possible sequences is not the only contributor
to the complexity of the problem. The idle times can be used as a basis
for fathoming dominated sequences. For M_{1}↔M_{2}
with setup time problems, an increase in the C_{max} value at
node s does not mean that node s can be fathomed. A more alternative operation
down the branching tree may reduce the C_{max}. Consequently,
only the nodes at the bottom level of the branching tree can be fathomed.
Lemma 4: Consider node s which includes the alternative operation
for Y of J_{[n]} ∈ A_{s} in the schedule. Node s
is fathomed by its parent node, ,
if any of the following two conditions hold.
• 
A
or C
" Ø and q_{[n]1} >= . 
• 
A
or C
= Ø and (q_{[n]1}+t) >= .

Proof: Based on the definition of C_{max}( )
and C_{max}(s), the following two situations exist.
• 
If A or C ≠ Ø, then C_{max}(s)–C_{max}( )
= I_{s1}–+
q_{[n]1} >= 0. Since I_{s1} >= 0 and q_{[n]1}
>= .
Hence, the total 
production time C_{max}(s) is not decreased if the alternative
operation occurs.
• 
If
= Ø, then C_{max}(s)–C_{max}( )
= I_{s1}–+
(q_{[n]1}+t) >= 0. Since I_{s1} >= 0 and (q_{[n]1}+t)
>=.
Hence, the maximum completion time C_{max}(s) is not decreased
if the alternative operation occurs. 
Lemma 5: Consider node s which includes the alternative operation
for X of J_{[n]} ∈ B_{s} in the schedule. Node s
is fathomed by its parent node, ,
if any of the following two conditions hold.
• 
B
or D
≠ Ø and p_{[n]2} >= . 
• 
B
or D
= Ø and (p_{[n]2} + t) . 
Proof: Similar to the proof of Lemma 4.
Lemma 6: Consider node s which includes the alternative operation
of J_{[n]} ∈ C_{s} in the schedule. Node s is fathomed
by its parent node, , if both
the following conditions hold.
• 

• 
Either B_{} or D _{}≠
Ø
and p_{[n]2} – q_{[n]2} >= ,
orB orD = Ø
and p_{[n]2} – q_{[n]2} + t >= .

Proof : For any schedule S_{s} of node s, there exist
• 

Where:
• 

Where:
Suppose both operations of J_{[n]} are processed by alternative
machines. From the definition of T_{s1}, T_{s2}, and the
following two situations exist.
>= 0. Thus, the introduction of the alternative operations for both o_{[n]1}
and o_{[n]2} does not decrease the maximum completion time.
Modified branch and bound algorithm
Step 1: 
Set s = 0 and set all jobs to belong to D_{s}.
Apply Johnson`s rule for the n/2/F/C_{max} problem to find an
initial schedule without considering any alternative operations. Calculate
the idle time I_{s1}, I_{s2}, I`_{s1} and I`_{s2} 
Step 2: 
Generate a new node s by the branching tree generation
procedure. If no such node can be generated, go to step 4. Otherwise,
go to step 3. 
Step 3: 
Apply Lemmas 46 to node s. If node s can be fathomed,
go to step 2. Otherwise, find makespan according to the “procedure
for calculating C_{max}”. Calculate the idle time and go
to step 2. 
Step 4: 
Stop. 
A genetic algorithm approach: Previous researchers have assumed
that a genetic algorithm contains the following main components: solution
representation, initial population and population size, fitness of the
members in a population, selection of parents, genetic operators and a
termination criterion (Chen et al., 1995). The following discusses
the ingredients of a genetic algorithm based heuristic for a twomachine
flexible flowshop scheduling problem with consideration of setup time.
Solution representation: For a scheduling problem, a structure
can be easily described as a sequence of the jobs in the problem. However,
in a twomachine flexible flowshop scheduling problem, the structure
must be slightly modified to display the operation`s alternative situation.
The structure can be described as a disjointed job set (e.g., E_{12},
E_{11}, E_{22} and E_{21}).
Generation of initial population and population size: The efficiency
of genetic algorithms can be markedly increased by selecting a good initial
population and reasonable population size. This heuristic sets the population
size to equal n. The initial population uses the n schedules produced
by method of each schedule has only one job with an alternative operation.
For M_{1}↔M_{2} with the setup problem, the alternative
operation type can be generated randomly by selecting alternative machines
M_{1}, or M_{2}, or both M_{1} and M_{2}.
For instance, if we consider a sixjob problem, then the six schedules
in the initial population are 100000, 010000, 001000, 000100, 000010 and
000001. The schedule 100000, denotes J_{[1]} ∈ E_{11}
and the other jobs J_{[i]} ¢ E_{11}, where i = 2,
3, …, 6. Moreover, the digit 0 indicates one job that has no alternative
operations, i.e., the job belongs to E_{12}. The digit 1 denotes
that one job has alternative operation(s) and that its (their) type may
randomly select one of M_{1}, M_{2}, or both M_{1}
and M_{2}, i.e., the job may randomly select one of E_{11},
E_{22}, or E_{21}.
Fitness function and the selection of parents: For a maximization
problem, the measure of performance generally constitutes the fitness
function. However, the objective of scheduling problems is usually to
minimize a certain measure of performance. For minimization problems,
the method of determining the fitness function differs slightly from that
for maximization problems. This study now discusses the method used to
determine the fitness function for twomachine flexible flowshop problems.
The makespan for all the members in a population is calculated using
the Procedure for calculating C_{max}. From this the largest makespan
is determined and is denoted as C_{max}. The deviation of the
makespan of each member in the population from the C_{max} is
the fitness value of that particular member. This procedure ensures a
high probability of selection for a schedule with lower makespan. This
is also the criterion used for the selection of parents for the reproduction
of children.
Genetic operators: Genetic algorithms contain two common genetic
operators: crossover and mutation. A crossover operator involves combining
the elements from two parent structures into one or more child structures.
Mutation typically works with a single structure leaving the parent intact
with the population. Goldberg`s (1989) Partially Mapped Crossover (PMX)
operator, edge recombination operator, subtourswap operator, subtourchunk
operator, subtourreplace operator and weighted chunking operator are
some of the popular crossover operators for scheduling problems (Chen
et al., 1995). This heuristic uses Goldberg`s (1989) PMX operator
for the purpose of crossover.
Termination criterion: The proposed heuristic uses the number
of generations as the termination criterion in our heuristic. Again, based
on the trial examples, we found that the solutions become stable after
twenty generations. Therefore, twenty generations is used as the termination
criterion in the proposed heuristic.
Genetic algorithm based heuristic: We are now at the position
to present the genetic algorithm based heuristic for the twomachine flexible
flowshop problem. The following notation will be used in describing the
heuristic:
G(r) 
: 
The population in the rth generation. 
g_{i}(r) 
: 
The ith member in G(r). 
C(g_{i}(r)) 
: 
The makespan of g_{i}(r). 
C_{max}(r) 
: 
The max {C(g_{i}(r))}, for all g_{i}(r)
∈ G(r). 
f(g_{i}(r)) 
: 
The fitness of g_{i}(r), which equals C_{max}(r)
C(g_{i}(r)). 
SUMFIT(r) 
: 
The sum of f(g_{i}(r)), for all g_{i}(r) ∈
G(r). 
Procedure for implementing genetic algorithm
Step 1: 
Determine the initial population, G(r), where r =
0. The size of the population, POPSIZE, is n and the number of generations
considered, GENER, is twenty. 
Step 2: 
Calculate the fitness value of each member, f(g_{i}(r)),
for population, G(r). 
Step 3: 
Calculate the selection probability for each g_{i}(r),
where the selection probability is defined as:


Step 4: 
Select a pair of members (parents) that will be used for
reproduction via the selection probability. 
Step 5: 
Apply the PMX operator to the parents. Replace the parents
with the resulting offspring to form a new population, G(r + 1), for generation
r + 1. If the size of the new population equals the POPSIZE, then go to
Step 6, else go to Step 4. 
Step 6: 
If current generation, r+1, equals GENER, then stop, otherwise
go to step 2. 
NUMERICAL INVESTIGATIONS
Computational experiments were conducted to test the effectiveness
of the proposed modified branch and bound, as well as the efficiency of
the genetic algorithms. The processing times of operations performed by
respective primary machines were generated from a uniform distribution
of integers in [1, 100]. Meanwhile, the processing times of operations
performed by respective alternative machines are v times those by the
primary machines, where v = 1.2, 1.4 and 1.6. All of the alternative processing
times were rounded to the nearest integers.
The algorithms were tested over three different problem sizes, n = 20,
25 and 30. Twenty replications were randomly generated for each problem
size. A total of 180 problems were thus tested. The computer programs
were coded in Visual C++ language and run on an Intel P4/2.67GHz with
512 M SDRAM. Table shows the average CPU time (sec) of branch and bound
algorithm (B and B) and Genetic Algorithm (GA), as well as the average
percentage error of GA for each 20 replications.
Table 2: 
Computational results for B andB and GA model 

^{†} The processing times of operations
by respectiv alternative machines are v times those by the primary
machines 
The effectiveness of the GA is measured by the percentage error, which
is defined as:
where, C_{max}(GA) denotes the makespan obtained by the GA and
C_{max}(B and B) represents the optimal makespan. Table
2 yields the following observations.
• 
The modified branch and bound algorithm can solve optimal schedule
with 30 jobs in a reasonable time. The time required to find an optimal
schedule increased nearly ten times for every increment of five jobs
in the problem size. The Branch and bound algorithm can fathom a majority
of the nodes, but the total number of nodes increases at an exponential
rate. 
• 
The genetic algorithm is efficient and the average percentage error
is less than 5%. 
• 
The magnitude of v decides the average CPU time. That is, the larger
the value of v the less the average CPU time. 
• 
The average percentage error of GA decreases with increasing v. 
CONCLUSIONS
This study considers a scheduling problem in a twomachine flowshop
in which both machines are versatile and setup time is considered. A modified
branch and bound algorithm is developed to minimize the makespan of jobs
for these problems. The genetic algorithm is also used to rapidly find
nearoptimal schedules for large scale problems. The modified branch and
bound algorithm and genetic algorithm were tested over three different
problem sizes, n = 20, 25 and 30, for the twomachine flexible flowshop
scheduling with setup times. For the modified branch and bound algorithm,
the computation time increases at an exponential rate as the problem scale
grows. The genetic algorithm is effective and that the average percentage
error is smaller than 5%.
Future research may address problems under different shop environments,
including flowshop and jobshop. Problems with other performance measures,
such as mean flow time or mean tardiness, may also be considered.