S.C. Graves et al., Eds., Handbooks in OR & MS, Vo'l.

4
© 1993 Elsevier Science Publishers B.V. All rights reserved.

Chapter 5

Performance Evaluation of Production Networks

Rajan Suri and Jerry L. Sanders

Universi O, of Wisconsin-Madison, Department of lndustrial Engineering,
1513, University Avenue, Madison, W1 53706, U.S.A.

Manjunath Kamath
Oklahoma State University, School of b~dustrial Engineering and Management,
322 Engineering North, Stillwater, OK 74078, U.S.A.

1. Introduction

1.1. M o t i v a t i o n : The role o f p e r f o r m a n c e evaluation

The decade of the 1980s has brought with it the widespread recognition of
the importance of manufacturing in maintaining a firm's competitiveness
[Hayes, Wheelwright & Clark, 1988; Dertouzos, Lester & Solow, 1989]. As a
result, most industrial corporations are now devoting a lot of effort to
constantly improving their manufacturing methods and systems. Effective
analysis and improvement of manufacturing systems has thus become an
important activity in the survival of the modern firm. During the lifetime of a
particular manufacturing facility, the firm responsible for it goes through many
phases of decision making, from an analysis of initial feasibility through
detailed design of the facility, installation and startup, operation of the system,
ongoing improvements, and finally obsolescence of the facility [Suri, 1988a].
Typical decisions that must be made for a manufacturing system include: the
products to be manufactured, the number and types of equipment to be used,
process plans and part routings, tooling and fixtures, material handling meth-
ods including number and types of transporters, facility tayout, and buffer
sizes. Typical performance measures used to evaluate these decisions include
physical measures such as production rates, equipment utilization, work in
process, and part flow times, as weil as financial measures such as return on
investment, payback period, and net present valuc. As a starting definition of
performance evaluation (PE) we say it is 'a methodology (including techniques
and tools) for determining the performance measures that can be expected to
result from a given set of decisions'.
Of course, manufacturing systems analysis is not a new field. The use of
factories for manufacturing has been weil established since the industrial

199
200 R. Suri et al.

revolution, and as any industrial engineer knows, the formal study of manufac-
turing systems is at least as old as Taylor's studies begun in the 1880s [Emerson
& Naehring, 1988]. A modern manufacturing system, however, can be quite
different from the more traditional system. It is most offen a complex system
consisting of many interconnected components of hardware and software. Due
to this greater complexity, decision making for such a system can be very
difficult compared to, say, a traditional job shop. This complexity is due to
several factors that are elaborated in Suri [1988a], but briefly they are: the high
degree of interconnection and integration, leading to 'global' effects of seem-
ingly 'local' decisions; increased sharing of resources in order to improve
efficiency; little 'slack' in the system; and fewer 'humans in the loop'. Because
of such factors, even experienced manufacturing personnel have difficulty in
perceiving the consequences of a given decision. For such systems, the role of
PE as defined above becomes even more critical in providing techniques and
tools which will aid manufacturing managers in making their decisions while
attempting to achieve their goals with respect to performance measures such as
those above.
In order to keep the preceding comments in line with modern manufacturing
concepts, it should be mentioned that at the same time there is a trend to
reduce complexity in manufacturing [e.g., see Schonberger, 1982]. In other
words, an alternative view one might take is to question the need for
complexity, and try to reduce it, rather than simply provide tools to analyze
and deal with the complex systems [Suri & Shimizu, 1989]. In view of this one
might ask whether this trend would eliminate the need for many of the
modeling approaches discussed in this article and elsewhere in this Handbook.
Indeed this raises an issue that is critical to the success of research and
development in this applications area. In order to build on and improve the
modeling approaches described below, for PE of manufacturing systems, it is
not enough for the analyst to have an understanding of modeling techniques
such as stochastic processes and queueing theory. It is necessary that the
analyst has a good understanding of manufacturing systems too. In fact, it is
suggested in Suri [1988a] that many of the recent fundamental developments in
manufacturing systems have come from outside the traditional analysis com-
munity, and part of the reason for this may have been a preoccupation with
modeling rather than a concern for the underlying manufacturing issues. As
authors of a basic chapter on this topic, we feel a great responsibility to
communicate to potential researchers in this field the importance of maintain-
ing a strong connection with actual manufacturing systems while working on
models and techniques for PE of these systems.
Returning now to the question posed above, namely, the relevance of
various analysis approaches in light of the trend to simplicity, this is discussed
in detail in Suri [1988a]. Also discussed is the trend towards just-in-time (JIT)
systems and its impact on the need and relevance of analysis. It is shown there
that, with appropriate understanding of the new issues that emerge with these
trends, PE techniques and tools can be used to complement and improve the
 Ch. 5. Performance Evaluation 201

application of these trends, rather than be displaced by them. On the other

hand, examples are also given to show that ignoring the ultimate needs of the
manufacturing enterprise can lead to a whole generation of models and journal
publications that become irrelevant to the very subject they purport to assist.

1.2. Overview of PE approaches

The title of this chapter refers to 'production networks' (PN). This terminol-
ogy is nonstandard, but intentional, in order to clarify the class of manufactur-
ing systems what we address. In general terms, they fall into the category of
discrete manufacturing systems, where products are worked on individually or
in 'batches' (as opposed to continuous systems such as an oil refinery or
chemical processing plant), and furthermore to systems where products tend to
visit several different workstations, in varying sequences, before they are
completed. Thus the system can be viewed as a 'network' of workstations:
hence the term PN.
We should also clarify the approaches that we will cover under the topic of
PE. In order to do this, it is useful to introduce a classification of methods.
Broadly speaking, the main approaches to PE of discrete manufacturing
systems can be placed in three categories.
(i) Static (allocation) models. These simply add up the total amount of work
allotted to each resource, and estimate the performance from these totals. Such
a model tends to be somewhat simple as it ignores most of the dynamics,
interactions, and uncertainties typically seen in a manufacturing system. How-
ever, it can be useful as a rough initial estimator of system size and per-
formance. For example, the 'rough cut capacity planning' module of a typical
material requirements planning (MRP) system uses such an approach. Many
planning analyses are also based on such a model, orten enhanced with Linear
Programming techniques to optimize the decisions in the model. For example,
such a model could be used for selecting the product mix and corresponding
equipment to maximize profit based on a budget constraint. Usually, due to the
use of mathematical programming methods in conjunction with the models,
such models fall in the realm of deterministic optimization methods, and also
do not exploit the 'network structure' of the manufacturing system, so they will
not .be covered in this chapter. See Chapter 8 for more on these approaches.
(ii) Aggregate dynamic models (ADMs). Such models do account for some
of the dynamics, interactions, and uncertainties in the system, but in an
aggregate way. Typically, they use analytical techniques from stochastic pro n
cesses, queueing theory, queueing networks, and reliability theory. Some of
the assumptions in these models may be restrictive for certain manufacturing
configurations. The performance measures estimated are often only the steady
state averages. Still, these models tend to give reasonable estimates of per-
formance and (relative to alternative approaches) are very efficient. There have
been major advances in the development and application of these models in
the last two decades, and they are becoming popular in industry for rapid
202 R. Suri et al.

decision making. More background and perspective will be given on these

below as they are the subject of this chapter.
(iii) Detailed dynamic models. These approaches model the manufacturing
system in considerable detail, in some cases, to the level of detail desired by
the analyst. They can be further divided into two categories: deterrninistic and
stochastic. Detailed deterministic models include scheduling approaches [e.g.,
see Graves, 1981 for a review] and Petri Nets [Kamath & Viswanadham, 1986].
Detailed stochastic models include Monte Carlo simulation [Law & Haider,
1989] and stochastic Petri Nets [Balbo, Chiola & Franceschinis, 1989]. Simula-
tion models deserve special mention since simulation is becoming a widely used
tool in industry. In the current context, this refers to computer-based discrete
event simulation. These models can mimic the operation of the system in as
much detail as required by the analyst. Thus they can be made very accurate,
but the price to be paid is in terms of model development time and computer
time each time the model is run. Combined with visual animation, these
models can be powerful tools for communicating the results of an analysis.
Still, for industrial problems, such an approach typically requires one to three
orders of magnitude more effort than a queueing model, as shown by actual
case studies [Anderson, 1987; Brown, 1988]. This is a major reason behind the
development and extension of the analytical models discussed in the body of
this chapter. Related to simulation approaches are the emerging sample-path
based approaches such as perturbation analysis (see Suri [1989a] for an
up-to-date review) and likelihood ratio methods [Glynn, 1989; Reiman &
Weiss, 1989; Rubinstein, 1989] which provide efficient means for sensitivity
analysis of the detailed dynamic models; sensitivity analysis can be a valuable
addition to a PE study.
Further discussion on the above categorization, as well as an extensive set of
references on performance evaluation of discrete manufacturing systems can
also be found in a recent survey by Leung & Suri [1990]. In addition, two
recent books on this subject are Buzacott & Shanthikumar [1992b] and
Viswanadham & Narahari [1992].

1.3. A i m s and scope o f the chapter

T h e aims of this chapter are: (i) to serve as an advanced introduction to the

s u b j e c t - f o r example, it could be the starting point for a researcher or
graduate student beginning work on this topic, or it could be used to
accompany a graduate course in this area; (il) to provide a fairly exhaustive
view of the subject, along with an organization that assists the reader in
comprehending the field; and (iii) to serve as an up-to-date reference for
teachers, researchers and practitioners of operations research and management
science.
In terms of scope of the chapter, using the classification above, we will deal
primarily with ADMs. Our reason for focusing on ADMs is, in the context of
this chapter and its potential educational use, our firm belief that they
 Ch. 5. Performance Evaluation 203

represent a class of methods that will occupy a significant portion of the PE

methodology in the coming decade. The forces behind this are, first, the fact
that analytical models usually provide more insight and understanding of a
system (as contrasted with, say, simulation models), and second, they enable
rapid PE of alternative decisions, a fact that results in significant strategic
advantage (both these points are elaborated below). A final reason for not
spending time on the other approaches is that some of them are covered in
depth in the other chapters in this Handbook.
As an additional comment on the scope of the chapter, using the classifica-
tion in Suri [1985a], our view of PE is that it is concerned mainly with
evaluative models, i.e., those that predict system performance given a set of
decisions, as opposed to generative models, which find a set of decisions to
meer a given set of performance criteria.
Several articles identify a correspondence between the three major modeling
approaches above and the stages of manufacturing decision making. Specifical-
ly, they can be related, respectively, to feasibility studies, aggregate decisions,
and detailed decisions- see, e.g., Stecke [1985], Suri [1985b], and Gershwin,
Hildebrant, Mitter & Suri [1986]. These decisions could refer to either the
design phase or the operation phase of a facility [Suri, 1988@ For instance, in
the operation phase they might refer to decisions with a time horizon of
(respectively) years, weeks to months, and minutes to days. A decision support
system that integrates various phases of decision making should ideally com-
bine these various approaches and use the one appropriate to the particular
decision being reviewed. Such a hierarchicaI approach has been suggested by
several authors [e.g., see Hax & Meal, 1975; Kimemia & Gershwin, 1983; Suri
& Whitney, 1984; Gershwin, Hildebrant, Mitter & Suri, 1986, and Stecke,
1985]. As we are concerned only with one of the modeling approaches, we will
not consider such hierarchical approaches, except for two special cases:
hierarchical queueing network models, and integrated modeling environments,
both covered in Section 8. A current review of hierarchical approaches can be
found in Chapter 10.

1.4. A perspective on the development and use of aggregate dynamic mode&

The development of ADMs for manufacturing dates back to a few seminal

papers by Koenigsberg for cyclic systems (see the review in Koenigsberg
[1982]) and Jackson [1963] for job shops. These models were developed as
attempts to provide analytic formulas that would predict the performance of
manufacturing systems. As such, some initial successes were achieved. For
example, as we will discuss later, the work of Jackson [1963] showed that under
suitable assumptions the performance of a complex job shop could be pre-
dicted just from available formulas for single queues. Despite some of this
progress, these models gained popularity only in the academic and research
world, and, due to the perceived restrictive nature of some of the assumptions
in the models, they did not find their way into the mainstream of manufactur-
204 R. Suri et al.

ing analysis in industry. In particular, they were viewed as overly theoretical

and less accurate tools than, say, simulation models. This situation has changed
considerably in the last few years. For one, similar models have enjoyed over a
decade of success in the field of computer systems performance modeling-
there are whole textbooks on this topic, such as Sauer & Chandy [1981], and
many available software tools [e.g., see BGS Systems, 1982, and Lazowska,
Zahorjan, Graham & Sevcik, 1984]. A second, more important factor is that it
has now been recognized how, especially in the competitive environment of
modern manufacturing, ADMs can play a strategically important role. The key
lies in the fact that ADMs allow rapid analysis of many different manufacturing
alternatives, enabling a firm to constantly explore ways of remaining competi-
tive, and also enabling the firm to make rapid decisions and gain greater
decision leverage [Suri, 1989b]. This remains true even though ADMs provide
a more 'rough' analysis than, say, simulations [Suri & Diehl, 1987]. As noted in
Suri [1989b], the role of ADMs is to provide insight on the key factors in a day
or so, as compared with a detailed analysis of all the factors that may weil take
a few months. This has impact on both the design and the operation phases of
manufacturing systems. In the design of a new facility, such a rapid analysis can
provide early feedback to the process and equipment designers. In the oper-
ation of an existing plant, it can lead to bettet planning decisions and
exploration of many alternative operating options. Finally, ADMs have been
shown to support modern competitive manufacturing strategies such as Time-
Based Competition and Kaizen [Suri & DeTreville, 1991, 1992]. With this
recognition, recently ADMs have seen a marked increase in use in industry: as
examples of this, Alcoa and IBM have used ADMs effectively in the design of
new factories [Nymon, 1987; Brown, 1988], and DEC, Pratt & Whitney, and
Siemens have used ADMs in improving their operational decisions [Anderson,
1987; Harper & O'Loughlin, 1987; Suri, 1988b].

1.5. Classification o f systems

While detailed explanation of the classifications will be given in the sections

that follow, we give a brief overview of the main categories here. An ADM in
its simplest form consists of a set of stations, each of which may have one or
more servers, and a set of jobs that visit the stätions requiring service. This
models a manufacturing system where each station represents a set of function-
ally identical resources (such as machines, operators, cranes, etc.), which we
will henceforth just call 'servers', and each job represents a workpiece or batch
of workpieces. The workpieces have a specified routing which requires them to
visit the stations in a given sequence, requiring operations to be performed on
them from orte of the servers at the station visited, and the operation times at
each station are also specified. These specifications need not be deterministic;
they may be in terms of parameters of probability distributions, for example, if
machine failures are to be modeled. Thus a job is characterized by its (possibly
stochastic) routing and service times. The network model may be 'open', which
 Ch. 5. Performance Evaluation 205

means that jobs arrive from an external source and depart from the network
when completed, or it may be 'closed' which means that a fixed number of jobs
circulates in the network. The model may be 'single class' which means that all
jobs are assumed to be statistically identical (in terms of their routing and
service requirements), or it may be 'multiple class' where each class of jobs has
its own characteristics. A multiple class model may have some classes open and
other closed, in which case the network is called 'mixed'. Each station is
characterized by the number of servers, the maximum queue space available
('finite buffer') or 'infinite buffer' if queue space is assumed to be unlimited,
the service discipline, e.g., first-come-first-serve (FCFS) or shortest processing
time (SPT). A special case is a 'tandem' network in which all the jobs enter the
system at the first station, visit each station in order, and leave the system after
visiting the last station. While many additional classifications exist, this will
serve as an introduction to the main categories.

1.6. Overview of typical analysis outputs

Except for the simplest of systems, ADMs usually provide estimates only of
steady state performance measures (PMs), and orten just average values are
estimated (as opposed to say, entire distributions, or a 95% percentile, etc.).
The PMs estimated fall primarily into the category of physical PMs rather than
financial PMs. This chapter will deal only with physical PMs. Typical PMs
estimated by an A D M include (all of these are steady state averages):
utilization of each server; throughput (of production rate); flow time of a job
through the system; queue length at a station; and work-in-process (WIP) in
the system. These are among the primary physical PMs of interest to manufac-
turing personnel and, eren though only steady state average values are
estimated, they can be quite valuable in manufacturing decision making
[Brown, 1988; Suri, 1989b].

1.7. Structure of the chapter

We begin in Section 2 by studying a single workcenter with multiple identical

machines. This 'single queue system' has been the starting point for analytical
results on production networks, and also serves as a building block for more
complex systems. At the beginning of that section we also establish the main
notational conventions which will be used throughout the chapter. Then we
cover the results for a large number of cases of this single queue system, many
of which are then referenced later in the chapter. Section 3 considers the
simplest topological configuration of a n e t w o r k - a tandem production line.
Section 4 covers tree-structured manufacturing systems, also known as assem-
bly networks. Sections 5 and 6 survey open networks and closed networks,
respectively, allowing for general network structures. Then, Section 7 consid-
ers, for the first time, multiple levels of resources: in tlais case, queueing for
machines and operators (also known as machine-operator interference
206 R. Suri et al.

models). Finally, Section 8 gives an overview of certain advanced topics and

mentions potential research areas.

2. W o r k c e n t e r with identical machines and a single queue

2.1, System definition

In this section, we consider queueing models of a workcenter consisting of

identical machines. The machines are identical in that each can process any of
the arriving jobs and we assume here that they do so one at a time. Jobs arrive
at the workcenter from external sources, and if all machines are busy process-
ing jobs, the arriving job has to wait. Jobs waiting for service form a single
queue which feeds all machines (see Figure 2.1). When a machine finishes the
processing of its current job, it chooses another job from those that are
waiting, in accordance with a prescribed scheduling discipline. A commonly
employed scheduling discipline is FCFS (first-come-first-served), where jobs
are served by the workcenter in the order of their arrival.
The study of this single queue system is useful and interesting for two major
reasons. First, this simple queueing system is the starting point for all analysis.
Hence, a large body of results is available for this system. Understanding the
dynamics of the queueing phenomenon is easier in the context of this simple
model. Secondly, this simple queueing system is a building block for most

WORKCENTER WlTH
m IDENTICALMACHINES

WAITING AREA ] L
(C2~MMON BUFFEI]) I

Jobs Jobs
arriving Jobs waiting ! Departing
for machineservice

Jobs being processed

Fig. 2.1. A workcenter with identical machines and a single queue.
 Ch. 5. Performance Evaluation 207

other analyses. For example, the task of modeling and analyzing production
systems usually involves systems having multiple resources (workcenters, trans-
porters, robots, etc.). This complex structure of multiple interacting resources
can be modeled using queueing networks (see Sections 5 and 6). Several useful
analysis techniques have been developed for queueing networks by incorporat-
ing simple single queue models as submodels in queueing network models.
T h e queueing system described above can be characterized using a standard
shorthand form, A / S / m / N / K / Z , known as Kendall's notation. In this nota-
tion, A specifies the interarrival-time distribution, S the service-time dis-
tribution or the probability distribution for the time it takes to process a job, rn
the number of parallel (identical) servers or machines, N the restriction on
system capacity or the maximum number of jobs (waiting and being processed)
that can be simultaneously present in the workcenter, K the size of the external
source or calling population, and Z the scheduling or service discipline. It is
c o m m o n practice to omit the symbol N if no restriction is imposed on system
capacity and symbol K if the calling population is infinite. If the scheduling
discipline is FCFS then the symbol Z is usually omitted. Some standard
symbols for the interarrival-time and service-time distributions are:
M = Exponential (Markovian) distribution,
D = Deterministic (constant time),
Eh = Ertang type k (k = 1, 2 . . . . ),
H~ = Hyperexponential distribution of order k (k = 1,2 . . . . ),
G = General (an arbitrarily specified distribution).
A symbol GI offen used to specify interarrival times is a shorthand for
'General, Independently distributed interarrival times'. When the interarrival-
time distribution is exponential, the arrival process is a Poisson process and we
say the queue has Poisson arrivals.

Example. The queue M / D / 2 / 1 0 represents a work center with two identical

machines where the arrival process is Poisson, the processing time for all jobs
is the same fixed (deterministic) value, a maximum of ten jobs can be present
in the system at a time, the source of jobs is infinite, and the scheduling
discipline is FCFS.

Notation. We use the following notation. The squared coefficient of variation

(SCV) of a random variable (r.v.) is defined as the variance of the r.v. divided
by the square of its mean. Hereafter, 'system' includes the workcenter and
buffer.

{Input or given quantities}

m : number of machines in the workcenter,
N : maximum number of jobs allowed in the system,
A : mean arrival rate of jobs to the system,
2
c« - interarrival-time SCV,
208 R. Suri et al.

~- " mean service time of a job at a machine,

2
c, • service-time SCV.
{Output or computed q u a n t i t i e s - a l l are steady-state performance measures}
p : utilization of a machine,
2
c a : interdeparture-time SCV,
p,, : probability that there are n jobs in the system,
q, • probability that an arriving job sees n jobs in the system,
Lq : average number of jobs waiting (in the buffer) for service,
L " average number of jobs in the system,
Wc • average time a job spends waiting (in the buffer) before beginning service,
W : average time spent by a job in the system from arrival to departure.
Additional notation will be defined as needed.

Departure process. Information about the discharge or departure process of a

workcenter queueing model can be useful if the workcenter is a part of a
manufacturing network. In this case if, after visiting this workcenter, jobs are
required to visit other workcenters, then the departures from this workcenter
will b e c o m e arrivals to other workcenters. As we will see later in this chapter,
departure process information plays a key role in the development of analysis
techniques for certain general network models.

General service-time distributions. The assumption of exponential service

times makes an exact analysis of single queue models possible in most cases.
H e n c e , a majority of the queueing models used to analyze modern production
networks make this assumption. This assumption is usually not satisfied by
production systems such as a flexible manufacturing system (FMS) in which the
machining times are known quite accurately. Another example is an automatic
assembly station in which the assembly time is typically fixed (deterministic)
except when a station 'jam' occurs, when a repair process is required. In such
cases the exponential service-time models offen do not represent reality
faithfully, and the analysis using an exponential assumption can sometimes be
misleading especially when the service time SCV is near zero or larger than the
1.0 value for the exponential distribution [e.g., see Kamath & Sanders, 1987].
Some recently developed tools and techniques for analyzing production sys-
tems [Buzacott & Shanthikumar, 1985; Kamath, Suri & Sanders, 1988; Segal &
Whitt, 1989] use queueing models such as the G I / G / 1 and G I / G / m queues
that allow non-exponential service time distributions. It should be noted that
the assumption of exponential service times is only one of the assumptions that
is typically made when production networks are analyzed using queueing
models; some of the other common assumptions concern the arrival process,
scheduling discipline, and queue capacity.

For the discussion in Sections 2.2 and 2.3 we will assume that the scheduling
discipline is FCFS and source is infinite. In Section 2.2 we consider systems
 Ch. 5. Performance Evaluation 209

with no restrictions imposed on the capacity, that is, N = o c . Section 2.3

contains results for systems with a finite buffer or finite N. In both sections,
single-serve systems (m = 1) are considered separately. In Section 2.4 we
present some results for systems where the source is finite. We conclude
Section 2 with a brief discussion of results for non-FCFS queueing disciplines.

2.2. Systems without buffer constraints

In this section, we consider systems with no restrictions imposed on the

buffer capacity, i.e., N = ~. We start by reviewing some general relations that
hold for these systems.

General relations. The following relations hold for a parallel server queueing
system for general interarrival-time and service-time distributions. That is, for
a G / G / m queue (m >~ 1), we have [Tijms, 1988]
AT
p = -- (G/G/m), (2.t)

W = Wc + r (G/G/m), (2.2)

L = Lq + mp (G/G/m). (2.3)

The machine utilization P is usually less than 1.

Little's formula [Little, 1961; Stidham, 1974], possibly the most widely used
result in queueing theory, relates mean arrival rate, average system time, and
average number of customers (jobs) in a queueing system. For a queueing
system, Little's result simply states that

Average number o f customers in system = (Mean arrival rate)

x (Average system t i m e ) .

If any two of these quantities are known, the third is äutomaticaily determined.
For a G / G / m queue we have

L = AW. (2.4)

Applying Little's result to the jobs waiting in the buffer, we obtain

L« = awq. (2.s)

Note. Multiplying both sides of relation (2.2) by A and using Little's result
yields relation (2.3). The quantity mp is the average number of jobs in service.
H e n c e , relation (2.1) can be obtained by applying Little's result to jobs in
service.
 210 R. Suri et al.

For most queueing systems discussed below, we give an exact formula or an

approximation only for Wc, which is the average waiting time of jobs before
beginning service. The related congestion measures, Lq, W, and L can be
easily obtained by applying Little's result, Equation (2.5) and general relations
(2.2) and (2.3).

2.2.1. Single-server queues

A useful relation for general single-server queues ( G / G / l ) concerns the
server utilization and the probability that the queueing system is empty.

Po = 1 - p (G/G/l). (2.6)

The M / M / 1 queue. The most basic and widely used single-server model is the
M/M/1 queue. The interarrival times and service times are exponentially
distributed with means 1/A and ~-, respectively. Owing to the memoryless (or
Markovian) property of the exponential distribution, an exact analysis of this
queue is possible and a complete set of results can be found in standard texts
on queueing [Gross & Harris, 1985; Kleinrock, 1975]. We present below
formulas for the steady-state performance measures for this queue. Assurne
p < 1 here.
The machine utilization is given by the general equation (2.1). The average
waiting time of jobs is given by

W q - l _ ~Pp (M/M/l). (2.7)

The steady-state probability that there are n jobs in the system is

pù=(1-p)p", n>~O (M/M/l). (2.8)

Erlangian and hyperexponential queueing models. We shall consider in this

section single server queueing models where the interarrival times (or service
times) are Erlang type k (Ek) or hyperexponentially (Hk) distributed. These
probability distributions have a greater modeling flexibility than the exponen-
tial distribution. It is convenient to consider the Erlang type k as being made
up of k identical exponential phases, although the arrival or service mechanism
may not actually contain a sequence of phases. When k = 1 we have an
exponential distribution (SCV= 1) and as k approaches ~, the Erlang becomes
deterministic (SCV=0). Hence, the Erlang type k distribution can model
situations with SCV ~<1. The hyperexponential distribution is a mixture of
exponentials of different means and always has a SCV >/1.
For the Erlang service model, M / E J 1 , and Erlang arrival model, Ek/M/1,
exact analysis is possible by treating the Erlang as a sum of exponential phases.
In the Erlang service model, the average waiting time of jobs is
 Ch. 5. Performance Evaluation 211

k+l rp
Wq- 2k (l-p) (M/EJ1). (2.9)

Additional results for this model and formulas for the Erlang arrival model can
be found in Gross & Harris [1985].
An approach usually referred to as the method of phases or stages, approxi-
mates a general interarrival-time (or service-time) distribution by one that is
built up from a combination of Erlang and hyperexponential components (e.g.,
see Neuts [1981] for details).

The M / G / 1 queue. The M / G / 1 queueing model can be adapted to many

situations involving non-exponential service times. The arrivals are Poisson and
the distribution of service times (job processing times in our case) can be
arbitrary (but specified). However, an imbedded Markov chain [Gross &
Harris, 1985, pp. 252-254] can be constructed for the M / G / 1 queueing model
thus allowing the utilization of Markov-chain theory in the analysis. Formula
for the average waiting time of jobs is given below and its use is illustrated
next:

(l+c~~ (M/G/l). (2.10)

Equation (2.10) is often referred to as the Pollaczek-Khintchine (PK)

formula.

Automatic assembly station example. Consider an automatic assembly station

where all jobs require precisely the same assembly operation to be done, which
takes r time units. There is only one machine at this station and it is jam-free.
Assume that the jobs (assemblies) arrive according to a Poisson process with
rate A per unit time. The machine utilization p is given by Equation (2.1), and
is equal to AT (assume <1). As the machine is jam-free, there is no variation in
its service time, and hence the service time SCV is zero. The automatic
assembly station can be modeled by the M/D/1 queue, and the formula for
average waiting time follows from (2.10):

G=~1 (lr_~Pp) (M/D/l) (2.11)

If we had made the assumption that the service time is exponential (as pointed
out earlier, a common assumption) then we would have used equation (2.7) to
calculate the average waiting time which yields a value for the waiting time that
is exactly twice the value given by Equation (2.11). Hence, an exponential
assumption would give rise to 100% error in the value of the waiting time as
weil as work-in-process (WIP) in this case. Note that the exponential assump-
tion leads to a service time SCV of 1.0. This simple example brings not only
212 R. Suri et al.

the effect of the service-time variability on the waiting time and queue length,
but also the need to correctly model the service-time variability.

The G I / G / 1 queue. In general the GI/G/1 queue, in which the interarrival

and service times both have general probability distributions, is very difficult to
analyze. Early work on the G I / G / 1 queue includes that of Lindley [1952] who
published an integral equation for the stationary distribution of the waiting
time in queue of an arbitrary customer. However, Lindley's work yielded
useful analytical solutions only in some special cases. Over the last twenty-five
years considerable effort has been devoted to the development of approxi-
mations and inequalities for the G I / G / 1 queue. The works of Kingman [1962[
and Marshall [1968] laid the foundation for the development of approximations
for the G I / G / 1 queue. The interested reader is referred to Gelenbe & Pujolle
[1987], Kobayashi [1974], Marchal [1985], Reiser & Kobayashi [1974], Shan-
thikumar & Buzacott [1980], and Tijms [1988] for details regarding various
approximations that have been proposed for the G I / G / 1 queue.
Next some G I / G / 1 approximations that require only the first two moments
of the inter-arrival-time and service-time distributions are presented. These
two-moment G I / G / 1 approximations are proving to be useful in developing
analysis methods for networks of queues with general service-time servers
[Kuehn, 1979; Whitt, 1983; Kamath, Suri & Sanders, 1988].
The mean arrival rate and the interarrival-time SCV are used to partially
characterize the general interarrival-time distribution, while the mean service
time and the service time SCV partially specify the service time process. It is
assumed that p < 1. The main congestion measure which is the average waiting
time (or delay in queue) is approximated by the simple formula [Kuehn, 1979;
Whitt, 1983; Shanthikumar & Buzacott, 1980]:

(« 2+ 2
a C~)( "l'p ~
(GI/G/1). (2.12)

The above expression is exact for the M/M/1 and M / G / 1 queueing modets.
When the arrival process is Poisson, that is, the interarrival-time distribution is
exponential, cä = 1, then (2.12) reduces to the PK formula (2.10) for the
M / G / 1 queueing model. If the service time distribution is also exponential,
c2 = 1 and (2.12) reduces to (2.7) for the M/M/1 model. A refinement of the
approximation for Wq developed by Kraemer & Langenbach-Belz [1976] which
yields improved approximations especially when c 2 < 1 is as follows:

2+2
w~ = gL---T-)L -~- - ~ ) (GI/G/1), (2.13)

2 c 2) is defined as
where g =- g(p, ca,
 Ch. 5. P e r f o r m a n c e Evaluation 213

l e x p;~--2-(- 1S-f pf -)- (1-c~) 2

~G2--+-~2) ,
2 < 1,
c,,

g("<" / / ,~ , (c,,-J) ~
[exp~-u-p) iT+~c2~) j ' c,,> l .

2
The factor g tends to be significantly less than 1 when p, c~, and G, are
relatively small [Whitt, 1985].
As we will see later in this chapter (Sections 5 and 6), the G I / G / 1 queueing
model forms the building block in the development of analysis techniques for
queueing networks with general service time servers. In a queueing network,
the departures from a node or a server often are arrivals to the other nodes in
the network. Hence, departure process results for the G I / G / 1 queueing model
will be useful in deriving information regarding these internal arrival processes.
The departure process of a G I / G / 1 queue is approximated by a renewal
process partially characterized by the first two moments of the interdeparture-
time. By flow conservation, the mean of the interdeparture-time is just the
mean of the interarrival-time, so that the departure rate equals the arrival rate.
2
The SCV the interdeparture time, c d, is given by
2 2 2
c d = c a + 2 p c« -
2
2(1 - p)AWq (GI/G/1). (2.14)

This expression is originally due to Marshall [1968].

Kuehn [1979] used formula (2.14) together with the simple approximation
for W q , (2.12), to yield the following approximation for the departure process
of a G I / G / 1 queue

c2
d = (1- P 2) G 2
+P
2G2 (GI/G/1). (2.15)

The interdeparture-time SCV as given by the above expression is just a convex

combination of the interarrival-time SCV and service-time SCV. Under light
load conditions (values of server utilization close to zero), Equation (2.15)
yields c 2 approximately equal to interarrival-time SCV, whereas under heavy
toad conditions (server utilization close to 1), when the server or machine is
almost always busy, Equation (2.15) gives cä approximately equal to service-
time SCV. This intuitively appealing expression was suggested as a direct
heuristic by Sevcik, Levy, Tripathi & Zahorjan [1977].

Just-in-time (JIT) example. The following example is from Suri [1988b]. In a

flexible workcell consisting of a single robot capable of working on a variety of
parts, raw material - at the rate of one lot every H hours - is delivered to the
cell on a JIT basis ffom a neighboring plant. However, because the deliveries
are never exactly on time, a standard deviation of S n hours around the delivery
time can be expected. Next, plotting a histogram of the cycle times for the
variety of parts the robot will make indicates that the average cycle time for a
214 R. Suri et al.

lot is C hours, and the standard deviation of the cycle times is Sc hours. By
using the simple formula (2.12) we can quickly determine a rough-cut answer
for the average waiting time for a lot at the cell. (Note: A = 1 / H , c2a= ( S n / H ) 2,
r = C, c~ = (Sc~C) 2, and p = C/H.)

(SH)2+(S«) 2
w~t= 2 -H-7~"

lot
Now, the average lead time for the lot is given by C + Wq .
Even the simple approximation presented above can provide insight in the
planning of a JIT implementation. Suppose the raw material is delivered once
each shift (H = 8 hours) and the analysis of part cycle times indicates that C = 6
hours and S c = 2 hours. Currently, the plant supplying the raw material does
only a fair job of adhering to the eight-hour delivery schedule. Past delivery
records indicate that S n = 4 hours. What would the reduction in the lead time
be if the material supply could be made more reliable, for instance with only
one hour standard deviation (S u = 1 hour)? The prediction is that, because
S H = 4 hours, a lead time of roughly 9.25 hours is required for each lot
produced by the robot cell. However, if SI4 is reduced to 1 hour, the lead time
is reduced to approximately 7 h o u r s - a n improvement of almost 25%. We
have, therefore, been able to quantify the benefit of more reliable supply.

2.2.2. Multi-server queues

Multi-server queues are in general more difficult to analyze than their
single-server counterparts. In this section we first present the exact formulas
for the tractable model of the M / M / m queue and then describe approxi-
mations for the G I / G / m queueing model.

The M / M / m queue. The commonly used parallel-server single queue model is

the M / M / m queue. A detailed analysis of this queue can be found in standard
texts on queueing [Gross & Harris, 1985; Kleinrock, 1975; Ross, 1989]. The
formulas for the steady-state (congestion) measures for this queue are pre-
sented next.
The probability of an empty system is given by

m--I (mp)_~~" (mp) m ] - '

P ° = [ ~ ~ = 0 n, + m.TÕ---p) (M/M/m). (2.16)

The probability that there are n jobs in the system is given by

p,, =
• °
Po, l<~n<~m
(M/M/m). (2.17)
(mp)"
mn-mm! Po , tl >~ m
 Ch. 5. Performance Evaluation 215

The average waiting time of jobs is

We=[ m,!(__mp_)"
( 1 - p) 2
]po (M/M/m). (2.18)

The G I / G / m queue. An approximation for the congestion measure, Wq, for

the G I / G / m model is obtained by modifying the exact formula for the
(M/M/m)
M / M / m model. Let Wq be the mean delay time for the M / M / m queue
as given by (2.18). A simple approximation for Wq, in the case of the G I / G / m
model is
2 2

Wq q -

This approximation is based on heavy-traffic limit theorems (see [Whitt, 1983]

and references therein). For the M / G / m model (c2a = 1), (2.19) is known to be
usually an excellent approximation [Whitt, 1983]. The approximation can be
improved by using a correction factor similar to the factor g for the G I / G / 1
queue [see Whitt, 1989]. Other waiting time approximations for this general
multi-server queue can be found in Tijms [1988] and Marchal [1985].
The renewal process approximation for the SCV of the interdeparture-time,
2
Ca, as given in Whitt [1983] is,
2 2
p (c s - 1 )
c 2d 1+(1-p2)(c~-1)+ (GI/G/m) . (2.20)

For single-server queues, m = 1 and (2.20) agrees with (2.15). For the M / M / m
queueing model (c2a = 1 and c 2 = 1), (2.18) yields c d2 = 1. This is indeed true as
the departure process is known to be Poisson for the M / M / m queue [Burke,
1956].

2.3. Workcenter with a finite buffer

This section contains results for a workcenter with a finite capacity of N jobs
(total of buffer and servers). Since there can be no more than N jobs (or
customers) in the system, if an arriving job finds that there are already N jobs
in the system, then it does not enter the system. In a manufacturing context if
jobs represent production orders then jobs arriving when the system is full are
assumed to be lost. On the other hand if jobs represent parts or workpieces
coming from other sections of a production line to a workcenter, then the jobs
attempting to enter this workcenter when it is full are blocked at the source. In
this case, the source or portion of the production line that is attempting to
release a job will normally be shut down until the destination workcenter is
ready to accept a new job. Analysis of finite capacity systems is important
since, such systems are frequently encountered in industry. As in Section 2.2
single-server systems (m = 1) are considered separately.
216 R. Suri et al.

With regard to the congestion measures of the expected time spent by a job
in the system or expected waiting time in the buffer, it makes more sense to
calculate these for a job that actually entered the system. Hence, while
applying Little's formula to finite buffer systems, the arrival rate that should be
used is not the mean arrival rate but rather the mean rate of jobs actually
entering the system. Let A«ffdenote this rate. For a G / G / m / N queue we have

L = AeffW (2.21)

and for jobs waiting in the buffer

Lq = AeffWq . (2.22)

The mean arrival rate and A«f are related through the probability that an
arriving job sees the system full in steady state. That is,

A«r = A(1 - qN) (G/G/m/N), (2.23)

as ( 1 - qN) is the fraction of arrivals that actually enter the system. If the
arrival process is Poisson, then the arrival time probability qN = PN, as Poisson
arrivals see time averages [Wolff, 1989]. The general relations (2.1) and (2.2)
still hold for a G / G / m / N queue, but the load factor p defined by (2.1) is not
restricted to be less than 1. This is because a finite capacity queueing system is
always stable since customers are lost if the limit determined by the total
capacity of the system is exceeded. Relation (2.3) needs to be modified as
follows:

L = Lq q- Aeff~" (G/G/m/N). (2.24)

2.3.1. Single-server queues with finite capacity

We start this section by presenting exact formulas for the tractable model of
the M / M / 1 / N queue. Next, we briefly discuss the M / G / 1 / N queue and give
some references that contain an analysis of the queueing system.

The M / M / 1 / N queue. This finite capacity queue with Poisson arrivals and
exponential servers, can be analyzed easily [see, e.g., Gross & Harris, 1985;
Ross, 1989]. The probability that the system is empty in steady state is given by

1-- N-+I ' p#l

Po = (M/M/1/N) (2.25)

and the probability that the system is full in steady state (or the long-run
fraction of arrivals that are rejected) is
 Ch. 5. Performance Evaluation 217

PN = (M/M/1/N) . (2.26)
LN+I ' p=l

The average number of jobs in the system is given by

f p _ (N + 1)p N+I
L = 1 7p 1 -- pN+l , P• 1
(M/M/1/N) , (2.27)
N/2, p =1

The other congestion measures can be readily obtained by the use of Little's
formula, general relation (2.2), and

lA( 1 - - p N
Aeff ~ \l__pN+lj , p#l
= (M/M/1/N). (2.28)

The M / G / 1 / N queueing system. An imbedded Markov chain analysis for this

queueing system can be performed in a way similar to that of the unlimited
waiting room case. The restriction on the capacity leads to a finite number of
steady-state probabilities, pù. Given the specific service-time distribution, the
stationary equation of the imbedded Markov chain can be numerically solved
for all the probabilities. These probabilities can then be used to derive the
congestion measures. A detailed description of the analysis is contained in
Gross & Harris [1985] and Tijms [1988].

2.3.2. Multi-server queues with finite capacity

The M / M / m / N queue. This parallel-server exponential model with finite

capacity can be analyzed easily and we present below a summary of the results.
In the formulas given below, we will assume that p # 1. We start with the
steady-state probability of an empty system, which is

~-1 (mp)n ( m p )m (l--pN-m+1)]-~

P°=[~o - -n' + m! -(i----~) J (M/M/m/N).
(2.29)

The probability that the system is full (or an arriving job is rejected) is given by

PN = po[F ~(mp) ~ o~-,ùlJ (M/M/m/N) . (2.30)

The average number of jobs waiting in the buffer is

218 R. Suri et al.

Lq =P0 m! (] p)2 ( l - p - (1 - p ) ( N - m + 1)pN-m).

(2.31)

Expressions for other congestion measures can be derived in a straightforward

manner using relations (2.21)-(2.24).

The M / G / m / N queueing system. Some approximations for this finite capacity

M / G / m queueing system are described in Tijms [1988]. For the special case
when N = m (that is, no queueing allowed) some exact results are available
[Gross & Harris, 1985]. In fact, for the M / G / m / m queue, the steady-state
probabilities are independent of the form of the service-time distribution, i.e.,
they depend only on the mean service time.

The G I / G / m / N queueing system. For a discussion on some bounds and

approximations for this queueing system, and some recent references see
Stoyan [1983], Tijms [1988], and Wolff [1989].

2.4. Finite source queueing models

We now consider a queueing model where the calling population of jobs is

finite, say of size K. A typical application of this queue is the machine-
repairman model (see Section 7 for details). In the machine-repairman model,
the ealling population is the (K) machines, the (m) repairmen are the servers,
and an arrival corresponds to a machine breakdown. We present below results
only for the exponential machine-repairman model, ( M / M / m / . / K ) , where
the service times of the m servers (or repair times) are exponentially distribut-
ed with mean % and the time a machine spends working before it breaks down
is also exponential with mean 1/A.
Using standard birth-death theory, the steady-state probabilities can be
easily derived [see, e.g., Gross & Harris, 1985] and are

O«_n<m
P. (M/M/m/./K),
(Kl ~! - ( ~~)~o m<~n«_K
\ n / m"-"m!
(2.32)
where Po is found by equating the sum of the probabilities to 1 and is

po= [ ~~(~)
~o (AT)"+
2«) o' ]1
n
n m n-mm! (At)

(M/M/m/, /K). (2.33)

 Ch. 5. Performance Evaluation 219

The average number of customers in system or machines down for repair can
be easily obtained using the definition of expected value as
K

L = ~ npn (M/M/m/. /K). (2.34)

n=O

Additional results for this queueing model and a discussion of other more
general machine-repairman models can be found in Section 7.

2.5. Non-FCFS scheduling disciplines

Thus far, in all the workcenter queueing models considered, jobs belong to a
single class (that is, are of the same type) and proceed to service on a
first-come-first-served (FCFS) basis. In modern production systems such as an
FMS, jobs belonging to several classes are simultaneously present in the system
[Suri & Hildebrant, 1984]. Furthermore, in several manufacturing applications,
job-related priority scheduling schemes have to be devised and implemented in
order to provide preferential service to certain classes of jobs. In priority
scheduling disciplines, jobs with the highest priorities are selected for process-
ing ahead of those with lower priorities, independent of the time at which they
joined the queue. By increasing the priority of a job class, the throughput
(manufacturing lead time) of jobs belonging to this class can be increased
(reduced). Hence, in production systems, modeling of priority scheduling
disciplines is essential when exploring the effects of various product mixes and
control strategies.
Priority queues are in general more difficult to model than nonpriority
systems. Gross & Harris [1985] state that as long as the scheme of priorities is
in no way a function of the relative size of the processing time, then the
steady-state probabilities and congestion measures (only average values) are
independent of the scheduling discipline. However, several manufacturing
scheduling disciplines such as 'the shortest processing time (SPT) rule' depend
on service times. The literature on such priority queues and related models is
enormous. Gelenbe & Pujolle [1987], Gross & Harris [1985], and Wolff [1989]
have results for certain priority models and several references on this topic.

3. Tandem production line

3.1. System definition

We begin by defining a synchronous line as a number of machines connected

in series with synchronized part transfer between machines [Leung & Kamath,
1991]. With this, we define a tandem production line as a series arrangement of
manufacturing/assembly stages, where each production stage consists of a
single machine, several identical machines in parallel, or a synchronous line.
220 R. Suri et al.

Between each pair of stages is a buffer of a specified size. A job visits all stages
sequentially from the first stage to the last with no loops or rework and hence
the name, tandem production line. Tandem production lines are also referred
to as transfer lines and flow lines in the literature [Buzacott, 1972; Muth, 1979].
As examples of our definition, in the two-stage transfer line considered by
Buzacott & Hanifin [1978] and the automatic transfer line modeled by Ohmi
[1981], each stage is itself a synchronous line and not a single machine or a set
of parallel machines.
The particular tandem production line configuration that will be considered
in this section is an asynchronous line consisting of a single machine at each
stage. The queueing network model is then an open tandem queueing model or
a series arrangement of M single server machines (Figure 3.1). The output of
machine i (i = 1, 2 , . . , M - 1) forms the input of the next machine in line,
which is, machine i + 1. New jobs are processed first by machine 1 and jobs
depart from the system after they are processed by machine M. Based on the
type of new job input to machine 1, two types of models can be defined. We
define a Type i model as one which assumes that the first machine has an
inexhaustible supply of new jobs to process. On the other hand, if new jobs
arrive from an external source to the first machine (see Figure 3.1), then we
will call the model a Type 2 model. In this case, an infinite input queue is
sometimes allowed upstream of the first machine. In both models, there is a
finite buffer between two adjacent machines where in-process parts temporarily
wait if the downstream machine is busy. An assumption that is always made is
that there is unlimited buffer space for the last machine to release its finished
jobs.
A machine is said to be blocked if it is unable to release the job that it just
finished processing, due to unavailability of space in the destination buffer.
Blocking reduces the productivity of a manufacturing/assembly system by
forcing machines to be idle during the period of time they are blocked. Two
common definitions of blocking exist in the literature [Altiok & Stidham, 1982;
Suri & Diehl, 1986]. The description above is the definition of what Suri &
Diehl [1986] call transfer-blocking. In the second case, a machine or server is
not allowed to start service until space is available in the destination buffer.
Suri & Diehl [1986] call this the service-blocking definition. Generally, transfer-
blocking is appropriate for models of production lines (hence it is also called
manufacturing blocking), while service-blocking is appropriate for models of
communication networks where the service process involves transmission of
data to the destination station (hence the alternative name communication

Type 1 Buffer 1 Buffer M-1

~~o...o
Type 2 Machine 1 Machine 2
o...ol to...ol-~
Machine M-1 Machine M

Fig. 3.1. A tandem queueing model.

 Ch. 5. Performance Evaluation 221

blocking). Except in special cases, these two definitions of blocking are not
equivalent [see Altiok & Stidham, 1982].
The blocking phenomenon makes the solution of such queueing network
models nontrivial. In such models, one is interested in determining the effects
of service time variability and blocking due to finite buffers on the system
performance measures including production rate, work-in-process, and job
flow time. The variability of service times can arise from machine breakdowns
and repairs in fixed cycle production systems [Buzacott, 1967; Gershwin &
Schick, 1983; Gershwin, 1987a,b] or simply from randomness in processing
times.
Early works in the analysis of tandem production lines with finite capacity
buffers are summarized in a review paper by Koenigsberg [1959]. Although the
problem of blocking in such production networks has been studied by re-
searchers for several years, closed form solutions of such models are not
available except for a few special cases. If processing times at each machine are
assumed to be exponential (or geometric), exact analytical solutions are
available only for cases involving a small number of stages and buffers [see,
e.g., Gershwin & Berman, 1981; Gershwin & Schick, 1983]. These cases will
be discussed in Section 3.2. An important reason for the difficulty in studying
models with blocking is the state-space explosion; the number of states grows
combinatorially with the number of stages and buffer sizes in the network
model [Gershwin, 1987a] and in the exponential/geometric case the resulting
Markovian models become intractable. The following is an example of a fixed
cycle transfer line from Gershwin [1987a] that shows the great size of the state
space even for a system of moderate size.
Consider an M-machine line, where each machine can be in one of two
states: operational or failed. Let the capacity of buffer i, the buffer in front of
machine i + 1, be B i. Buffer i can be in the B i + 1 states, n i = 0, 1, 2 . . . . . B i,
where n i is the number of jobs in buffer i. A Markov chain representation of
the M-machine line with M - 1 buffers has a state space of size
M-1

2M I ] ( B i + l ) .
i=1

A 20-machine line with 19 buffers, each of capacity 10 has over 6.41 × 10:5
states.
Since an exact analytic solution is difficult to obtain, several approximation
methods and numerical techniques have been proposed by researchers for
M-stage open tandem queueing models with blocking [Brandwajn & Jow,
1988; Buzacott, 1967; Choong & Gershwin, 1987; Dallery, David & Xie, 1988,
1989; Gershwin, 1987a,b; Perros & Altiok, 1986; Pollack, Birge & Alden,
1985]. More references are contained in a comprehensive bibliography on
queueing networks with blocking published by Perros [1984]. Some results on
reversibility properties of transfer lines are in Muth [1979] and Yamazaki,
Kawashima & Sakasegawa [1985]. The topic of approximations for general
finite buffer tandem models is the subject of Section 3.3.
222 R. Suri et al.

3.2. Solution of two-stage and three-stage tramfer lines

3.2.1. Two-stage transfer lines

Based on the review of work on two-stage transfer lines reported in
Gershwin & Berman [1981], the two-stage transfer line systems that have been
studied and for which results are available can be classified into three main
categories.
(i) The processing times at the machines are random and machines do not
fail. Most models assume exponential processing times. In this category, both
Type 1 and Type 2 models have been considered [see, e.g., Foster & Perros,
a980].
(ii) The second category includes models that assume deterministic process-
ing times, but that allow random machine failures. In other words, this
category includes fixed cycle production lines with unreliable machines. Almost
all models are Type 1. A majority of the models assume geometrically
distributed times to failures and times to repair.
(iii) The third category is one in which machine processing times are random
and machines fail randomly. The failure and repair processes are assumed to
be exponential. Again a Type 1 model is assumed.
The literature on two-stage models is enormous: the article by Gershwin &
Berman [1981] has extensive references. Due to the vastness of literature, only
two-stage models belonging to the third category will be described in the
remaining part of this subsection. Furthermore, these models seem to be the
most general. Such models were studied by Buzacott [1972] and Gershwin &
Berman [1981]. In both papers, a continuous time Markov chain was used to
represent a two-stage transfer line. The solution of the Markov chain model
yielded steady-state system probabilities which were then used to evaluate the
measures of performance such as production rate and average in-process
inventory.
In Gershwin & Berman's [1981] model (Figure 3.2), the state of the transfer
line system is given by the 3-tuple, (n, a~, az), where n, n = 0, 1 , . . . , B + 1, is
the number of jobs in the interstage buffer plus the number of jobs in machine
2 and the binary variable ai, i = 1, 2, is defined to be 1 when machine i is
operational and 0 when machine i is failed or under repair. The steady-state
probability that the system is in state (n, a~, az) is denoted by p(n, a~, a2). The
two-stage line is completely characterized by seven parameters, which are,
inter-stage buffer size B, machine i mean service time, r~, i---1, 2, and the
failure and repair rates for machine i, Pi and ri, i = 1, 2, respectively. As stated

Machine 1 Buffer Machine 2

Fig. 3.2. A two-stage transfer line.

 Ch. 5. Performance Evaluation 223

before, the service, failure, and repair times are assumed to be exponential. It
is also assumed that machines fail only while processing jobs. Machine 1 is
blocked if it is operational and if there is no room in the buffer to put the
finished job. (As Altiok and Stidham [1982] point out, this leads to a
service-blocking assumption, which according to them does not seem to
represent the physical reality of blocking in production lines.) Machine 2 is
starved if it is operational and has no jobs to process in the buffer and machine
2. Machine 1 is never starved and machine 2 is never blocked.
Gershwin and Schick then proceed to define the balance equations satisfied
by the steady stare system probabilities, p(n, %, %). They present a set of
explicit expressions for the probability distribution p(n, %, %) and outline an
algorithm to calculate the same. This distribution is then used in a straight-
forward manner to calculate the following system performance measures: (i)
utilization (efficiency) of machine i which is the long run fraction of time
machine i is processing jobs, (ii) production rate of the system, and (iii)
average in-process inventory which is the average number of jobs in the buffer
plus the average number of jobs in machine 2.
The main difference between Buzacott's model and that of Gershwin and
Berman is that in Buzacott's failure model, the probability of failure is
independent of the amount of processing time, while in Gershwin and Ber-
man's model, the longer the processing of a job takes, the more likely it is that
the machine fails before the processing is complete. In other words, in
Buzacott's model, the time between successive breakdowns of a machine,
measured in number of job processing cycles completed, has a geometric
distribution. In Buzacott & Hanifin's [1978] terminology, Gershwin and Ber-
man model time dependent failures, while Buzacott models operation dependent
failures. Also, Buzacott makes a simplifying assumption that the characteristics
of machine 1 and machine 2 are identical. In addition to an exact analysis,
Buzacott also presents simple approximations for the two-stage line by combin-
ing the results of some previous works. Buzacott & Kostelski [1987] present a
recursive solution to this model, based on solutions from Yao & Buzacott
[1985c].

3.2.2. Three-stage transfer lines

The three-stage transfer line analyzed by Gershwin & Schick [1983] falls into
category 2 described in Section 3.2.1. It is a Type 1, fixed production cycle
transfer line. All three machines have equal and deterministic processing times.
Time is scaled so that a machine cycle takes exactly one time unit. Machines
are assumed to have geometrically distributed times between periods of failure
and times to repair. For machine i, i = 1, 2, 3, the average operating time,
expressed in cycles, between failures is 1/Pi and the mean time to repair is 1/r i
cycles. Machines are assumed to fail only while processing jobs.
Figure 3.3 shows the three-stage transfer line modeled by Gershwin & Schick
[1983]. The line parameters are the capacities of the interstage buffers, Bi,
i = 1, 2, and the failure and repair rates for machine i, Pi and ri, i = 1, 2, and 3,
224 R. Suri et al.

Machine 1 Buffer 1 Machine 2 Buffer 2 Machine 3

Fig. 3.3. A t h r e e - s t a g e t r a n s f e r line.

respectively. The state of the three-stage line at any time can be completely
described by the 5-tuple, (n 1, n 2, a 1, a 2, a3) where ni, 0 ~< n i ~< Bi, for i = 1, 2
is defined to be the number of jobs in buffer i, and ai, the machine i
(i = 1, 2, 3) condition, is defined to be 1 when machine i is operational and 0
when machine i is failed or under repair. The dynamic behavior of the 3-stage
line is modeled as a discrete Markov chain and the failure and repair
probabilities are used in obtaining the state transition probabilities of the
Markov chain. A large portion of Gershwin & Schick [1983] deals with the
development of an algorithm for catculating the steady-state probabilities of
large scale structured Markov chains such as the one used to model the transfer
line.
As in the two-stage case, the steady-state probabilities, p ( n l , n2, oll, c~2, oz3) ,
are then used to calculate the following important performance measures: (i)
utilization (efficiency) of machine i, which is the steady-state probability that a
job emerges from the machine during any given cycle, (ii) production rate of
the system (per machine cycle) which is equal to the utilization or efficiency of
a machine, since the machine cycles are fixed and equal, and (iii) average level
of buffer i. Forced down (starvation and blockage) probabilities and related
quantities are also calculated in Gershwin & Schick [1983] and Gershwin
[1987a]. In Gershwin & Schick [1983], the authors mention that the algorithm
for the solution of the Markov chain model exhibits certain numerical problems
for large buffer sizes. This coupled with the large storage and computer time
requirements make the method impractical for large buffers. Reliability of the
results has been verified for cases with buffer sizes equal to 15. Gershwin and
Schick also consider a two-stage line of a similar type.
A three-stage line that falls into category 3 (exponential processing times,
exponential failure and repair processes) was analyzed by Altiok & Stidham
[1983[. They show that the service completion process at each machine has a
phase-type distribution and then proceed to develop a continuous Markov
chain model of the three-stage line. A search procedure is also developed to
find the allocation of buffer capacities of the three-stage line that maximizes a
total profit function.

3.3. M-machine case - A p p r o x i m a t i o n s

Most decomposition methods used to approximately analyze M-machine

lines with finite buffers fall into one of the following two classes.
(i) The behavior of the M-machine line is approximated by the behavior of a
set of two-machine lines, so that results available for two-machine lines can be
 Ch. 5. Performance Evaluation 225

used. The methods developed are based on probability theory and Markov
chain theory. In Section 3.3.1 we will discuss Gershwin's decomposition
method and its extensions that belong to this set of approximations.
(ii) The second class of approximations decomposes the M-machine line into
M single machine (server) lines. That is, the behavior of the tightly coupled
(because of finite buffers) system of M single server queues in series, is
approximated by the behavior of M single server queues operating in-
dependently. The service times for the individual queues are revised to
approximately capture the interactions with the neighboring queues in the
original M-machine line. The approximation methods in this category use a
variety of single server queueing models from an infinite capacity Markovian
queue to finite capacity G I / G / 1 queueing model. Some of these approximation
methods are summarized in Section 3.3.2.
A recent approximation method suggested by Brandwajn & Jow [1988] is
similar in spirit to that of Gershwin's. Although their method uses the solution
of a two-stage system as a building block, they do not decompose the original
line into a set of two*stage lines. Their algorithm proceeds by iterating over
pairs of adjacent stations and hence using results available for a two-stage
system. In their model, the processing time at a station can have a state-
dependent exponential distribution. That is, the mean processing time can
depend on the number of jobs present at this station.

3.3.1. Gershwin' s decomposition technique

The M-stage transfer line considered by Gershwin [1987a] is identical in
characteristics to the three-stage line studied by Gershwin & Schick [1983]. It is
a Type 1 fixed cycle line with the fixed processing time same for all machines
and which is taken as the time unit. The machines have geometrically
distributed working time and repair time distributions. The extension of the
method used for the three-stage line to this general case is difficult because of
the enormous size of the state space. Exact methods are not available for lines
with more than three machines [Gershwin, 1987@ Hence, Gershwin [1987a]
has proposed an approximate decomposition technique.
The basic assumption behind the decomposition technique is that for each
buffer in the M-machine line, two hypothetical machines can be described,
whose behavior closely models the upstream and downstream part of the line.
That is, a single M-machine line is approximated by a set of ( M - 1) two-
machine lines, L(i) for i = 1, 2 . . . . . M - 1. The buffer in the two-machine line
L(i) has the same capacity as t h e / t h buffer in the M-machine line. It is further
assumed that the machines in the two-machine lines have geometric working
time and repair time distributions. Then for every two-machine line, four
parameters must be chosen (two failure rates and two repair rates). These four
parameters are chosen so that the performance of the upstream (downstream)
machine of the /th two-machine line L(i) closely matches that of the line
upstream (downstream) of the buffer i in the original M-machine line. A set of
polynomial equations are derived to determine four parameters per two-
226 R. Suri et al.

machine line or a total of 4(M - 1) parameters. An iterative scheme is used to

solve the polynomial equations. Gershwin shows through experimental results
that the decomposition technique is very accurate but, he also reports certain
convergence problems with the iteration algorithm. Some cases where the
algorithm failed to converge contained examples of long lines (M > 20). The
performance measures of the two-machine lines yield the performance mea-
sures of the original M-machine line.
Dallery, David & Xie [1988] proposed a simpler algorithm than that of
Gershwin [1987a] to iteratively solve for the parameters of the two-machine
lines. Dallery, David and Xie actually replace the original set of polynomial
equations by an equivalent one and develop a computationally attractive
iterative algorithm to solve the new set of equations. Further, in the cases
examined in Dallery, David & Xie [1988], the algorithm always converged.
In another paper, Gershwin [1987b] proposed a method to extend his
decomposition method to M-machine lines where machines are allowed to
have different processing times. The basic idea is to transform the original line
(with different processing times) to a line in which all machine processing times
are identical so that the decomposition technique described above can be used
for the new line. This is done by replacing every machine but one by a
hypothetical two-machine line. The behavior of the resulting line is an approxi-
mation of the behavior of the original line. Gershwin [1987b] shows through
numerical examples that this method provides good results but again reports
some convergence problems. In another article, Choong & Gershwin [1987]
adapt Gershwin's [1987a] method to transfer lines with random processing
times. The transfer line model analyzed by Choong and Gershwin is an
extension of Gershwin & Berman's [1981] two-stage line model with unreliable
machines (see Section 3.2.1). A different decomposition approach is in Liu &
Buzacott [1989].
Dallery, David & Xie [1989] have developed a new approximation method
for analyzing M-machine lines with unreliable machines and finite buffers.
They approximate the flow of discrete parts in a transfer line by a continuous
flow. Their article also contains a review of earlier works on continuous flow
modeling of transfer lines. First, they consider a Type 1 fixed cycle line with
the fixed processing time same for all machines and where the machine failure
and repair times are exponential (a line model similar to that in Gershwin
]1987a]). The decomposition method presented is very similar to Gershwin's
technique described above. Next, using Gershwin's idea [1987b] they extend
their decomposition method to nonhomogeneous lines where machines may
have different processing times. Justification for the use of continuous flow
models, for performance analysis of discrete lines, is in Alvarez, Dallery &
David [1991] and Suri & Fu [1991].

3.3.2. Decomposing the line into individual queues

Early work on this approach includes Hillier & Boling [1967]. Most approxi-
mation methods that fall into this category assume exponential processing
 Ch. 5. Performance Evaluation 227

times. In general, machine failures are not included. The most common
assumptions made regarding the arrival of jobs to the first machine and buffer
size in front of the first machine are, (i) Poisson arrivals, a finite capacity buffer
at the first machine, and jobs arriving when this buffer is full are lost [Altiok,
1982; Perros & Altiok, !986; Pollock, Birge & Alden, 1985], and (ii) Poisson
arrivals and an infinite capacity buffer at the first machine [Foster & Perros,
1980]. The basic assumption behind most approximation methods in this
category is that a solution of a model with modified machine service times
(modified to handle blocked times approximatety) is an approximate solution
to the model with blocking.
Altiok [1982] decomposes a finite buffer tandem line with exponential
service times into individual finite capacity queues which are analyzed in
isolation. The input process to each queue is assumed to be Poisson. In revising
the service times it is assumed that each queue can be blocked only by the
immediate destination queue, that is, a single queue cannot block more than
one upstream queue. The effective service time (actual service time + blocked
time) of a machine is approximated by a two-stage Coxian distribution. Each
queue is then analyzed as an M / C 2 / ! / N queue except the last which is
analyzed as an M / M / 1 / N queue. Takahashi, Miyahara & Hasegawa [1980],
suggested a similar method for approximately analyzing open queueing net-
works with finite buffers, Poisson arrivals, and exponential processing times.
Perros & Altiok [1986] extend Altiok's [1982] approximation to allow blocking
to be backlogged over any number of successive queues. Again, their modified
or effective service times have a phase-type or Coxian distribution. The
network is decomposed into individual single queueing systems with revised
buffer capacities, and modified arrival and service processes. The individual
queues are analyzed in isolation and solution is obtained via iteration. They
present two cases, one in which the buffer of the first machine is unlimited in
size and the other in which it has a finite capacity. Pollock, Birge & Alden
[1985] extended this idea of modifying service times to analyze M-machine
lines with general processing time distributions at the machines.

4. Tree-structured manufacturing systems (assembly networks)

4.1. System definition; Practical examples

This class of models arises ffom manufacturing settings where components

from the output of two or more processes are required in order for the next
process to begin its work. For example, in order for a complete automobile to
emerge from the manufacturing operation at some point both an engine and a
body taust come together to be assembled. The station that performs the
engine-body mating process is necessarily dependent on inputs from the engine
assembly operations and the body manufacturing facility. Examples of this type
are found everywhere because in principle every assembty operation is of this
228 R. Suri et al.

type. Even an operation as simple as inserting a screw in a computer cover

depends on a supply of computers (sans screw in the cover) and the supply of
screws. The implication is that the assembly operation cannot begin until all
required subassemblies or components have arrived. Hence the start time of
the assembly operation is offen regarded as a random variable which depends
on the maximum of the arrival times of the subassemblies or components.
Performance analysis of these systems is very difficult analytically. If small
buffers (in-process inventories) are added to reduce idle time of the assembly
process, then the situation becomes more tractable from a production planning
view point but even more problematic analytically. If very large buffer stocks
of components are assumed then the assembly process is effectively decoupled
from the component production process. In most cases, however, this is an
unreasonable assumption and one is forced to deal with the problem in its full
complexity.
In major development processes involving the construction (assembly) of
complex aircraft, or ships, major subassemblies are themselves the object of
development activity and hence the total assembly leadtime of the entire ship
or aircraft must necessarily depend on the merging of unique subassemblies.
The leadtime models have the same character as project planning models for
projects with stochastic activity times. The time frame is considerably longer
for these project planning environments than those associated with the usual
manufacturing process. In a standard discrete parts manufacturing environment
we may consider models which describe many assemblies in various stages of
manufacturing and assembly in a network of stations.
Alternatively, the models may describe a network such as the one described
above but where the stations consist of two or more merging assembly
processes where the feed processes have deterministic cycle times but where
the stations are subject to random breakdowns and random repair times. One
can obviously complicate this situation by assuming that the cycle times of the
feed processes are themselves random.
In these models, questions arise regarding the ideal time between releases of
individual jobs or components into the assembly network, estimation of
production leadtimes, in-process inventories and station utilizations. In addi-
tion, if parts are to be ordered from external vendors, then the problem of
setting order times must be considered in the analysis to account for impact of
stochastic order leadtimes on the leadtimes of each completed assembly.
Generally the use of equilibrium conditions is out of the question in these
models since, at least for small lots, the transient response of the network must
be incorporated in the models.

4.2. Solutions and approximations- Infinite buffers

In this section, we examine a class of manufacturing systems such as those

described in the previous section which have the property that repeated merges
of sub-assemblies must occur in a timely fashion in order for the next stage of
 Ch. 5. Performance Evaluation 229

Parts Buffers

Assembly Stations

Fig. 4.1. Multi-stage assembly line.

the manufacturing to continue (Figure 4.2). In this section, we further assume

that all interstage buffers are large enough to prevent blocking. These systems
are most often encountered in assembly applications. However, many of the
intermediate steps may require fabrication as weil as assembly. As an extreme
example of this class of systems we would see the tree stripped of all of its
'branches' and as a consequence we would have an asynchronous flow line
where at each node parts buffers are assumed to be sufficiently targe to prevent
delivery delays (Figure 4.1). In the more general case at each node of the
network, delays could be caused in delivery of components from any of the
incoming branches.
in early contributions to the modeling of tl]is type of system, Harrison [1973]
showed that an assembly station with two input streams whose interarrival
times were governed by independent renewal arrival processes and where there
is no limit on the number of parts waiting in either queue has the property that
the waiting time process does not converge in distribution to a nondefective
limit, or in simple terms, there is no equilibrium distribution. This result has
implications for analytical modeling since it shows that the simplest model is
unreasonable and additional operational assumptions are required. Latouche
[1981] showed that if the processes are Poisson and the assembly station has
exponential service times then, if the excess number of one type of part over
the other is bounded, the waiting time process is stable.
Analytical performance modeling of assembly networks is difficult primarily
because in order for an assembly to move through a processing stage one or
more additional parts or subassemblies must be present at the same time in
order to complete the operation. As a consequence we have the following
relationships.

--~ [] [] ~ .~
[] [] r ~
[] []
Fig. 4.2. Tree-structured manufacturing system.
230 R. Suri et al.

In a simple station where (as in Figure 4.1) parts are being added to an
assembly we have

b]j= S o + Pü, (4.1)

S o = max(F/_l,j, Fi,~-l, A u ) , (4.2)

where F ü is the finish time for assembly j at station i, Sij is the start time for
assembly j at station i and Pij is the processing time for assembly j at station i.
Aq is the time at which the patts for assembly j are available at station i. The
formulation presented in (4.1) and (4.2) contrasts with flow line analysis where
it is common to assume that patts or components to be added at an individual
station are kept there in quantity so that A ü is usually 0. In addition, in most
manufacturing systems anatysis, the emphasis is on the performance of the
total collection or network of assembly or manufacturing stations but in this
formulation we are tracking the individual piece or assembly through the
network. This particular formulation is appropriate where the manufacturing
system is low volume and/or where the final product is large and expensive.
This formulation is also appropriate where component and final product
delivery leadtimes are of special interest. In more complex networks such as
the orte depicted in Figure 4.2 the relationship for Sq may be more complex
because an operation may require more than one subassembly as weil as parts
from the station in order to begin the operation at station i.
This formulation is used by Saboo & Wilhelm [1986]- see also Ahmadi-
Marandi [1982]- in which a recursive procedure is developed to estimate the
mean and the variance of the times at which events take place in the assembly
network. All random variables are assumed to be normally distributed (al-
though they may be correlated). Approximations by Clark [1961] are used to
obtain the moments of the maximum of two bivariate normal variates.
Specifically, Saboo and Wilhelm begin with the Fundamental Assumption
that all operation start and finish times are mutually related by the multivariate
normal distribution and that operation times are normally distributed and are
mutually independent. If X and Y are normal random variates with parameters
(/*1, °'1) and (/'/'2' O'2)' respectively, and correlation p = r(x, y) then the mo-
ments Z = max(X, Y) are given by

E[Z] = / , l O ( a ) + / . 2 ~ ( - o ~ ) + a4~(a),

E[Z ~1 = (u~ + «~)4,(«) + (~,:~ + « ~ ) O ( - «) + (~, + ~~)~0(«),

(4.3)
Var[Z] = E [ Z 2] - E2[Z],
2
where a 2 = 0-~ q- 0" 2 -- 2p0"1o-z, a = (/*1 - Ju'2)/a, q0(«) = standard normal CDF
evaluated at a, and ~b(o0 = standard normal PDF evaluated at «.
 Ch. 5. Performance Evaluation 231

This procedure is extended to three or more variates via the relation

max(U, V, W) = max(U, max(V, W)) and hence if max(V, W) is assumed to be
normally distributed, then the moments of max(U, V, W) can be approximated
by using Clark's procedure twice. The correlation r[U, max[V, W]] is calculated
as

r[ U, max[V, W]] = o-1P~4)(«) + o-2 P2 4~(- a ) / V a r 1/2[M],

(4.4)
where M = max[V, W] , p~ = r[U, V], P2 = r[U, W].

These methods are developed into a seven-step procedure by Wilhelm and

Ahmadi-Marandi to estimate finish times and leadtimes for assembly networks.
The procedure requires the expansion of Equation (4.2) in terms of the
properties of earlier operations. All of the moments required to estimate the
mean and variance of Fq are known or can be estimated recursively from
earlier stages in the system except the correlation coefficient r =
r(Fi_14, F~,j 1). All the required moments to estimate r are assumed to be
known from the practical context or can be obtained from earlier stages except
f o r r(Fi_2,j, Fi,j_2) and it is assumed that this correlation is associated with
random variables that are sufficiently 'remote' that this correlation can be
assumed to be zero. Some care taust be taken with these procedures because of
the n u m b e r of approximations and assumptions used since they are likely to be
useful in 'large' systems where the procedure is applied over and over again in
a recursive iashion and as a result errors may cumulate over a large number of
stations.
From these estimates, one can derive the estimated completion times (and
the variance of the completion times) of assemblies at each stage of the
manufacturing process. Further it is possible to set the delivery leadtimes for
components (or kits) at each stage of the assembly process in a way that will
yield appropriate final product delivery times.
This basic model has been extended in a number of ways by Wilhelm and his
coauthors. In Wilhelm [1986a] and Saboo & Wilhelm [1986] considerations of
the transient performance of the assembly network, the impact of the spacing
of release times of jobs into the network and the impact of vendor leadtime
safety margins are incorporated in the analytic models and the results are
compared with simulation results. In Wilhelm, Saboo & Johnson [1986] the
basic models are extended to incorporate random operation times and the
effects of parallel stations. In Wilhelm [1986b] the normality assumptions are
extended to consider the lognormal distribution. In Wang & Wilhelm [1985] a
set of recursive models are used to extend the analysis to include the effects of
finite buffers, routing and sequencing aspects. The accuracy of all of these
models are reported by the authors to be excellent and the run time advantages
are reported to range from a factor of two up to a factor of 100 fastet than the
time to obtain the same results from simulation.
232 R. Suri et al.

4.3. Solutions and a p p r o x i m a t i o n s - Finite buffers

Hopp & Simon [1989] have examined the case of two 'up-stream' stations
feeding a single assembly station AM (see Figure 4.3) with separate buffers B1
and B2 for parts from the two feed stations M1 and M2. They assume that the
assembly station is never blocked and that the upstream machines continue to
work so long as empty space exists in the queues that they feed. The assembly
station and the feed stations are all assumed to have exponential service times.
They begin by showing this system (shown in Figure 4.3) is equivalent
(stochastically) to a three-stage transfer line with finite buffers between the
stages. They derive bounds for the average throughput and inventories and
they develop a method to approximate the steady-state throughput. They
compare the results to earlier work by Lipper & Sengupta [1986]. Their
method provides performance bounds and the throughput approximations are
claimed to be easier to calculate than the method of Lipper and Sengupta, but
the Hopp and Simon results are limited to two input processes. A variation of
this system is also analyzed by Flatto & Hahn [1984]. Ammar [1980] analyzes
assembly networks with deterministic service times, and finite buffers where
the assembly stations are subject to random breakdown with random repair
times. Liu & Buzacott [1990] provide approximations and analysis of an
automotive assembly system. Buzacott & Shanthikumar [1992b] give a detailed
treatment of Flexible Assembly Systems. Gershwin [1991] analyzed assembly/
disassembly networks with unreliable machines and finite buffers. Mascolo,
David & Dallery [1991] approximate such a system by a continuous flow
model.
In summary it appears that, while some progress has been made in this
difficult area, a good deal more work is required before routine performance
analysis of manufacturing systems with this structure can be undertaken
without the aid of simulation tools.

Fig. 4.3.
 Ch. 5. Performance Evaluation 233

5. Open networks of queues

5.1. System definition

While open queueing network theory has been applied in a number of

practical settings including the analysis of computer systems and telecommuni-
cation networks, in manufacturing, perhaps the most common setting for this
analysis is the job shop environment. Here the system consists of a number of
separate processing departments each involving machines or stations of a
certain type and capability. Jobs arrive at random from the environment and
each has a given set of processing requirements that specify the routing through
the stations which the job must follow. If the distribution of processing times at
each station is the same for any possible arriving job then we have a single
customer class. If the set of arriving customers can be grouped into classes each
of which has its own routing and common distribution of processing times at
each station, then we have a multi-class network. Here, as in most production
networks, the more important system performance criteria include the leadtime
for each job class (mean time in the network), the station utilizations, and the
mean work in process for each job class.

5.2. Single class analysis

Among the earliest attempts to provide queueing network models that can
be used to analyse job shop environments are the exponential network results
of Jackson [1963]. The elegance of the results of this analysis have given rise to
a variety of attempts to generalize the results to approximate the behavior of
networks of G I / G / m stations where the input process to each station is
assumed to be (approximately) a renewal process characterized by the mean
and the variance of the interarrival times of customers. The station service
times are assumed to have general distributions but are assumed to be
characterized by the mean and variance of the service times. Two early papers
in this line of research are Reiser & Kobayashi [1974] and Kuehn [1979].
Shanthikumar & Buzacott [1981] were the first to apply this approach to
manufacturing job shop control.
Continued work in this area has led to a large volume of papers culminating
in a fairly comprehensive paper by Whitt [1983] and in the development of
software for routine analysis of open networks, [e.g., Whitt, 1983; Suri, Diehl
& Dean, 1986; Bitran & Tirupati, 1988; and Suri & DeTreville, 1991].

5.2.1. Jackson networks and product form

Following Heyman and Sobel [1982] we define a Jackson network to be a
collection of queues with exponential service times in which the customers
travel from node to node according to transition probabilities given by a
Markov chain. Specifically the network consists of M service facilities num-
bered 1, 2 . . . . . M. We assume that station i contains m i identical servers,
234 R. Suri et al.

m i >/1. C u s t o m e r s w h o arrive f r o m outside the n e t w o r k arrive at facility i

according to a Poisson process with rate Ac, i = 1, 2 , . . . , M. W h e n a c u s t o m e r
receives service at station i it leaves the n e t w o r k with probability Pi0 or goes
i m m e d i a t e l y to station j with probability Pcj, r, pq = 1. These transition prob-
abilities are a s s u m e d to be i n d e p e n d e n t of past events in the n e t w o r k .
C u s t o m e r s are served at each facility according to a F C F S discipline. Service
times at e a c h facility i are i.i.d, exponential with m e a n 1//x~, i = 1, 2 , . . . , M.
Visits to successive service facilities are m a d e according to the M a r k o v chain
with transition matrix P = { p q } w h e r e P00 = 1 by definition. P is called the
r o u t i n g matrix for the n e t w o r k and the state labeled 0 represents the 'outside'.
D e f i n e Po as the P matrix with row 0 and c o l u m n 0 r e m o v e d .
L e t a~ r e p r e s e n t the asymptotic m e a n arrival rate at station i. We see that the
a i must satisfy
M
ai = i~i + E pjiaj , i = 1, 2, . . . , M . (5.1)
j=l

T h e s e e q u a t i o n s are called the 'traffic equations'. I n vector f o r m we h a v e

a = A + aP o ,

where a=(al,a2, . . , a M ) , A : ( / ~ I , / ~ 2 , ' ' ' ' AM)' and if 1 - P i 0 ~ < l for all
i va 0, then there is a unique solution for a which is nonnegative.
N o w d u e to the M a r k o v properties of the system let s = (sl, s 2 , . . , SM),
r e p r e s e n t the state of the system w h e r e the n u m b e r of customers at facility i is
s i. T h e n define p ( s ) to be the steady-state probability that the system is in state
s (assuming that the steady state exists). T h e n we have the following.

Jackson's T h e o r e m . I f Pi = ai/(tzimi) < 1 f o r each facility, then p ( s ) = rl pi(si),

where
n
pi(O)ai
n
if n <~ m i
tx t n!
pi(n) = mi n --m i (5.2)
pi(O)ai Pi
mi 1 if n ~>m i ,
]'Z i (mi).

where n = 0, 1 . . . . , and pc(O) is a normalizing constant.

W e can see that except for the fact that it was necessary to solve the traffic
e q u a t i o n s (5.1) for the ai, J a c k s o n ' s T h e o r e m effectively d e c o m p o s e s the
entire n e t w o r k for us because E q u a t i o n (5.2) is just the set o f steady-state
probabilities for an M / M / m c queue. This n e t w o r k n o d e d e c o m p o s i t i o n allows
us to treat each facility as an i n d e p e n d e n t service facility and to use the familiar
m a c h i n e r y o f M / M / m queues, as in (2.17), to e x a m i n e the behavior at each
 Ch. 5. Performance Evaluation 235

facility. (One has to be a bit careful about the use of Jackson's Theorem. It
teils us that at a given instant the stationary distribution for the system has the
property that the random variables associated with the number of individuals at
each of the stations are independent at a given instant of time. It does not say
for example that XI(t ) is independent of X2(t + 1) and more specifically it does
not say that the waiting times at each of the stations are independent random
variables.)
For modeling a network with a single job class this class of models has the
great advantage that the analysis is simple and exact (under the assumptions
stated). From a manufacturing systems perspective, however, it has some
drawbacks. Specifically, the assumption of exponential service time at each
station is almost always violated in a manufacturing environment. Since for an
exponential distribution, the service time distribution at a station is completely
captured by a single parameter (the mean service time) there is no way to
incorporate information about the variance of the service time in the model. In
addition, as noted above, the waiting times at each station are correlated in the
general case and the obvious estimates (expected time in station multiplied by
the expected number of visits to the station) of expected flow times that are
provided by Jackson network models can be in error by 40% or more.
If the correlations between waiting times at each pair of stations can be
neglected, we can obtain the estimated mean flow time in the network from the
following procedure (see Shanthikumar & Buzacott [1984] for an examination
of this procedure). Since the entire network is decomposed into sets of
M / M / m queues with known arrival and mean service times for each station we
can calculate a vector W which contains the mean time spent at each station
directly from the individual station models. From this we can obtain the total
expected system leadtime for customers that begin their first service at each of
the possible stations in the network by calculating the vector

= [ l - eo]-~w. (».3)
The matrix N = [I - P0]-1 is known as the 'fundamental' matrix and the typical
element from this matrix, say nij, can be shown to be the expected number of
visits to station j by a customer who enters the system at station i before that
customer exits the system. As a consequence, T i is the total expected time in
the system for a job that begins its stay in the network at station i.
Station utilizations and other station performance measures such as expected
queue lengths can be obtained from the formulas provided in Section 2.

5.2.2. Node decomposition for networks of G I / G / m queues

In the case of networks of more general stations or facilities where one
cannot assure the conditions of Poisson arrival streams and exponential service
times the problem is naturally much more complex and no general exact
network theory exists. H o w e v e r one may effect an approximate network
deeomposition composed of a set of facility models which are approximate
236 R. Suri et al.

G I / G / m models linked together by sets of traffic equations similar to those

required for Jackson networks.
As in the section above, we will confine out attention to the open network
case (closed network examples will be treated in Section 6). We will assume
(following Whitt [1983]) that all of the assumptions required by Jackson
networks are satisfied except those related to the distributions of service times
and interarrival times. We will also use the notation of the previous section
except when additional parameters are required by the distributional assump-
tions.
Customers who arrive from outside the network arrive at facility i according
to a renewal process with mean rate Aoi, i = 1, 2 , . . . , M. Service times at each
facility i are i.i.d, with mean 1//xi, i = 1, 2 , . . . , M.
In addition we require c2j, c,2 for each facility j in the network where these
parameters represent respectively the squared coefficient of variation of the
interarrival times for station j" for arrivals from outside the network and the
squared coefficient of variation of the service times of servers at station j. We
also need the number of service channels mj at station j and the mean service
rate #j for servers at station j. Hence each station can now be described by the
parameters { C2oj, c ~j, 2 Aoj,/xj, mj}. From these parameters we can obtain the
i n p u t - o u t p u t characteristics of each facility and EW, the expected steady-state
response time for each facility.

5.2.2.1. A n overview of the analysis process. In most regards, the approximate

decomposition analysis of networks of G I / G / m queues proceeds along the
same lines as the analysis of Jackson networks. Some obvious extensions are
required. Since both arrival and departure processes are assumed to be
(approximately) renewal processes we require methods for estimating the
parameters (mean and variance of interevent times) of processes that are
f o r m e d by merging other renewal processes and we need to be able to estimate
the parameters of processes that are obtained by splitting renewal processes.
Finally since we will be using both the mean and the variance (or the coefficient
of variation) of each random process in the system we will obtain not only the
traffic equations of Jackson networks that estimate the composite mean arrival
rates to each station but a second set of equations that will be solved to provide
the variability of the arrival process to each station. We will take these issues
up in order in the following three sections.

5.2.2.2. Merging of arrival streams. If the arrival stream to a facility is made

up of the merging of a series of k streams each with arrival rate Ai, i =
1 . . . . , k, then we need to calculate the arrival rate )t and the squared
coefficient of variation of interarrival times c 2 for the merged stream.
Clearly the composite mean arrival rate is A = X Ai.
The value of c 2 is approximated by

c2 w A~ A~ c~ + l - w ,
 Ch. 5. Performance Evaluation 237

where w = l 1 + 4 ( 1 - p ) 2 ( v - 1 ) 1 - 1 , u = [ E i ( A j E kai)2] - ' , c 2 is the squared

coefficient of variation of interarrival times for stream i, and p is the load factor
of the station to which the streams are arriving.
These approximations are based on an extensive series of investigations
undertaken by Albin [1982] and Whitt [1982] and are the resutt of forming a
convex linear combination of two separate approximation methods referred to
as the Stationary Interval method and the Asymptotic Method. Whitt [1983]
has further simplified these approximations to obtain the equations above
which are linear in the c o m p o n e n t c~.

5.2.2.3. Splitting o f departure streams. If a departure stream with inter-

departure process coefficient of variation c 2 from a facility is split into k
streams of customers where customers go to stream i with probability Pi then
the coefficient of variation of stream i is

C~ = pi c2 + 1 -- Pi " (5.5)

This result is exact when the departure process is renewal and the p / s
represent independent events ( M a r k o v routing). The mean flow rate in stream
i is clearly Ap~ where A is the mean arrival rate of the original arrival stream to
the station.

5.2.2.4. Departures. If a facility is not saturated (i.e., p < 1) and it is in steady

state, then the mean input rate is equal to the m e a n output rate. Consequently
the m e a n interdischarge time is known when the mean input rate is known.
The variance of the interdischarge time however is not so easy to obtain. Whitt
[1983] uses the following approximate expression for the coefficient of variation
of the interdeparture times of G I / G / m facilities:

c 2a = l + ( 1 - p 2)(c a2 - 1) + _&(c 2 -
2

1). (5.6)

This reduces to c 2 = (1 - p 2 )c a2 + p 2 c,2 for the G I / G / I queue and the reader

m a y refer to Section 2 for the origin of these approximations.

5.2.2.5. Traffic and traffic variability equations. If one uses all of these rela-
tions given above plus the knowledge that customers cannot be created or
destroyed in the network then one can obtain two sets of simultaneous linear
equations to be solved respectively for the internal traffic (arrival) rates Ai and
the internal traffic variability coefficients c]i. Specifically we have

A : A 0 ( I - Po) -1 , (5.7)

where A0 is the vector of external arrival rates, A is the vector of composite

arrival rates and Po as before is the routing matrix.
The squared coefficient of variation of composite arrival process at each
238 R. Suri et al.

station is obtained from the following equations:

M
2
Caj : aj -~- E 2
caibij , (5.8a)
i=1

where
[( M ]]
aj=l+wj q0i«0j2
2 _I)+E q/j[(1-pij)+pijP~Xi (5.8b)
i=1

b~j = wjp~jqii(1 - p 2 ) , (5.8c)

and where

qij = ( a~/Aj)p~j,

xi= 1+ m i
-0.5," • 2
tmaXtCsi, 0.2] - 1 ) , vj =
E~0 ~1
qij
-~
,

wj = [1 + 4(1 - pj) 2(vj -- 1)] -1

At this point we have all of the building blocks to completely analyse a single
class open network of queues (subject to the assumptions given in the
beginning of the section).
The mean and coefficient of variation of both the interarrival times and the
station service times are now known and by assuming each station to be a
GI/G/m queue, one can calculate all of the usual queueing information for
each station (such as mean total time in station, mean number in the queue,
mean number in station, busy and idle probabilities etc., see Section 2.2.2).
Using the routing matrix Po one can calculate total expected time in system,
expected total number of customers in the system etc.

5.3. M u l t i p l e class analysis

5.3.1. Product form networks

Perhaps the most comprehensive reference on the exact analysis of product
form networks is the paper of Baskett, Chandy, Muntz & Palacios [1975] which
considers an extremely broad class of such systems encompassing open, closed,
and mixed networks with both a single customer class and multiple customer
classes. They examine four classes of stations that incorporate cases of first-
come-first-served, last-come-first-served, processor sharing and preemptive-
resume service disciplines. They examine cases involving state-dependent
arrival and service rates as well as service time distributions that generalize the
standard exponential assumptions to include service time distributions that
have rational Laplace transforms. It should be noted that not all possible
 Ch. 5. Performance Evaluation 239

combinations of these generalizations are analyzed. In fact, for stations where

the service discipline is FCFS the service time of all jobs must have an
exponential distribution that is identical for all job types, hence multiclass
FCFS networks cannot be handled with the analysis approach of the article.
Nevertheless some very complex multiclass networks can be analyzed and
perhaps the principal result of the paper is that for a broad range of systems
the equilibrium state probabilities can be written as a 'product form'

P(s) = Cd(«)f, (x,)... fN(XN),

where C is a normalization constant, d is a constant that depends on the state s,
B. is a function that depends on the type of station (one of four possible types)
identified as station i, and x i is a state vector describing the state of station i.
The explicit form of the f functions is given for all of the four admissable
station classes. The numerical values of the parameters in the equilibrium
probabilities must be obtained either by solving the standard equilibrium
equations or by formulating a somewhat simpler set of balance equations
referred to as the 'independent balance equations'. Formulating and solving
these equations directly can be a formidable task. This problem and the
restriction to single customer classes for FCFS stations makes this approach of
somewhat limited value for manufacturing systems.

5.3.2. Non-product form networks

Whitt [1983] provides an approximate analysis of multiple customer class
queueing networks in the form of an input aggregation which he calls 'inputs by
classes and routes'. Each customer class is assumed to have its own route
through the network and that route is assumed to be deterministic. Each class
may have its own service rate at each station. This set of information is
converted into the parameters of a single aggregate customer class and the
analysis requirement is effectively reduced to that of the previous section.
Once the aggregate network has been analyzed then individual customer
classes can be segregated and congestion measures and response times for each
individual class can be extracted from the aggregate network performance.
Bitran & Tirupati [1988] have developed an improved approach to estimat-
ing the interaction between classes in estimating EW for multiple class network
problems. Once again they assume deterministic routing but they do not
aggregate the arrival and service time parameters in the same way as Whitt.
They split the analysis at a station of the network into calculations for a single
product (say product i) and they accumulate the properties of the remaining
products into a single aggregate product. As a result they derive an improved
expression for the coefficient of variation of the departure stream from each
station. They show that this new approximation provides an improvement over
Whitt's method and they show that it leads to improved systems analysis
performance for the network parameters. Results are given for 10 different
network examples with 13 stations and 10 products each. Comparison with
240 R. Suri et al.

simulation results show that the improved approximation yields estimates of

the total number of jobs in the network that average within 5% of the
simulation results for all 10 examples when compared to average errors of the
order of 20% + using Whitt's analysis. They also provide further improvements
that use Erlang rather than Poisson interarrival assumptions at each station.
These more general assumptions result in better accuracy, albeit at the cost of
more complex formulae. In Bitran & Tirupati [1991] they extend their ap-
proach to allow overtime at stations.
Harrison & Nguyen [1990] have developed an entirely different approach to
modeling of open queueing networks which is based on heavy traffic limits of
(multiclass) single server stations [see Reiman, 1984]. These approximations
are based on diffusion approximations and their associated reßected Brownian
motion processes. The modeling process is again based on two moment
approximations but the machinery is quite different than the usual queueing
network formulas. The equilibrium distribution for W, the total time in the
system is obtained by solving partial differential equations associated with what
is called the Basic Adjoint Relation. They report success only with one- and
two-dimensional systems to date but the results for this approach, caUed
Q-Net, is really quite good even for systems where the heavy traffic assump-
tions are not met. In the case of higher dimensional systems a product form
assumption is inserted and the resultant approach is referred to as II-Net. This
seems to produce equations for most networks that are fairly similar to those
found in QNA. In fact, QNA often produces better results than the II-Net
models on the examples provided in the paper. Wein [1990a,b] has applied this
class of analysis to the consideration of optimal scheduling of stations in some
simple (two station) multiclass queueing networks. The results obtained out-
perform standard scheduling rules such as SPT and FCFS by performance
margins of 30% or more in the examples provided. More complex networks
are analyzed in Wein [1991]. Analysis of networks of infinite server stations is
in Glynn & Whitt [1991]. Sojourn time distributions are approximated in
Fleming & Simon [1991].
This very general approach to the analysis of queueing networks appears to
be quite promising because of the ease with which it can handle multiple
classes of customers and general routing assumptions. However, beeause of the
complexity associated with solving the partial differential equations associated
with the Q-Net approach it does not yet appear to be a practieal tool for
manufacturing systems problems. It remains to be seen whether the approxi-
mate method (II-Net) offers fundamental advantages that are not found in the
more classical approaches described earlier.

5.4. Applications to manufacturing systems

As reviewed by Koenigsberg [1982], some of the earliest work on queueing

networks arose from attempts to provide analytic formulas that would predict
the performance of manufacturing systems, such as the work of Jackson [1963]
 Ch. 5. Performance Evaluation 241

for job shops. Many of the advances in queueing network theory and algo-
rithms then took place in the context of computer systems performance
modeling. However, the 1980s saw a resurgence in manufacturing modeling
using queueing network models. In the context of open networks, fundamental
developments include those by Buzacott [1982], Shanthikumar & Buzacott
[1981], who model dynamic job shops, and Buzacott & Shanthikumar [1985]
who extend such models to shops with SPF (shortest processing time) service
discipline. Yao & Buzacott [1985b] further extend the models to the situation
where waiting areas are limited. Karmarkar [1987] uses a simple model to
provide insight on lot sizing and lead time issues in job shops; more complex
cases are analyzed in Karmarkar, Kekre & Kekre [1985a], Zipkin [1986], and
Calabrese & Hausmann [1991].
Case studies documenting the use of open network models in manufacturing
also began to appear more frequently in the late 1980s [e.g., Chen, Harrison,
Mandelbaum, Van Ackere & Wein, 1988], particularly with the availability of
commercially supported software packages such as QNA [Whitt, 1983], Manu-
Plan [Suri, Diehl & Dean, 1986] and MPX [Suri & DeTreville, 1991], along
with their PC-based versions [Suri, Tomsicek & Derleth, 1990; Suri & De-
Treville, 1992]. In fact, it can now be said that queueing network analysis has
found its way out of the academic/research environment into the mainstream
of manufacturing analysis. We find, for instance, applications at major corpora-
tions such as Alcoa [Nymon, 1987], Digital Equipment [Harper & O'Loughlin,
1987], IBM [Dietrich & March, 1985; Brown, 1988], Kodak [Karmarkar,
Kekre, Kekre & Freeman, 1985b], Pratt & Whitney [Suri, 1988b], and Siemens
[Anderson, 1987], as weil as at many smaller firms [Suri, 1989b; DeTreville,
1991]. Indeed, Suri [1989b] and Suri & DeTreville [1992] explain why, in the
competitive context of modern manufacturing, the use of queueing network
analysis assumes strategic importance in manufacturing decision-making, and
they document this with several industrial case studies.

6. Closed networks of queues

6.1. System definition

A closed network is one where the number of jobs of each class present in
the network is fixed. Typically in such a model, one of the stations is a
'load/unload' station: when a job arrives at that station it is removed from the
network and another job of the same class is entered in its place. Thus the time
for a particular job to return to this station is its flow time, and the production
rate of this station models the throughput of the network. Such a model can
represent a flexible manufacturing system (FMS) or automatic assembly system
where parts require specific fixtures or pallets before they can be put into the
manufacturing system, and the fixed number of jobs in the network models the
limited number of pallets/fixtures.
242 R. Suri et al.

As an example, consider the FMS in Figure 6.1. This consists of a load/

unload station and several numerically controlled machines, all linked by an
automated material handling system. Workpieces are mounted on fixtures and
placed on pallets at the load/unload station. The material handling system can
transport workpieces from machine to machine, in any desired sequence.
When the required operations have been completed, the workpiece is returned
to the load/unload station. Thus an FMS can be considered as an automated
job shop. If the system is operated such that, whenever a workpiece is
dismounted at the unload station, another workpiece is mounted in its place,
then the number of workpieces in the system remains fixed and we can
represent the FMS by a closed queueing network model. A great deal of the
manufacturing-related work on closed networks was stimulated by the per-
formance analysis of FMSs [e.g., Solberg, 1977]. Although specific context-
related references will follow in this section, some general references on FMS
modeling, which themselves contain further references, are Buzacott & Yao
[1986], Choobineh & Suri [1986], Seidmann, Schweitzer & Shalev-Oren [1987],
and Stecke & Suri [1985, 1986, 1988, 1989].
If we wish to represent different types of fixtures for different part types, we
can enhance the above-described model by using multiple classes; this will be
discussed later in the section. However, throughout this section we will assume
that the buffer sizes at all stations equal or exceed the number of jobs in the
network, so that there is no blocking; models with blocking will be considered
in Section 8.

~m
-I
/ J
Fig. 6.1. Flexiblemanufacturingsystem.
 Ch. 5. Performance Evaluation 243

6.2. Sing& class analysis

6.2.1. Systems with exponential service times

T h e simplest case of a closed network model is a single class model similar to
the open Jackson network described in Section 5. It is assumed that all stations
have exponentially distributed service times. The service discipline is FCFS
everywhere. It is also assumed that after finishing service at station i, jobs go to
station j with probability p~j. Finally, instead of having a vector of arrival rates
()t~) f r o m external sources as in the open model, here we are given the value of
N = n u m b e r of circulating jobs. Thus the given p a r a m e t e r s for this network
are:
M = n u m b e r of stations,
mi= n u m b e r of servers at station i,
N= n u m b e r of jobs in the network,
~= m e a n service time of a job at station i,
po= probability that a job goes f r o m station i to station j.
A slightly m o r e general m o d e l is obtained by allowing the service rate
p a r a m e t e r of the exponential distribution to depend on the n u m b e r of jobs
present at the station. In this case, instead of the p a r a m e t e r s m i and ~-i above,
we are given ani = the service rate of station i when n jobs are present. Such a
station is called a load-dependent server. The first model is a subset of this one,
since we can represent a multiple server station simply by assigning ani = n/'c i
for n ~< m~ and an~ = mi/"r~ for n > m~. We will begin hefe by considering the
case where there is only one server at each station, and return to the general
model later.
Because the n u m b e r of jobs is fixed, this network is always stable. As in the
open network, let n = (nl, n2, . . . , n M ) denote the state of the network, where
n~ = n u m b e r of jobs present at station i. We will only consider the steady state
p e r f o r m a n c e measures for this network, the main ones being:
p~ = utilization of a server at station i,
ai = production rate (rate of completion of jobs) at station i,
L~ = average n u m b e r of jobs present at station i,
W, = average time spent by a job (waiting and service) per visit to station i,
P(n) = probability that the state of the network is n,
Pni = probability that there are n jobs at station i.
In addition, two important p e r f o r m a n c e measures result from identifying the
l o a d / u n l o a d station, say station O.
X 0 = system throughput ( = a 0 f r o m above),
W = average time spent in the system by a job.
F r o m the definitions above, we see that W equals the average time between
returns to station O. Sinee there are no external arrivals and the system is
stable, the produetion rate at each station equals the arrival rate to it, and so,
244 R. Suri et al.

analogous to the open network case, from simple flow conservation considera-
tions we get the following set of traffic equations:
M

a i = ~, pjiaj. (6.1)
j=l

Now however, without the A~ values which were known and appeared in the
equations for the open network, Equations (6.1) only determine the relative
values of the a i and so the actual value of the system throughput needs to be
determined by additional analysis. Such a network was analyzed by G o r d o n &
Newell [1967a] who derived the analytic form of the joint probability dis-
tribution for the number of jobs at each station, and showed that it too has a
product form:

1 M
P(n) = ~ I-[ (y~)"' , (6.2)
i=1

where

Yi = vi "ri ,
vi = any set of values satisfying ( 6 . 1 ) , (6.3)
G = a normalization constant (see below).

T h e normalization constant is defined by requiring the probabilities of all

possible states to sum to unity. Although the above holds for any set of values
v i which satisfy (6.1) - s i n c e the relative magnitude of the v i values is offset by
the magnitude of the resulting normalization c o n s t a n t - for the manufacturing
case it is useful to define v i by a i = % X o, so that v0 = 1 (i.e., for the
l o a d / u n l o a d station). The v, are called v i s i t r a t i o s . T h e y can be interpreted as
the average n u m b e r of visits to station i by each new job. Now, provided the
matrix of routing probabilities defines an irreducible chain, solution of the
resulting equations
M

Oi = 2 PjiOy for i ¢ 0 , V0 = 1 (6.4)

]-1

provides a set of unique values for the v~. In principle, we could now compute
the value of G and then compute relevant performance measures from the P ( n )
values.
H o w e v e r , computation of the normalization constant apparently requires
summing over all possible system states. Since the number of states equals
M+N-1
N ) this would appear to require a great deal of computational effort
even for moderately sized networks. Thus, even after the discovery of the
product form solution, the practical usage of closed network models remained
severely limited until the development of efficient computational algorithms.
 Ch. 5. Performance Evaluation 245

6.2.2. Computational algorithms

6.2.2.1. Convolution. The development of computational algorithms for

ctosed queueing networks was initiated by Buzen [1973]. From the discussion
surrounding (6.2) we see that
M

G = ~2 I~ ( y , ) n , (6.5)
nCS(1V,M) i=1

where

S(N, M) = {n [ ~ n, = N and n, ~O Vi} .

i=1

Buzen defined the quantities

g(n,m)= E f i (y,)n, (6.6)

n~S(n,m) i=1

and

G(n) = g(n,M).

Note that with these definitions, the normalization constant G equals G(N).
Buzen then showed that the g(n, m) values could be computed by a simple
recursion, namely

g(n,m)=g(n,m-1)+ ymg(n-l,m ) form>landn>0,

g(n, 1)=yln for n = 0 , 1 , . . , N , (6.7)

g(0, m ) = l for r a = l , 2 . . . . , M .

Thus for the network with all single server stations, G can be computed
extremely efficiently in O(NM) operations, by an easily implemented algo-
rithm. Buzen further showed that many of the common performance measures
are simple functions of the values computed during the recursion. For instance,

G ( N - 1)
X°- G(N)'

P, = y~Xo , (6.8)
C(N- n) - y,C(N - n - ~)
P~, = YI'
G(N)
246 R. Suri et al.

Buzen [1973] also generalized the computation of G and the performance

measures for the load-dependent case. The details are omitted here, but we
note that the computational effort is just O(NM 2) and that algorithm is also
easy to implement. Buzen's algorithms are also known as convolution algo-
rithms because the steps can be interpreted as the convolution of probability
distributions. With the development of these convolution algorithms the
popularity of closed network models increased significantly, particularly for
computer systems modeling (e.g., see Spragins [1980] and that entire issue of
I E E E Computer). Along with this increased usage came development of
alternative computational algorithms as well as algorithms for more complex
models. Both these topics will be covered in sections below.

Example. An example of a manufacturing modeling tool based on the above

network model, which uses the Buzen algorithm, is CAN-Q [Solberg, 1977].
This tool is most suited to evaluäte FMS configurations, although some
applications to other manufacturing systems are also reported. CAN-Q pro-
vides quick estimates of performance measures such as throughput and utiliza-
tions, and can even be implemented on a hand calculator. Although the early
developments of computational algorithms for closed networks occurred in the
computer systems modeling community, Solberg's work on CAN-Q can also be
viewed as one of the pioneering efforts since it spurred the study of computa-
tional älgorithms by the manufacturing modeling community. These enhanced
the modeling capabilities for manufacturing applications and are described in
sections below.

6.2.2.2. Mean value analysis. Although the convolution algorithm is simple

and efficient, it does suffer from some numerical problems - since it uses sums
of quantities raised to high powers, it can result in 'floating point overflow' or
'underflow' problems during the computations. In fact, this can be easily seen
by subjecting a tool such as CAN-Q to extreme cases (e.g., systems with large
N and high utilizations). Several 'renormalization' methods are available to
correct the numerical behavior of the algorithm, but they result in a more
complex implementation. A second, more fundamental impediment to the use
of convolution algorithm is that it does not lend itself naturally to heuristic
extensions for more general system models. Both these shortcomings are
addressed by an alternative approach termed mean value analysis (MVA)
developed by Reiser & Lavenberg [1980]. Although their development was for
multiclass networks, we will first describe it for the single class network with
single-server stations.
The starting point for MVA is the proof of the relation

Wi(N )=,r~+ Lg(N-1)~-~, i=l,...,M, (6.9)

where Wg(n) denotes the value of the measure W i in a network with n

circulating jobs (and similarly for other measures).
 Ch. 5. Performance Evaluation 247

This equation has an appealing interpretation. To see this, note that the total
time a job spends at a station (on average) is comprised of its own service
time - the first term on the RHS of (6.9) - plus its waiting time. Thus the term
L~(N - 1)r i must be the average waiting time. Due to the memoryless property
of the exponential distribution, this means that the average number of jobs
ahead of an arriving job is L , ( N - 1) - which equals the mean number of jobs
present at that station for a network with N - 1 jobs on it. Thus (6.9) can be
interpreted as saying that a job circulating in the network 'sees' a network in
equilibrium with itself removed. This result is also known as the arrival
theorem [Sevcik & Mitrani, 1979].
The relation (6.9) allows the development of an efficient computational
algorithm. Suppose we have computed the values of L ~ ( N - 1 ) , for i =
1 . . . . , M. Then we can obtain the values of L~(N), i = 1 . . . . , M , as follows.
First we calculate W~(N) i = 1 . . . . . M, from (6.9). Next, by Little's Law
applied to the whole network, we have
M

X o ( N ) = N/i~=l_ v i W i ( N ) , (6.10)

where the v~ values are obtained as before, from (6.4). Finally, applying
Little's Law to each station gives

L,(N)= Xo(N)viW~(N ), i= l,. . . ,M. (6.11)

Thus we have a way of computing the values L i ( N ) given those of L i ( N - 1).

In order to start this recursion, we only need to note the trivial relation

L~(0)=0, i=1 ..... M. (6.12)

Starting with this set of values, we can use Equation (6.9), (6.10) and (6.11) to
calculate Li(1), L i ( 2 ) , . . . , L i ( N ). Since each step involves O ( M ) operations,
the whole algorithm takes O ( N M ) operations. At the end of the algorithm we
obtain three of the main performance measures, namely X0, Li, and p/(which
equals viriXo, see (6.8) and (6.3)). As can be seen from the form of the three
equations used in the iterations, this algorithm is likely to have good numerical
properties. However, it only provides the three performance measures stated.
T o obtain more detailed performance measures, such as Pni, a n d / o r to
analyze load-dependent stations, more elaborate forms of MVA are given in
Reiser & Lavenberg [1980] and Reiser [1981]. These involve an iteration on
certain marginal probabilities - the Pn~(N) values are derived from Pùi(N - 1).
H e r e there is a greater possibility of numerical problems, but a simple
'renormalization' procedure can be included in each step of these algorithms.

6.2.2.3. Additional developments. Since the introduction of the two basic

methods for computing performance measures, namely convolution and MVA,
248 R. Suri et al.

there has been a good deal of research on additional algorithms. This was
motivated primarily by the need to find more efficient methods for networks
with multiple classes of customers. We will therefore derer discussion on these
developments to the section on multiclass networks.

6.2.3. Approximations for non-exponential distributions

6.2.3.1. Flow-equivalence, aggregation, and decomposition. For networks with

non-exponential service times, most of the approximations available are based
on variations of the 'flow equivalent' approach, which is also related to the
terms 'aggregation' and 'decomposition'. Thus we begin by describing these
concepts. The seminal paper in this area is one by Chandy, Herzog & Woo
[1975a], which showed the following interesting result, reminiscent of Norton's
Theorem for electrical networks. Consider a closed network with exponential
service times, M stations (which can be load-dependent) and N jobs, which we
call network N. Now 'short out' orte of the stations in the network, say station
m, so that all jobs going to that station are immediately routed back to the rest
of the network (the correct manner of doing this, given the routing prob-
abilities, is in Chandy, Herzog & Woo [1975a]). Call this network N ~-m~ to
denote the shorting out of station m. Now let TP(n) be the throughput,
measured at the 'shorting loop', for network N (-m) when it has n = 1 , . . . , N
jobs in it. Next, consider a new network with just two stations in it. The first is
station m, with its original characteristics. Station 2 is a load-dependent station,
with parameters Ogn2= T P ( n ) for n = 1 , . . , N. (This is termed the flow-
equivalent server for the network N ~ m~.) Then it turns out that for this new
network, the steady-state distribution of the number of jobs at the first station,
as weil as the throughput at this station, are identical to the values they would
have in the original network N. In other words, as far as station m is
concerned, replacing the rest of the network by this 'aggregate' representation
(a single flow-equivalent server), has no effect on its steady-state performance
measures.
Related to this result are the ideas of exact and approximate decomposition
[Courtois, 1977]. Consider now a general network (not necessarily product
form), and replace a subsystem in this network by its flow-equivalent server. (If
the subsystem is not analytically tractable, the parameters for this server might
be found by simulation.) Then, in informal terms [e.g., see Agrawal, 1985], the
approximate decomposition principle states that if the state transitions within
the subsystem occur at a much greater rate than interactions between the
subsystem and the rest of the system, not rauch error is introduced by this
replacement. Of course, the 'Norton's Theorem for queueing networks' above
is an instance of exact decomposition. However, in that case notice that there
is no restriction on the state transition rates at all! This curious result is a
consequence of the special form of the transition equations for product form
networks and is explained at length in Courtois [1977[.
 Ch. 5. Performance Evaluation 249

6.2.3.2. Approximate models. The above concepts give rise to a host of

approximation methods for non-exponential networks. The basic idea is to
replace one or more subnetworks by flow-equivalent servers, and then to
analyze the resulting network. To see the relation between the various
alternative terms used for this in the literature, separating a network into
multiple subnetworks is called decomposition and modeling a subnetwork by
one station is called aggregation. Often, analysis of the network of aggregate
stations produces some inconsistencies or deficiencies in the performance
measures, which suggest modifications to the decomposition or aggregation
steps. In this way, an iteration procedure can be developed which successively
refines the accuracy of the model. Thus the two key steps in most of the
methods below are (i) the development of the equivalent server, and (ii) the
refinement step (il any).

Example. The simplest instance of the above approach is the case where only
step (i) is applied. An early application of such an approach is in Brandwajn
[1974] for a computer system model. As a manufacturing example of this,
Buzacott & Shanthikumar [1980] model an FMS with a random arrival process
and N pallets. In such a case it is likety that in practice the number of jobs in
the FMS would not be fixed at N, but rather, would have an upper limit of N.
They decompose the system into a waiting area for arriving jobs, and the
subnetwork of FMS stations. The FMS subnetwork is analyzed as a closed
network and its throughput rates for n = 1 , . . . , N jobs define a flow-equiva-
lent server. The arrival process and this aggregate server then define a simple
birth-death process which can be analyzed to get the behavior at the waiting
area.

Several researchers have proposed methods to analyze networks with general

service times using the two-stage method above. Chandy, Herzog & Woo
[1975b] use a method that uses M submodels, each consisting of one station
and a flow-equivalent server for the complementary subnetwork. They iterate
between these submodels to achieve certain consistency criteria. Marie [1978]
extends this procedure by using a more sophisticated submodel. In a slightly
different approach, Shum & Buzen [1977] use an M / G / 1 / N queue to represent
each general service time station, and use the queue length distribution of this
queue to estimate the network throughput. The arrival parameters for the
M / G / 1 / N queues are obtained iteratively. In a similar vein, an 'exponentiali-
zation' approach is developed by Yao & Buzacott [1986a], where all servers
with general service times are replaced by servers with exponential service
times and appropriate state-dependent service rates. Approximate decomposi-
tion approaches based on diffusion approximations for G I / G / 1 queues were
proposed by Kobayashi [1974] and Reiser & Kobayashi [1974]. Shanthikumar
& Gocmen [1983] improved upon these methods, although their iteration
scheme is quite computation intensive and may fail to converge for systems
with service time SCVs greater than unity. Kamath, Suri & Sanders [1988] also
250 R. Suri et al.

use G I / G / 1 approximations for closed networks. Their algorithm is efficient

and convergent, but applies only to closed loop systems - such systems will be
discussed in Section 6.3. Another decomposition approach is the isolation
method of Labetoulle & Pujolle [1980].
The above methods are based mainly on the convolution approach. Reiser
[1979] showed how the basic MVA algorithm could be easily modified to
account for non-exponential service times. The idea is to replace the basic
MVA relation (6.9) by a heuristic modification such as

W~(N) = ~~ + ~ i L i ( N - 1)~-i, i= 1,.., M. (6.13)

Here /3i is a 'correction factor' that modifies the queue length seen by an
arriving job, according to the service time characteristics for station i. Several
variations of this correction are possible, and manufacturing applications of it
will be discussed in Section 6.4.
A completely different approach to approximations for closed queueing
networks uses the maximum entropy principle. In general, entropy maxi-
mization is a method for estimating a probability distribution from an unde-
termined set of linear equations about the probabitistic states of the system.
The maximum entropy principle states that from all distributions which satisfy
the constraints, we should select the distribution which maximizes the entropy
of the system. The intuitive justification for this is that this distribution is best
supported by the information conveyed by the constraints, and which is least
biased with respect to the information that is missing. We will not review the
method any further here, but indicate some relevant references. A good
treatment of the maximum entropy formalism can be found in Shore &
Johnson [1980, 1981]. Applications to networks of queues are in Ferdinand
[1970] and Kouvatsos [1985]. For the interested reader, these papers, in turn,
contain references to other material that provides additional insight into this
approach.
A rauch simplified model that exhibits macroscopic behavior consistent with
a closed network has been proposed by Spearman [1991]. A good review of
many other approximation methods can be found in Agrawal [1985].

6.3. Closed loop systems

The queueing model discussed herein is that of a special class of closed

queueing networks known as cyclic queueing networks. The model has M
stations or servers numbered 1, 2 , . . . , M and arranged in tandem with the
output of the last station or server, M, fed back to the first station (Figure 6.2).
The queueing discipline at each server is FIFO (frst-in-first-out). A fixed
number of customers, say N, perpetually circulate in the system and cyclically
visit stations 1, 2 , . . . , M. The model data includes values for M and N and the
service time parameters at the M servers. The primary performance measure is
 Ch. 5. Performance Evaluation 251

N custoßers

Fig. 6.2. A closed loop system.

the network throughput which is the average arrival rate of customers to a

server and the same for all servers by virtue of the network structure.
In the following discussion, we will restrict ourselves to a model where each
station is a single server station. We shall also ignore any blocking effects due
to limited buffers. In other words, between any pair of adjacent stations, we
assume that there is sufficient waiting room for ( N - 1) customers.
Applications of this closed loop model have been found in several areas
related to manufacturing such as production lines, inspection operations, and
maintenance and repair facilities [Koenigsberg, 1982], and in a class of
assembly systems known as asynchronous automatic assembly systems [Kamath
& Sanders, 1986, 1987; Kamath, Suri & Sanders, 1988].

6.3.1. Closed loop systems with exponential servers

Here we consider the case where the service time at station i is exponentially
distributed with mean ~. Now the model falls into the class of product form
models for which a well-developed theory exists. A review of the theory and
applications of cyclic queues with exponential servers is contained in Koenigs-
berg [1982]. Exact solution of this closed exponential model can be easily
obtained by applying standard methods available for product form networks
(see Section 6.2). Some results for customer response time distributions in
cyclic exponential queueing networks are contained in Boxma, Kelly &
Konheim [1984].

6.3.2. Closed loop systems with general servers

Here the service time at station i, i = 1, 2 , . . . , M, has a general probability
distribution. The network no longer has a product form structure. An exact
solution for this general server case may not be possible. However, several
approximate methods are available [Agrawal, 1985; Kamath, Suri & Sanders,
1988; Shanthikumar & Gocmen, 1983; Shum & Buzen, 1977; Whitt, 1984b].
Here we describe one such method that was primarily developed to analyze
closed cyclic queueing models of asynchronous automatic assembly systems in
Kamath & Sanders [1986, 1987] and Kamath, Suri & Sanders [1988]. In this
case the service time is typically fixed (deterministic) except when a station
'jam' occurs, when there is a repair time distribution. Such a system is not
modeled well by the exponential case. The method below is an extension of the
hode decomposition method in Section 5.2 and is based on weil developed
252 R. Suri et al.

two-moment approximations for the G I / G / 1 queue (see Section 2.2.1). Only

the mean and variance of the service times are needed to perform the
calculations.
2 are the mean
Following the notation in Section 5.2, for station i, r i and c~i
2
and the SCV of service times, respectively, c]i the interarrival-time SCV, cai the
interdeparture-time SCV, P~the utilization, and Wqi the average waiting time. A
•is the throughput or production rate of the closed loop system. We first outline
the approximation method which can be classified as a parametric decomposi-
tion method [Kuehn, 1979; Whitt, 1984b] and then present the solution only
for the balanced case.
In the closed loop system under consideration, the arrival process to each
station is the departure process of the preceding station in line and the last
queue feeds into the first. Using this information about the flow of customers
together with the two-moment renewal approximation to the departure process
of a G I / G / 1 queue (formula (2.15)), elosed form expressions are derived for
2
cù;. The arrival rate to each queue is the unknown network production rate A.
The interdependency among the various station queues is approximately
captured by these rate and variability parameters. Next, the queues are treated
(approximately) as being stochastically independent and for each queue, the
expected waiting time, Wqi, is computed using an approximate formula for
G I / G / 1 queues [formula (2.12) or (2.13)]. Using Little's result a relationship
is established between the total number of customers in the system and the
mean flow times at the individual G I / G / 1 nodes through the unknown network
production rate. In the unbalanced system case, writing this relationship in an
equation form gives us a nonlinear equation in a single unknown. In Kamath,
Suri & Sanders [1988], an efficient biseetion scheme was developed to find the
solution (root) of this equation. In the case of a balanced system, the
relationship yields a quadratic equation when the simple formula (2.11) for the
waiting time approximation is used. We present below the solution for a
balanced system.
All stations have the same parameters, i.e., ri = r and c2i = c 2 for i = 1 ,
2 , . . . , M. It is easy to see that the following equalities hold because of the
symmetric nature of the cyclic model:

2
tal = Ca2
2
~ . . . ~
2
CaM ~
2
Ca
(6.14)

and
2
Cd1 ~ Cd2
2 =
2
. . . ~___ C d M =
z
Cd •
(6.15)

In a closed cyclic network since each arrival process is the departure process
from the previous queue and because of equalities (6.14) and (6.15), the
following equality holds:
2 2
c a = cù. (6.16)
 Ch. 5. Performance Evaluation 253

Focusing on a particular queue (station) and using formula (2.15) and equality
above, we have
2 2
C a = Cs •

The queues representing the M stations in the closed loop system are now
analyzed separately. Let P be the (unknown) station utilization (which is the
same for all stations in this case). Thus the expected equilibrium waiting time
of a customer in queue at station i [using formula (2.12)] is then

TO i=1,2,.. M. (6.17)
w«=«~ 1-0'
Little's result applied to the entire closed loop system gives
M

N = h ~', (Wqi + r). (6.18)

i=l

Using (6.3-6.4) and rewriting the above relationship in the form of an

equation we have

p 2 ( M - Mc 2 ) - p ( M + N ) + N = O. (6.19)

The above equation can be solved explicitly for p to get

if c 2 = 1 ,

P - ] ~ / ( M + N ) 2 + 4MN(c~ - 1) - (M + N) (6.20)
if c~ ¢ 1.
L
Once p is known the production rate is given by

h = -p . (6.21)
T

The above analysis used the simple formula (2.12) for the G I / G / 1 waiting
time approximation. This works weil for large systems [Kamath & Sanders,
1987]. For small systems (say less than ten stations and one customer per
station), more accurate results can be obtained by using the refined G I / G / 1
approximation (2.13). Also, a correction factor derived in Kamath, Suri &
Sanders [1988], which accounts for the fixed number of customers (N) in the
system, considerably improves the accuracy of performance prediction for
small systems. The use of these refined approximations leads to a nonlinear
equation and efficient solution algorithms have been developed in Kamath,
Suri & Sanders [1988].
254 R. Suri et al.

6.4. Multiple class analysis

In this section we consider closed networks with multiple classes of custom-

ers. First we will discuss networks for which exact solutions are known, after
which we will consider approximations for more general systems. A great deal
of the development of this area has come from performance analysis of
computer systems, and some general references on this are Sauer & Chandy
[1981], Lavenberg [1983], and Lazowska, Zahorja, Graham & Sevcik [1984].

6.4.1. Product form solution

6.4.1.1. Theory. A very general category of multiple class closed networks

which exhibit a product form solution was stated by Baskett, Chandy, Muntz &
Palacios [1975]. These networks are known as BCMP networks, after the four
authors, and have already been described in Section 5. They altow various
combinations of service time distributions and service disciplines. However, in
the case where the service discipline is FCFS, the service time distribution must
be exponential with the same (possibly load-dependent) rates for all classes.
The cases where different classes may have different mean service times, and
the product form is retained, involve service disciplines that would be unusual
for manufacturing-such as immediate pre-emption of service. These condi-
tions severely restrict the applicability of the BCMP model to manufacturing
systems, and in most cases one has to resort to approximate solutions of more
realistic models.
Some generalizations of the class of product form networks are possible,
including deterministic routings [Kelly, 1975] and more general service times
than in the original BCMP paper [e.g., Kelly, 1976; and Barbour, 1976]. Also,
the concepts of insensitivity [Schassberger, 1978] and reversibility [Kelly, 1979]
are useful in understanding the properties of product form networks.

6.4.1.2. Computational algorithms. The convolution algorithm was developed

for multiclass networks by Reiser & Kobayashi [1976], while computation of
performance measures using the MVA algorithm is in Reiser & Lavenberg
[1980] and Reiser [1981]. Although both convolution and MVA are relatively
efficient in the single class case, their computational requirements are less
satisfactory for multiclass networks. This is because their needs grow exponen-
tially with the number of classes. Specifically, in a network with M single-server
stations and K classes, with N k customers in class k, both algorithms require of
the order of MK II~= K 1 (N k + 1) operations to compute the main performance
measures. They are also space-intensive, with convolution requiring
K K
2 II~=1 (N k + 1) 2 IIk= 1 (N k + 1) storage locations, and MVA taking
K
M H~=1 (Ne + 1) storage locations [Bruell & Balbo, 1980; Reiser & Lavenberg,
1980]. Agrawal [1985] gives an example showing how these numbers grow
rapidly with the number of classes. For example, a network with 15 stations, 5
classes, and 10 customers in each class requires about 48 million operations,
 Ch. 5. Performance Evaluation 255

and 322000 locations (convolution) or 1.4 million locations (MVA). These

numbers all increase substantially if the stations are load-dependent.
This computational burden has been addressed through three avenues of
developments. The first exploits networks with special structure. The second
uses approximations - some based on analysis and others heuristic, see Zahor-
jan [1983] for a detailed treatment of this topic. The third supplies performance
bounds instead of point estimates. These are now discussed.
6.4.1.2.1. Networks with special structure. Balsamo & Iazeolla [1982] intro-
duced an extension of Norton's Theorem which is computationally advantage-
ous if one only needs to compute performance measures for a small sub-
network of the whole network. The LBANC (Local Balance Algorithm for
Normalizing Constants) and CCNC (Coalesce Computation of Normalizing
Constants) algorithms were proposed by Chandy & Sauer [1980] to reduce the
storage requirements during computation. The tree-convolution method [Lam
& L i e n , 1983] and tree-MVA method [Hoyme, Bruell, Afshari & Kain, 1982]
are efficient for sparse networks, for example, where each class tends to stay in
a sub-area of the network. R E C A L (Recursion by Chain Algorithm) de-
veloped by Conway & Georganas [1986] is particularly efficient when the
number of classes is large compared with the number of stations. De Souza e
Silva & Lavenberg [1989] developed a DAC (Distribution Analysis by Chain)
algorithm which can compute joint queue-length distributions more efficiently
than other approaches.
6.4.1.2.2. MVA-based methods. A large number of approximation tech-
niques for multiclass networks are based on variations of MVA. First we
describe methods for reducing the computational requirements by producing
approximate solutions for product form networks. One of the earliest of these
is the so-called Schweitzer-Bard (SB) approximation, proposed by Schweitzer
[1979] and extensively tested by Bard [1979]. Consider the multiclass version of
the MVA equation (6.9) which is
K
Wik(N) = ~'ik+ ~ Lij(N - lk)~'ik, i = 1. . . . , M , (6.22)
j=l

where the second subscript now refers to the class, N is the vector of class
populations, and 1k is the unit vector in the kth direction. (Thus N - 1« is the
population vector that has one less customer of class k.) Note here that the
service time parameter (~'ik) multiplying the summation term has the fixed
subscript k - this will be significant when we discuss nonproduct form networks
below. In order to reduce the number of computations, the SB method
proposes the approximation

f Lij(N) , j ~ k,
Li'(N-lk)=l-~, l Lik(N), j=k, (6.23)
256 R. Suri et al.

which says intuitively that the number of customers of class j in the equilibrium
distribution for a network with one less customer of class k is simply the
equilibrium number when j ~ k, and smaller by the ratio of (N k - 1 ) / N k when
j = k. Obviously this is a very simplistic approximation, and improvements to it
will be discussed below. Nevertheless it performs reasonably [Schweitzer,
Seidmann & Shalev-Oren, 1986]. The idea now is that instead of iterating from
zero population up to the vector of full populations, we simply note that with
(6.23) the MVA equation (6.22), along with the multidimensional versions of
(6.9)-(6.11) now define a set of nonlinear equations in the unknowns Lij(N ).
These can be solved simply by iterating through the Equations (6.23), (6.9)-
(6.11), or else by any other fixed point solution scheme. For large networks,
convergence is often achieved much fastet through the fixed point iteration,
as compared to working up the vector of populations with the exact algo-
rithms.
Due to the simplistic form of the approximation (6.23), the SB algorithm can
occasionally perform poorly (as much as 30% oft the exact values) for so-called
'stress cases'. Such examples can be found in Chandy & Neuse [1982] who also
proposed the Linearizer algorithm as a way of obtaining improved estimates.
The basic idea is still to iterate at a given population, but at the same time they
iteratively develop an improved estimator for L I j ( N - 1«).
6.4.1.2.3. Asymptotic expansions. A powerful analytical technique, based
on a completely different approach, was introduced by McKenna & Mitra
[1982, 1984]. This uses asymptotic expansions for integral representa-
tions of the performance measures, and is particularly efficient for large net-
works.
6.4.1.2.4. Bounds. In some cases where large networks are being analyzed,
the use of bounding techniques, rather than exact solutions, may be preferable.
Such techniques provide upper and/or lower bounds on various performance
measures, with substantially less computational effort. If the bounds are
acceptably tight, then it may be that the additional computational effort of an
exact solution is not justifiable.
The simplest bounds are obtained from asymptotic bound analysis (ABA)
and only require a few arithmetic operations [Muntz & Wong, 1974; Kleinrock,
1976; Denning & Buzen, 1978]. A B A bounds are, however, typically very
loose. A rauch improved set of bounds, also requiring just a few arithmetic
operations, was developed by Zahorjan, Sevcik, Eager & Galler [1982], and
called balanced job bounds (BJBs). These bound the performance measures of
the original network by two networks, both of which have balanced resource
usage, and whose performance can be computed very simply. A more sophisti-
cated set of bounds is provided by the performance bound hierarchy (PBH)
which is a hierarchy of successively more accurate upper and lower bounds
with the exact solution as its limit [Eager & Sevcik, 1983]. This provides the
analyst with a sequence of trade-offs between computational effort and ac-
curacy.
 Ch. 5. Perforrnance Evaluation 257

6.4.2. Non-product form networks

6.4.2.1. Flow-equivalent approaches. This is the first of the techniques we will

discuss for dealing with nonproduct form networks. The results on flow-
equivalent representations, by Chandy, Herzog & Woo [1975a], were derived
for multiclass networks, so in principle the approximation procedures based on
aggregation and decomposition that were discussed previously, could be ap-
plied to multiclass networks as weil. In practice, however, there is a computa-~
tional problem. Suppose we are interested in approximating a nonproduct form
network, and we derive a multiclass flow-equivalent server for a subsystem in
that network. Note that the service rate function of this server will be of the
form ~(n 1, n z , . . . , nK) where nzc is the number of customers of class k present
at the server, i.e., the service rate for the server depends on the number of
customers of each class. The problem is that the computational complexity for
solving a network with such servers is very great. Therefore, to use aggregation
and decomposition procedures for multiclass networks, one usually has to
incorporate them along with additional approximations. One such approxi-
mation, proposed independently by Brandwajn [1982] and Lazowska & Zahor-
jan [1982] is to replace the varying values of n k above by a fixed value for all
but one class. Thus the K-dimensional function i.t(nl, n 2 , .. , nx) is replaced
by K one-dimensional functions. The fixed values used are the average number
of each class present in the subsystem. This decomposes the network into K
single class networks which need to be solved via an iterative process to ensure
consistency.

6.4.2.2. MVA extensions. Nonproduct form networks can also be analyzed via
heuristic extensions of MVA. The starting point for these is the multiclass MVA
equation (6.22), which lends itself nicely to intuitively reasonable approxi-
mations. A major drawback to the product form solutions is that they do not
apply in a multiclass network where classes may have different service parame-
ters at an FCFS station. This however, is the norm in manufacturing. An
obvious heuristic modification of (6.22) is to replace the fixed service time
parameter in the summation (~'ik) by the service time parameter for each class.
This has the intuitive explanation that the estimated number of each class,
L i j ( N - l k), is multiplied by its mean service time (~-ij). The resulting equation
is
K
W~k(N)= ~ik + ~ L i j ( N - lk)~',/, i=l,...,M. (6.24)
j=l

Example. The above approximation was used by Suri & Hildebrant [1984] to
analyze FMS performance. They also describe how the analysis tool was
implemented and used as part of a decision support system for an FMS at
Hughes Aircraft Co. Their implementation actually incorporated two other
258 R. Suri et al.

approximations as well: the SB approximation for Lij(N - lk), and another one
to account for multiple server stations. Eren with the three approximations,
the predictions from their algorithms were oft only 10%-15% from detailed
simulations. However, as they also showed, the set of approximations enabled
a very efficient implementation, from both CPU time and memory considera-
tions. These approximations were further enhanced by Shalev-Oren, Seidmann
& Schweitzer [1985] whose algorithm showed excellent performance in the
context of FMSs with priority scheduling.

Another obvious extension of the above approximation, to account for

non-exponential distributions, is to modify the summation term by a correction
factor as already shown in equation (6.13). This idea was introduced by Reiser
[1979] in the context of communication networks and was used by Cavaille &
Dubois [1982] for analyzing FMS behavior.

6.5. Special properties of closed networks

Closed networks, because of their structure, enjoy various interesting prop-

erties, which will be discussed in this section. These properties can be useful
for qualitative analysis of the networks, for a priori statements about impact of
parameter changes, for network optimization, or purely as aids to providing
insight into the network behavior.

6.5.1. Monotonicity and second order properties

In general, monotonicity of a performance measure, say Y(0), where 0 is any
parameter of the network, implies that Y is always nondecreasing (of always
non-increasing) in 0. Intuitively, monotonicity assures us that the network is
'well-behaved' with respect to that parameter. For example, one would expect
that if the processing power of a station is increased, then the throughput of
the network should increase (or at least, not decrease). This however, is not
always the ease, as shown by a simple eounterexample in Suri [1985c]. Thus the
question is, under what circumstances do we get the intuitively expected
(monotonic) behavior?
This question has been studied by several researchers for various types of
closed networks. Suri [1985c] begins by looking at monotonicity of throughput
with respect to the number of jobs in a single class product form network, and
then shows that several other intuitively desirable properties follow once this
monotonicity is assured - examples of such properties are, well-behaved partial
derivatives with respect to service time parameters. He also derives various
sufficient conditions for this throughput monotonicity to hold. Related results
for product form networks, and various alternative methods of proof, can be
found in Robertazzi & Lazar [1985], Yao [1985], Shanthikumar & Yao [1987],
and Van der Wal [1989].
The broadest available result on monotonicity is due to Adan & Van der Wal
[1989], and states that the throughput of a single class closed queueing network
 Ch. 5. Performance Evaluation 259

with general service times is nondecreasing in the number of jobs. Note, in

particular, that the network need not have a product form solution for this
result.
As discussed at length in Suri [1985c], monotonicity has many practical uses
in network design and analysis. It can be used in conjunction with performance
bound analysis, in parameter optimization, and in understanding the robust-
ness of queueing network models. Examples of the use of monotonicity in
development of optimization algorithms for FMS are in Vinod & Solberg
[1985], Dallery & Frein [1986], and Lee, Srinivasan & Yano [1989].
Monotonicity and the resulting optimization algorithms are useful in search-
ing for parameter values satisfying the first-order optimality conditions. How-
ever, usuaUy one requires certain second-order properties (e.g., convexity) to
hold for the objective function, at least locally, in order to verify that an
optimum has been found. Second-order properties have traditionally been very
difficult to establish, even for simple queueing systems. Recently however,
Shanthikumar & Yao [1989, 1992] have developed tools based on sample-path
analysis that have provided a host of results on second-order properties for
queueing networks. In particular, they define and use the notion of strong
stochastic convexity and are able to establish results for fairly general classes of
networks. Examples are concavity or convexity with respect to job populations,
server allocation, and service times. In many cases their methods allow them to
derive the properties for nonproduct form networks (e.g., a cyclic network with
general service time distributions). Shanthikumar & Yao [1989] also provide a
survey of existing results and alternate methods of proof for second-order
properties, as weil as several references to optimization and control applica-
tions. In the manufacturing context, several authors have developed algorithms
for optimizing the performance of a manufacturing system based on a queueing
network model for the system. In addition to the references in the previous
paragraph, Stecke & Solberg [1985] and Yao [1985] look at workload alloca-
tion, while Yao & Shanthikumar [1986, 1987] consider workload, server alloca-
tion and buffer allocation. These qualitative properties are also useful in
establishing the simplified model of Spearman [1991].

6.5.2. Sensitivity analysis and robustness

An important question in the application of queueing network models is,
how sensitive are the performance predictions to errors in parameter
estimates? Open network models can be quite sensitive to such errors [Brum-
field, 1982]-intuitively this is understandable since queue lengths become
unbounded as utilization levels approach unity. On the other hand, it turns out
that the main performance measures for closed networks are actually quite
robust to parameter errors; in fact, in general the errors seem to be attenuated,
not magnified. This is a rather desirable property and conducive to practical
use of such models. In order to establish such a property, we first need
expressions for the sensitivity of performance measures to parameters. Hence
260 R. Suri et al.

the connection between the seemingly opposite properties in the subsection

title, namely sensitivity and robustness!
Expressions for parameter sensitivities for closed networks have been de-
rived by Williams & Bhandiwad [1976], Gordon & Dowdy [1980], Suri [1983]
and Tay & Suri [1985]. As an example of the robustness of performance
predictions, consider a system from Tay & Suri [1985]. Here 10 different
parameters (visit ratios and mean service times) can each be estimated with a
5% error. Yet the throughput prediction will still be within 10% of the true
value, and all utilizations will be within 20%.
A deeper use of the robustness results is made by Suri [1983]. It had been
widely observed that queueing network models worked well even for systems
that did not conform to the classical assumptions (i.e., conditions for product
form). For example, Spragins [1980] states, 'The amazing thing is that they
have been successful despite the fact; that a number of the most common
assumptions.., are orten seriously violated for real systems'. As one way of
explaining this phenomenon, Buzen [1976] advanced the concept of operational
analysis, subsequently extended by Denning & Buzen [1978] for queueing
networks, which showed that most of the performance measures for queueing
networks could be derived from a set of assumptions involving no statement of
the underlying probability distributions. However, one of these assumptions,
denoted homogeneous service times (HST), was viewed as being overly
restrictive. Suri [1983] shows that the performance measures are in fact
extremely robust to violations in HST. This provides analytical insight into the
success of closed network models for performance prediction in real systems.

7. Queueing models for machine-operator interference

7.1. Machine-operator interference problem

Automatic or semi-automatic machines require operator service for a variety

of tasks including loading and unloading of parts, scheduled maintenance,
clearing of part jams, and more major machine repairs. The operators may also
be required to perform ancillary duties such as feeding part hoppers in
assembly systems. With the increasing level of automation today, it is common
for an operator to be responsible for tending several machines. When a
machine requires the services of an operator and finds all operators busy
servicing other machines, the machine must wait to be serviced. This waiting
time is known as interference time in the literature [Benson & Cox, 1951;
Palesano & Chandra, 1986; Stecke, 1982; Stecke & Aronson, 1985]. Interfer-
ence or waiting for operator service is undesirable as it decreases the produc-
tivity of a machine and consequently that of the production system. The
amount of interference is a function of the distribution of the operator service
times, the distribution of production times of machines, the number of
machines, and the number of operators. The operator walking times between
 Ch. 5. Performance Evaluation 261

machines and the order in which the machines are tended will also have an
effect on the interference time.
The machine interference problem has received the attention of several
researchers over the last few decades [Ashcroft, 1950; Benson & Cox, 1951;
Stecke, 1982; Stecke & Aronson, 1985]. An expository introduction to various
machine interference problems and brief descriptions of models, charts, and
solution techniques are contained in the review paper by Stecke & Aronson
[1985]. In Stecke [1982] and Stecke & Aronson [1985], several deterministic
and probabilistic models available for the interference problem are reviewed.
The probabilistic models reviewed include the binomial probability analysis
method, queueing theoretic approaches, and simulation models. Information
regarding models that explicitly consider operator walking times and various
types of tending (or operator service) disciplines such as cyclic, alternating
cyclic, distance priority, etc. is contained in Stecke [1982] and Stecke &
Aronson [1985].
In this section, only queueing models that are used for interference calcula-
tions will be described. First, the classical machine-repairman model is de-
scribed and the results are summarized. This is followed by a discussion on the
generalization of this classical model. Next, a closed queueing network model
of the machine-operator system is presented. This alternative model will be
advantageous in situations when the operator service times and the machine
production times have general probability distributions. We then present a
discussion on models that can handle different types of machine stoppage. We
conclude this section with a brief look at the modeling of general production
networks that exhibit instances of interference.

7.2. Preliminaries

Definitions. A failed or a down machine is defined as one either waiting for

operator service or being serviced by an operator. The production time of a
machine is its 'up' time between successive periods of breakdown. Operator
service process is also known as the repair process. (This is due to historical
reasons when the main operator task was repair.)

Notation.
{Given parameters}
K = number of machines,
m = number of operators,
r = average repair (operator service) time,
A =machine breakdown rate (1/A is the average production time of a
machine).
{Performance measures to be predicted}
p~ : steady state probability that there are n failed machines,
L = average number of failed machines,
262 R. Suri et al.

Lq = average number of machines waiting for operator service,

A = machine availability or the long run proportion of time a machine is
available,
I = average interference time which is the amount of time a failed rnachine
has to wait on the average before receiving operator service,
O e = operator efficiency or the long tun proportion of time an operator is busy
or working.

Basic performance relations. Machine availability. From standard reliability

t h e o r y for a system with repair [Barlow & Proschan, 1975], we have

average production time (7.1)

A = average production time + average down time "

If on the average there are L failed machines, then on the average, ( K - L )

are running and each has a breakdown rate of A. Hence, the mean rate of
arrivals, say A«f, into the system is

Aeff = A(K - L ) . (7.2)

Dividing the numerator and denominator of the R H S of (7.1) by A~ù, and

using Little's result (see Section 2) the machine availability can also be defined
as
A = avg. # of running machines
avg. # of running machines + avg. # of failed machines
(7.3)

Since the denominator of (7.3) is just K, the total number of machines,

another definition for machine availability is

A = 1- L __(7.4)
K'

Operator efficiency. This is given by

average numbers of busy operators
(7.5)
Oc = number of operators
or

L - Lq
Oc = - - (7.6)
m

Average interference time. Using A~ef (Equation (7.2)) and Little's result we
can get the average interference time as

! = Lq
A~ff (7.7)
 Ch. 5. Performance Evaluation 263

Assumptions. Unless stated otherwise, the following assumptions are made.

(A1) Any one of the failed machines requires only one of the rn operators to
repair it. Repair times are independent of the number of failed machines.
(A2) Machines fail independently and randomly. All repair times and
production times are independent.
(A3) The operators artend to failed workstations in the order they failed or,
alternatively, the machines are tended in a totally random order.
(A4) The repair times include the time required for an operator to walk to a
machine in need of service.

7.3. Classical machine-repairman model

This classical model assumes that the production time of a machine is

exponential with mean 1/A and operator service time is exponential with mean
z for each operator and each machine. This can be modeled as a finite source
multi-server exponential queueing system, where the operators are the seivers
and machines are the customers. An arrival corresponds to a machine break-
down. Since the number of machines is finite, we have a finite source (of size
K). We now use the results for the M / M / m / • / K queueing system presented in
Section 2.4.
The steady-state probabilities Pn and average number of failed machines, L
are given by formulas (2.32) and (2.34), respectively. Now, the machine
availability A is obtained using formula (7.4). La, the average number of
(failed) machines waiting for operator service is given by
K

Lq = E (n - m)p n , (7.8)
n=m

where Pn is given by formula (2.32). The average interference time 1 can be

obtained using formula (7.7).

7.4. Models with general distributions

General production time distribution and exponential repair times. An im-

portant invariance result was shown for the G / M / m / • / K queue by Bunday &
Scraton [1980]. For this queueing system they showed that the steady-state
probabilities are insensitive to the distributional form of G. In other words, the
probability distribution given by (2.32) and (2.33) are valid for any finite
source system with exponential service or repair times, independent of the
form of the production time distribution. The only requirement is that the
production times of a machine should be independent with a mean 1/A. Hence,
the formulas derived in the previous section are valid for a non-exponential
production time case.
Exponential production time distribution and general repair times. The
queueing model for this case is the M / G / m / • / K queue. For the special case of
rn = 1, i.e., K identical machines handled by a single operator, this queueing
264 R. Suri et al.

system has been solved using an imbedded Markov chain approach [Takacs,
1962]. Any interested reader is also referred to Tijms [1988] for a detailed
analysis of the finite source M / G / 1 queue using a regenerative process
approach. For the multiple operator case some approximations for the steady-
state probabilities are contained in Tijms [1988].
General production time and repair time distributions. Few results are
available for this case which is the most general case of the machine-repairman
problem. The model is a G I / G / m / • / K queue. For this general case, viewing
the machine-repairman model as a closed queueing network may lead to the
development of some useful approximations. This alternative view is presented
next.

7.5. A closed queueing network model

Because of the finite customer population, the machine-operator interfer-

ence model can be visualized as a two-stage cyclic queueing network model
(Figure 7.1). The number of customers circulating in the network is fixed and is
equal to K, the number of machines. One of the stages corresponds to running
machines (i.e., those that can fail but are in a working state). We refer to this
stage as Stage 1. This stage has K identical parallel servers. This parallel server
node can be replaced by an infinite server or delay node as customers do not
have to wait in queue at this stage. The other stage, Stage 2, is an m-server
node with a common queue. This stage corresponds to the pool of operators.
Customers waiting in the common queue correspond to the failed machines
waiting for operators to become available. A customer movement from Stage 2

Kcustomers

-iß OP 1

-~ OP 2
H
I~ OP m

Stage1 Stage2
Fig. 7.1. Two-stage machine-operator cyclic queueing model.
 Ch. 5. Performance Evaluation 265

to Stage 1 corresponds to the completion of a repair operation and a customer

departure from Stage 1 corresponds to the stoppage or breakdown of a
machine.
The service time distribution of a server in Stage 1 is the production time
distribution of the machines, while that of a server in Stage 2 is the repair time
distribution. We will consider the steady-state solution. The probability of
finding n customers at Stage 2 is Pn and average interference time I is just the
expected waiting time in queue at Stage 2. Machine availability is the utiliza-
tion of a server in Stage 1 and operator efficiency is the utilization of a server in
Stage 2. Hence, the solution of the closed queueing network model directly
yields the desired performance measures. The mean arrival rate to each stage
or the unknown network throughput rate is Aeff. Estimating the values of p,,
may not be required because most solution techniques for closed networks (see
Section 6) directly yield a value for the network throughput rate which in our
case is Aef«. This in conjunction with a waiting time result for the queue at
Stage 2 would suffice to determine the basic performance measures. The
problem is thus reduced to solving a closed queueing network with general
service time FIFO servers. Approximate methods of solving such a network are
discussed in Section 6.

7.6. Different types of stoppage

In the interference models considered so far, we implicitly assumed that

either (i) the machines experience only one type of stoppage or (ii) the
machines experience different types of stoppage and the stoppage modeled is
an 'aggregate' of the different types. In this section, we describe briefly certain
models that (explicitly) consider different types of stoppage.
Benson & Cox [1951] provide solutions to the following problems involving
different types of stoppage. (i) A single operator attending a n u m b e r of
machines which are liable to two types of stoppage, the time to stoppage
exponentially distributed with mean 1/A 1 or 1/A 2 depending on whether the
stoppage is of the first or second type and the operator service times exponen-
tial with mean r I (type 1 stoppage) or r: (type 2 stoppage). For this problem
their results seem to suggest that the choice between attending machines with
long and short stoppages is of little importance. (ii) A team of m operators
attending a particular number of machines eaeh of which can experience rn
types of stoppage. Each operator is trained to attend only one type of
stoppage. The time to stoppage is exponentially distributed with mean 1/A r if
the stoppage is of type r, r = 1, 2 . . . . , m. The repair time for a stoppage of the
rth type is distributed exponentially with mean %.
Kelly [1976] considers an example machine interference problem which is
closely related to the second problem described above. He considers closed
queueing network models of m a c h i n e - o p e r a t o r interference. His example
system contains K identical machines and two operators with different skills.
266 R. Suri et al.

Machines may experience two types of stoppage and the type of stoppage
determines which operator attends to the machine. The assumptions on the
production times of machines and stoppages themselves are quite general and
are (i) the production time distribution of a machine can be arbitrary, (ii) the
current production time and the reason for the current machine stoppage may
depend upon previous production times and previous reasons for stoppage for
that machine, and (iii) the reason for a machine stoppage may also depend
upon the current production time. Each operator attends to the machines that
are waiting for his service in the order of their stopping. The operator service
times are distributed exponentially with mean r I (operator 1) o r r 2 (operator
2). For further details see Kelly [1976].
Interference problems with multiple types of stoppage are also studied by
Palesano & Chandra [1986]. Their system has a single operator and a group of
identical machines, each subject to r (r/> 2) types of stoppage and the time
between type i (i = 1, 2 , . . . , r) stoppages is exponential. The operator service
time can be either deterministic, exponential, Erlang, or hyperexponential and
the mean service time can depend on the type of stoppage. The operator uses a
nonpreemptive fixed-priority rule to service the failed machines. Palesano and
Chandra perform an imbedded Markov chain analysis and develop a numerical
method for obtaining the steady-state performance measures. They also per-
form a sensitivity analysis of the performance measures to the type of the
service time distribution. One of their observations is that the average interfer-
ence time becomes insensitive to the type of service time distribution and the
order of priorities as the operator efficiency approaches unity.

7. 7. Production n e t w o r k m o d e l s and interference

The queueing models used to solve interference problems, such as the

classical machine-repairman model, assume that information (e.g., the mean)
about machine production time or the time to the next request for operator
service is known. Some probability based models [Stecke, 1982] that calculate
interference, require the probability that a machine is down or failed at any
given moment. When machines are part of a production network, these
(probabilities and mean times) have to be calculated from other system
parameters. In this situation, a simultaneous solution of the machine interfer-
ence problem and the production network model is called for. An example of
this situation can be found in Bulgak, Kamath & Sanders [1989], Kamath
[1989], and Kamath & Sanders [1991], where one of the problems considered is
the determination of the performance of an automatic assembly system for a
given assignment of operators.
Next, we present a different perspective on the production network problem
which has an interference problem as one of its components. If the machines
and operators are viewed as resources, then, in the event of a machine
stoppage, the job currently occupying the machine would be using two
resources, the machine and an operator, at the same time. In the product form
 Ch. 5. Performance Evaluation 267

network terminology, the queueing network, with machines and operators as

resources and jobs as customers, has an instance of simultaneous resource
possession (SRP) [De Souza e Silva & Muntz, 1987; Jacobson & Lazowska,
1982; Pattipati & Kastner, 1988]. Any network with SRP falls into the category
of nonproduct form queueing networks and in general this network can be
solved only approximately.
Practical solutions to the machine-operator interference problem have been
implemented and used in a few cases. For instance, the MPX package models
multiple classes of operators tending multiple classes of machines [Suri &
DeTreville, 1991]. The solution approach (similar to that in Section 7.5)
consists of decomposing the network into two levels: the machine-operator
problem is analyzed as a multiple class closed network; this generates PMs that
are used to modify the machine service times in the open network. Application
of this to an industrial example with operators is in DeTreville [1991].

8. Advanced topics

8.1. General networks with finite buffers

Limited buffer space is a reality in any manufacturing system, as well as in

computer systems and communication networks. Thus the topic of per-
formance analysis of networks with finite buffers has received a lot of attention
from researchers. Perros [1984] provides a bibliography of 75 papers, Suri &
Diehl [1986] also have a large bibliography, and the collection in Perros &
Altiok [1989] provides a set of very recent papers. Even so, despite all the
research effort devoted, a fairly robust and universal solution to the blocking
problem has eluded analysts- we will elaborate on this point below.

8.1.1. Types of blocking

In a finite buffer system, the number of jobs that can queue for a station may
be limited. In this case, when the buffer is full, and another job tries to depart
from its current server and queue for that station, we say 'blocking' is
occurring: the job that is attempting to join the full buffer is called the blocked
job, and the server from which the blocked job is trying to depart is also said to
be blocked. The unsuspecting reader starting on this topic should immediately
be alerted to the fact that many different definitions of blocking exist, and it is
possible to make a grave mistake by modeling the wrong type of blocking. The
key is how the blocked job is treated. The two most common types of blocking
are: transfer blocking (also called manufacturing blocking) where a job, after
completing service, attempts to go to the next queue, but if it is blocked it stays
at its current server which cannot serve another job and thus is also blocked;
and service blocking (also called communication blocking) where a job taust
announce its destination before starting service, and service cannot begin if the
268 R. Suri et al.

destination buffer is full, and again the blocked job stays at its current server
which gets blocked. Other types of blocking include the case where service
must be restarted if the destination buffer is full, and where the job that is
blocked is lost (disappears from the network). We will primarily cover work
relating to transfer blocking (the most common in manufacturing), and block-
and-recirculate - a particular case of the restarting situation which can repre-
sent certain material handling systems. In the remainder of this section, we will
first cover the cases where exact solutions are available, then divide our
coverage of approximations into those for open and closed networks. Due to
the complexity and diverse nature of the approaches, we cannot do justice to
each approach in the space here, so our coverage will necessarily be brief. We
will mention some recent references, as weil as papers that themselves have a
good bibliography.

8.1.2. Exact solutions

In general, the occurrence of blocking destroys the product form solution,
making analytical solutions intractable even for the case of exponential service
times - the stare space becomes unmanageably large. However, there a r e a few
special situations where the solutions are tractable. The key here is whether the
'reversibility' property is retained [Kelly, 1979]. If it is, then the product form
solution is available, along with the possibility of efficient computational
algorithms. Some of the early work along these lines was by Yao & Buzacott
[1985b] in the context of FMSs, particularly those with a centralized material
handling system - Yao [1989] gives an up to date review. More recent develop-
ments include those of Akyildiz [1989] and Onvural [1989], who also provide
extensive references.

8.1.3. Approximations for finite buffers in open networks

The most rigorously analyzed open configuration with finite buffers is the
case of the tandem network. This has been covered in detail in Section 3, so
here we shall deal only with approaches for more general configurations. The
most common approaches involve decomposition and aggregation methods (see
Section 6.2.3) where the finite buffer system is replaced by a pseudo-equivalent
system with unlimited buffers and modified parameters for the servers
[Takahashi, Miyahara & Hasegawa, 1980; Jun & Perros, 1989; Takahashi,
1989; Schweitzer & Altiok, 1989]. Daskalaki & Smith [1989] also consider
routing in finite buffer networks. In some cases, special methods are used for
specific topologies, e.g., Konheim & Reiser [1976, 1978], or special blocking
definitions [Boxma & Konheim 1981]. Finally, a completely different approach
is provided through the use of the maximum entropy formalism [Kouvatsos &
Xenios, 1989], also see Section 6.2.3.2. The analysis of open networks with
acyclic job routing is rauch easier, but any recirculation or cyclic routing
usually makes the approximations poor (see also Section 8.1.6).
 Ch. 5. Performance Evaluation 269

8.1.4. Approximations for finite buffers in closed networks

The analog of the open tandem network, for closed systems, is the closed
loop system or cyclic network (see Section 6.3). Cyclic networks with blocking
are analyzed by Gordon & Newell [1967b], Suri & Diehl [1986], Kamath
[1989], and Onvural & Perros [1990]. More general networks are again
analyzed by decomposition and/or aggregation methods [Suri & Diehl, 1986;
Dallery & Frein, 1989]. Other approaches involve heavy traffic limit theorems
[Kogan & Krichagina, 1989] and maximum entropy methods [Kouvatsos &
Xenios, 1989].

8.1.5. Bounds and qualitative properties

Recently there has been much attention on the qualitative properties of
queueing networks (see Sections 6.4.1.2.4 and 6.5). This attention has extend-
ed to finite buffer systems as weil. Van Dijk [1989] derives performance bounds
for such networks, and provides other recent references on bounding methods.
Monotonicity properties are studied by Adan & Van der Wal [1989] and
Shanthikumar & Yao [1989, 1992] who also consider second-order properties
and convexity for finite buffer systems.

8.1.6. Remarks
In concluding this subsection it can be said that, for general networks with
limited buffers, no single solution technique exists that is efficient, applies to a
wide class of systems, and is robust (i.e., works weil over a wide range of
configurations and parameter values). This is in contrast to networks with
unlimited buffer space: for example, for general open networks, Whitt [1983]
and Bitran & Tirupati [1988] provide solution techniques that are both efficient
and robust, and this is also evident to the extent that many industrial
applications have been reported (Section 5.4). No such widespread use is
found for general finite buffer solution algorithms. While the problem of
finding a 'universal' finite buffer solution technique remains an open one, it is
interesting to speculate on the reasons that make it difficult. First, blocking by
its very nature means that the status of one station can seriously affect the
service at another station, which destroys the 'pseudo-independence' of sta-
tions that is exploited by most of the efficient techniques. Attempts at
decomposition and aggregation, therefore, become elaborate and require many
special cases to be considered. Second, whenever one station blocks two or
more stations, one needs to make sequencing decisions for the order of the
unblocking. These decisions can have major effect on the performance, which
means that this type of analysis needs to consider a greater level of sequencing
detail than for the case of unlimited buffers. In fact, minor changes in topology
or unblocking rules can have large effects on performance, a situation that
always pushes the limits of analysis. Finally, there is also the possibility of
deadlock with blocking, and it seems difficult to incorporate its effects efficient-
ly in analytical models for the general case. For all these reasons, we see the
development of a robust and efficient general purpose analyzer for networks
with finite buffers as a continuing challenge for the indefinite future.
270 R. Suri et al.

8.2. Kanban and related production control systems

Along with the inftuence of Japanese manufacturing techniques [e.g., Schon-

berger, 1982] have come several schemes to assist in the shop floor im-
plementation of JIT. Probably the most well known of these is the Kanban
system [Schonberger, 1983]. Performance analysis of Kanban systems has
attracted the attention of the OR/MS community [see the review in Uzsoy &
Martin-Vega, 1990]. Related to this is the analysis of various other production
control schemes which interface with the new Kanban methods. We will
therefore review related schemes here as well.
Essentially, Kanban is a card, or other form of signal, which instructs an
upstream workstation to begin working on the next job. (Hence the alternative
term 'pull system'.) In the more complex Dual Kanban system [Schonberger,
1983], Kanban are also used to signal material handling tasks. As in the
previous sections, we will only review network-related ADMs below; other
techniques to analyze pull systems (deterministic models, inventory models,
petri nets, and simulation) are reviewed in Uzsoy & Martin-Vega [1990].
Suri & DeTreville [1986] analyze the behavior of a simple Kanban system,
focusing on modeling the learning effects described in the JIT literature.
Seidmann [1988] uses a semi-Markov decision program to compare alternative
pull policies. Karmarkar and Kekre [1989] provide insight into batching
policies for Kanban systems using Markov models of elementary systems, while
more complex models are considered by Groenevelt & Karmarkar [1988].
Kanban-related production control policies are analyzed in Glassey & Resende
[1988], Deleersnyder, Hodgson, Muller & O'Grady [1989], Karmarkar [1989],
Mitra & Mitrani [1990, 1991], and Spearman & Zazanis [1992]. Models that
address both M R P and Kanban systems are in Buzacott [1989] and Buzacott &
Shanthikumar [1992a]. CONWlP, an alternative pull system, is analyzed in
Spearman, Woodruff & Hopp [1990]. Much of the remaining work on analyti-
cal models is very recent, and still in the form of working papers; we have only
covered articles that have appeared in the open literature.
Since Kanban policies essentially restrict the number of jobs in the system,
their analysis is related to closed network models with blocking (since the
non-availability of a Kanban can shut down a station). However, the blocking
mechanism induced by Kanban is different from the other ones mentioned in
Section 8.1.4. Still, it is possible that many approaches referenced in Section
8.1.4 could be applicable, with minor modifications, to performance analysis of
Kanban systems. We feel here a responsibility to communicate to the O R / M S
community the importance of 'not missing the boat' in modeling Kanban
systems. To view Kanban (and JIT) as merely an inventory control policy is to
ignore most of the benefits of JIT. As elaborated in Suri & DeTreville [1986],
the major effects of JIT and Kanban come from the longer term learning and
organizational changes induced by these mechanisms, not from the per-
formance obtained with a given set of parameters. Ignoring this aspect will lead
O R / M S publications on Kanban to the same fate as the EOQ formula.
 Ch. 5. Performance Evaluation 271

8.3. Simulation and other dynamic models

As stated in Section 1, in this chapter we only deal in some depth with

analytical models related to queueing networks. Hefe we simply summarize
other types of dynamic models used for production network analysis. From an
industrial applications point of view, the most widely used method is discrete
event simulation, and a number of software packages are available for this
[Law & Haider, 1989]. A large number of industrial applications of simulation
can be found in the annual Proceedings of the Winter Sirnulation Conference,
published each December. Related to simulation, and of more interest to the
research community, are some recent techniques for sensitivity analysis based
on sample-path approaches [Ho, 19871. These include perturbation analysis
[see the review in Suri, 1989a] and likelihood ratio methods [Glynn, 1989;
Reiman & Weiss, 1989; Rubinstein, 1989]. Suri & Dille [1985] give a detailed
example illustrating the use of such sensitivity analysis methods for decision
making in an FMS.
Another approach involves the use of Petri net models. A Petri net is a
formal mathematical language and set of symbols used to model a discrete
event system. Although originally Petri nets were used primarily to analyze
qualitative or logical questions (e.g., 'is there a possibility of deadlock with this
control rule?') more recently, stochastic Petri ner models have been used for
performance analysis as weil [Holliday & Vernon, 1987]. Examples of manufac-
turing applications include modeling of FMS [Kamath & Viswanadham, 1986;
Viswanadham & Narahari, 1992] and Kanban systems [Di Mascolo, Frein,
Dallery & David, 1989]. Other analytical models include algebraic models
[Cohen, Dubois, Quadrat & Viot, 1985; Olsder, Resing, De Vries, Keane &
Hooghiemstra, 1988] and formal language models [Inan & Varaiya, 1989;
Ramadge & Wonham, 1989]. An up-to-date overview and bibliography of
many of these other approaches can be found in Leung & Suri [1990].

8.4. Hierarchical, hybrid, and integrated models

This subsection covers models of systems that are rauch more complex than
the ones discussed in earlier sections. In manufacturing, it is common for a
workpiece to require multiple resources, such as a machine, an operator, and a
fixture. This becomes difficult to analyze, and often simulation models must be
used for performance analysis. One set of approximation schemes that has
been proposed, however, uses hierarchical queueing network models. A
special case of these, namely machine-operator interference models, has
already been discussed in Section 7, and involves a two-level hierarchy.
Pattipati & Kastner [1988] present a three-level hierarchical model for the
analysis of a large and complex electronics facility. Such models bear a relation
to the literature on 'simultaneous resource possession' in computer systems
modeling, and a good review of various approaches can be found in Agrawal
[19851.
272 R. Suri et al.

In some cases, complex systems can be analyzed using hybrid models, which
are models composed of more than one type of technique. Shanthikumar &
Sargent [1983] describe and classify a number of hybrid simulation/analytic
models, while Balbo, Bruel & Ghanta [1986] combine queueing network
models with Petri nets.
Generally, during the life cycle of a manufacturing system, or during the
course of an analysis project, no single performance analysis tool will serve all
purposes. Therefore, a set of tools or 'toolbox' is more appropriate. Rather
than work with a number of independent tools, each with their own data and
models, some recent efforts have been made to develop integrated tools for
manufacturing analysis [Anderson, Diehl, Shimizu & Suri, 1988; Suri &
Tomsicek, 1988]. The benefits of integration include consistency of data across
models, eliminating the need to build new models from scratch, and rapid
exploration of multiple alternatives [Shimizu, 1991]. Manufacturing applica-
tions of such integrated tools are documented in Shimizu & Van Zoest [1988]
and Desruelle, Gujar & Hammer [1990].

8.5. Research issues

We could state here a long list of network configurations that remain

unsolved, or for which current approximations remain unsatisfactory. Such a
list can, however, be easily derived by the researcher who carefully reads each
of the preceding sections along with some of the key references. Therefore, we
prefer to keep our remarks here at more of a fundamental level, in terms of
general directions for the community, and also add a few somewhat subjective
observations on what we consider to be important future directions of this
field.
A critical observation that can be made about this subject is that industrial
application of ADMs in manufacturing remain relatively limited- this is in
contrast with other OR tools such as Linear Programming whose use is
widespread. Although tools based on queueing network models are beginning
to see greater use in manufacturing (see Section 5.4), we feel their potential
remains largely untapped. This has an important implication for our communi-
ty: it means we need to devote more effort (and provide greater incentives) to
applying the modeling methods described in this chapter, and to publicizing the
successful applications.
Given the recent successes of JIT and other Japanese manufacturing tech-
niques, as weil as the industrial awareness and acceptance of the need for those
methods, a good strategy would seem to be for researchers to find analysis
tools to assist in and complement the implementation of those techniques. One
area that has already attracted attention is that of Kanban or pull systems, as
discussed in Section 8.2. However, we restate our earlier remark that by simply
modeling the control policy we risk missing many of the effects of JIT. In their
recent review of models for Kanban systems, Uzsoy & Martin-Vega [1990] list
the major benefits of JIT and then state: 'The large number of unquantifiable
 Ch, 5. Performance Evaluation 273

factors among those listed above and their intimate interrelation has rendered
the development of mathematically based decision support tools for JIT
environments difficult.' We see this not as an insurmountable task, but as a
challenge for the modeling community: if our work is to remain relevant to the
latest trends in manufacturing, then we must find better ways to quantify and
model the benefits of JIT and related methods. For instance, one the benefits
of JIT is the longer term learning that takes place on the shop floor, and a
simple model in Suri & DeTreville [1986] gives insight into the benefits of JIT
as weil as the potential pitfalls of poor implementation of JIT. Also, extensive
studies in Mody, Suri, Sanders & Tatikonda [1991], Mody, Suri, Sanders &
Van Zoest [1991] and Mody, Sanders, Suri, Contreras & Rao [1991], based on
ADMs, show the benefits of JIT implementation, including some of the
so-called unquantifiable factors. Taking this idea a step further, any ways of
using ADMs to support manufacturing strategy are likely to receive more
attention than simply analyzing operational details [Suri & DeTreville, 1991].
Another way for expanding the use of these models is to integrate them with
existing mainstream organizational procedures. Two important areas for which
integration seems feasible in the short term are Manufacturing Resource
Planning (MRP II) systems, and costing systems. Initial steps in integrating
with MRP II systems have been discussed [Karmarkar, 1989; Luber, 1990;
Buzacott & Shanthikumar, 1992a], but this requires better analysis of tree-
structured assembly systems (Section 4), multi-period models, as weil as
analysis of the distribution of leadtimes [e.g., Shanthikumar & Buzacott, 1984;
Seidmann & Nof, 1985; Shanthikumar & Sumita, 1988]. Integrating with
costing systems involves improved modeling of total system costs, including
overheads, so that the full benefits of various alternatives can be quantified
[e.g., Fu, Falkner, Suri & Garlid, 1988; Mody, Suri, Sanders & Tatikonda,
1991].
A technical problem that deserves being singled out here is that of modeling
general networks with blocking. As discussed in Section 8.1.6, the problem of
finding a good and fairly universal approximation procedure for such networks
remains unsolved. At the same time, buffer sizing is important in many modern
automated systems, as well as in JIT systems. Related to this is the general
problem of modeling material handling systems (such as automatic guided
vehicle systems), where blocking is also an important issue. While a few
analytical inroads have been made into these areas, currently simulation is the
major technique used to study the performance of such systems.
A general approach to such complex systems is to look for qualitative
results. Initial successes in this area are represented by Shanthikumar & Yao
[1989, 1992] and Glasserman & Yao [1991, 1992a,b].
Finally, instead of trying to extend our analytical models for more and more
complex systems, there is an alternative: that is, to simplify the manufacturing
systems so that they can be analyzed by weU-understood models. Much of the
basis for success of JIT and related methods comes from simplification, such as,
reducing the number of levels of assembly, cutting down the number of
 274 R. Suri et al.

components using group technology, and simplifying layouts using cellular

manufacturing [Schonberger, 1982, 1986]. Here we refer to a particular type of
simplification, that which comes from analyzability. This is not just a hypoth-
esis: Suri & Shimizu [1989] term this approach Design for Analysis, argue why
it is worth investigating, and give several examples of industrial situations
where such a methodology has resulted in competitive advantage. The research
agenda related to this approach is therefore twofold: (i) what are the manufac-
turing building blocks, and ways of combining them, that result in systems that
are analyzable with known models; and (ii) in which directions should we push
the frontiers of our modeling abilities to make the set of such building blocks
m o r e universal. It should also be noted that if this approach gains acceptance,
it intimately binds performance analysis with design, and it would accomplish
our stated goal of having our community play a more active and strategic role
in design and manufacturing decisions.
In conclusion, in the last two decades there has been an exponential (!)
growth in performance analysis techniques for production networks, and it is
also encouraging to see some industrial applications of these methods. How-
ever, there is much to be done to bring these techniques and tools to the point
where they are in everyday use by manufacturing and industrial engineers. We
see this as the most important challenge for the performance analysis com-
munity during the decade of the 1990s.

Acknowledgements

Several researchers provided us with valuable feedback on an earlier version

of this chapter. In particular, we would like to acknowledge useful comments
f r o m John Buzacott, Ramki Desiraju, Bor-Ruey Fu, Ying-Tat Leung, Chandu
R a o , Avi Seidmann, Kathy Stecke, Kalluru Venkateswar, and David Yao.

References

Adan, I, and J. Van der Wal (1989). Monotonicityof the throughput of a closed queueing network
in the number of jobs. Oper. Res. 37(6), 953-957.
Agrawal, S.C. (1985). Metamodeling: A study of approximations in queueing models, Research
Reports and Notes, Computer Systems Series, MIT Press, Cambridge, MA.
Akyildiz, I.F. (1989). Exact analysis of queueing networks with rejection blocking, in: H.G. Perros
and T. Altiok (eds.), Queueing Networks with Blocking, Elsevier, Amsterdam, pp. 19-32.
Albin, S.L. (1982). Poisson approximations for superposition arrival processes in queues. Manage-
ment Sci. 28(2), 126-137.
Altiok, T. (1982). Approximate analysis of exponential tandem queues with blocking. European J.
Oper. Res. 11, 390-398.
Altiok, T., and S. Stidham Jr (1982). A note on transfer lines with unreliable machines, random
processing times, and finite buffers. IIE Trans. 12(2), 125-127.
Altiok, T., and S. Stidham Jr (1983). The allocation of interstage buffer capacities in production
lines. IIE Trans. 15(4), 292-299.
 Ch. 5. Performance Evaluation 275

Alvarez, R., Y. Dallery and R. David (1991). An experimental study of the continuous flow model
of transfer lines with unreliable maehines and finite buffers. IMACS-IFA C Symposium: Model-
ing and Control of Technological Systems 9I, Lilie, France.
Ammar, M.H. (1980). Modelling and analysis of unreliable manufacturing assembly networks with
finite storage, MIT Laboratory for Information and Decision Sciences, Report LIDS-TH-1004.
Anderson, K.R. (1987). A metbod for planning analysis and design simulation of CIM systems.
Proc. 1987 Winter Simulation Conf., IEEE Computer Society Press, pp. 715-720.
Anderson, K.R., G.W. Diehl, M. Shimizu and R. Suri (1988). Integrating spreadsheets, system
modeling, and animation for rapid computer-aided design of manufacturing systems. Proc. 1988
University Programs in Computer-Aided Engineering, Design and Manufacturing (UPCAEDM)
Conf.
Ashcroft, H. (1950). The productivity of several machines under the care of one operator. J. Roy.
Statist. Soc. B 12(9) 145-151.
Balbo, G., S.C. Bruel and S. Ghanta (1986). Combining queueing network and generalized
stochastic Petri net models for the analysis of some software blocking phenomena. IEEE Trans.
Software Engrg. 12(4), 561-576.
Balbo, G., G. Chiola and G. Franceschinis (1989). Stochastic Petri net simulation for the
evaluation of flexible manufacturing systems. Proc. 1989 European Simulation Multi«onference,
pp. 5-12.
Balsamo, S., and G. Iazeolla (1982). An extension of Norton's theorem for queueing networks.
IEEE Trans. Software Engrg. 8(4), 298-305.
Barbour, A.D. (1976). Networks of queues and the method of stages. Adv. Appl. Probl. 8,
584-591.
Bard, Y. (1979). Some extensions to multiclass queueing network analysis, in: M. Arato (ed.),
Performance of Computer Systems, North-Holland, Amsterdam.
Barlow, R.E., and F. Proschan (1975). Statistical theory of Reliability and Life Testing: Probability
Models, Holt, Reinhart, and Winston, New York.
Baskett, F., K.M. Chandy, R.R. Muntz and F.G. Palacios (1975). Open, closed, and mixed
networks of queues with different classes of customers. J. ACM 22(2), 248-260.
Benson, F., and D.R. Cox (1951). The productivity of machines requiring attention at random
intervals. J. Roy. Statist. Soc. B 13(1), 65-82.
BGS Systems, Inc. (1982). BEST/1 User's Guide, Waltham, MA.
Bhat, U.N. (1972). Elements of Applied Stochastic Processes, Wiley, New York.
Bitran, G.R., and D. Tirupati (1988). Multiproduct queueing networks with deterministic routing:
Decomposition approach and the notion of interference. Management Sci. 34(1), 75-100.
Bitran, G.R., and D. Tirupati (1991). Approximations for networks of queues with overtime.
Management Sci. 37(3), 282-300.
Boxma, O.J., F.E Kelly and A.G. Konheim (1984). The product form of the sojourn time
distributions in cyclic exponential queues. J. ACM 31(1), 128-133.
Boxma, O.J., and A.G. Konheim (1981). Approximate analysis of exponential queueing systems
with blocking. Acta Inform. 15, 19-66.
Brandwajn, A.E. (1974). A model of a time-sharing virtual memory system solved using
equivalenee and decomposition methods. Acta lnform. 4(1), 11-47.
Brandwajn, A.E. (1982). Fast approximate solution of multiprogramming models, Proc. 1982
ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, Seattle,
August 1982, Performance Evaluation Rev. I1(4), 141-149.
Brandwajn, A., and Y.L. Jow (1988). An approximation method for tandem queues with blocking.
Oper. Res. 36(1), 73-83.
Brown, E. (1988). IBM combines rapid modeling technique and simulation to design PCB
factory-of-the-future. Ind. Eng. 20(6), 23-26.
Bruell, S.C., and G. Balbo (1980). Computational Algorithms for Closed Queueing Networks,
Elsevier, New York.
Brumfield, J.A. (1982). Operational analysis of queueing phenomenon, Ph.D. Thesis, Dept. of
Computer Sciences, Purdue University, West Lafayette.
276 R. Suri et al.

Bulgak, A.A., M. Kamath and J.L. Sanders (1989). Research on the dynamics and design
optimization of automatic assembly systems. Proc. 15th Conf. on Production Research and
Technology, SME, 275-283.
Bunday, B.D., and R.E. Scraton (1980). The G / M / r machine interference model. European J.
Oper. Res. 4, 399-402.
Burke, P.J. (1956). The output of a queueing system. Oper. Res. 4, 699-704.
Buzacott, J.A. (1967). Automatic transfer lines with buffer stocks. Internat. J. Prod. Res. 5(3),
183 -200.
Buzaeott, J.A. (1972). The effect of station breakdowns and random processing times on the
capacity of flow lines with in-process storage. A l l E Trans. 4(4), 308-312.
Buzacott, J.A. (1982). 'Optimal' operating rules for automated manufacturing systems. I E E E
Trans. Automat. Control, 80-86.
Buzacott, J.A. (1989). Queueing models of Kanban and MRP controlled production systems.
Engrg. Costs Prod. Econom. 17, 3-20.
Buzacott, J.A. (1990). Abandoning the moving assembly line: Models of human operators and job
sequencing. Internat. J. Prod. Res. 28(5), 821-839.
Buzacott, J.A., and L.E. Hanifin (1978). Models of automatic transfer lines with inventory
banks- A review and comparison. A l l e Trans. I0(2), 197-207.
Buzacott, J.A., and D. Kostelski (1987). Matrix-geometric and recursive algorithm solution of a
two-stage unreliable flow line. HE Trans. 19(4), 429-438.
Buzacott, J.A., and J.G. Shanthikumar (1980). Models for understanding flexible manufacturing
systems. A H E Trans. 12, 339-350.
Buzacott, J.A., and J.G. Shanthikumar (1985). On approximate queueing models of dynamic job
shops. Management Sci. 31(7), 870-887.
Buzacott, J.A., and J.G. Shanthikumar (1992a). A general approach for coordinating production
in multiple-cell manufacturing systems. Prod. Oper. Management 1(1), 34-52.
Buzacott, J.A., and J.G. Shanthikumar (1992b). Stochastic Models o f Manufacturing Systems,
Prentice-Hall, Englewood Cliffs, NJ.
Buzacott, J.A., and D.D. Yao (1986). Flexible manufacturing systems: A review of analytical
models. Management Sci. 32(7), 890-905.
Buzen, J.P. (1973). Computational algorithms for closed queueing networks with exponential
servers. Commun. A C M 16(9), 527-531.
Buzen, J.P. (1976). Operational analysis: The key to the new generation of performance prediction
tools. COMPCON Fall 1976, Washington, DC, 166-171.
Calabrese, J.M., and W.H. Hausman (1991). Simultaneous determination of lot sizes and routing
mix in job shops. Management Sci. 37(8), 1043-1057.
Cavaille, J.B., and D. Dubois (1982). Heuristic methods based on mean value analysis for flexible
manufacturing systems performance evaluation. Proc. 21st I E E E Conf. on Decision and
Control, Orlando, Florida, pp. 1061-1065.
Chandy, K.M., U. Herzog and L. Woo (1975a). Parametric analysis of queueing networks. IBM J.
Res. Develop. 19(1), 36-42.
Chandy, K.M., U. Herzog and L. Woo (1975b). Approximate analysis of general queueing
networks. I B M J. Res. Develop. 19(1), 43-49.
Chandy, K.M., and D. Neuse (1982). Linearizer: A heuristic algorithm for queueing network
models of computing systems. Commun. A C M 25(2), 126-134.
Chandy, K.M., and C.H. Sauer (1980). Computational algorithms for product form queueing
networks. Commun. A C M 23(10), 573-583.
Chen, H., J.M. Harrison, A. Mandelbaum, A. Van Ackere and L.M. Wein (1988). Empirical
evaluation of a queueing network model for semiconductor wafer fabrication. Oper. Res. 36,
202-215.
Choobineh, F., and R. Suri, eds. (1986). Flexible ManuJhcturing Systems: Current lssues and
Models, Industrial Engineering & Management Press, Atlanta, GA.
Choong, Y.F., and S.B. Gershwin (1987). A decomposition method for the approximate evalua-
tion of capacitated transfer lines with unreliable machines and random processing times. I1E
Trans. I9(2), 150-159.
 Ch. 5. Performance Evaluation 277

Clark, C.D. (1961). The greatest of a finite set of random variables. Oper. Res. 9(2), 145-162.
Cohen, G., D. Dubois, J.P. Quadrat and M. Viot (1985). A linear-system-theoretic view of
discrete-event processes and its use for performance evaluation in manufacturing. IEEE Trans.
Automat. Control 30, 210-220.
Conway, A.E., and N.D. Georganas (1986). R E C A L - A new efficient algorithm for the
exact anatysis of multiple-chain closed queueing networks. J. Assoc. Cornput. Mach. 33(4),
768-791.
Courtois, P.J. (1977). Decomposability: Queueing and Computer System Applications, Academic
Press, New York.
Dallery, Y., R. David and X.L. Xie (1988). An efficient algorithm for analysis of transfer lines
with unretiable machincs and finite buffers. IIE Trans. 20(3), 280-283.
Dallery, Y., R. David and X.L. Xie (1989). Approximate analysis of transfer lines with unreliable
machines and finite buffers. IEEE Trans. Automat. Control 34(9), 943-953.
Dallery, Y., and Y. Frein (1986). An efficient method to determine the optimal configuration of a
flexible manufacturing system. Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Sys-
tems, Ann Arbor, MI, pp. 269-282.
Dallery, Y., and Y. Frein (1989). A decomposition method for the approximate analysis of closed
queueing networks with blocking, in: H.G. Perros and T. Altiok (eds.), Queueing Networks with
Blocking, Elsevier, Amsterdam, pp. 19-32.
Daskalaki, S., and J.M. Smith (1989). Real-time routing in finite queueing networks, in: H.G.
Perros and T. Altiok (eds.), Queueing Networks with Blocking, Elsevier, Amsterdam, pp.
313-324.
Deleersnyder, J.-L., T.J. Hodgson, H. Muller and P.J. O'Grady (1989). Kanban controUed pull
systems: An analytical approach. Management Sci. 35(9), 1079-1091.
Denning, P.J., and J.P. Buzen (1978). The operational analysis of queueing network models. ACM
Comput. Surveys 10(3), 225-261.
Dertouzos, M.L., R.K. Lester, R.M. Solow and the MIT Commission on Industrial Productivity
(1989). Made in America: Regaining the Productive Edge, MIT Press, London.
De Souza e Silva, E., and S.S. Lavenberg (1989). Calculating joint queue-length distributions in
product-form queueing networks. J. Assoc. Comput. Mach. 36(1), 194-207.
De Souza e Silva, E., and R.R. Muntz (1987). Approximate solutions for a class of nonproduct
form queueing networks. Performance Evaluation 7, 221-242.
Desruelle, P., R. Gujar and R. Hammer (1990). Design of a circuit board manufacturing module
using a consistent sequence of PC-based analysis tools. Proc. Manufacturing Intl. '90 Conf.,
ASME Press.
DeTreville, S. (1991). FMS: Finnish manufacturing systems. Manuf. Syst. 9, 14-17.
Dietrich, B.L., and B.M. March (1985). An application of a hybrid approach to modeling a
flexible manufacturing system. Ann. Oper. Res. 3, 263-276.
Di Mascolo, M., Y. Frein, Y. Dallery and R. David (1989). Modeling of Kanban systems using
Petri nets. Proc. Third ORSA/T1MS Conf. Flexible Manufacturing Syst., Elsevier, Amsterdam,
pp. 307-312.
Disney, R., and D. Koenig (1985). Queueing networks: A survey of their random processes.
S1AM Rer. 27, 335-403.
Eager, D.L., and K.C. Sevcik (1983). Performance bound hierarchies for queueing networks.
ACM Trans. Comp. Syst. 1(2), 99-115.
Emerson, H.P., and D.C.E. Naehring (1988). Origins of Industrial Engineering: The Early Years
of Profession, Industrial Engineering & Management Press, Atlanta, GA.
Ferdinand, A.E. (1970). A statistical mechanical approach to systems analysis. IBM J. Res'.
Develop. 14, 539-547.
Flatto, L., and S. Hahn (1984). Two parallel queues created by arrivats with two demands. I.
SIAM J. Appl. Math. 44(5), 1041-1053.
Fleming, P.J., and B. Simon (1991). Interpolation approximations of sojourn time distributions.
Oper. Res. 39(2), 251-260.
Foster, F.G., and H.G. Perros (1980). On the blocking process in queue networks. European J.
Oper. Res. 5, 276-283.
278 R. Suri et al.

Fu, B.R., C. Falkner, R. Suri and S. Garlid (1988). Combining economic analysis and system
modeling to evaluate test strategies for circuit board assembly lines, in: J.A. Edosomwan and A.
Ballakur (eds.), Productivity and Quality Improvement in Electronics Assembly, Industrial
Engineering & Management Press, Atlanta, GA, pp. 479-506.
Gelenbe, E., and G. Pujolle (1987). Introduction to Queueing Networks. Wiley, New York.
Gershwin, S.B, (1987a). An efficient decomposition method for the approximate evaluation of
tandem queues with finite storage space and blocking. Oper. Res. 35(2), 291-305.
Gershwin, S.B. (1987b). Representation and analysis of transfer lines with machines that have
different processing rates. Arm. Oper. Res. 9, 511-530.
Gershwin, S.B. (1991). Assembly/disassembly systems: An efficient decomposition algorithm for
tree-structured nctworks. IIE Trans. 23(4), 302-314.
Gershwin, S.B., and O. Berman (1981). Analysis of transfer lines consisting of two unreliable
machines with random processing times and finite storage buffers. AIIE Trans. 13(1), 2-11.
Gershwin, S.B., R.R. Hildebrant, S.K. Mitter, and R. Suri (1986). A control perspectivc on
recent trends in manufacturing systems. IEEE Control Syst. Mag. 6, 3-15.
Gershwin, S.B., and I.C. Schick (1983). Modeling and analysis of three-stage transfer lines with
unreliable machines and finite buffers. Oper. Res. 31, 354-380.
Glasserman, P., and D.D. Yao (1991). Algebraic structure of some stochastic discrete event
systems, with applications. Discrete Event Dynamic Systems: Theory and Applications 1, 7-35.
Glasserman, P., and D.D. Yao (1992a). Monotonicity in generalized semi Markov processes. Math.
Oper. Res. 17(1), 1-21.
Glasserman, P., and D.D. Yao (1992b). Generalized semi-Markov processes: Antimatroid struc-
tute and second-order properties. Math. Oper. Res. 17(2), 444-469.
Glassey, C.R., and M.G.C. Resende (1988). Closed-loop release control for VLSI circuit
manufacturing. IEEE Trans. Semiconductor Manuf. 1, 36-46.
Glynn, P.W. (1989). Likelihood ratio derivative estimators for stochastic systems. Proc. 1989
Winter Simulation Conf., IEEE Computer Society Press, pp. 374-380.
Glynn, P.W., and W. Whitt (1991). A new view of the heavy-traffic limit theorem for infinite-server
queues. Adv. in Appl. Probab. 23(1), 188-209.
Gordon, K.D., and L.W. Dowdy (1980). The impact of certain parameter estimation errors in
queueing network models. Proc. Performance '80, Toronto, Canada, Performance Evaluation
Rer. 9(2), 3-9.
Gordon, W.J., and G.F. Newell (1967a). Closed queueing systems with exponential servers. Oper.
Res. 15, 254-265.
Gordon, W.J., and G.F. Newell (1967b). Cyclic queueing systems with restricted length queues.
Oper. Res. 15, 266-277.
Graves, S.C. (1981). A review of production scheduling. Oper. Res. 29(4), 646-675.
Groenevelt, H., and U.S. Karmarkar (1988). A dynamic Kanban system case study. Prod. lnvent.
Management J. 29, 46-50.
Gross, D., and C.M. Harris (1985). Fundamentals of Queueing Theory, Wiley, New York.
Harper, R., and M.J. O'Loughlin (1987). Manufacturing process analysis- Tools and applications.
Proceedings of the 1987 Winter Simulation Conference, IEEE Computer Society Press, pp.
731-737.
Harrison, J.M. (1973). Assembly like queues. J. Appl. Probab. 10, 354-367.
Harrison, J., and V. Nguyen (1990). The QNET method for two-moment analysis of open
queueing networks. Queueing 8yst. 6, 1-32.
Hax, A.C., and H.C. Meal (1975). Hierarchical integration of production planning and scheduling,
in: M.A. Geisler (ed.), Logistics, North-Holland, Amsterdam.
Hayes, R.H., S.C. Wheelwright and K.B. Clark (1988). Dynamic Manufacturing: Creating the
Learning Organization, The Free Press, New York.
Heyman, P., and M.J. Sobel (1982). Stochastic Models in Operations Research, McGraw-Hill, New
York.
Hillier, F.S., and R.W. Boling (1967). Finite queues in series with exponential or Erlang service
t i m e s - A numerical approach. Oper. Res. 15, 286-303.
 Ch. 5. Performance Evaluation 279

Ho, Y.C. (1987). Performance evaluation and perturbation analysis of discrete event dynamic
systems. IEEE Trans. Automat. Control 32, 563-572.
Holliday, M.A., and M.K. Vernon (1987). A generalized timed Petri ner model for performance
analysis. IEEE Trans. Software Engrg. 13, 1297-1310.
Hopp, W.J., and J.T. Simon (1989). Bounds and heuristics for assembly-like queues. Queueing
Syst. 4, 137-156.
Hoyme, K.P., S.C. Bruell, P.V. Afshari and R.Y. Kain (1982). A tree-structured MVA algorithm,
Tech. Report 82-17, Computer Science Dpartment, University of Minnesota, Minneapolis, MN.
Inan, K.M., and P.P. Varaiya (1989). Algebras of discrete event models. Proc. IEEE 77, 24-38.
Jackson, J.R. (1963). Jobshop-like queueing systems. Management Sci. 10, 131-142.
Jacobson, P.A., and E.D. Lazowska (1982). Analyzing queueing networks with simultaneous
resource possession. Commun. ACM 25(2), 142-151.
Jun, K.P., and H.G. Perros (1989). Approximate analysis of arbitrary configurations of queueing
networks with blocking and deadlock, in: H.G. Perros and T. Altiok (eds.), Queueing Networks
with Blocking, Elsevier, Amsterdam, pp. 259-279.
Kamath, M. (1989). Analytical performance models for automatic assembly systems, Ph.D. thesis,
Dept. of Industrial Engineering, University of Wisconsin-Madison.
Kamath, M., and J.L. Sanders (1986). Analysis of asynchronous automatic assembly systems with
bottleneck stations. SYSTEMS I Conf. Papers, SME, Chicago, IL.
Kamath, M., and J.L. Sanders (1987). Analytical methods for performance evaluation of large
asynchronous automatic assembly systems. Large Scale Syst. 12(2), 143-154.
Kamath, M., and J.L. Sanders (1991). Modeling operator/workstation interference in asynchron-
ous automatic assembly systems. Discrete Event Dynamic Systems: Theory and Applications 1,
93-124.
Kamath, M., R. Suri, and J.L. Sanders (1988). Analytical performance models for closed-loop
flexible assembly systems. Internat. J. Flexible Manuf. Syst. 1, 51-84.
Kamath, M., and N. Viswanadham (1986). Applications of Petri net based models in the modeling
and analysis of flexible manufacturing systems, Proc. IEEE 1986 Internat. Conf. Robotics
Automation, IEEE Computer Society Press, pp. 312-317.
Karmarkar, U.S. (1987). Lot sizes, lead times and in-process inventories. Management Sci. 33,
409 -418.
Karmarkar, U.S. (1989). Capacity loading, release planning and master scheduling with WIP and
lead times. J. Manuf. Oper. Management.
Karmarkar, U.S., and S. Kekre (1989). Batehing policy in Kanban systems. J. Manuf. Syst. 9(4),
317-328.
Karmarkar, U.S., S. Kekre and S. Kekre (1985a). Lot sizing in multi-item multi-machine job
shops. IIE Trans. 17, 290-292.
Karmarkar, U.S., S. Kekre, S. Kekre and S. Freeman (1985b). Lotsizing and lead time per-
formance in a manufacturing cell. Interfaces 15, 1-9.
Kelly, F.P. (1975). Networks of queues with customers of different types. J. Appl. Probab. 12,
542 -554.
Kelly, F.P. (1976). Networks of queues. Adv. Appl. Prob. 8, 416-432.
Kelly, F.P. (1979). Reversibility and Stochastic Networks, Wiley, New York.
Kimemia, J.G., and S.B. Gershwin (1983). An algorithm for the computer control of production
in flexible manufacturing systems. IIE Trans. 15(4), 353-362.
Kingman, J.F.C. (1962). Some inequalities for the GI/G/1 queue. Biometrika 49, 315-324.
Kleinrock, L. (1975). Queueing Systems Vol. 1: Theory. Wiley, New York.
Kleinrock, L. (1976). Queueing Systems Vol. 2: Computer Applications, Wiley, New York.
Kobayashi, H, (1974). Application of the diffusion approximation to queueing networks I:
Equilibrium queue distributions. J. ACM 21, 316-328.
Koenigsberg, E. (1959). Production lines and internal s t o r a g e - A review. Management Sci. 5,
401-433.
Koenigsberg, E. (1982). Twenty five years of cyclic queues and closed queue networks: A review.
J. Oper. Res. Soc. 33, 605-619.
 280 R. Suri et al.

Koenigsberg, E., and A. Mamer (1982). The analysis of production systems. Internat. J. Prod.
Res. 20, 1-14.
Kogan, Ya.A., and E.V. Krichagina (1989). Closed exponential queueing networks with blocking
in heavy traffic, in: H.G. Perros and T. Altiok (eds.), Queueing Networks with Blocking,
Elsevier, Amsterdam, pp. 217-225.
Konheim, A.G., and M. Reiser (1976). A queueing model with finite waiting room and btocking.
J. Assoc. Comput. Mach. 23(2), 328-341.
Konheim, A.G., and M. Reiser (1978). Finite capacity queueing systems with applications in
computer modeling. S1AM J, Comput. 7(2), 210-229.
Kouvatsos, D.D. (1985). Maximum entropy methods for general queueing networks, in: D. Poltier
(ed.), Modelling Techniques and Tools for Performance Analysis, North-Holland, Amsterdam,
pp. 589-608.
Kouvatsos, D.D., and N.P. Xenios (1989). Maximum entropy analysis of general queueing
networks with blocking, in: H.G. Perros and T. Altiok (eds.), Queueing Networks with Blocking,
Elsevier, Amsterdam, pp. 281-309.
Kraemer, W., and M. Langenbach-Belz (1976). Approximate formulae for the delay in the
queueing system GI/G/1. Proc. 8th Internat. Teletraffic Congress, Melbourne, pp. 235-
1/8.
Kuehn, P,J. (1979). Approximate analysis of general queueing networks by decomposition. IEEE
Trans. Comm. 27, 113-126.
Labetoulle, J., and G. Pujolle (1980). Isolation method in a network of queues. IEEE Trans.
Software Engrg. 6(4), 373-381.
Lam, S.S., and Y.L. Lien (1983). A tree convoluted algorithm for the solution of queueing
networks. Commun. ACM 26(3), 203-215.
Latouche, G. (1981). Queues with paired customers. J. Appl. Probab. 18, 684-690.
Lavenberg, S.S. (ed.) (1983). Computer Performance Modeling Handbook, Academic Press, New
York.
Law, A.M., and S.W. Haider (1989). Selecting simulation software for manufacturing applications:
Practical guidelines and software survey. Ind. Eng. 21, 33-46.
Lazowska, E.D., and J. Zahorjan (1982). Muttiple class memory constrained queueing networks,
Proc. 1982 ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems,
Seattle, August 1982, Performance Evaluation Rev. 11(4), 130-140.
Lazowska, E.D., J. Zahorjan, G.S. Graham and K.C. Sevcik (1984). Quantitative System
Performance: Computer System Analysis Using Queueing Network Models, Prentice-Hall,
Englewood Cliffs, NJ.
Lee, H.F., M.M. Srinivasan and C.A. Yano (1989). An algorithm for the minimum cost
configuration problem in flexible manufacturing systems, in: K.E. Stecke and R. Suri (eds.),
Proc. 3rd ORSA/T1MS Conf. on Flexible Manufacturing Systems: Operations Research Models
and Applications, Elsevier, Amsterdam, pp. 85-00.
Leung, Y.T., and M. Kamath (1991). Performance analysis of synchronous production lines. IEEE
Trans. Robotics and Automation 7(1), 1-8.
Leung, Y.T., and R. Suri (1990). Performance evaluation of discrete manufacturing systems. IEEE
Control Syst. Mag., 77-86.
Lindley, D.V. (1952). The theory of queues with a single server. Proc. Cambridge Philos. Soc. 48,
277 -289.
Lipper, E.H., and B. Sengupta (1986). Assembly4ike queues with finite capacity: Bounds,
asymptotics and approximations. Queueing Syst.: Theory Appl. 1, 67.
Little, J.D.C. (1961). A proof for the queueing formula L = AW. Oper. Res. 9, 383-387.
Liu, X.-G., and J.A. Buzacott (1989). A zero-buffer equivalence technique for decomposing
queueing networks with blocking, in: H.G, Perros and T. Altiok (eds.), Queueing Networks with
Blocking, Elsevier, Amsterdam, pp. 87-104.
Liu, X.-G., and J.A. Buzacott (1990). Approximate models of assembly systems with finite
inventory banks. European J. Oper. Res. 45(2-3), 143-154.
Luber, A, (1990). Rapid mode]ing systems: A practical alternative to MRP II rough cut capacity
planning. P & IM Rev., March.
 Ch. 5. Perforrnance Evaluation 281

Marchal, W.G. (1985). Numerical performance of approximate queueing formulae with application
to flexible manufacturing systems. Arm. Oper. Res. 3, 141-152.
Marie, R. (1978). Modelisation par reseaux de files d'attente, Ph.D. thesis, Université de Rennes,
France.
Marshall, K.T. (1968). Some inequalities in queueing. Oper. Res. 16, 65t-665.
Mascolo, M.D., R. David and Y. Dallery (1991). Modeling and analysis of assembly systems witb
unreliable machines and finite buffers. IIE Trans. 23(4), 315-330.
McKenna, J., and D. Mitra (1982). Integral representations and asymptotic expansions for closed
Markovian queueing networks: Normal usage. Bell Syst. Tech. J. 61(5), 661-683.
McKenna, J., and D. Mitra (1984). Asymptotic expansions and integral representations of
moments of queue lengths in closed Markovian networks. J. A C M 31(2), 346-360.
Mitra, D., and I. Mitrani (1990). Analysis of a Kanban discipline for cell coordination in
production lines. I. Management Sci. 36(12), 1548-1566.
Mitra, D., and I. Mitrani (1991). Analysis of a Kanban discipline for cell coordination in
production lines. II: Stochastic demands. Oper. Res. 39(5), 807-823.
Mody, A., J i . Sanders, R. Suri, F. Contreras and P.C. Rao (1991). International Competition in
the Bicycle lndustry: Keeping Pace with Technological Change, The World Bank, Washington
DC.
Mody, A., R. Suri, J.L. Sanders and M. Tatikonda (1991). International Competition in the Printed
Circuit Board Industry: Keeping Pace with Technological Change, The World Bank, Washington,
DC.
Mody, A., R. Suri, J.L. Sanders and D. Van Zoest (1991). International Competition in the
Footwear Industry: Keeping Pace with Technologial Change, The World Bank, Washington, DC.
Muntz, R.R., and J. Wong (1974). Asymptotic properties of closed queueing network models.
Proc. 8th Ann. Princeton Conf. on Information Science and Systems, Princeton University.
Muth, E.J. (1979). The reversibility property of production lines. Management Sci. 25(2),
152-158.
Neuts, M.F. (1981). Matrix-Geometric Solutions in Stochastic Models, Johns Hopkins University
Press, Baltimore.
Nymon, J. (1987). Using analytical and simulation modeling for early factory prototyping.
Proceedings of the 1987 Winter Simulation Conference, IEEE Computer Society Press, pp.
721-724.
Ohmi, T. (1981). An approximation for the production efficiency of automatic transfer lines with
in-process storages. A l l E Trans. 13(1), 22-28.
Olsder, G.J., J.A.C. Resing, R.E. De Vries, M.S. Keane and G. Hooghiemstra (1988). Discrete
event systems with stochastic processing times. Proc. 27th IEEE Conf. Decision and Control.
IEEE Computer Society Prëss.
Onvural, R. (1989). On the exact decomposition of deadlock free closed queueing networks with
blocking, in: H.G. Perros and T. Altiok (eds.), Queueing Networks with Blocking, Elsevier,
Amsterdam, pp. 73-83.
Onvural, R.O., and H.G. Perros (1990). Approximate throughput in cyclic queueing networks
with blocking. IEEE Trans. Software Engrg. 15, 800-808.
Palesano, J., and J. Chandra (1986). A machine interference problem with multiple types of
failures. Internat. J. Prod. Res. 24(3), 567-582.
Pattipati, K.R., and M.P. Kastner (1988). A hierarchical queueing network model of a large
electronics test facility, lnform. Decision Tech. 14(1), 45-64.
Perros, H.G. (1984). Queueing networks with blocking: A bibliography. Performance Evaluation
Rev., A C M SIGMETRICS 12, 8-12.
Perros, H.G., and T. Altiok (1986). Approximate analysis of open networks of queues witb
blocking: Tandem configurations. I E E E Trans. on Software Engrg. 12(3), 450-461.
Perros, H.G., and T. Altiok (eds.) (1989). Queueing Networks with Blocking, Elsevier, Am-
sterdam.
Pollock, S.M., J.R. Birge and J.M. Alden (1985). Approximation analysis for open tandem queues
with blocking: Exponential and general service distribution, Technical Report 85-30. Depart-
ment of Industrial and Operations Engrg., The University of Michigan, Ann Arbor, MI.
 282 R. Suri et al.

Ramadge, P.J., and W.M. Wonham (1989). The control of discrete event systems. Proc. IEEE 77,
81-98.
Reiman, M (1984). Open queueing networks in heavy traffic. Math. Oper. Res. 9, 441-458.
Reiman, M.I., and A. Weiss (1989). Sensitivity analysis for simulations via likelihood ratlos. Oper.
Res'. 37, 830-844.
Reiser, M. (1979). A queueing network analysis of computer communication networks with
window flow control. IEEE Trans. Comm. 27, 1199-1209.
Reiser, M. (1981). Mean-value analysis and convolution method for queue-dependent servers in
closed queueing networks. Performance Evaluation 1, 7-18.
Reiser, M., and H. Kobayashi (1974). Accuracy of the diffusion approximation for some queueing
systems. IBM J. Res. Develop. 18, 110-124.
Reiser, M., and H. Kobayashi (1976). Queueing networks with multiple closed chains: Theory and
computational algorithms. IBM J. Res. Develop. 19, 283-294,
Reiser, M.; and S.S. Lavenberg (1980). Mean-value analysis of closed multichain queueing
networks. J. ACM 27, 313-322.
Robertazzi, T.G.', and A.A. Lazar (1985). On the modeling and optimal flow control of the
Jacksonian network. Performance Evaluation 5, 29-43.
Ross, S.M. (1989). Introduction to Probability Models. Academic Press, Orlando, FL.
Rubinstein, R.Y. (1989). Sensitivity analysis and performance extrapolation for computer simula-
tion models. Oper. Res. 37, 72-81.
Saboo, S., and W.E. Wilhelm (1986). An approach for modeling small-lot assembly networks. I1E
Trans. 18, 322-334.
Sauer, C.H., and K.M. Chandy (1981). Computer System Performance Evaluation, Prentice-Hall,
Englewood Cliffs, NJ.
Schassberger, R. (1978). The insensitivity of stationary probabilities in networks of queues. Adv.
Appl. Prob. 10, 906-912.
Schonberger, R.J. (1982). Japanese Manufacturing Techniques: Nine Hidden Lessons in Simplicity,
The Free Press, New York.
Schonberger, R.J. (1983). Applications of single-card and dual-card Kanban. lnterfaces 13(4)
56-67.
Schonberger, R.J. (1986). World Class Manufacturing: The Lessons of Simplieity Applied, The
Free Press, New York.
Schweitzer, P. (1979). Approximate analysis of multiclass closed networks of queues, Presented at
the International Conference, Stochastic Control and Optimization, Amsterdam, The Nether-
lands.
Schweitzer, P.J., and T. Altiok (1989). Aggregate modeling of tandem queues without inter-
mediate buffers, in: H.G. Perros and T. Altiok (eds.), Queueing Networks with Blocking,
Elsevier, Amsterdam, pp. 47-72.
Schweitzer, P.J., A. Seidmann and S. Shalev-Oren (1986). The correction terms in approximate
mean value analysis. Oper. Res. Lett. 4(5).
Segal, M., and W. Whitt (1989). A queueing network analyzer for manufacturing. Proc. 12th
Internat. Teletraffic Congress, Torino, Italy, June 1988, pp. 1146-1152.
Seidmann, A. (1988). Regenerative pull (Kanban) production control policies. European J. Oper.
Res. 35, 401-413.
Seidmann, A., and S.Y. Nof (1985). Unitary manufacturing cell design with random product
feedback flow. HE Trans. 17, 188-193.
Seidmann, A., P.J. Schweitzer and S. Shalev-Oren (1987). Computerized closed queueing network
models of flexible manufacturing systems: A comparative evaluation. Large Scale Systems 12,
91-107.
Sevcik, K.C., A.I. Levy, S.K. Tripathi and J.L. Zahorjan (1977). Improving approximations of
aggregated queueing network subsystems, in: K.M. Chandy and M. Reiser (eds.), Computer
Performance, North-Holland, Amsterdam, pp. 1-22.
Sevcik, K.C., and I. Mitrani (1979). The distribution of queueing network states at input and
output instants, in: Performance of Computer Systems, North-Holland, New York, pp. 319-335.
 Ch. 5. Performance Evaluation 283

Shalev-Oren, S., A. Seidmann and P.J. Schweitzer (1985). Analysis of flexible manufacturing
systems with priority scheduling: PMVA. Ann. Oper. Res. 3, 115-139.
Shanthikumar, J.G., and J.A. Buzacott (1980). On the approximations to the single server queue.
Internat. J. Prod. Res. 18, 761-773.
Shanthikumar, J.G., and J.A. Buzacott (1981). Open queueing network models of dynamic job
shops. Internat. J. Prod. Res. 19, 255-266.
Shanthikumar, J.G., and J.A. Buzacott (1984). The time spent in a dynamic job shop. European J.
Oper. Res. 17, 215-226.
Shanthikumar, J.G., and M. Gocmen (1983). Heuristic analysis of closed queueing networks.
Internat. J. Prod. Res. 21, 675-690.
Shanthikumar, J.G., and R.G. Sargent (1983). A unifying view of hybrid simulation/analytic
models and modeling. Oper. Res. 31(6), 1030-1052.
Shanthikumar, J.G., and U. Sumita (1988). Approximations for the time spent in a dynamic job
shop with applications to due date assignment. Internat. J. Prod. Res. 26, 1329-1352.
Shanthikumar, J.G., and D.D. Yao (1987). Stochastic monotonicity of the queue lengths in closed
queueing networks. Oper. Res. 35, 583-588.
Shanthikumar, J.G., and D.D. Yao (1989). Second-order stochastic properties in queueing
systems. Proc. IEEE 77(1), 162-170.
Shanthikumar, J.G., and D.D. Yao (1992). Spatiotemporal convexity of stochastic processes and
applications. Probab. Engrg. Inform. Sci. 6, 1-16.
Shimizu, M. (1991). Application of an integrated modeling approach to design and analysis of
manufacturing systems. Adv. Manuf. Engrg., to appear.
Shimizu, M., and D. Van Zoest (1988). Analysis of a factory of the future using an integrated set
of software for manufacturing systems modeling. Proc. 1988 Winter Simulation Conf., IEEE
Computer Society Press, pp. 671-677.
Shore, J.E., and R.W. Johnson (1980). Axiomatic derivation of the principle of maximum entropy
and the principle of minimum cross-entropy. IEEE Trans. Inform. Theory 26(1), 26-37.
Shore, J.E., and R.W. Johnson (1981). Properties of cross-entropy minimization. IEEE Trans.
Inform. Theory 27(4), 472-482.
Shum, A.W., and J.P. Buzen (1977). The EPF technique: A method for obtaining approximate
solutions to closed queueing networks with general service times. Proc. 3rd Internat. Syrnpos. on
Measuring, Modelling and Evaluating Comput. Systems, Bonn, Germany. North-Holland,
Amsterdam, pp. 201-220.
Solberg, J.J. (1977). A mathematical model of computerized manufacturing systems. Proc. 4th
Internat. Conf. Production Research, Tokyo, Japan.
Spearman, M.L. (1991). An analytic congestion model for closed production systems with IFR
processing times. Management Sci. 37(8), 1015-1029.
Spearman, M.L., D.L. Woodruff and W.J. Hopp (1990). CONWIP: A pull alternative to Kanban.
Internat. J. Prod. Res. 28(5), 879-894.
Spearman, M.L., and M.A. Zazanis (1992). Push and pull production systems: Issues and
comparisons. Oper. Res. 40(3), 521-532.
Spragins, J. (1980). Analytical queueing models: Guest editors introduction. IEEE Computer
13(4), 9-11.
Stecke,, K.E. (1982). Machine interference: The assignment of machines to operators, in: G.
Salvendy (ed.), Handbook of lndustrial Engineering, Wiley, New York.
Stecke, K.E. (1985). Design, planning, scheduling, and control problems of flexible manufacturing
systems. Ann. Oper. Res. 3, 3-12.
Stecke, K.E., and J.E. Aronson (1985). Review of operator/machine interference models.
Internat. J. Prod. Res. 23(1), 129-151.
Stecke, K.E., and J.J. Solberg (1985). The optimality of unbalancing both workloads and machine
group sizes in closed queueing networks of multi-server queues. Oper. Res. 33(4), 882-910.
Stecke, K.E., and R. Suri (1985). Flexible Manufacturing Systems: Operations Research Models
and Applications, J.C. Baltzer, Basel, Switzerland.
284 R. Suri et al.

Stecke, K.E., and R. Suri (1986). Proceedings of the Second ORSA/T1MS Conference on Flexible
Manufacturing Systems: Operations Research Models and Applications, Elsevier, Amsterdam.
Stecke, K.E., and R. Suri (cds.) (1988). Flexible Manufacturing Systems: Operations Research
Models and Applications H, J.C. Baltzer, Basel, Switzerland.
Stecke, K.E., and R. Suri (1989). Proceedings of the Third ORSA/TIMS Conferenee on Flexible
Manufacturing Systems: Operations Research Models and Applications, Elsevier, Amsterdam.
Stidham, S. (1974). A last word on L = AW. Oper. Res. 22, 417-421.
Stoyan, D. (1983). Comparison Methods for Queues and Other Stochastic Models (English edition,
edited and revised by D.J. Daley), Wiley, New York.
Suri, R. (1983). Robustness of queueing network formulas. J. ACM 30(3), 564-594.
Suri, R. (1985a). An overview of evaluative models for flexible manufacturing systems, Arm. Oper.
Res. 3, 13-21.
Suri, R. (1985b). Quantitative techniques for robotic systems analysis, in: S.Y. Nof (ed.),
Handbook of lndustrial Robotics, Wiley, New York, Chapter 31.
Suri, R. (1985c). A concept of monotonicity and its characterization for closed queueing networks.
Oper. Res. 33, 606-624.
Suri, R. (1988a). A new perspective on manufacturing systems analysis, in: W.D. Compton (ed.),
Design and Analysis of lntegrated Manufacturing Systems, National Academy Press, Washington,
DC, pp. 118-133.
Suri, R. (1988b). RMT puts manufacturing at the helm. Manuf. Engrg. 100(2), 41-44.
Suri, R. (1989a). Perturbation analysis: The stare of the art and research issues explained via the
G / G / 1 queue. Proc. IEEE 77, 114-137.
Suri, R. (1989b). Lead time reduction tbrough rapid modeling. Manuf. Syst. 7, 66-68.
Suri, R., and S. DeTreville (1986). Getting from 'Just-in-Case' to 'Just-in-Time': Insights from a
simple model. J. Oper. Management 6(3), 295-304.
Suri, R., and S. DeTreville (1991). Full speed ahead: A look at rapid modeling technology in
operations management. OR/MS Today 18, 34-42.
Suri, R., and S. DeTreville (1992). Rapid modeling: The use of queueing models to support
time-based competitive manufacturing, in: G. Fandel (ed.), Proceedings of the German/U.S.
Conference on Recent Developments in Operations Research, Springer, Berlin.
Suri, R., and G.W. Diehl (1986). A variable buffer-size model and its use in analyzing closed
queueing networks with blocking. Management Sci. 32(2), 206-224.
Suri, R., and G.W. Diehl (1987). Rough-cut modeting: An alternative to simulation. CIM Rev. 3,
25 -32.
Suri, R., G.W. Diehl and R. Dean (1986). Quick and easy manufacturing systems analysis using
MANUPLAN. Proc. Spring IIE Conf., Dallas, TX, IIE, Noreross, GA, pp. 195-205.
Suri, R., and J.W. Dille (1985). A technique for on-line sensitivity analysis of flexible manufactur-
ing systems. Ann. Oper. Res. 3, 381-391.
Suri, R., and B.R. Fu (1991). On using continuous flow lines for performance estimation of
discrete production lines, in: B.L. Nelson, W.D. Kelton and G.M. Clark (cds.), Proceedings of
the 1991 Winter Simulation Conference, pp. 968-977.
Suri, R., and R.R. Hildebrant (1984). Modeling flexible manufacturing systems using mean-value
analysis. J. Manuf. Syst. 3(1), 27-38.
Suri, R., and M. Shimizu (1989). Design for analysis: A new strategy to improve the design
process. Res. Engrg. Des. 1, 105-120.
Suri, R., and M. Tomsieek (1988). Rapid modeling tools for manufacturing simulation and
analysis. Proc. 1988 Winter Simulation Conference, IEEE Computer Society Press, pp. 25-32.
Suri, R., M. Tomsicek and D. Derleth (1990). Manufacturing systems modeling using ManuPlan
and SimStarter: A tutorial. Proc. 1990 Winter Simulation Conference, IEEE Computer Society
Press, pp. 168-176.
Suri, R., and C.K. Whitney (1984). Decision support requirements in flexible manufacturing. J.
Manuf. Syst. 3(1), 61-69.
Takacs, L. (1962). Introduction to the Theory of Queues, Oxford Univ. Press, Oxford.
 Ch. 5. Performance Evaluation 285

Takahashi, Y. (1989). Aggregate approximation of acyclic queueing networks with communication

blocking, in: H.G. Perros and T. Altiok (eds.), Queueing Networks with Blocking, Elsevier,
Amsterdam, pp. 33-46.
Takahashi, Y., H. Miyahara and T. Hasegawa (1980). An approximation method for open
restricted queueing networks. Oper. Res. 28(3), 594-602.
Tay, Y.C., and R. Suri (1985). Error bounds for performance prediction in queueing networks.
ACM Trans. Comput. Syst. 3(3), 227-254.
Tijms, H.C. (1988). Stochastic Modelling and Analysis: A Computational Approach, Wiley, New
York.
Trivedi, K.S. (1982). Probability and Statistics with Reliability, Queueing, and Computer Science
Applications, Prentice-Hall, Englewood Cliffs, NJ.
Uzsoy, R., and L.A. Martin-Vega (1990). Modelling Kanban-based demand-pull systems: A survey
and critique. Manuf. Rev. 3(3), 155-160.
Van der Wal, J. (1989). Monotonicity of the throughput of a closed exponential queueing network
in the number of jobs. OR Spektrum 11, 97-100.
Van Dijk, N.M. (1989). A simple bounding methodology for non-product-form queueing networks
with blocking, in: H.G. Perros, and T. Altiok (eds0, Queueing Networks with Blocking,
Elsevier, Amsterdam, pp. 3-17.
Vinod, B., and J.J. Solberg (1985). The optimal design of fexible manufacturing systems. Internat•
J. Prod. Res. 23(6), 1141-1151.
Viswanadham, N., and Y. Narahari (1992). Performance Modeling of Automated Manufacturing
Systems, Prentice-Hall, Englewood Cliffs, NJ.
Wang, L., and W.E. Wilhelm (1985). Management of component accumulation in small-lot
assembly systems, Working Paper 1985-005, Department of Industrial and Systems Engineering,
Ohio State University.
Wein, L.M. (1990a). Optimal control of a two-station Brownian network. Mth. Oper. Res. 15,
215-242.
Wein, L.M. (1990b). Scheduling networks of queues: Heavy traffic analysis of a two-station
network with controllable inputs. Oper. Res. 38, 1065-1078.
Wein, L.M. (1991). Brownian networks with discretionary routing. Oper. Res. 39(2), 322-
340.
Whitt, W. (1982). Approximating a point process by a renewal process: Two basic methods. Oper.
Res. 30, 125-147.
Whitt, W. (1983). The queueing network analyzer. Bell Syst. Tech. J. 62, 2779-2815.
Whitt, W. (1984a). Approximations to departure processes and queues in series. Naval Res. Logist.
Quart. 31,499-521.
Whitt, W. (1984b). Open and closed networks of queues. AT& T Bell Lab. Tech. J. 63, 1911-1979.
Whitt, W. (1985). The best order of queues in series. Management Sci. 31(4), 475-487.
Whitt, W. (1989). Approximations for the GI/G/m queue. Adv. Appl. Probab., to appear.
Wilhelm, W. (1986a). A model to approximate transient performance of the flowshop. Internat. J.
Prod. Res. 24(1), 33-50.
Wilhelm, W. (1986b). The application of lognormal models of transient operations in the flexible
manufacturing environment. J. Manuf. Syst. 5(4), 253-266.
Wilhelm, W., and S. Ahmadi-Marandi (1982). A methodology to describe the operating charac-
teristics of assembly systems. I1E Trans. 14(3), 204-213.
Wilhelm, W., S. Saboo and R. Johnson (1986). An approach for designing capacity and managing
material flow in small-lot assembly lines. J. Manuf. Syst. 5(3), 147-160.
Williams, A.C., and R.A. Bhandiwad (1976). A generating function approach to queueing
network models of multiprogrammed computer systems. Network 6, 1-22.
Wolff, R.W. (1989). Stochastic Modeling and the Theory of Queues, Prentice-Hall, Englewood
Cliffs, NJ.
Yamazaki, G., T. Kawashima and H. Sakasegawa (1985). Reversibility of tandem blocking
queueing systems. Management Sci. 31(1), 78-83.
286 R. Suri et al.

Yao, D.D. (1985). Some properties of the throughput function of closed networks of queues.
Oper. Res'. Lett. 3(6), 313-317.
Yao, D.D. (1989). Modeling flexible manufacturing systems using product form queueing net-
works, in: J.A. White and I.W. Pence (eds.), Progress in Materials Handling and Logistics - Vol.
I, Springer, Berlin, pp. 223-235.
Yao, D.D., and J.A. Buzacott (1985a). Queueing models for a flexible machining station. Part 1:
The diffusion approximation. European J. Oper. Res. 19, 233-240.
Yao, D.D., and J.A. Buzacott (1985b). Modeling the performance of manufacturing systems.
Internat. J. Prod. Res. 23, 945-959.
Yao, D.D., and J.A. Buzacott (1985c). Queueing models for a flexible machining station, Part Il:
The method of Coxian phases. European J. Oper. Res. 19, 241-252.
Yao, D.D., and J.A. Buzacott (1986a). The exponentialization approach to flexible manufacturing
systems models with general processing times. European J. Oper. Res. 24, 410-416.
Yao, D.D., and J.A. Buzacott (1986b). Models of flexible manufacturing systems with limited local
buffers. Internat. J. Prod. Res. 24, 107-118.
Yao, D.D., and J.G. Shanthikumar (1986). Some resource allocation problems in multi-cell
systems. Proc. 2nd O R S A / T I M S Conf. on Flexible Manufacturing Systems. Ann Arbor, MI.
Elsevier, Amsterdam, pp. 245-256.
Yao, D.D., and J.G. Shanthikumar (1987). Optimal server allocation in a system of multi-server
stations. Management Sci. 33(9), 1173-1180.
Zahorian, J. (1980). The approximate solution of large queueing network models, Ph.D. Disserta-
tion (Tech. Rep. CSRG-122), Univ. of Toronto, Toronto, Canada.
Zahorjan, J., K.C. Sevcik, D.L. Eager, and B.I. Galler (1982). Balanced job bound analysis of
queueing networks. Comrnun. A C M 25(2), 134-141.
Zipkin, P.H. (1986). Models for design and control of stochastic, multi-item batch production
systems. Oper. Res. 34, 91-104.