discrete event system simulation by jerry banks PDF

Preview

Summary

Download discrete event system simulation by jerry banks PDF

Description

.,. 'l";;.•,�.''"···· ·· · ·'· " '"�·.-· < �� · ··= ...c-�..�

.

.

.

��

.

.

.

.

Discrete-Event System Simulation

FouRTH E DITION

Jerry Banks Consultant Independent :-.

John S. Carson II Brooks Automation

·

Barry L Nelson Northwestern University David M. Nicol University of Illinois, Urbana-Champaign

Prentice Hall is an imprint of PEARSON ------

Contents

xiii

Preface About the Authors

I

Introduction to Discrete-Event System Simulation

l.l

I

·

l.ll

3

When Simulation Is the Appropriate Tool

4 4 5 6 8 8 9 9 ll 12 12 16 17

When Simulation Is Not Appropriate

Advantages and Disadvantages of Simulation Areas of Application

Systems and System Environment

Components of a System

Discrete and Continuous Systems Model of a System

l)pes of Models

Discrete-Event System Simulation Steps in a Simulation Study References

Exercises

· Chapter 2. Simulation Examples 2.1 2.2 2.3 2.4

Simulation of Queueing Systems

Simulation of Inventory Systems Other Examples of S imulation

Summary

References

Exercises

I

L

1

Introduction to Simulation

Chapter 1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10

XV

19 20 35 43 51 52 52

v

.::-::J.·.2:l..:i';'.

._:_,

;,

.._l.'lo..)..iJ.-J�.h...,:...>J-

10

j

i:i .!2

s

"'(;!

a '1:1 r:

c

- ·g

;;-��

.. 'r:l ;a

"' c-o

.g ] ]� � £1

·:;;

8.

:� .g � ·!ll

� w

. -

"'!:!

ble. Figure 1 . 1 Discrete-system state varia

�

::E

.s

00

�

13.

1::

"'0 u

r: QJ a·= u � '1:1 :g � g·r:� � -a� .60 •t: '0 ?A,

U.

.tl .c

�

jj} "' u

... 0

0

�

�.... � '0

� l.'ll

-� Ill(

i�S

�

�� 'B c. · :6 � e"' ;;'iil1'a � E!:

J

·· ·-

oo

�i

�u

.... :! .c c.

(I)

"' .,c

:a i;l

�

,g OS =

.Slo

�

!i

�

u

"'

., "'0"'

�

�

01) "0 "'

� "'Q)"'

�

"'

g g

'r:l

£

Time

ble. figure 1.2 Continuous-system state varia

c

8.� fi "0 -o'i

�

c 0 '1:1

..u

·a ::l

�

u 0

c B c Q) >

.s

sented and activities, models are repre system were entities, attributes, onents Just as the components of a comp The . study the ts that are relevant to contains only those componen similarly. However, the model extensively in Chapter 3. of a model are discussed more

1 .9 TYPES OF MODELS

notation ematical mod el uses symbolic mathematical or physical. A math Models can be classified as being type of mathematical cular parti a is el mod n latio represent a system. A simu and mathematical equations to m. syste a astic, and model of dynamic, deterministic or stoch er classified as being static or sents a, Simulation models may be furth repre n, latio called a Monte Carlo simu simulation model, sometinles time. er v o ge discrete or continuous. A static chan they as ms syste ls represent time. Dynamic simulation mode system at a particular point in lation. simu mic dyna of a ple exam an 9:00 A.M. to 4:00 P.M. is rministic mod­ The simulation of a bank from classified as deterministic. Dete in no random variables are conta that ls mode n Simulatio would occur als arriv istic Determin ts. outpu of which will result in a unique set n model latio els have a known set of inputs, simu appointment time. A stochastic nts arrived at the scheduled uts are outp the e at a dentist's office if all patie Sinc uts. outp om lead to rand bles as inputs. Random inputs varia om rand more or has one

�:

13

12

INTRODUCTION TO SIMUlATION

DISCRETE-EVENT SYSTEM SIMUlATION

random, they can be considered only as estimates of the true characteristics of a model. The simulation of

a bank would usually involve random interarrival times and random service times. Thus, in a stochastic

simulation, the output measures-the average number of people waiting, the average waiting time of a

2,---'----. Setting of

customer-must be treated as statistical estimates of the true characteristics of the system.

objectives

Discrete and continuous systems were defined in Section 1.7. Discrete and continuous models are

defined in an analogous manner. However, a discrete simulation model

and overall

is not always used to model a dis­

project plan

crete system, nor is a continuous simulation model always used to model a continuous system. Tanks and pipes are modeled discretely by some software vendors, even though we know that fluid flow is continuous.

In addition, simulation models may be mixed, both discrete and continuous. The choice of whether to use a

discrete or continuous {or both discrete and continuous) simulation model is a function of the characteristics

of the system and the objective of the study. Thus, a communication channel could be modeled discretely

if the characteristics and movement of each message were deemed important. Conversely, if the flow of .

messages in aggregate over the channel w�e of importance, modeling the system via continuous simulation could be more appropriate. The models considered in this text are discrete, dynamic, and stochastic.

1.10 DISCRETE·EVENT SYSTEM SIMULATION This is a textbook about discrete-event system simulation. Discrete-event systems simulation is the model­

ing of systems in which the state variable changes only at a discrete set of points in time. The simulation

Yti

models are analyzed by numerical methods rather than by anal

cal methods. Analytical methods employ the deductive reasoning of mathematics to "solve" the modeL For example, differential calculus can be used

to compute the minimum-cost policy for some inventory models. Numerical methods employ computational

procedures to "solve" mathematical models. In the case of simulation models, which employ numerical methods, models are "run" rather than solved-that is, an artificial history of the system is generated from the model assumptions, and observations are collected to be analyzed and to estimate the true system

performance measures. Real-world simulation models

are rather large, and the amount of data stored and

manipulated is vast, so such runs are usually conducted with the aid of a computer. However, much insight

can be obtained by simulating small models manually.

In summary, this textbook is about discrete-event system simulation in which the models of interest are

analyzed numerically, usually with the aid of a 20

Figure 2. 1 7 Frequency of lead-time demand.

Table 2.28 Random Digit Assignment lor Lead Time Lead Time (Days)

Random Digit Assignment

Probability

Cumulative Probability

I

0.36

0.36

01-36

2

0.42

0.78

37-78

1.00

79-00

0.22

3

Figure 2. 1 8

Table 2.29 Simulation Table lor lead-Time Demand Digits for Lead Time

Lead Time (Days)

57

2

Random

Cycle

2

33

1

3

46

2

91

3

4

Random

Digits for Demand

Demand

Lead-Time Dem&ui

3 5

8

13

4 3

4

80

5

8

27

4

66 47

be carried out sequentially; others can be done in parallel. The project can be represented by a network of activities, as shown in Figure 2.18. There are three paths through the network, each path representing a

sequence of activities that must be completed in order. The activities on two different paths can be carried out in parallel.

In the activity network in Figure 2.18, the arcs represent activities and the nodes represent the start or

5

4

� like that in Figure 2.17. This result was obtained from simulating 20 cycles of lead-time demand,

using the Excel spreadsheet found at www.bcnn.net.

Suppose you have a project that requires the completion of a number of activities. Some activities must

11

64 37

might

Activity network.

13

end of an activity. The time to complete all activities on a path is the sum of the activity times along the path. To complete the entire project, all activities must be completed; therefore, project completion time is the maximum over all path completion times. The topmost path is along the path Start � A� B � Finish. The middle path Is along the path Start � C � Finish. The bottom path is given by Start � Finish.

DISCRETE-EVENT SYSTEM SIMULATION

50 Example 2.8:

Frequency Distribution of Project Completion Time

Project Simulation

160

Here's a concrete example using Figure 2.18. Let's say that three friends wanted to cook bacon, eggs, and

toast for breakfast for some weekend visitors. Each friend was going to prepare one of the three items. The

-;;;, • ·- · . . -·

; �.'t}','· '�'t • ' ' ,,\�

84

DISCRETE-EVENT SYSTEM SIMULATION

, using the event-scheduling 8. Redo Example 2.4 (the (M, N) inventory system) by a manual simulation

lnslructions to the reader: For most exercises, the reader should first conslruct a model by explicitly defining

manual simulation, using the event­ 9. Redo Example 2.5 (the bearing-replacement problem) b y a

approach. .

10.

1. 2.

system state;

3.

sets, and the entities that may be put into the sets;

4.

events and activities; everit notices;

5.

variables needed to collect cumulative statistics.

system entities and their attributes;

in preparation for using the process-interaction approach. Most problems contain activities that are uniformly distributed over an interval [a, b]. When conducting

b are the only possible values; that is, the activity time

is a discrete random variable. The discreteness assumption will simplify the manual simulation.

1.

{a)

Using the event-scheduling approach, continue the (manual) checkout-counter simulation in

Example 3.3, Table 3.1. Use the same interarrival and service times that were previously gene1ated

and used in Example 2.1. Whea the last interarrival time is used, continue the simulation until time 60 using the data in Tables 2.8 and 2.9. (b) Do exercise

l(a) again, adding the model components nec·essary to estimate mean response time

and proportion of customers who spend 5 or more minutes in the system. Table 3.2.)

(c)

2.

(Hint: See Example 3.4,

Comment on the relative merits of manual versus computerized simulations.

Give the detailed flow chart for the simulation of a single-server queueing system.

3. In the dump-lruck problem of Example 3.5, it is

desired to estimate mean response time and the pro­

portion of response times which are greater·than 30 ntinutes. A response time for a !ruck begins when that !ruck arrives at the loader queue and ends when the !ruck finishes weighing. Add the model com� ponents

and

cumulative statistics needed to estimate these two measures of system perfonnance.

Simulate for 8 hours.

4. Consider a single-server queueing system with arrival and service details as: Interarrival times 3 2 6 2 4 5 Service times 2 5 5 8 4 5 Prepare a table similar to Table 3.2 for the given data Stop simulation when the clock reaches 20.

5.

Continue the table that is prepared in Exercise 4 till C5 leaves the system.

6. The data for Table 3.2 are changed to the following: Interarrival times 4 5 2 8 3

7

Service times 5 3 4 6 2 7

Prepare a table in the manner of Table 3.2 with a stopping event at time 25.

7.

Redo Example 2.2 (the Able-Baker call center problem) by a manual simulation, using the event­ scheduling approach.

Loading times 5 10 5 5 1 0 5 10 1 0 Travel times 80 80 100 40 100 40 60 40

Second, the reader should either ( l ) develop the event logic (as in Figures 3.5 and 3.6 for Example 3.3) in

a manual simulation, assume that a, a + I, a + 2, . . . ,

scheduling approach.

Redo Example 3.5 with the following data: Weighing times 1 2 1 2 1 2 16 16 12 1 2 16

preparation for using the event-scheduling approach, or (2) develop the system processes (as in Figure 3.4)

:�

85

EXERCISES the following:

l

GENERAL PRINCIPLES

SIMULATION SOFTWARE

,j:

-. ! ·i : "

4 Simulation Software

87

has been used to simulate systems of great complexity. It was fust introduced by IBM; today, there are various implementations of GPSS, GPSS/H being one of the most widely used . . In the third category, we have selected a number of simulation software packages for discussion. There are-many simulation packages currently available; we have selected a few that have survived and thriven for a number of years, to represent different approaches for model-building. One of the important components of a simulation environment is the output analyzer, which is used to conduct experimentation and assist with analyses. To illustrate the range of desirable characteristics, we look at four tools incorporated into some of the simulation environments. 1Jpically these statistical analysis tools compute summary statistics, confidence intervals, and other statistical measures. Some support warmup determination, design of experiments, and sensitivity analyses. Many packages now offer optimization tech­ niques based on genetic algorithms, evolutionary strategies,. tabu search, scatter search, and other recently developed heuristic methods. In addition to the support for statistical analysis and optimization, the simula­ tion environments offer data management, Scenario definition, and run management Data management offers support for managing all the input and output data associated with the analyses.

4.1 HISTORY OF SIMULATION SOFTWARE

In this chapter, we first discuss the history of simulation software. Simulation software has a history that is just reaching middle age. We base this history on our collective experience, articles written by Professor Richard Nance, and panel discussions at the annual Winter Simulation Conference. Next, we discuss features and attributes of simulation software. If you were about to purchase simula­ tion software, what would concern you? Would it be the cost, the ease of learning, the ease of use, or would it be the power to model the kind of system with which you are concerned? Or would it be the animation capabilities? Following the discussion of features, we discuss other issues and concerns related to the selection of simulation software. Software used to develop simulation models can be divided into three categories. First, there are the general-purpose programming languages, such as C, C++, and Java Second, there are simulation programming languages, examples being GPSS!lf'M, SIMAN V®and SLAM fi®, Third, there are the simulation environments. This category includes many products that are distinguished one way or another (by, for example, cost, application area, or type of animation), but have common characteristics, such as a graphical user interface and an environment that supports all (or most) aspects of a simulation study. Many simulation environments contain a simulation programming language, but some take a graphical approach similar to process-flow diagramming. In the first category, we discuss simulation in Java. Java is a general-purpose programming language that was not specifically designed for use in simulation. Java was chosen since it is widely used and widely avail­ able. Today very few people writing discrete-event simulation models are using programming languages alone; however, in certain application areas, some people are using packages bas�d on Java or on another general-purpose language. Understanding how to develop a model in a general-purpoSe language helps to understand how the basic concepts and algorithms discussed in Chapter 3 are implemented. In the second category, we discuss GPSS/H, a highly structured process-interaction simulation lan­ guage. GPSS was designed for relatively easy simulation of queuing systems, such as in job shops, but it 86

Our discussion of the history of simulation software is based on Nance [1995], who breaks the years from 1955 through 1986 into five periods. Additional historical information is taken from a panel discussion at the 1992 Winter Simulation Conference entitled "Perspectives of the Founding Fathers" [Wilson, 1992], during which eight early users of simulation presented their historical perspectives. We add a sixth and most recent period: 1 955-60 196 1-65 1 966-70 197 1-78 1979-86 1987-?

The Period of Search The Advent The Formative Period The Expansion Period The Period of Consolidation and Regeneration The Period of Integrated Environments

The following subsections provide a brief presentation of this history. As indicated in [Nance, 1995], there were at least 137 simulation programming languages reported as of 1981, and many more since then. This brief history is far from all-inclusive. The languages and packages we mention have stood the test of time by surviving to the present day or were the historical forerunner of a package in present use.

4. 1 .1 The Period of Search ( 1 955-60) In the early years, simulation was conducted in FORTRAN or other general-purpose programming language, without the support of simulation-specific routines. In the fust period (1955-1960), much effort was expended on · the search for unifying concepts and the development of reusable routines to facilitate simulation. The General Simulation Program of K.D. Tocher ...