Operational Research Notes > Operational Research Techniques Notes

This is an extract of our **Queuing Theory 1** document, which
we sell as part of our **Operational Research Techniques Notes** collection written by the top tier of
LSE students.

* The following is a more accessble plain text extract of the PDF sample above, taken from our Operational Research Techniques Notes.
Due to the challenges of extracting text from PDFs, it will have odd formatting:
*

Lecture 11: Queuing Theory 1 Topics

* Introduction

* Key Factors Influencing the Life Cycles of Queues

* What is "the System"?

* Arrival Patterns

* Queue Discipline

* Service Characteristics

* Queue Development

* Queues and Markov Chains

* General Equations of the Steady State

* Single-Server Rates-Independent Model: Major Statistics

* Example

Reading

* Taha (Chapter 15)

Definitions

* Balance Equation for state 0 = In state 0 in the steady state, the mean entering rate balances the mean leaving rate

* Initial Phase = When the shop opens and for a short period after that

* Steady State = When the various probabilities have become constant

* Transient Phase = When the probability that there are j customers in the system varies with time t

Introduction

* Any sequence of arrivals and departures is a realisation of a stochastic process

* The queuing system may exhibit steady state or equilibrium behaviour Key Factors Influencing the Life Cycles of Queues

* Three key factors influence the life cycles of individual queues: a. The arrival patterns of the 'items' b. The logic of the queue behaviour c. The characteristics of the service facility

Formulae

*

*

*

* E[inter-arrive time]=1/

* General Balance Equation for state j =

* Almost all queuing systems are stochastic processes

* We look to identify the expected values of the system characteristics

* Not to predict the future

* Number in the system = Number being served + number queuing

What is "the System"?

* The system consists only of the customers who are being served or who are queuing

* The number in the system does not include:

* The servers

* The customers who are still shopping

* Number in the system = Number being served + number queuing Arrival Patterns

*

is the average number of arrivals per unit of time

*

is the probability of an arrival in the extremely small time interval (t,t+dt)

* This is independent of what happened earlier

* These arrivals follow a Poisson distribution with an expected rate of per unit time

* The time between successive arrivals has an exponential distribution with mean value

* P(j in the system) is:

* P(system is in state 0 at time t and an arrival occurs in (t,t+dt)) =

* P(system switches from state 1 to state 2 in (t,t+dt)) =

* Probability of x arrivals per unit time:

* The cumulative density function of arrival pattern:

units of time

* Probability of x arrivals per unit time:

*

*

*

*

The cumulative density function of arrival pattern: The inter-arrival times have an exponential distribution E[inter-arrive time]=1/

We assume:

* that the arrivals are independent ([?] individual)

* The arrivals are random in time

* The arrival rate does not vary with time

Queue Discipline

* i.e. FIFO, LIFO, random, balking, jockeying, reserving, swapping, priorities

* There may be limits on queue size

* Customers may leave the queue after a certain time if they haven't been served Service Characteristics

* There may be more than one server

* There may be specialist servers i.e. less than 10 items or cash only

* We assume service times have an exponential distribution

* Expected number of services per unit time being

* There is a constant probability that a service will end during the time period

* A truncated Normal or preferably a Beta distribution is more likely Queue Development

* There are usually 3 development phases

* Initial Phase = When the shop opens and for a short period after that

* Transient Phase = When the probability that there are j customers in the system varies with time t* Steady State = When the various probabilities have become constant simply as

? We then write

* The first two phases are often bundled together for convenience

* We are most interested in the steady state Queues and Markov Chains

* Some queues can be represented as Markov Chains

* We suppose arrivals and departures occur singly at discrete times

* We also assume that the probability of an individual arrival or departure is independent of what has happened previously

* We model this as a Markov Process which can be represented by a Markov Chain

* We can also consider queues in continuous time General Equations of the Steady State Case 1: Rates are Dependent on k, the No. of Customers in the System

* Let arrival rate be

? This is either an increasing function of j (e.g. customers being attracted to a successful restaurant)

? Or a decreasing function of j (e.g. customers entering a supermarket may balk (leave) if they observe that long queues are building up)

* The values of (from ) are all different We also assume that the potential service rates also vary with j

Course Notes Page 22

Key Points

* Life cycles of queues

* What is the system?

* Arrival patterns

* Queue discipline

* Service characteristics

* Queue development

* Markov chains

* Steady states, balanced equations and recurrence relations

* Case 1: Rates are dependent on k (the number in the system)

* Case 2: Rates independent of k (only one server)

* Major statistics of case 2

*Buy the full version of these notes or essay plans and more in our Operational Research Techniques Notes.*