IFSM 300 – Lecture 3



IFSM 300 – Class 23

April 22, 2002

Preliminaries

• Homework 5 due today.

• Returning graded exam 2.

• Assignment 23: read chapter 15.

• Class Web site reminder:

Probabilistic Models

• Recall that most of the mathematical methods of OR may be placed into one of three categories – simulation, optimization, or pattern recognition. Also recall that within each of those categories we find two kind of models --deterministic and probabilistic (also called stochastic).

• The queueing models that we will study in chapter 15 belong in the realm of probabilistic simulation, also called risk analysis in some cases. The queueing world does contain optimization modeling, but that is an advanced topic in the field.

• Inventory models illustrated a special type of optimization model -- optimization for which the application is specific and the optimization result has been worked out in advance in the form of solution equations. You might call this a special-purpose optimization model (my own term, not an official part of the OR vocabulary). So too queueing models bring us a special breed. Here we meet special-purpose simulation, which we may contrast with basic-building-block simulation.

• A basic simulation, usually built with commercial simulation software, contains no systematic optimization. That is, decision choices must be examined one-at-a-time in separate simulation runs. Probabilistic simulations, moreover, require many runs with the same model (incorporating the same decision choice) in order to sample from the probability distributions that describe the uncertain quantities (called random variables) that are inputs in the model. These numerous runs are needed to develop estimates of the distributions of the uncertain outputs.

• A special-purpose simulation model, such as a queueing model, focuses on a specific type of application and derives information about the distributions of the outputs, or some of them, in advance. It’s the simulation counterpart of special-purpose optimization.

• Even though any application may be handled by means of commercial, general-purpose simulation software, the information a special-purpose model supplies is highly valuable. This is because the special-purpose model furnishes greater insight into how the modeled situation operates, and speeds simulation calculations.

• That’s the first idea to orient us as we venture into queueing. A second orienting point emerges when we step back to ask the fundamental question: Why bother with probabilistic modeling?

• When uncertain quantities are important in an analysis, which is most of the time, to work strictly with averages, or with averages and extreme values, throws away much vital information about how the uncertain quantities might actually vary, separately and together.

• In the past, management rarely thought formal analysis could help clarify uncertainty and risk, and therefore usually settled for deterministic support studies.

• Furthermore, many managers who did think about using probability failed to take advantage of it. As the new generation of management, many having gone to business schools where they were introduced to probabilistic analysis, ascends to top jobs, this barrier is falling.

• The power of probabilistic methods to reveal the implications and likely consequences of uncertainty and risk is huge. It constitutes one of the unique advantages that OR and decision support bring to executives and managers.

Probabilistic Simulation Models

• Suppose we wish to model a random variable (uncertain quantity). The simplest view we might take is that the probabilities (the probability distribution) stays the same, and we observe variable values (called realizations) produced by sampling from it. The best known probability distribution is the normal distribution.

• In practice you often want to model a variable (such as monthly sales) whose values may be moving around as time goes on. Regular observations of a particular variable over time (sales month by month, cost quarter by quarter) is called a time series. To model a time series, we need a probability model that produces regular outputs over time. It may or may not describe changing probabilities. In any event, it’s completely specified except for input parameter values, which we adjust to fit to our data. Such a model of successive observations is called a stochastic process. The applicability of stochastic process models is not limited to time series. The successive observations may be in any dimension, such as physical space (e.g., particle positions in a liquid).

Arrival Process

• Complete notes below. Summary here.

• Cover these topics:

• Introduction.

• Probability mass and density functions.

• Distribution functions.

• Assumptions of the Poisson process.

• Poisson mass function (of number of arrivals).

• Properties of the Poisson mass function.

• Exponential density function (of interarrival time), and properties.

• Distribution functions for the Poisson and exponential.

Service Process

• Complete notes below. Summary here.

• We now add to the foregoing model of customers arriving a model of customers being served. In this example, we have a simple queueing system composed of customers arriving into a single queue, customers waiting in line, and, finally, customers at the head of the line being served and then leaving.

• Two probability distributions determine the properties of this system: the distribution of time between arrivals (interarrival time) and the distribution of time for service (service time). The stochastic model we are studying here is classified as M/M/1. See page 783. We are assuming exponential distributions of interarrival and service times, and a single server. The M refers to Markov process, a general class of memoryless stochastic process. The exponential distribution is the only continuous-variable probability function with lack of memory.

• In this simplest case, we further assume no limit on (1) number of customers we can accommodate in the queueing system, and (2) the number of customers available to enter or reenter the system.

• Refer to Storeroom Service, situation 15.2, page 761.

• Cover these topics:

• Poisson mass function (of services completed by a busy server).

• Exponential density function (of service time).

Millionaire Q1

A queueing (meaning “waiting-line”) model is a special kind of:

A. Simulation model. (!!)

B. Optimization model.

C. Pattern recognition model.

D. None of the above.

Millionaire Q2

A queueing model describes the number of things (people, airplanes, e-mail messages) waiting as a stochastic process, which is a sequence of similar:

A. Deterministic variables.

B. Random variables. (!!)

C. Realizations of deterministic variables.

D. Realizations of random variables.

Millionaire Q3

The most common stochastic process used to model arrivals into a queue is the Poisson process. The Poisson process does NOT apply when we can have:

A. Zero arrivals or one arrival in a very small time interval.

B. The probability of 1 arrival in a very small interval (t be approximately ((t, where ( is the average arrival rate.

C. The time between successive arrivals be described well by the exponential density function.

D. A period of past arrivals at an above-average rate cause us to decrease the probability of future arrivals so as to keep the same average rate (. (!!)

Millionaire Q4

When we model arrivals into a queue as a Poisson process, we will have a:

A. Poisson density function of interarrival times.

B. Poisson mass function of interarrival times.

C. Poisson density function of number of arrivals in a given time.

D. Poisson mass function of number of arrivals in a given time. (!!)

Millionaire Q5

The Poisson process is the most common process used to describe not only arrivals but also service. A Poisson model applies to service during the time service is:

A. Waiting or busy.

B. Waiting.

C. Busy. (!!)

D. Eating lunch.

Millionaire Q6

When the Poisson process describes service during times it is busy, the memoryless exponential density function describes the:

A. Time to serve all waiting customers.

B. Time to serve one waiting customer. (!!)

C. Number of customers in line.

D. Number of customers complaining.

Notes: Queueing Models

Arrival Process

Introduction. We now begin our study of probabilistic models of queues (meaning waiting lines). The queue occupants may or may not be people. They might, for example, be planes waiting to land, or messages waiting to be transmitted.

Queues are present in very many everyday situations. Thus when we build probabilistic models (also called stochastic models) to improve systems ranging from communications to transportation to manufacturing to finance, queues are part or all of the picture.

The following table gives various examples of queueing applications:

The main goal of a queueing model is to describe the waiting line during successive time intervals – successive minutes, hours, days, or whatever. In other words, the primary information we want is a the stochastic process describing the waiting line.

In this lecture we will examine a stochastic-process model often applied to queues – the Poisson process. It turns out that the waiting line itself is not best depicted as a Poisson process. In the queueing system, a Poisson process often does describe well the arrivals and also the service. If arrivals and service are Poisson, then we can derive the associated waiting-line stochastic process – which, as we shall see, is not Poisson.

The Poisson process is called a counting process because it describes the counting of events that occur over time. In this first queueing application, we are counting arriving customers (e.g., how many arrivals in an hour). Later we’ll count served customers.

Function. Recall that a function assigns an output (dependent variable) to one or several inputs (dependent variables). For example,

y(x) = a + b x,

z(x,y) = (x + y)2.

Probability Function. A probability function assigns probability (dependent variable) to possible values of one or several random variables (uncertain quantities, which are the independent variables of this function).

Let’s consider the case of a single random variable (RV). If the possible values of the RV are discrete values, then the function is called a probability mass function. For example, the outcomes of tossing a fair coin are assigned probabilities in this mass function:

If, on the other hand, the possible values of the RV are continuous values, the function is called a probability density function.

With a continuous RV, there are an infinite number of possible RV values and therefore the probability assigned to any one RV value is zero. We obtain a non-zero probability only for a selected range of RV values. For instance, as depicted in the graph below, if we want the probability that the random variable x (heights in the example on the graph) will fall between x1 and x2 , that is the area under the curve of the density function f(x) from

x = x1 to x = x2, which area is given by the integral ( f(x) dx over the range x1 to x2:

Probability Distribution and Distribution Function. The name probability distribution is used as a synonym for probability function, either mass function or density function.

To add to the confusion, there is such a thing as a distribution function. This refers to a probability function (also called, as just noted, a probability distribution) in the cumulative form Pr(RV ( X) versus X, where X is an upper limit:

Poisson Process Model of Arrivals. As noted before, we will begin to model a simple queueing system by modeling the arrivals.

To do this, we make three key assumptions:

1. In a very small time interval ( t, the probability of more than one arrival is negligible. We only can have one arrival or no arrival.

2. If the mean rate of arrival is ( (e.g., ( = 30 arrivals per hour), the probability of one arrival in a very small time interval ( t is approximately ( ( t.

3. If we were to take any large time interval and divide it into successive subintervals (e.g., divide an hour into minute 1, minute 2, and so on), arrivals in the subintervals are independent. That is, whatever happens in one subinterval doesn’t affect another. The process is memoryless. What happens in the past does not change the probabilities for the future.

When the pattern of activity we wish to model satisfies these assumptions, the Poisson process fits.

Poisson Probability Functions. A Poisson process model enables us to obtain various information, coming first and foremost from two probability functions. In the case of modeling arrivals, those functions are:

1. Poisson probability mass function of the total number of arrivals in a specified time interval.

2. Exponential probability density function of the time between successive arrivals (called the interarrival time).

Poisson Mass Function. We’ll adopt this notation:

T – length (in basic time units, such as hours) of a specified total time period (e.g.,

T = 5 hours, or T = 0.5 hours, or T = 1 hour).

x – number of arrivals in the specified total time period T.

( – mean (average) rate of arrival per basic unit of time (e.g., ( = 12 arrivals per

hour).

The uncertain quantity x is the random variable; T and ( are parameters.

Then the Poisson mass function that assigns a probability to the possible number of arrivals x in time interval T is:

Pr(x) = [e-(T ((T)x] / x! , for x = 0, 1, 2, …,

where

ex = lim [1 + (x/n)]n e1 = 2.71828…

n((

y = ex ( x = ln y eln y = y

x! = x (x –1)(x –2)…(1). 0! = 1, 1! = 1

Poisson Model is a Stochastic Process Model. For a selected value of T, the Poisson model is a single mass function. But since T may be varied to provide a series of advancing times (e.g., T = 1 hour, then 2 hours, then 3 hours, and so on), this model is in fact a stochastic process model.

Numerical Example. Let the basic time unit be an hour. In other words, we decide to measure time in hours rather than in minutes or days or something else.

Then let the selected total time interval of study T be 1 hour. Note that T is not restricted to be the same as the basic time unit. T could be 5 hours, or 24 hours, or whatever we want.

And let the mean arrival rate ( be 4 arrivals per hour.

In this case, the Poisson mass function becomes:

Pr(x) = {e-(4)(1) [(4)(1)]x} / x!

= (e-4 4x) / x! , for x = 0, 1, 2, …

For instance,

Pr(0) = (e-4 40) / 0! = [(e-4)(1)] / 1 = e-4 = 0.01832

Pr(1) = (e-4 41) / 1! = [(e-4)(4)] / 1 = 4 e-4 = 0.07326.

The probabilities assigned to various other values of x are listed in table 15.4 of the book, page 756. A graph of the Poisson mass function for this example is shown below.

Properties of The Poisson Mass Function. For the Poisson mass function,

Pr(x) = [e-(T ((T)x] / x! , for x = 0, 1, 2, …,

we know that the total of all probability assigned must be 1:

(

( P(x) = 1.

x = 0

There is an average value of x, called the mean value or expected value, given by

_

x = E(x) = x1 Pr(x1) + x2 Pr(x2) + … + xn Pr(xn).

_

In the case of the Poisson mass function, x = ( T .

Measures of spread around the mean are the variance (in units that are the units of x squared) and the standard deviation (in the same units as x). The variance is

_ _ _

(2 = E[(x – x)2] = (x1 – x)2 Pr(x1) + … + (xn – x)2 Pr(xn),

which in this case becomes

(2 = ( T.

Then the standard deviation, symbol (, computed as + ( (2 , becomes

( = + ( ( T.

_

With the data in the earlier example, x = ( T = (4)(1) = 4 arrivals in the selected time interval of T = 1 hour, (2 = ( T = 4 arrivals squared, and ( = + ( ( T = 2 arrivals.

Exponential Density Function. We retain the previous notation, and add one more symbol:

t – length of time (in basic time units, such as hours) between two successive

arrivals.

Now t is the random variable – a continuous variable. And we’ll use ( as a parameter. The exponential density function that assigns probabilities to intervals of t is:

f(t) = ( e-(t , t ( 0.

The summary measures that describe this density function are:

_

mean t = 1 / ( , variance (2 = 1 / (2 , standard deviation ( = 1 / ( .

In the numerical example where ( = 4 arrivals per hour,

_

t = 1 / 4 = 0.25 hours, (2 = 1 / 42 = 1 /16 (hours)2 , ( = 1 / 4 = 0.25 hours.

Shown below is a graph of the exponential probability density function of interarrival time, with ( = 4.

Distribution Functions. Corresponding to the Poisson mass function and exponential density function, we have these distribution functions:

X

Poisson Pr(x ( X) = ( [e-(T ((T)x] / x! , X = 0, 1, …

x = 0

T

exponential PR( t ( T) = ( ( e-(t dt = 1 – e-(T , T ( 0.

0

Graph of Probability Density Function for Interarrival Time.

Poisson Model of Service. Let’s assume, as is widely applicable in practice, that the time a customer in the queueing system requires to receive service is a memoryless (and thus exponentially distributed) random variable. Then the number of customers served when the server is busy will be modeled as a Poisson process.

The notation we need is the same as when modeling arrivals. But we call the rate of service completion (. And to avoid confusing this with the arrival model, we let the number of service completions, the random variable, be y. Define:

T – length (in basic time units, such as hours) of a specified total time period (e.g.,

T = 5 hours, or T = 0.5 hours, or T = 1 hour).

y – number of service completions, by a continually busy server, in the specified

total time period T.

( – mean (average) rate of service completion, by a continually busy server, per

basic unit of time (e.g., ( = 5 customers served per hour).

Then the Poisson mass function that assigns probability to the number of service completions y in time T is:

Pr(y) = [e-(T ((T)y] / y! , for y = 0, 1, 2, …,

where

_

y = (2 = (T, ( = +( (T .

If we further define:

t – length of time (in basic time units, such as hours) between two successive

service completions (that is, the time a busy server takes to serve one

customer),

then the exponential density function that assigns probabilities to possible intervals of t is:

f(t) = ( e-(t , t ( 0.

And the summary measures that describe this density function are:

_

mean t = 1 / ( , variance (2 = 1 / (2 , standard deviation ( = 1 / ( .

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download