Chapter 17 - Køteori

Question 1

What is the basic queueing process?

Answer 1

We have customers that require some kind of service. Customers are generated over time by some kind of input source. These customers enter the queueing system and join a queue IF service is not immediately available.

At certain times, the queueing discipline determines some customer to serve.
The required service is then performed by the “service mechanism”.

After service, the customer leaves the queuing system.

Question 2

Elaaborate onthe input source

Answer 2

The input source generates customers. We usually just consider infinite popluations, because this is more easy. However, there are important cases where we cannot do this.

We MUST use finite input source popluations if the “rate” at which the source generates customers is significantly affected by the size.

We must also specify the distribution by which the source generates customers. We usually assume Poisson. This means that the number of customers generated will follow some mean rate per time, but randomly.

If we have unusual characteristics, we must also specify them. for instance, “balking” is the process of avoiding a queue if it is too long. This could impact the queueing system.

Question 3

What is balking?

Answer 3

balking is the process of avoiding a queue if it is too long.

Question 4

What is the queue?

Answer 4

The queue is where customers wait BEFORE being served.

A queue is charactersized by its capacity, the maximum number of customers it can serve. Sometimes we just assume inifnite.

Question 5

What is QUEUE DISCIPLINE?

Answer 5

Queue discipline refers to how the queueing process selects custoemrs t obe served. FIFO, LIFO, prioirity.

Question 6

Elaborate on the service mechanism

Answer 6

The service mechanism refers to the unit(s) serving the customers. It can be a single station, or multiple i parallell. We can also have sequential stations.

It is important to characterize the service time. The service time follow a probability distribution as well. Typically exponential.

Question 7

Why do we use exponential distribution rather than others?

Answer 7

it is “better” than others. It is not perfect.

we want the markov property. The markov property says that the next state should only depend on the current state, and not on anything else. We can get this exact result from the memoryless property found in the exponential distribution.

Question 8

How do we typically label a queueing model?

Answer 8

We use the “Kendall-notation”.
Distribution of arrival times / Distribution of service times / Number of servers / Capacity of queue / Size of input source

We use the following letters:
M : Expo
D : Degenerate
Ek : Erlang k
G : General distribution

For instance: M/G/3/8/infinity

We typically omit the last one if it is infinity:

M/G/3/8

Question 9

What is the “state of the system”?

Answer 9

The state of the system refers to the number of customer in the queuing system.

Question 10

What is “queue length”?

Answer 10

The number of customers waiting for service to begin

Question 11

What is N(t)?

Answer 11

The number of custoemrs in the queueing sytem at time t. Basically just “state at time t”.

Question 12

What is Pn(t)?

Answer 12

The probability of there being exactly “n” customers in the queueing system at time t.

Question 13

What is “s”?

Answer 13

S is the number of service stations, or “servers”.

Question 14

What is lambda n?

Answer 14

Lambda n is the mean arrival rate of customers into the queueing system when the number of customers in the queueing system is already “n”.

Question 15

What is µ n?

Answer 15

µ n is the mean service rate when there are n custoemrs in the queueing system. This is: The expected number of service completions per time when there are n people in the queueing system.

Question 16

When lambda n is constant, what do we have?

Answer 16

We omit the “n”, and just use lambda. Same with µ

Question 17

Use lambda and µ, when they are constant, to find expressions for the expected interarrival time, and the expected service time

Answer 17

1/lambda, 1/µ

Question 18

What is the utilization factor of the service facility?

Answer 18

p = lambda / (sµ)

Recall that s is the number of servers, µ is the mean rate of service completion, lambda is the mean rate of arrivals.

Question 19

Elaborate on transient and steady states

Answer 19

If enough time pass, the queueing system will become independent of the initial state. It will reach a steady state.

During the time the system is still affected by the initial state, we say the system is in a transient state.

Question 20

What is Pn?

Answer 20

The probability of there being exactly n customers in a queueing syustem in its steady state.

Question 21

What is L?

Provide the formula

Answer 21

L is the expected number of customers in the queueing system.

L = ∑nPn [n=0, infinity]

Question 22

What is Lq?

Answer 22

Lq is expected queue length. It excludes the customers that are currently being served.

Lq = ∑(n-s)Pn [n=s, infinity]

Question 23

What is W with fucked up notation?

Answer 23

The waiting time in the system for each individual custoemr, including service time.

Question 24

What is W?

Answer 24

W =ExpectedValue(WfuckedNotaiton)

Question 25

What is Wq?

Answer 25

Expected waiting time in the queue for some customer.

Question 26

Give Little’s formula

Answer 26

L = lambdaW

[expected number of customers in the entire system] = [mean rate of arrivals]x[expected waiting time for each customer]

the following is also true:

Lq = lambda Wq

IF lambda is not the same (constant) for all n, we need to use the average lambda.

Question 27

What is the relationship between W and Wq?

Answer 27

W = Wq + 1/µ

µ is the total server capacity. Important to include the fact that there might be more than one single server.

Question 28

Why are L, Lq, W, Wq important+

Answer 28

Assuming we know lambda and µ, we just need one of these quentities, and we can use that one to find the remaining ones.

I suppose we do it like this:
1) We find L. L is usually the easiest to find.
2) Then we use Little to find W.
3) Then we use W=Wq+1/µ to find Wq.
4) Then we use Little to find Lq.

Question 29

THe operating characteristics of queueing systems are determined largely by two factors:

Answer 29

1) Distribution of arrivals

2) Distribution of service times.

We use random variables that denote the time between arrivals, and time between services

Question 30

What does the exponential probability function look like? how about its cumulative?

Answer 30

Question 31

What is the mean of the exponential distribution?

Answer 31

1/alpha.

Question 32

What is the variance of the expo?

Answer 32

1/alpha^2

Question 33

What is the standard deviation of the expo?

Answer 33

1/alpha, the same as the mean.

Question 34

When we assume that the queueing factors (interarrival times and service times) follow exponential distributions, what are the implications?

Answer 34

we consider 6 properties that are important for our models.

1) The expo is a strictly decreasing function of t. Therefore, it has a long tail. this tail represent outliers of customers that take a LOT of time to be serviced, or outliers in terms of LONG interarrival times.

Mathematically, the tail property means that “the probability of T being between 0 and ∆t is GREATER than the probability of T being between t and t+∆t”.

The RESULT of this is that T is likely to have a small value. This is the important outcome.

One problem with this representation is that if all server-operations for all customers is the same, we would expect most customers to be within the mean. But, in queueing where the operations are not necessarily the same, the expo is good.

2) Lack of memory.
The probability of T being greater than some value t+∆t , given that T>∆t, is the same as the probability of T being greater than t.
This means that the probability of “waiting t more time” is the same regardless of how long we have already waited. This is an important property of the exponential function.

3) The minimum of several expo random variables is a random variables with parameter a=∑ai, for all i=1 to n.

4) Relationship to Poisson distribution.

5) For all positive values of t,
fuck off

Question 35

What is a birth and death process?

Answer 35

Arrivals and departures of customers before and after they have been served.

The entire point about birth and death processes, is the implication of state transitions. The point is that we can only increment or decrement the state. We move along a rate diagram of the states. We cannot go from state 5 to 15 in a sudden move. It is all controlled. Going from state 1 to state 3 involves going THROUGH state 2.

Question 36

What does a birth and death process dsescribe?

Answer 36

Birth and death processes are a type of queueing process where a state can only increment or decrement by one at a time.

It is a simple system that assumes a simple way of looking at a state and state transitions.

Question 37

What are the assumptions of a birth and death process?

Answer 37

1) Given a state N(t) = n, the current probability distribution of the remaining time until next “birth” (arrival) is exponential with parameter lambda n.

2) given a state N(t) = n, the current probability distribution of the remaining time until service completion (death) is exponential with parameter µn.

3) The random variable of assumption 1 and assumption 2, are mutually independent. The next transition is either n = n+1, or n = n-1, dependent on whether the former or latter random variable is smaller.

Question 38

Lambda n and µn is typically the same for all values of n. But, what could make thm not the same?

Answer 38

Some queueing systems are more likely to experience “balking” or “reneging”. Balking is fucking off when looking at the queue. Reneging is leaving the queue at some point if they are pissed.

Of course we also have cases of multiple servers and finite calling populations which gives different rules for lambda n and mu n.

Question 39

What is the outcome of the assumptions of the birth and death process?

Answer 39

The prrobabilities involving how the process will evolve in the future depends only on the current state. This lack of memory property is a key feature of the markov chain.

Question 40

What is En(t)

Answer 40

The number of times that some process enters state n by time t.

Question 41

What is Ln(t)

Answer 41

The number of times that some process Leaves state n during time between 0 and t.

Question 42

We can never enter some state n two times in a row. If we want to enter state n, and we are currently in state n, we must enter either n+1 or n-1. What is the result of this?

Answer 42

|En(t) - Ln(t)| <= 1

We can then divide by t on all sides, and we get:

|En(t)/t - Ln(t)/t| <= 1/t

Then we let t go large.

lim t-> large |En(t)/t - Ln(t)/t | = 0

To elaborate on what this actually means: it means that we can use the principle of alternating states to create a probabilistic model that describes the probability of being in some state by looking at the probabilities of being in neighboring states as well as their rates.
Then we use the markov chain property to extend on the fact that each probability of being in some state can be found by using only previous state. This allows us to backtrack all the way until the beginning, where we have no probabilities involved. This is insane, and it is the entire foundation for that our queueing system model relies on. Without it, we would have required probabilities, which are extremely difficult to find. This makes birth and death processes very easy and elegant.

Question 43

What is En(t)/t?
What is Ln(t)/t?

What happens if we let t grow large?

Answer 43

Considering the fact that En(t) is the number of times that the queueing process have entered state n within time 0-t, dividing by t gives us the rate of “entered state n per time unit”.

The same applies to Ln(t)/t. IT is the rate of how often we leave state n per unit time, between time 0 and t.

letting t grow large gives us the MEAN RATES. The mean rate of how many times per unit time we reach state n, and the mean rate of how many times we leave state n, during the specific time interval.

Question 44

What is the balance equation for state n?

Answer 44

Builds on the principle of “mean in equals mean out”.

I suppose the principle is simple enough. In the long run, we should have the same mean for hte number of times we enter a state as the number of the times we leave a state.

We use this principle to build balance equations. We can construct balance equations for all states in terms of unknown Pn. Then we use these balance equations to solve for the unknown probabilities.

Question 45

Consider being in a steady state, state 0. Draw up the balance equation fuckery for this state.

Answer 45

State 0 can only be accessed (entered) from state 1.

The steady state probability of being in state 1, is P1. This value, P1, represent the probaiblity of us being in state 1. It would therefore represent hte proportion of all time that we are in state 1. this also means that this (P1) is the proportion of time where we can actually enter state 0.

Given that the process is in state 1, we leave state 1 and enter state 0 with a mean rate of µ1. Therefore, the mean entering rate of state 0, is:

µ1P1 + 0(1 - P1) = µ1P1.

The reason we use 0, is that there is 0 probability of entering state 0 if we are in any other state than 1.

We use the same reasoning for the leaving state 0 rate. We can only leave state 0 from state 0. P0 is the proportion of time we are at state 0. The leaving rate is lambda0. we cannot leave state 0 from any other state than state 0. Therefore, we get the following:
lambda0P0.

Since the mean entering rate must be the same as the mean entering rate, we get that

µ1P1 = lambda0P0

Question 46

How do we use the mean in = mean out primciple to find probabilities?

Answer 46

We set up the balance equation for all states.

This gives us a massive system of equations. We solve this by following a simple pattern of recursion.

Look at how we only need the probability of the state 0, and then the lambda and mu values.

Question 47

In a steady state queueing model using birth and death process, what is the expression for P0?

Answer 47

Question 48

When a queueing system is based on the birth and death process, what is the measure of performance?

Answer 48

first of all, recall that a birth and death process includes the flow of customers through the queueing system.

The key measures of performance are the usual suspects of L, Lq, W, Wq. Basically just waiting times and lenght of the queueing system.

Question 49

Given n arrival rates, lambda, along with the probaiblity of being in each state, Pi, what expression finds the average value of lambda?

Answer 49

We use the basic principle of relative frequency.

avgLambda = ∑(lambda i)x(P(state=i))

Question 50

We of course assume poisson input and exponential service time. What does this do in terms of our queuing process models?

Answer 50

The different models will differ only in regards to how the different values for lambda and µ change with the state of the queueing system.

Question 51

When we have the M/M/s model, how is µ and lambda represented?

Answer 51

Lambda is the same, and is constant, regardless of both “n” and “s”.

However, the mu value is not that simple.

If there is one server, then µ is constant as well.

But, if tehre are mutiple servers, than it is more complicated.

Recall that µ actually is: The overall mean rate of service completions in the queing system per busy server. Therefore, increased number of servers will have an impact. If n, the number of custoemrs in the system, also known as the state, is less than the number of servers, then µn is equal to n times µ, nµ.
If n is greater than the number of servers, then µn is equal to sµ.

Question 52

in the M/M/s model, If the utilization factor, p=lambda/(sµ) <1, we will …

Answer 52

eventually reach a steady state.

Question 53

Use the results of birth and death process, along with the M/M/1 model and find the results. For both s=1, and s>1.

Answer 53

S=1 first.

We have Cn = (lambda/µ)^n = p^n.

From the birth-and-death we had Pn = Cn x P0.

Therefore, Pn = [utilizationFactor]^n x P0.

Recall that we also had that P0 = (∑p^n)^(-1)

Using rules of summation, we get:
P0 = 1 - utilizationFactor.

Thus, Pn = (1-utilizationFactor)xUtilizationFactor^n

We can then smack this result into the eqations for W, L, Wq and Lq.

Question 53

Recall that Cn is given as follows:

In the M/M/1 model, what does this reduce to?

Answer 53

Recall that if s=1, lambda and mu becomes constant. Therefore, we get:

Cn = (lambda / µ)^n

Cn = p^n, where p is the utilization factor.

Question 54

What happens if lambda > µ?

Answer 54

The queue blows up. Grows without a bound.

Question 55

Why is it called utilization factor?

Answer 55

Because it represent the fraction of time it is expected to be busy/utilized.

lambda / (sµ)

Question 56

Name the properties of the exponential function. Elaborate on them.

Money card.

Answer 56

The first thing we should understand, is what we use the exponential distribution for. We use it mainly for the “interarrival times” of the customers from the input source, AND for the service times.

Property 1) The exponential distribution is strictly decreasing. This means that we are more likely to see small values for T, rather than large.

The OBS part here, is that if the service station basically perform the same series of tasks for every customer, with relatively small variations, then the exponential distribution is NOT a good one to use. The assumption of the exponential function is more about assuming that most customers are actually very, very fast, but some are extremely slow.

Property 2) Memoryless. The probability of T>t is the same at all times, regardless of how long it have been.

Property 3) The minimum of several independent exponential random variables has an exponential distribution.

Suppose we have T1, T2, …, Tn different exponential random variables with their own parameter, alpha1, alpha2, …, alphan.
Let U = min{T1, T2, …, Tn}. U represent the time until the first event occurs, when each of the Ti’s represent the time until their own first event occurs.
P(U > t) = P(T1>t, T2>t, T3>t, …, Tn>t)
= P(T1>t) P(T2>t)….P(Tn>t), becasue independent.

= e^(-a1t)e^(-a2t) … e^(-ant)

= e^(-xt), x = ∑ai [i=1, n]

Thus, we can see that U is indeed an exponential random variable with parameter x=∑ai [i=1, n]

But why do we care about the random variable of the minimum of the servers or customers?

For interarrival times, it means that we can simply choose to IGNORE the individual types of customers, and treat them as a single unit following the big exponential distribution.

For service times, it means that when we have multiple servers, each following their own exponential distribution, we can treat the entire system as a single server problem. Say we have n different servers. The rate of service completions would then not be µ, as µ is just for a single busy station. Since we have n servers, the rate is multiplied by n. We therefore get a rate of nµ. So, we can model the case with multiple servers as a single server following the exponential distribution with service rate of nµ.

Property 4) Relationship to poisson distribution.
This is just about how the rate of arrivals or rate of service completions that we use in the exponential distribution, is the same rate that we use in the Poisson process to model the probabilities for observing a specific number of events within a specified time frame.

Property 5) P(T <= t+∆t | T>t) approx= alpha x ∆t

Question 57

Say we have n different servers. What is the probability of server J being the first one to complete service?

Answer 57

Question 58

What is the steady state condition?

Answer 58

We say that we have achieved a steady state when the probability of some event is independent of the time that has passed.

Question 59

Consider M/M/s models. What is hte most important thing?

Answer 59

We need to understand that things are very different whenver there are more custoemrs than servers VS when there are more servers than customers. The entire expression change.

Question 60

What do we need to do in order to change the M/M/s model to M/M/s/K?

Answer 60

It is about the rate of arrivals. Since the queue is now of finite length, it means that we have a maximum capacity for it. We assume that if some customer meets the queue at max cap, it will leave and never come back.

Therefore, if the queue is full, our rate of arrivals will be 0.

lambda_n = lambda, for n=1,2,3,…,(K-1)
lambda_n = 0, for n>=K

Such a queueing system will always be able to reach a steady state, even with an utlization factor of larger than 1.

Question 61

Consider M/M/s/K with s=1. Give the Cn constant.

what abuut for s>1?

Answer 61

Single server case is easy.

Cn = (lambda / µ)^n = p^n, if n=1,2,3,…,(K-1)
Cn = 0, if n>=K

Cn is 0 for larger values than K, because the lambda is 0.

When the number of servers are greater than 1, we get 3 different cases to consider:
1) The number of servers is less than the number of customers.
2) The number of customers is greater than the number of servers, but less than K.
3) The number of customers is greater than the number of servers, and equal to K.

The great part is that it is just the same as with M/M/s, with the extension of “0” for N=K.

Question 62

What do we do to treat M/M/s models with finite population?

Answer 62

We need to keep track of customers “inside” vs “outside”.

Once the customer(s) is inside, we treat them like normal. But, we need to change the way we consider arrivals.

Say we have a population of N customers. Then say n of these are inside. This means that there are (N-n) customers remaining from the outside that can possibly enter.
Each of these (N-n) customers will enter the queueing system with probability given by the exponential distribution. As we know, we only give a fuck about the first one entering at all times. Therefore, we are actually interested in the minimum of each of the exponential random variables.
We also know that one of the properties of the exponential function is that the minimum of independent exponential random variables is actually an exponential random variable itself, and its parameter is the sum of all the individual parameters in the set of possible exponential variables from which we took the “min”.

This means that the arrival rate is the sum of individual ones.

We can find the Cn constant with the preceding information.

We first consider infinite queue and single server.

The important thing here is that the rate of arrival will CHANGE based on the number of customers that are still outside. When there are 0 people inside, and all are outside, we have a rate of arrival of lambdaN, assuming each customer has the same rate of arrival, lambda.
If 1 is inside, we get (N-1)lambda.

so, Cn = (lambda^n/µ^n) N!/(N-n)!, if n<=N
Cn = 0, if n>N.

Question 63

what 3 types of models are we considering?

Answer 63

We have M/M/s, with various levels of s.

We have M/M/s/K, with various levels of K.

We have M/M/s/K, with finite population.

Question 64

What is the underlying assumption of Little’s formula?

Answer 64

Little’s formula assumes constant lambda.

Question 65

Regardless of model we’re looking at, what is really the !!! part of this chapter?

Answer 65

There is an important connection with size of servers vs size of population vs size of the state. K, n, s. If we account for all of these, we should be fine.

Accounting for those is sort of “part 1”. Part 2 is about finding L, Lq, W, Wq.

Question 66

What is “mean rate in = mean rate out”?

Answer 66

It is a principle.

If we create an equation based on this principle, we call the equation a “balance equation for state n”.

Question 67

How can we find out whether the Cn constant have “n” or “n-1” as the enumerator or denominator?

Answer 67

We set up the balance equation for state 0.

At state 0, the only way to move out of state 0, is to move UP to state 1. This is P0 x lambda0
The only way to access state 0, is to move down from state 1; P1µ1.

Thus the equation is: P0lambda0 = P1µ1

We restructure to get it on the format of Pn=CnP0

P1 = (lambda0/µ1)P0

Thus, n-1 above, n below.

Question 68

How do we go from having Pn=CnP0, to find an expression for P0?

Answer 68

We know that ∑Pn [n=1, infinity] = 1.

we can use this to find an expression for P0.
We cannot sum over P0, as this is constant, and just a single state. therefore, the following must apply:

∑Pn = ∑(Cn P0) [n=1, infinity]= 1

The sum is of the variable n, which is not used in P0. We can therefore place it outisde of the summation:

==>

P0∑Cn [n=1, infinity] = 1

P0 = 1 / (∑Cn [n=1, infinity])

Also known as:

P0 = (∑Cn [n=1, infinity])^(-1)

Question 69

What is the formula for expected length of the entire queuing system?

Answer 69

L = ∑nPn [n=1, infinity]

We can insert the results from the birth-and-death process:

L = ∑n(Cn)(∑Cn [n=1, infinity)^(-1) [n=1, infinity]

Question 70

What is the general procedure for finding the important values in this chapter?

Answer 70

it seems like we first want to find L. Then we find Lq. Then we use Littl’s formula to find W and Wq.

L is not always the best one to find first. Multi server is usually better with Lq first.

Question 71

What is the sum of this series/summation?:

∑ax^r [r=0, infinity]

Answer 71

a / (1-x), when |x|<1

Question 72

What is the difference between p and P?

Answer 72

p is the utilization factor.
P is the probability of being in some state.

Question 73

Exactly what does the exponential distribution model+

Answer 73

Exponential distribution model the probability of “the next event occurring within some time interval”.

This means that the cumulative exponential distribution model the probability of the next even occurring within some threshold “t”, represeting a time.

Because of the memoryless property, the probability of the next event occurring within “t time”, is the same always.

Question 74

Når oppstår køer?

Answer 74

Køer oppstår når det ankommer flere enheter til servicested enn som betjenes.

Kø oppstår fordi folk ikke ankommer samtidig, og folk bruker forskjellig mengde med tid.

Question 75

Det er 2 ting som påvirker køer, hva da?

Answer 75

Tid til neste ankomst.
Betjeningstid

Question 76

Hva består et køsystem av?

Answer 76

et køsystem består av 2 ting:
1) Selve køen
2) Serverings mekanismen

Andre ting, som populasjon/input source er ikke en del av køsystemet, men skal likevel være med i visse beregninger.

Question 77

Si vi har et køsystem der kendall notasjon er M/M/x/8.

HVor mange er det plass til i køen?

Answer 77

Det kommer an på kapasiteten på server, x. Tallet som brukes i kendall er totalt i køsystemet. Derfor er det plass til 8-x i køen.

Question 78

Customers can enter either …

Answer 78

The queue, which is the equivalent of the waiting room in the doctors office.

OR

Straight to the server/serving mechanism. this would be the doctor’s room.

The choice between the two depends on whether the server(s) have space or not/availability.

Question 79

What can we say about the input source?

Answer 79

The input source will have a size. Commonly regarded as “infinite”. The size is formally defined as the total number of distinct individuals that may require service.

The rule about size of input source: IF the “rate” at which customers are generated is being significantly affected by the size of the population, then we have to make an assumption on the fact that the population is in fact not infinite.

input sources are also always described by a statistical distribution, by which the input source is generating the rate of customers. Usually, this statistical distribution, is heavily linked to a Poisson process. Following a poisson process is basically just saying that the number/rate of customers being generated per unit time by the source is following a poisson distribution. Recall that this is equivalent of saying “the time between arrivals is given by the exponential distribution”.

Finally, recall the process of “balking”: Balking refers to customers choosing to opt out after looking at the queue.

Question 80

Explain what the queue is

Answer 80

Do not confuse the queue with the queueing system.

The queue only refers to the waiting area of the entire queueing system.
The Queueing system includes the queue AND the server-space.

Queues are characterized by their size, and their capacity. The capacity is typically assumed to be “infinite”, because the extra work of dealing with finite queues is usually not relevant. However, if the maximum capacity is rather small, this can impact the queue.

Question 81

what’s Pn?

Answer 81

The probability of there being exactly n people in the queuing system

Question 82

What’s L?

Answer 82

L is the expected number of people in the entire queueing system.

Given as:

L = ∑(nPn)[n=0, infinity]

Question 83

What is Lq=

Answer 83

Lq is the expected length of just the queue. It is given as:

Lq = ∑(n-s)Pn [n=s, n=infinity]

This is the same as:

Lq = ∑nPn[n=s, s=infinity] - ∑sPn [n=s, n=infinity]

Question 84

What do we do if lambda n is not the same for all lambdas?

Answer 84

This means that we cannot just use “lambda” (without the n) as universal rate. Therefore, to make things easy for us, we can use the average rate of arrivals instead.

Question 85

What equation do we need to be able to connect the four fundamental quantities together?

Why is this a particular important result?

Answer 85

W = Wq + 1/µ

To be precise, this formula allows us to do the following:
- Assuming known values for lambda and mu, we only need one of the four fundamental quantities in order to calculate all the others.

The reason this is such an important thing, is that some of the quantities are significantly less difficult to otherwise compute. Therefore, we want to compute the easy one, and use Little’s formula and this result right there to compute the remaining quantities.

Just to be clear, we usually need all four of the quantities when we want to analyze the queueing system. It makes a lot of sense to include the expected size in people both in entire and queueing system, and the size in terms of time.

Question 86

We usually highlight 2 considerations when using statistical distributions to create our models…?

Answer 86

1) the distribution must be sufficiently realistic
2) Sufficiently easy so that it allows us to get some value

Based on these 2 considerations, the exponential distribution is widely used in queueing theory. So, this means that the exponential distribution is by no means perfect, but it offers a great trade off.

Question 87

name the implications/outcomes of assuming that the exponential distribution fits our case

Answer 87

1) expo is strictly decreasing, which means that it is more likely to take on a smaller value than a larger value, and it tends to pick close to 0.
This is a problem near 0 if the server usually eprforms the same number and sequence of steps, as most serving mechanisms have limits on how close to zero they can get (Source). Therefore, the exponential distribution does not provide a close approximation for the service time for such cases (Source).

however, the expo fits better in cases where most of the cases are in fact non-time-consuming. For instance ER.

2) Lack of memory.

3) The minimum of a set of individual exponentially distributed random variables is actually exponential.
The rate is equal to the sum of the individual rates.
The result of this property is that you can choose to ignore the fact that there are possible multiple types of different customers and STILL have an exponential arrival time shite.
BUT: This property is mainly a topic to consider for service times in cases where we have multiple servers. The trick here is that the entire serving system can be viewed as a single server system. If we have n servers currently being busy, and each is exponentially distributed in regards to serving time, with the same parameter µ, then the abstract single server case is exponentially distributed with rate = nµ.

4) Relationship to Poisson. this is basically just the fact that we can use the Poisson distribution to caculate hte probability there being less than or equal to X amount of people being served or whatever in some unit of time.

5)

Question 88

Say we are looking at a multi-server case where each server has different rates. Then the case is this: we want to calcualte the probability that server “j” will finish first. How do we do this?

Answer 88

to do this, we need the mean rate of server “j” and the sum of all rates. Then we divide the rate of server “j” on the total sum of all rates.

P(Tj = U) = µj /(∑(µi)[i=1, n])

When U is the smallest RV, j is the specific server in question (constant) and “i” is the summation index.

Question 89

Notation-wise, how do we represent the “state of the queueing system” in a birth-and-death process?

Answer 89

N(t) to indicate the state (size) after time t.

Question 90

What does a birth and death process actually describe?

Answer 90

A birth and death process describes probabilistically how the state of the queueing system change with time.
It says that births and deaths occur randomly, and their “rates” only depend on the specific state. Thus, we care a lot about what the rates are at the various states.

It is based on a list of assumptions.

A1) Given N(t)=n, the births are given by exponentially distributed RV with rate specific to state n.

A2) same but with service times (deaths)

A3) A1 and A2 are mutually independent. this means that the next state is either caused by a death, or it is caused by a birth. Not both.
So, we either have:
n = n+1 (birth)
or
n = n-1 (death)

Question 91

Instead of referencing the assumptions of the birth and death process, what is the main outcome of the assumptions?

Answer 91

The main outcome is the fact that the next state is determined ONLY on the basis of the current state. We dont need any information about other states than the current state.

This is essentially the markov property.

Question 92

describe why the probability of exponential distributon is greater for intervals happening sooner rather than later

Answer 92

If we want to find the probability of a later interval, this would include finding the probability that NO EVENT happen all the way up until this interval begin. Then we multiply this by the probability of event happening in the next interval. This is essentially the memoryless property multiplied by the probability of no event occurring before the start of this interval.

Because of this, it makes a whole lot of sense to use exponential distribution to model queueing systems.

Question 93

Elaborate on the process of finding the balance equations

Answer 93

We start by considering some state n. As we know, we cannot reach the same state multiple times in a row without leaving it first. Therefore, we differ between two cases:
1) Entering state x
2) Leaving state x
These two MUST alternate always. We can enter a state by serving a customer or by adding generating a customer. We can leave a state by the same.

We use En(t) as the number of times we have reached state n (entered state n) within time t.
We use Ln(t) as the number of times we have left state n within time t.

Since they must alternate, we have the following result:

|En(t) - Ln(t)| <= 1
then we divide by t:
|En(t)/t - Ln(t)/t| <= 1/t

Now we ask ourselves: What happens if we let t grow large?

The term 1/t will grow towards 0. This means we get the following;
lim t->LARGE |En(t)/t - Ln(t)/t| = 0

this means that En(t)/t = Ln(t)/t
These terms represent the mean rate of entrance vs the mean rate of departures per unit of time. They represent convergent numbers that will grow stable with time. This has nothing to do with stability of the queueing system, but only about the fact that they are alternating, and 1000 vs 1001 entries vs departures is approximately the same.

To set up the balance equation of some specific state, we look at the state in question, and we look at the probability of being in that state. Including the probability allows us to extend this equation so to be usable in determining the final expected characteristics of the queueing system.

Consider state 0. We can only enter state 0 from state 1 by leaving state 1.
P(state 1)µ1 = P1µ1
We can leave state 0 from state 0 only, and we can only move UP:
P(state 0)lambda0 = P0lambda0
Then we apply get
P1µ1 = P0λ0

Now let us consider states not equal to state 0. Say state 1:
We can enter state 1 by going down from state 2 or going up from state 0:
mean rate in = P2µ2 + P0λ0
mean rate out = P1µ1 + P1λ1

Which gives us :

P2µ2 + P0λ0 = P1µ1 + P1λ1
P2µ2 + P0λ0 = P1 (µ1 + λ1)

Now we utilize the fact that we have already computed something for state 0:
We have that P1 = P0 λ0/µ1
We use this in the above result:

P2µ2 + P0λ0 = (P0 λ0/µ1) (µ1 + λ1)

P2µ2 = (P0 λ0/µ1) (µ1 + λ1) - P0λ0

Common factor, slide it in:

P2µ2 = (P0λ0(µ1 + λ1) - P0λ0µ1) / µ1

Same as

P2 = (P0λ0(µ1 + λ1) - P0λ0µ1) / (µ1µ2)

P2 = P0 (λ0(µ1 + λ1) - λ0µ1)/(µ1µ2)

P2 = P0 (λ0 λ1)/(µ1µ2)

This is sort of the main result. We call the lambda and mu part Cn to represent the rates part. If lambda and mu are the same for all states, we basically just get p^n where p is the utilization factor.

important part here is that this gives rise to the formula
Pn = P0Cn.

Also, since we knwo the probaiblity of all states must be equal to 1, we know that the following applies:

∑Pn = 1 ==> P0∑Cn = 1

==> P0 = 1 / (∑Cn) = (∑Cn)^(-1)

Question 94

Regarding different queueing models that are based on birth and death process: How do they really differ?

Answer 94

The differ in regards to how the lambdas and mu’s are changing based on the state. In other words, the characteristics of rate of arrivals and rate of services will determine the different queueing models that are based on birth-and-death processes.

In the simplest case, they dont change at all and remain constant. Suitable for infinite capacity queues and single server case.

However, if we have multiple servers, and capacities on the queue etc, lambda and mu will behave differently.

Question 95

elaborate on euler number

Answer 95

euler number is actually used in modeling because of the fact that it simplifies computations a lot. Typically used for symmetrical abilities.

This means, we could use any number in the normal distribution instead of e and still be able to produce a function with the desired properties (must change some other things as well probably).

Question 96

Elaborate on the waiting time in the queueing system, with the weird W.

Answer 96

It represent the waiting time for some individual customer. It is a random variable.

Since it is referencing waiting time in the entire queueing system, it will also take account for the time spent being served. Note that in some cases, it is more fitting to only use the waiting time in the queue-line, not the entire queueing system.

In order to calculate this waiting time, we use the following facts:
1) We are currently in state n. The probability of being in state n is Pn, which is equal to P0Cn etc.
2) The waiting time depends on each individual customer, and how much time they spend being served.
3) We also include the time WE are using being served. Therefore, we need to sum together n+1 random variables.

The individual waiting times are each exponential. Apparently, the sum of exponentia lvariables (independent variables) is an Erlang-k distribution.

The IMPORTANT part is that with CONSIDERABLE manipulation, the expression from the Erlang distribution will reduce into something that is purely exponential, at least the cumulative distribution is exponential.
This means that we can use this fact to find the mean.

NBNBNBNBNB: There is no damn point in figuring this shit out. We only need to use Little’s formula.

Question 97

How do we go from an infinite queue to a finite queue?

Answer 97

We change lambda so that lambda is just simply 0 for all levels above or equal to the limit we want our queue to have.

Question 98

Name one property of the M/M/s/K model?

Answer 98

As long as K is not infinite, this queue will always reach a steady state, regardless of the lambda and mu.

Question 99

What do we do in order to handle finite populations?

Answer 99

Say we have population of size N.

We consider them to be outside, and we consider them all as individual exponentially, individually distributed random variables representing OUTSIDE TIME. As we know, the minimum of exponential RVs is also exponential, but with rate parameter equal to the sum of all rate parameters. Thus, if there are N customers outside, the rate for this state would be Nlambda.

Question 100

Why do we write only Pn?

Answer 100

Pn is actually only usable in steady states. If the state aint steady, we use Pn(t) to indicate the fact that the probability is dependent on the time as well

Question 101

Given M/M/s queue with s>1, what is easiest to compute first and why?

Answer 101

When s>1 we have to use two different coefficients for the Cn expression. If we want to calculate L first, we need to use both of these expressions, which means that we need to split the expression.

However, if we find Lq first, we only focus on the queue. Since we only focus on the queue, we are ALWAYS looking at the case where there are more people than servers (or equal to). This can greatly reduce the difficulty.

We find the solution to Lq=∑(n-s)Pn by performing a substitution of j=n-s. We also need to remember that the utilization factor is NOT JUST (lambda/mu). The utilization factor goes on the entire queueing system, and is therefore (lambda / (sµ)).

Given these two tricks/cues, we can solve the summation like we normally would, using differentiation technique and infinite sum.

The result is something that we can use. The only difficult part is P0, but this is usually given?

Question 102

Say we have “n” people in the queueing system. How do we proceed to find the waiting time for a new arrival?

Answer 102

The new arrival will have to wait n+1 exponentially distributed waiting times. this plus one part is due to his own time being served.

The sum of exponentuially distributed random variables have Erlang distribution. Recall that the erlang distribution is the same as gamma, but the shape parameter “k” is constrained to be an integer.

Question 103

Can we use Little’s formula when we are dealing with finite calling populations?

Answer 103

We can, but not with just the lambda. We need to use the average lambda. It is not really a question of lambda, it is a question about the arrival rate. We need the average arrival rate if we want to use littles formula. Therefore, we need to find average arrival rate like the formula.

The same is the case with the other formula using W and Wq and service rate.

Question 104

What is C0 defined as?

Answer 104

1.