Saifallah Benjaafar
Abstract
In this paper, we present a formulation of the plant
layout problem where the objective is to minimize
workinprocess. We show that the choice of layout
has a direct impact on workinprocess accumulation,
manufacturing lead time, achievable throughput
rates, and required material handling capacity. More
importantly, we show that layouts generated using a
queueingbased model can be very different from
those obtained using conventional layout procedures.
In particular, we present a number of surprising and
counterintuitive results. For example, we show that
reducing overall distances between departments can
increase average workinprocess in the plant. We
also show that the relative desirability of a layout
can be affected by nonmaterial handling parameters,
such as department utilization levels, variability
in processing times at departments and variability
in product demands.
1.
Introduction
Including queueing effects in design of plant
layouts has been notoriously difficult [2, 4, 5,
12]. This difficulty is due to a lack of
analytical models which are capable of
explicitly capturing the effect of layout
configuration on dynamic plant behavior. As a
result, most existing plant layout design
procedures attempt to simply minimize a static
measure of material handling time or cost [6,
11, 15]. This is certainly the case for the
widely used quadratic assignment problem (QAP)
formulation, where the objective is to minimize
the total distances traveled in moving material
from one processing department to another [6,
11, 15].
In this paper, we present a reformulation of the
quadratic assignment problem, where the
objective is to minimize workinprocess (WIP).
We show that the choice of layout has a direct
impact on workinprocess accumulation,
manufacturing lead time, achievable throughput
rates, and required material handling capacity.
More importantly, we show that layouts generated
using a queueingbased model can be very
different from those obtained using the
conventional QAP formulation. In particular, we
present a number of surprising and
counterintuitive results. For example, we show
that reducing overall distances between
departments can increase average workinprocess
in the plant. We also show that the relative
desirability of a layout can be affected by
nonmaterial handling parameters, such as
department utilization levels, variability in
processing times at departments and variability
in product demands. These results are different
from conclusions reached by Fu and Kaku in a
recent paper [4], where they argued that the QAP
formulation leads to a layout that also
minimizes average WIP.
In order to obtain average workinprocess due
to a particular layout configuration, we model
the manufacturing facility as a central server
queueing network. Each processing department is
modeled as either a single or a multiserver
queue with arbitrary distribution of product
processing and interarrival times. The material
handling system operates as a central server in
moving material from one department to another.
We assume that the material handling system
consists of discrete devices (e.g., forklift
trucks, human operators, automated guided
vehicles, etc.). The distances traveled by the
material transporters are determined by the
layout configuration, product
routings and product demands. In determining the
transporter travel time distribution, we account
for both empty and full trips by the material
transport devices. Detailed description of the
queueing model and our assumptions are given in
section 4.
Because we impose no assumptions regarding the
arrival processes of products or their
processing times, exact analytical solutions are
difficult to obtain. Therefore, we rely on
network decomposition and approximation
techniques to obtain approximate estimates of
average workinprocess. These approximations
have been shown elsewhere to provide fairly
reliable estimates of the actual workinprocess
for a wide range of parameters [3, 17, 18].
Since our objective in layout design is to
obtain a ranked ordering of different layout
alternatives, approximations are sufficient, as
long as they guarantee accuracy in the ordering
of these alternatives.
An alternative to analytical approximations is
to use computer simulation. However, simulation
can be very computingintensive when hundreds or
thousands of layout configurations, as it is
often necessary in layout design, must be
evaluated. Results from simulation are often
difficult to generalize to systems other than
those being simulated. This contrasts with
analytical models where the mathematical
relationships we obtain can be readily used to
gain general insights into the fundamental
relationship between various parameters.
Nevertheless detailed simulation is useful
whenever an accurate assessment of an individual
layout is required.
The organization of the paper is as follow. In
section 2, we provide a review of relevant
literature. In section 3, we briefly describe
the quadratic assignment problem. In section 4,
we describe our queueingbased formulation of
the layout problem and the corresponding
queueing network model. In section 5, we use our
model to study the relationship between layout
and workinprocess and to compare layouts
selected by the QAP to those selected by the
queueing model. We also validate our results
using simulation. In section 6, we present
extensions of our model and conclusions.
2.
Literature Review
Very little of the existing literature addresses
queueing issues in facility layout design. In a
recent review of over 150 papers published over
the past ten years on plant layout, Meller and
Gau [14] identified only one paper on the
subject. This paper is by Fu and Kaku [5] who to
our knowledge, were the first and only ones to
explicitly address queueing issues in layout
design. Similarly to our study, they used
average workinprocess as the layout design
criterion. To obtain average workinprocess,
they developed a simple queueing network model
in which they assumed all arrival processes to
be Poisson and all processing times to be
exponential, including transportation times. In
modeling transportation times, they also ignored
empty travel by the material handling devices
and accounted only for full trips. These
assumptions allowed them to treat the network as
a Jackson queueing network  i.e., a network of
independent M/M/1 and M/M/n queues for which a
closedform analytical expression of average
workinprocess is available. Using their model,
they showed that minimizing average
workinprocess is, in fact, equivalent to
minimizing average material handling cost, as
used in the conventional QAP formulation.
The limitations of the Fu and Kaku formulation
are in the assumptions used. By assuming that
interarrival times, processing times, and
material handling times are all exponentially
distributed, and by not accounting for empty
travel times, they failed to capture important
dynamics that arise under less restrictive
assumptions. These include, for example, effects
due to the second moments of transportation and
processing times, and variability in product
interarrival times. As we show in this paper,
when the distribution of processing, material
handling, and interarrival times are
appropriately accounted for, the layouts
obtained from the queueing model can be very
different from those obtained by the QAP
formulation. In fact, we show that under certain
circumstances, increasing travel distances can
reduce average workinprocess.
Other related literature include the work of
Kouvelis and Kiran [10] who consider a closed
queuing network for modeling Flexible
Manufacturing Systems (FMS). Their modeling
assumptions are similar to those of Fu and Kaku,
except that they assume workinprocess is
maintained constant. Therefore, they measure
performance by average throughput rather than
workinprocess. Johnson and Brandeau [7, 9] and
Thonemann and Brandeau [16] have extensively
used single stage queueing systems to model
discrete material handling devices, such as
automated guided vehicles. However, their models
do not explicitly capture differences in layout
configurations. Several other queueing and
simulation models have been proposed for the
design and analysis of material handling
systems. An excellent review on this subject can
be found in [8].
3.
The Quadratic Assignment Problem
The quadratic assignment problem (QAP) can be
formulated as follows [6, 11, 15]: Minimize
z
=∑∑∑∑
xikxilλ
ijdkl
i jkl
subject to:
K
∑
xik
=1
V
i
(1)
k
=1
M
+1
∑
xik
=1
V
k
(2)
i
=0
x_{ik}
= 0, 1
V
i, k
(3) where
x_{ik}
= 1 if department
i
is assigned to location
k
and
x_{ik}
= 0 otherwise,
d_{kl}
is the distance between locations
k
and
l,
and λ
_{ij }
is the amount of material flow (the number of
material unit loads) between departments
i
and
j.
Constraints 1 and 2 ensure, respectively, that
each department is assigned one location and
each location is assigned one department. The
objective function minimizes material handling
cost by minimizing the average distance traveled
by an arbitrary unit load of material. If
material transport is provided by a discrete
material handling device, then the QAP also
minimizes the average distance traveled by the
device when the device is full  i.e., while
carrying a load. Although the above formulation
adequately accounts for the cost/time in moving
material between departments, it has several
important limitations. The objective function is
a static
measure that does not account for variability in
material flows between departments. In systems
with discrete material handling devices, the
objective function does not capture empty travel
by these devices. Also, by minimizing only
average distances traveled, information about
the higher moments of travel distribution is
ignored. This could lead, for example, to
selecting a layout with a small mean but a high
variance. As we show in section 5, this would
result in higher variability in material
handling times and cause longer queueing delays.
More generally, by focusing only on average
material handling time, the QAP fails to capture
congestion effects due to waiting for material
handling resources when the number of these
resources is finite. Contention for finite
resources, coupled with variability, leads to
congestion and queueing delays which directly
affect overall manufacturing lead times and
workinprocess levels in the plant. In the next
section, we present a reformulation of the QAP
where many of the above limitations are
addressed.
4.
Model Formulation
In order to illustrate the procedure for
including queueing effects in layout design, we
make the following assumptions (most of these
assumptions are made only for illustrative
purposes and can be relaxed as discussed in
section 6). i) The plant produces
N
products. Product demands are independently
distributed random variables characterized by an
average demand
D_{i
}
and a squared coefficient of variation
C_{i
}
^{2}
for
i
=
1, 2, …,
N.
The squared coefficient of variation denotes the
ratio of the squared mean over the variance. ii)
Material handling is assured by a single
discrete material handling device. Material
transfer request are serviced on a first
comefirst served (FCFS) basis. In the absence
of any requests, the material handling
transporter remains at the location of its last
delivery.
iii) The travel time between any pair of
locations
k
and
l,
t_{kl},
is assumed to be deterministic and is given by
t_{kl}
=
d_{kl}/v,
where
d_{kl
}
is the distance between locations
k
and
l
and
v
is the speed of the
material handling transporter.
iv) Products are released to the plant from a
loading department and exit the plant through an
unloading (or shipping) department. Departments
are indexed from
i
= 0 to
M
+ 1, with the indices
i
= 0 and
M
+ 1 denoting, respectively, the loading and
unloading departments. v) The plant consists of
M
processing departments, with each department
consisting of a single server (e.g., a machine)
with ample storage for workinprocess. Jobs in
the queue are processed
in first comefirst served order. The amount of
material flow, λ
_{ij},
between a pair of departments
i
and
j
is determined from the product routing sequence
and the product demand information. The total
amount of workload at each department is given
by:
MM
+1λ
i
=
∑λ
ki
=
∑λ
ij
for
i
= 1, 2, …m,
(4)
k
=0
j
=1
N
λ
0=
λ
M
+1
=∑
Di,
and (5)
i
=1
MM
+1
λ
t
=
∑∑
λ
ij,
(6)
i
=0
j
=1
where λ
_{t}
is the workload for the material handling
transporter. vi) Processing times at each
department are independent and identically
distributed with an expected processing time
E(S_{i})
and a squared coefficient of variation
Cs^{2}_{i
}
for
i
= 0, 1, …,
M
+ 1
(the processing time distribution is determined
from the processing times of the individual
products). vii) A layout configuration
corresponds to a unique assignment of
departments to locations. We
use the vector notation
x
= {x_{ij}},
where
x_{ik}
= 1 if department
i
is assigned to location
k
and
x_{ik}
= 0
otherwise, to differentiate between different
layout configurations.
The plant is modeled as an open network of
GI/G/1 queues, with the transporter being a
central server queue. A graphical depiction of
product flow through the network is shown in
Figure 1. In order to obtain WIPrelated
performance, we use network decomposition and
approximation techniques (see [3] and [18] for a
general review) where the performance of each
department, as well as the transporter, is
approximated using the first two moments of the
associated job
Unloading department
Figure 1 Central server queueing network model
interarrival and processing times. Under a
given layout, expected WIP at department
i
can then be
obtained as:
ρ
_{i }
^{2}(Ca^{2
}
_{i }
+
Cs^{2}_{i})gi
E(WIPi)=
+ ρ
i,
(7)
2(1 ρ
i)
2
where ρ
_{i}
= λ
_{i}E(S_{i})
is the average utilization of department
i,
Ca^{2}_{i
}
and
Cs_{i
}
are, respectively, the
squared coefficients of variation of job
interarrival and processing times, and
2(1 ρ
i)(1
Ca^{2}_{i})^{2
}
exp[]
if Ca^{2
}
_{i }
<1 3ρ
i(Ca^{2
}
_{i }
+
Cs^{2}_{i})
22
gi
≡
gi(Ca_{i},
Cs_{i},
ρ
i)=
_{{}
(8)1
if Ca^{2
}
_{i }
≥ 1.
Similarly, expected WIP at the transporter is
given by:
ρ
_{t }
^{2}(Ca^{2
}
_{t }
+
Cs^{2}_{t})gt
E(WIPt)=
+ ρ
t,
(9)
2(1 ρ
t)
where ρ
_{t}
= λ
_{t}E(S_{t})
is the average utilization of the transporter,
E(S_{t})
is the expected travel time per material
transfer request and
Cs^{2}_{t
}
is its squared coefficient of variation. Note
that ρ
_{t }
and ρ
_{i}
must be
less than one for expected workinprocess to be
finite.
In order to compute expected WIP, the first and
second moments of transportation time, as well
as the coefficients of variation of
interarrival times to each department and to
the transporter must be known. As we show in the
following two theorems, these parameters are
directly determined by the layout
configurations.
Theorem 1:
Given a layout configuration
x =
{x_{ik}},
the first and second moments of transporter
travel time are given by the following:
M
+1
MM
+1
M
2
E(St)=
∑∑∑∑
λ
krλ
ij/λ
t
trij(x),
and
r
=1
i
=0
j
=1
k
=0
M
+1
MM
+1
M
2
E(S_{t
}
^{2})
=
∑∑∑∑
λ
krλ
ij/λ
t
(trij(x))^{2
}
,
r
=1
i
=0
j
=1
k
=0
where trij(x)=∑∑∑
xrkxilxjs(dkl
+
dls)/v
=∑∑
xrkxildkl/v
+∑∑
xilxjsdls/v
and
ss
kl kll
corresponds to the travel time, under layout
configuration
x,
from department r to department i and then to
department j.
Proof:
First note that travel time from department
i
to department
j,
under layout configuration
x
, is given by:
KK
tij(x)=∑∑
xikxjldkl/v
. (10)
k
=1
l
=1
Also note that in responding to a material
transfer request, the transporter performs an
empty trip from its current location (the
location of its last delivery), at some
department
r,
followed by a full trip from the origin of the
current request, say department
i,
to the destination of the transfer request at a
specified department
j.
Then, in order to obtain the first two moments
of the transporter travel time, we need to
characterize the probability distribution
p_{rij
}
of an empty trip from
r
to
i
followed by a full trip from
i
to
j.
The probability
p_{rij}
is given by:
M
prij
=∑
pkrpij,
(11)
k
=0
where
p_{ij
}
is the probability of a full trip from
department
i
to department
j
which can be obtained as
λ
ij
pij
= . (12)
MM
+1
∑∑
λ
ij
i
=0
j
=1
Noting that the time to perform an empty trip
from department
r
to department
i
followed by a full trip to department
j
is given by
t_{rij}(x)
=
t_{ri}(x)
+
t_{ij}(x),
the first two moments of transporter travel
time per transfer request can now be found as:
M
+1
MM
+1
E(St)=∑∑∑
prijtrij(x),
and (13)
r
=1
i
=0
j
=1
M
+1
MM
+1
E(S_{t
}
^{2})
=∑∑∑
prij(trij(x))^{2
}
,
(14)
r
=1
i
=0
j
=1
which, upon appropriate substitutions, lead to
the desired result.
#
Theorem 2:
Given layout
x
= {x_{ik}},
the squared coefficients of variation of job
interarrival and
departure times at processing departments and at
the transporter can be approximated by the
following:
NN
22
Ca_{0}=
∑
(Di/
∑
Di)C_{i
},
i
=1
i
=1
C_{a}^{2
}
_{i }
= π
_{i}(ρ
_{t }
^{2}C_{s}^{2
}
_{t }
+ (1 ρ
_{t }
^{2})C_{a}^{2}_{t})+1π
_{i }
, for
i
= 1, 2, …,
M
+ 1, and
MM M
2 22
∑π
iρ
_{i }
^{2}Cs_{i
}
+
∑π
i(1
ρ
_{i }
^{2})(1
π
i)+
∑π
_{i }
^{2}(1
ρ
_{i }
^{2})ρ
_{t }
^{2}Cs_{t
}
+ π
0(1
ρ
_{0}^{2})Ca_{0
}
2
i
=0
i
=1
i
=1
Ca_{t
}
=,
M
1∑π
_{i }
^{2}(1
ρ
_{i }
^{2})(
1 ρ
_{t }
^{2})
i
=1
where π
_{i}
= λ
_{i}/λ
_{t }
for
i
= 1, 2, …,
M
+ 1.
Proof:
We use the following known approximations for
characterizing, respectively, the squared
coefficients of variation in interarrival and
departure times at a node
i
in an open network of GI/G/1 queues [3]:
2
λ
jpji
λ
0γ
i
Ca_{i
}
=
∑
(pjiC_{d}^{2
}
_{j }
+ (1 pji))+
(γ
iCa^{2}_{0
}+ (1 γ
i)),
and (15)
j
≠
i
λ
i
λ
i
_{Cd}2
_{i }
2
= ρ
_{i }
^{2}Cs^{2
}
_{i }
+ (1 ρ
_{i }
^{2})Ca_{i},
(16) where
p_{ij
}
is the routing probability from node
i
to node
j
(nodes include departments and the material
handling device), γ
_{i}
is the fraction of external arrivals that enter
the network through node
2
i,
and 1/λ
_{0}
and
Ca_{0
}are, respectively, the mean and squared
coefficient of variation of the external job
interarrival times. In our case, γ
_{0}=
1 and γ
_{i}
= 0 for all others since all jobs enter the cell
at the
loading department, the routing probability from
departments
i
= 0 through
M
to the material handling transporter is always
one, that from the material handling transporter
to departments
j
= 1 through
M
+ 1 is
M
+1
∑λ
ij i
=0
ptj
= (17)
M
+1M
+1
∑∑
λ
ij i
=0
j
=0
and to the loading department (j
= 0) is zero. Parts exit the cell from
department
M
+ 1 (unloading department) so that all the
routing probabilities from that department are
zero. Substituting these probabilities in the
above expression, we obtain
NN
22
Ca_{0}=
∑
(Di/
∑
Di)C_{i
}
, (18)
i
=1
i
=1
MM
22
Ca^{2
}
_{t }
=
∑
(λ
i/λ
t)Cd_{i
}
=
∑π
iCd_{i},
and (19)
i
=0
i
=0
Ca^{2
}
_{i }
= π
iC_{d}^{2
}
_{t }
+1π
i
for
i
= 1, 2, …,
M
+ 1, (20)
which, along with equality (10), can be
simultaneously solved for the desired results.
#
The layout design problem can now be formulated
as:
M
+1
Minimize
E(WIP)
=
∑
E(WIPi)+
E(WIPt)
i
=0
subject to:
K
∑
xik
=1
i
= 0, 2, …,
M
+ 1 (21)
k
=1
M
+1
∑
xik
=1
k
= 1, 2, …,
K
(22)
i
=0
ρ
_{t}
< 1 (23)
x_{ik}
= 0, 1
i
= 0, 2, …,
M
+ 1;
k
= 1, 2, …,
K
(24)
The above formulation shares the same
constraints as the quadratic assignment problem.
We require an additional constraint, constraint
23, to ensure that a selected layout is feasible
and will not result in infinite workinprocess.
The objective function is however different from
that of the QAP. In the conventional QAP, the
objective function is a positive linear
transformation of the
expected transporter time. Therefore, a solution
that minimizes average travel time between
departments is optimal. In the next section, we
show that this is not necessarily the case when
queuing effects are accounted for and that
solutions obtained by the two formulations can
be very different. We also note that by virtue
of Little's law [13], minimizing epxected WIP is
equivalent to minimizing expected product flow
time. Therefore, our model can readily be used
to optimize lead time performance as well.
The quadratic assignment problem is notoriously
known for being NP hard. Therefore our model is
also NP hard (our objective function is a
nonlinear transformation of that of the QAP).
Although it is not our intent in this paper to
provide a solution algorithm, most of the
existing heuristics for the QAP can be readily
applied to the our model. For example, an
iterative pairwise or multistep exchange
procedure, such as CRAFT [1], can be used to
generate a solution. Note that in this case,
after each exchange, it is the expected WIP that
is calculated and used to evaluate the
desirability of the exchange. Other heuristics
may be used as well. For a recent review of the
quadratic assignment problem and solution
procedures, the reader is referred to Pardalos
and Wolkowicz [15].
5.
Model Analysis and Insights
Examining the expression of expected WIP in the
objective function, it is easy to see that it
has two sources: the processing departments and
the material handling transporter. In both
cases, WIP accumulation is determined by (1) the
variability in the arrival process, (2) the
variability in the processing/transportation
times, and (3) the utilization of the
departments and the transporter. Because the
transporter provides input to all the processing
departments, variability in transportation time
directly affects the variability in the arrival
process to all the departments. In turn, this
variability, along with the variability of the
department processing times, determines the
input variability to the transporter. Because of
this close coupling, the variability of any
resource affects the workinprocess at all
other resources.
The conventional QAP model, by focusing only on
average travel time, fails to account for the
important effect of variability. As we show in
the following observations, average travel time
can be a poor indicator of expected WIP.
Observation 1:
Layouts with the same average travel times can
have different average WIP.
Proof:
We use a counterexample to show that layouts
with similar average travel time can have very
different average WIP levels. Consider a
facility with three departments (i
= 0, 1, and 2). The facility produces a single
product, which is manufactured in the fixed
sequence shown in Figure 2(a). The corresponding
queuing network is shown in Figure 2(b). Other
relevant data is as follows:
D_{1}
= 1.62 parts/hour;
E(S_{i})=
36 min for
i
= 0, 1, and 2,
C_{1}^{2
}= 1; and
Cs^{2
}
_{i }
= 1 for
i
= 0, 1, and 2, and
v
= 10 ft/min. We consider two layout scenarios,
x_{1}
and
x_{2}.
The distances between departments are as
follows, scenario 1:
d_{01}(x_{1})
=
d_{10}(x_{1})
=
d_{12}(x_{1})
=d_{20}(x_{1})
=
d_{21}(x_{1})
= 100 ft ; and scenario 2:
d_{01}(x_{1})
=
d_{10}(x_{1})
=
d_{20}(x_{1})
= 10 ft,
d_{12}(x_{1})
= 190 ft, and
d_{21}(x_{1})
= 280 ft. It can be verified that the two
scenarios lead to an average travel time of
E(S_{t}(x_{1}))
=
E(S_{t}(x_{2}))
= 17.5 and a transporter utilization ρ
_{t}(x_{1})
= ρ
_{t}(x_{2})
= 0.945. The second moments of transportation
time are, however, different:
E(S_{t
}
^{2}(x_{1}))
=325 and
E(S_{t
}
^{2}(x_{2}))
= 644.5. From the first two moments of travel
time, we obtain
Cs^{2}_{t}(x1)
= 0.061224,
Ca^{2}_{t}(x1)
= 0.98841,
Ca^{2}_{0}(x1)
= 1,
Ca^{2}_{1}(x1)
=
Ca^{2}_{2}(x1)
= 0.580205,
Cs^{2
}
_{t}(x2)
= 1.10449,
Ca^{2}_{t}(x2)
= 1.00129,
Ca^{2}_{0}(x2)
= 1, and
Ca^{2}_{1}(x2)
=
Ca^{2}_{2}(x2)
= 1.046725, from which we can calculate expected
WIP as follows:
E(WIP(x_{1}))
= 99.33 and
E(WIP(x_{2}))
= 123.76. Since
E(WIP(x_{2}))
>
E(WIP(x_{1})),
although ρ
_{t}(x_{1})
= ρ
_{t}(x_{2}),
our result is proven.
#
To confirm our analytical result, we simulated a
detailed model of the two layout scenarios. For
each scenario, we obtained the following 95%
confidence interval for the value of expected
WIP:
E(WIP(x_{1}))
= 102.14 +/ 1.67 and
E(WIP(x_{2}))
= 123.12 +/ 1.79, which certainly support
our analytical findings. For the sake of
brevity, details of the simulation are omitted.
Observation 2:
A smaller average travel time does not always
lead to a smaller average WIP.
Proof:
We use again a counterexample to prove that
E(WIP)
is not necessarily decreasing in average travel
time. Consider a facility identical to the one
previously described. All parameters
(
(b) Queuing Model
Figure 2 Product flow sequence and the corresponding
queueing network model
are the same with the exception of department
processing time, where in this case
E(S_{i})
= 36.5 min for
i
= 0, 1, and 2. Again, we consider two layout
scenarios,
x_{1}
and
x_{2};
scenario 1:
d_{01}(x_{1})
=
d_{10}(x_{1})
=
d_{12}(x_{1})
=d_{20}(x_{1})
=
d_{21}(x_{1})
= 100 ft ; and scenario 2:
d_{01}(x_{1})
=
d_{10}(x_{1})
=
d_{20}(x_{1})
= 10 ft,
d_{12}(x_{1})
= 10 ft, and
d_{21}(x_{1})
= 170 ft. Layout
x_{1
}
results in an average travel time of
E(S_{t}(x_{1}))
= 17.5 and layout
x_{2}
in
E(S_{t}(x_{2}))
= 8.25. The resulting utilization of the
transporters is ρ
_{t}(x_{1})
= 0.945 and ρ
_{t}(x_{2})
= 0.4455. Thus, we have
E(S_{t}(x_{1}))
>
E(S_{t}(x_{2}))
and ρ
_{t}(x_{1})
> ρ
_{t}(x_{2}).
The second moments of transportation time can be
calculated as
E(S_{t
}
^{2}x_{1})
= 325 and
E(S_{t
}
^{2}x_{2})
= 198.25, from which we obtain
Cs^{2}_{t}(x1)
= 0.061224,
Ca^{2}_{t}(x1)
= 0.993961,
Ca^{2}_{0}(x1)
= 1,
Ca^{2}_{1}(x1)
=
Ca^{2}_{2}(x1)
= 0.580502,
Cs^{2}_{t}(x2)
= 1.912764,
Ca^{2}_{t}(x2)
= 1.001311,
Ca^{2}_{0}(x2)
= 1, and
Ca^{2}_{1}(x2)
=
Ca^{2}_{2}(x2)
= 1.091104 (note that
Cs^{2
}
_{t}(x2)
>
Cs^{2
}
_{t}(x1)).
We can now calculate expected WIP as follows:
E(WIP(x_{1}))
= 185.195 and
E(WIP(x_{2}))
= 210.966. Since
E(WIP(x_{2}))
>
E(WIP(x_{1})),
although ρ
_{t}(x_{2})
< ρ
_{t}(x_{1}),
our result is proven. Again, we confirmed or result
using simulation. The 95% confidence intervals for
expected WIP are:
E(WIP(x_{1}))
= 182.14 +/ 6.58 and
E(WIP(x_{2}))
= 205 +/ 5.72, which certainly support our
conclusion.
#
The above observations highlight the important
effect that variability in travel times between
departments can have on the desirability of a
layout. In both observations, layouts with the
smaller travel time variance were superior, even
when their average travel times were higher. In
fact, in
the example of observation 2, the average travel
time in layout
x_{2}
was less than half that of
x_{1
}
. These results clearly show that minimizing average
travel time (or transporter utilization) is not
always desirable. In fact, reductions in average
travel time if they come at the expense of
increasing travel time variance should at times be
avoided. Note that the increase in travel time, due
to the higher travel time variance, does not only
affect WIP accumulation at the transporter, but also
the level of WIP at the processing departments. The
greater variability in travel times translates into
greater variability in the arrival process to the
department which, in turn, leads to longer queues at
these departments. These results point to the need
to explicitly account for travel time variance when
selecting a layout. A layout that exhibits a small
variance may, indeed, be more desirable than one
with a smaller travel time average.
Travel distances are not, however, the only factor
that affects the relative desirability of a
layout. Non material handling factors such as
department utilization levels, variability in
department processing times, and variability in
demand levels could determine whether one layout
configuration is more desirable than another.
Observation 3:
The relative desirability of a layout can be
affected by nonmaterial handling factors.
Proof:
We use a series of examples to show that varying
either utilization levels or processing time and
demand variability can affect the relative
desirability of a layout. We consider the same
example described in observation 2 and the same two
layout scenarios
x_{1}
and
x_{2}.
In Table 1, we show the effect of varying department
processing time on the performance of
x_{1}
and
x_{2},
and in
Table 2, we show the effect of varying processing
and demand variability (for the sake of brevity,
only WIP values are reported). It is easy to see
that the same layout can be superior under one set
of parameters and inferior under another. For
example,
x_{2
}
has a smaller average WIP than
x_{1
}
when average processing time is 32 min and a much
larger average WIP than
x_{1}
when average
2
processing time is 37 min. Similarly,
x_{1}
has a smaller average WIP than
x_{2}
when
Ca_{0}
= 1 and
Cs^{2}_{i
}
= 0.5 and a larger average WIP when
Ca^{2}_{0
}=
Cs^{2}_{i
}
= 2.
#
The above results show that the relative
desirability of a layout is highly dependent on many
operating parameters. For example, a layout that is
effective in an environment where department
utilization is high may not be appropriate if
departments were lightly loaded. Similarly, a layout
that is effective when processing/arrival times are
highly variable may not be appropriate if
processing/arrival times were deterministic.
Generally speaking, layouts that reduce travel time
variability are more desirable when department
utilization is high or variability in either
interarrival or processing times is low. When
either department utilization is low or
processing/demand variability is high, minimizing
average travel times becomes more important.
However, definite guidelines are difficult to
identify because of the many interacting parameters.
Therefore, an evaluation of the queueing model will
often be required to generate an accurate layout
ranking.
Table 1 The effect of utilization on the
relative desirability of layouts
2
(Ca_{0
}= 1,
Cs^{2}_{i
}
= 1,
D
= 1.62 parts/hr)
E(Si)

E(WIP(x1))

E(WIP(x2))

32 min 
25.76 
20.55 
33 min 
30.55 
26.18 
34 min 
38.44 
35.51 
35 min 
53.99 
54.02 
36 min 
99.33 
108.20 
37 min 
2,588 
3,088 
Table 2 The effect of variability on the
relative desirability of layouts
(E(S_{i})
= 35 min,
D
= 1.62 parts/hour)
A special instance when minimizing average
travel time also minimizes average workin
Variability coefficients 
E(WIP(x1))

E(WIP(x2))

(Ca0
2
= 1,
Csi
2
= 0.5) 
38.75 
47.24 
(Ca0
2
= 1,
Csi
2
= 1) 
53.99 
54.02 
(Ca0
2
= 1,
Csi
2
= 2) 
86.41 
84.47 
(Ca0
2
= 2,
Csi
2
= 2) 
95.02 
92.96 
2
process is when
Ca^{2
}
_{i }
=
Cs^{2
}
_{i }
=
Ca^{2
}
_{t }
=
Cs_{t
}
= 1 for all
i
= 0, 1, …,
M + 1.
This is the case when the processing times,
interarrival times, and travel times are all
exponentially distributed. Average
workinprocess can then be shown to be a
function of only the utilization levels.
Therefore, a
layout that minimizes the utilization of the
transporter, ρ
_{t},
also minimizes average workinprocess. Since ρ
_{t}
is a linear transformation of average travel
time, minimizing average travel time minimizes ρ
_{t}.
Finally, we should note that in addition to
affecting workinprocess and lead time, the
choice of layout determines production capacity.
The stability condition ρ
_{t }
< 1 puts a limit on the
maximum feasible number of unit transfer loads
per unit time that can be moved by the
transporter. This limit, λ
_{max},
is given by
M
+1
MM
+1
λ
_{max}
= 1/
∑∑∑
prij(∑∑∑
xrkxilxjs(dkl
+
dls))/v,
(25)
r
=1
i
=0
j
=1
kls
which is clearly a function of the
transportation distances and the distribution of
transportation times. By limiting λ
_{max }
, the maximum achievable output rate from the
system is limited. This
means that the choice of layout could directly
affect the available production capacity.
Maximizing throughput by maximizing λ
_{max}
could be used as an alternative layout design
criterion. In this
case, layouts would be chosen so that the
available material handling capacity is
maximized. Such a design criterion could be
appropriate in high volume/maketostock
environments where minimizing lead time or
workinprocess is not critical.
The stability condition can also be used to
determine the minimum required number of
transporters,
n_{min},
for a given material handling workload, λ
_{t}:
M
+1
MM
+1
n_{min}
= λ
_{t }
∑∑∑
prij(∑∑∑
xrkxilxjs(dkl
+
dls))/v.
(26)
r
=1
i
=0
j
=1
kls
Similarly, we could obtain the minimum required
transporter speed, for a fixed number of
transporters, or the minimum required transfer
batch size. Note that in determining these
feasibility requirements, we account for both
full and empty travel by the material handling
device.
6.
Discussion and Conclusion
In this paper, we presented a formulation of the
plant layout problem where the objective is to
minimize workinprocess. We used the model to
explore the relationship between layout
configuration and operational performance. We
showed that the conventional criterion of
selecting layouts based on average material
handling distances can be a poor indicator of
queueing effects. In a series of
counterintuitive observations, we showed that
the conventional QAP formulation can lead to the
selection of very different layouts from those
obtained using the queueingbased model. In
particular, our analysis highlighted the
important effect that variance in material
handling times plays in determining layout
desirability. This effect is ignored in
conventional layout procedures. We also showed
that nonmaterial handling factors, such as
processing time variability or process
utilization, can directly affect layout
performance.
Certain simplifying assumptions we have made in
our current queueing model are easy to relax.
For example, the model can be extended to allow
for multiple transporters and multiple
processing units at each department.
Approximations for GI/G/n queues would simply
have to be used (see [3, 17]) for details).
Similarly, the assumptions of deterministic
distances between pairs of departments and
deterministic transporter speed can be
eliminated. Accounting for variability in these
two parameters can be easily accommodated by
appropriately modifying the second moment of
transportation time. Other assumptions are,
however, more difficult to relax. This includes,
for example, the modeling of control policies
other than FCFS for either routing transporters
or for sequencing products. In these cases,
simulation may be the only practical approach.
Our queueing model is based on known
approximations of GI/G/1 queues. While these
approximations are fairly robust, more
customized approximations could be constructed
for specific applications [3]. However, we
should note that the usefulness of the queueing
model is not as much in its accuracy, as it is
in its ability to capture key effects in the
relationship between layout and operational
performance and in its ability to lead to
consistent rankings of different layout
alternatives. More importantly, it is a tool
that can be used at the design stage to rapidly
evaluate a large number of alternatives, a task
that may be difficult to achieve using
simulation.
The queueing model also offers an opportunity to
design simultaneously the layout and the
material
handling system (e.g., determining the number of
transporters, transporter speed, travel paths,
etc.) and to examine the effect of both on
expected WIP. The ability to evaluate layout and
material handling concurrently is indeed absent
from most existing layout procedures.
Several avenues for future research are
possible. Better analytical approximations
should be developed to take advantage of the
special structure of the layout problem. Either
analytical or simulation models that account for
different routing and dispatching policies of
the material handling system should be
constructed. These models should then be used to
study the effect of different policies on layout
performance. Furthermore, it would be useful to
use the queueing model to evaluate and compare
the performance of different classical layout
configurations, such as product, process, and
cellular layouts, under varying conditions. This
may lead to identifying new configurations that
are more effective in achieving short lead times
and small WIP levels. In previous sections, we
have argued that variance in travel distances is
as important as the mean of these distances.
Therefore, identifying configurations that
minimize both mean and variance is important.
Examples of such layouts, as shown in Figure 3,
could include a Star layout, where departments
are equidistant from each other, or a
HubandSpoke layout, where each hub consists of
several equidistant departments and is serviced
by a dedicated transporter.
Acknowledgement:
The author's research is supported by the
National Science Foundation under grant No.
DMII9309631, the U.S. Department of
Transportation under grant No.
USDOT/DTRS93G0017, and the University of
Minnesota Graduate School.
References
[1] Armour, F. C. and E. S. Buffa, "A Heuristic
Algorithm and Simulation Approach to Relative
Location of Facilities,"
Management Science,
10,
294309, 1963.
[2] Benjaafar, S. and M. Sheikhzadeh, "Design of
Stochastic Plant Layouts,"
IIE Transactions,
in press.
[3] Buzacott, J. A. and J. G. Shanthikumar,
Stochastic Models of Manufacturing Systems,
Prentice Hall, Englewood Cliffs, New Jersey,
1993.
[4] Fu, M. C. and B. K. Kaku, "Minimizing
WorkinProcess and Material Handling in the
Facilities Layout Problem,"
IIE Transactions,
29,
1, 2936, 1997.
[5] Fu, M. C. and B. K. Kaku, "Minimizing
WorkinProcess and Material Handling in the
Facilities Layout Problem," Technical Report TR
9541, University of Maryland, College Park,
Institute for Systems Research, 1995.
[6] Foulds, L. R., "Techniques for Facilities
Layout: Deciding which Pairs of Activities
Should be Adjacent,"
Management Science,
29,
12, 14141426, 1983.
[7] Johnson, M. E. and M. L. Brandeau, "An
Analytic Model for Design and Analysis of Single
Vehicle Asynchronous Material Handling Systems,"
Transportation Science,
28,
4, 337353, 1994.
[8] Johnson, M. E. and M. L. Brandeau,
"Stochastic Modeling for Automated Material
Handling System Design and Control,"
Transportation Science,
30,
4, 330350, 1996.
[9] Johnson, M. E. and M. L. Brandeau, "An
Analytic Model for Design of a Multivehicle
Automated Guided Vehicle System,"
Management Science,
39,
12, 14771489, 1993.
[10] Kouvelis, P. and A. S. Kiran, "The Plant
Layout Problem in Automated Manufacturing
Systems,"
Annals of Operations Research,
26,
397412, 1990.
[11] Kusiak A. and S. S. Heragu, "The Facility
Layout Problem,"
European Journal of Operational Research,
27,
229251, 1987.
[12] Li, W. and J. M. Smith, "Stochastic
Quadratic Assignment Problems," in
Quadratic Assignment and Related Problems,
Editors: P. Pardalos and H. Wolkowicz, American
Mathematical Society, DIMACS Series in Discrete
Mathematics, 221236, 1994.
[13] Little, J. D. C., "A Proof of the Queueing
Formula
L
=
λ
W,"
Operations Research,
9,
383387, 1961.
[14] Meller, R. and K. Y. Gau, "The Facility
Layout Problem: Recent and Emerging Trends and
Perspectives,"
Journal of Manufacturing Systems,
15,
5, 351366, 1996.
[15] Pardalos, P. and H. Wolkowicz (Editors),
Quadratic Assignment and Related Problems,
American Mathematical Society, DIMACS Series in
Discrete Mathematics, 221236, 1994.
[16] Thonemann, U. W. and M. L. Brandeau,
"Designing a Single Vehicle Automated Guided
Vehicle System with Multiple Load Capacity,"
Transportation Science,
30,
4, 330350, 1996.
[17] Whitt, W., "Approximations for the GI/G/m
queue,"
Production and Operations Management,
2,
2, 114161, 1993.
[18] Whitt, W., "The Queueing Network Analyzer,"
Bell System Technical Journal,
62,
9, 1983.