Abstract
Performance Analysis of Manufacturing Systems
Queueing Approximations and Algorithms
This thesis is concerned with the performance analysis of manufacturing systems.
Manufacturing is the application of tools and a processing medium to the
transformation of raw materials into finished goods for sale. This effort includes all
intermediate processes required for the production and integration of a product’s
components.
For the design or improvement of manufacturing systems it is important to be
able to predict their performance. For this purpose, models are being developed and
analyzed. Many types of models can be distinguished. The types of models which
are most common are simulation models and analytical models.
Simulation models represent the events that could occur as a system operates
by a sequence of steps in a computer program. The probabilistic nature of many
events, such as machine failure and processing times, can be represented by sampling
from a distribution representing the pattern of the occurrence of the event. Thus,
to represent the typical behavior of the system, it is necessary to run the simulation
model for a sufficiently long time, so that all events can occur a sufficiently large
number of times.
Analytical models describe the system using mathematical or symbolic relationships.
These relationships are then used to derive a formula or to define an algorithm
by which the performance measures of the system can be evaluated. Often it is not
possible, within a reasonable amount of computer time or data storage space, to obtain
the performance measure from the relationships describing the system. Further
assumptions that modify these relationships then have to be made. The resulting
model is then approximate rather than exact, and to validate this approximation, a
simulation model may be required.
This thesis was carried out in the STW-project EPT, which is a combined effort
of groups from the Mechanical Engineering department and the Mathematics and
Computer Science department of Eindhoven University of Technology. It aims at
developing methods and techniques to analyze manufacturing systems by using the
concept of the ’effective process time’ (EPT). The effective process time is the total
time a job experiences at a work station; so besides the clean process time it includes
all kinds of disturbances. So, it is not needed to explicitly model these disturbances
in either a simulation or an analytical model. This makes it easier to collect data for
simulation or analytical models and immediately makes the development of more
realistic analytical models possible. The Systems Engineering group from the Mechanical
Engineering department focuses on the development of simulation models,
whereas the Stochastic Operations Research group from the Mathematics and Computer
Science department focuses on the development of analytical models.
The work in this thesis is an attempt to develop analytical methods to predict
the performance of manufacturing systems. The aim is that these methods can
be applied to realistic systems, and can be fed by EPT-data, yielding accurate
performance predictions. As a result, these methods may serve as an alternative
for, or an addition to, discrete-event simulation. To develop these methods we
will make use of queueing theory and, in particular, of matrix-analytic methods.
These methods, combined with decomposition techniques and aggregation methods,
give us the possibility to evaluate relatively large queueing systems very efficiently
and accurately. The ultimate goal is to be able to analyze complex networks with
different types of nodes within a reasonable time and with a reasonable accuracy.
There is still a long way to go before that goal will be reached. In this thesis some
steps towards that goal are taken.
In Chapter 1 we give an introduction to manufacturing systems and modeling
techniques. Also, we give an overview of the types of models that are treated in this
thesis, including a literature survey.
In Chapter 2 an overview is given of the basics of queueing theory which is used
in this thesis. As well as Markovian Arrival Processes, we introduce Quasi Birthand-
Death processes and the methods to solve them using matrix-analytic methods.
Also, we introduce some algorithms for determining the first two moments of the
inter-arrival times of a superposed arrival process and of the maximum of a number
of independent random variables.
Chapter 3 is motivated by a production system that manufactures the feet of
lamps. The model is a queueing system consisting of a number of multi-server
stations with generally distributed service times in tandem with finite buffers in
between. We develop an approximation using decomposition. Also, tests are performed
to check the quality of the approximation. This chapter is concluded with a
case study.
Production systems with single machine workstations and very small buffers in
between the workstations are common in the automotive industry. The results in
the previous chapter in this specific case were not good enough. Therefore we handle
a single-server tandem queue with small finite buffers in Chapter 4. By modeling
the arrivals and departures in more detail compared to the approach of Chapter 3,
we improve its results in the case of single server tandem queues.
In Chapter 5 we deal with an assembly system. Assembly systems are frequently
encountered in production lines in the automotive industry. A number of different
parts arrive at queues in front of an assembly server. This assembly server assembles
the parts into one product. We decompose the system into a number of subsystems
for each part. A wait-to-assembly time is introduced as the time the assembly
server has to wait for all parts to be available. The subsystems are solved by using
a matrix-analytic method and the characteristics of the wait-to-assembly times are
determined by means of an iterative algorithm. Finally, the throughput and mean
sojourn times are compared with results from discrete-event simulation to test the
quality of the algorithm.
Chapter 6 deals with a multi-server queueing system with multiple arrival streams,
this is a so-called ??GI/G/c-queue. We analyze it by aggregating the arrival process
and the service process in a suitable way. Then, we describe it as a state-dependent
Markov process, and solve it by using a matrix-analytic method. In this way we
are able to determine an approximation for the complete queue-length distribution.
The quality is tested by comparing the mean sojourn time and delay probability
against the results of a discrete-event simulation.
Chapter 7 is concerned with a priority system. In order-based production environments,
like in semi-conductor industry, some types of products are often prioritized
over others. Different types of customers arrive at a queueing system. These
types each have their own priority. The priority strategy we consider is preemptive
resume. Decomposing the queueing system gives a queueing system with vacations
for each type of customer. By exploiting the relationship between the subsystems,
we develop a method to determine the complete queue-length distribution. Again,
the results of the approximation are compared with a discrete-event simulation.
In Chapter 8 we present an outlook to the analysis of complete networks consisting
of queues we studied in earlier chapters. We focus on two types of networks.
First we discuss finitely buffered networks. Next, we consider networks with infinite
buffers. Further, we also give some other directions for future research.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Awarding Institution |
|
Supervisors/Advisors |
|
Award date | 10 May 2007 |
Place of Publication | Eindhoven |
Publisher | |
Print ISBNs | 978-90-386-0944-7 |
DOIs | |
Publication status | Published - 2007 |