Script

QUEUING MODELS – Basic Concepts

Slide 1

·  Welcome back.

·  In this module we begin our look at service models, in particular waiting line models.

Slide 2

·  Queue is the British word for waiting lines.

·  And hence queuing analysis is the evaluation of waiting line policies.

·  Queuing models have been used to determine

·  The number of checkout stands to staff in a grocery store

·  The kind of line (one long line or several short lines) to have at a bank

·  The seating procedures in a crowded restaurant

·  Scheduling of patients waiting to be seen at a clinic

·  Landing procedures for planes queued up at an airport

·  The flow of materials from one queue to the next in a production process

·  The number of toll booths to have open on a toll bridge during rush hour; and many other similar situations.

Slide 3

·  A queuing model consists of three parts

·  Customers arriving

·  Customer waiting in line

·  And customers being served

·  In queuing models, we refer to the customers in the queue as only those waiting in line

·  Whereas we say a customer is in the system if he is

·  Either in the queue

·  Or being served. The distinction is important because some managers feel that customers are happy as long as they are being served and thus focus mainly on the queue. Others feel that the entire queuing experience including time spent being served should be analyzed.


Slide 4

·  To illustrate, let’s look at this system where the three small rectangles represent clerks or servers and the circles represent customers.

·  The queuing process then consists of customers arriving

·  They may or may not have to wait in a queue depending on the number of customers in front of them

·  Then they get served and leave.

·  Now the queue consists only of those standing in line

·  While the system includes those standing in line and being served. So in this example, there are

·  4 customers in the queue and

·  7 customers in the system

Slide 5

·  There are literally thousands of queuing models depending on the arrival process, the characteristics of the waiting line and the service process. Questions which identify the arrival process include the following.

·  Is the time between arrivals known with certainty (that is the process is deterministic – such as sending product at fixed time intervals down an assembly line), or do arrivals occur according to some probability distribution (such as arrivals to a bank)? And if they do arrive according to a probability distribution what are the characteristics of this distribution? In our models we will assume that arrivals do arrive according to a probability distribution that we will describe later.

·  Are arrivals influenced by the number of customers already viewed in the system or not? When you go to a gas station, sometimes you see far too many cars already there and so you go to another one down the street or simply postpone buying gas until another time – you were going to join the system, but the line influenced you. In our models, we will assume this “balking” will not occur and a potential arriving customer will join the system no matter what.

·  Do customers arrive individually of do they arrive in groups of various sizes? Cars arrive to a baseball game individually, but people arrive in groups or batches depending on the number in each car. We will discuss only individual arrivals.

·  Are some arrivals treated differently than others or are they all treated the same? The President of the United States may get priority in terms of arriving to a restaurant over someone like you or me. Our models will assume that all arrivals are treated equally.

·  Is the number of possible arrivals finite or infinite? I guess all queuing situations, in some sense have a finite number of possible arrivals – the number of arrivals to Macy’s can’t be more than the number of people in the world. But we would say this is an infinite calling population. Now the Edgewood Private School with its own school bus repair facility may have only 4 school buses. In this instance the number in the calling population would be considered finite -- 4! We usually assume an infinite calling population, but we will also briefly discuss models with a finite calling population.


Slide 6

·  Queuing models also are influenced by the kind of waiting line that is used. Questions pertaining to the waiting line include the following.

·  Do we have one long line (like at most banks) or several short lines (like at most grocery stores)? We will discuss models only with one long line.

·  But if there were several short lines, is jockeying allowed? – that is can a person who is fed up with a line that he perceives is moving too slowly switch lines? Since we are only going to discuss models with one long line, we will not have to worry about this situation.

·  Is there a limit to the maximum number of customers that can be in line? Again, probably in all queuing situations, there is probably some upper limit – Macy’s can only hold 2000 customers according to the fire marshal. But by finite, we mean can there only be a few customers waiting in line? We begin our discussion assuming that there is no limit to the waiting line, but we discuss finite queues as well.

·  Can customers leave before they are serviced? You go to your bank to do some quick business during your lunch hour and you wait in line. But on this particular day, the line is extremely slow and you have to get back to work so you leave before you do your business with the bank. In the models we discuss, this will not happen – once a person joins the system, he stays there until his service is completed.

·  Do we just have one queue (like at a bank) or do we have a situation like a production process where once one operation is completed the item must then wait in another line for another operation. This is called queues in tandem, but we will not discuss them here.

Slide 7

·  Finally queuing models are also influenced by the service process. Questions pertaining to the service process include the following.

·  Is there just one server or are there many servers?

·  And if there are many servers do they all perform equally well? We’ll begin our discussion with analysis of a single server system. We will then discuss what happens when we have many identical servers. And when we discuss simulation later, we will also address the situation where each server servers at different speeds.

·  Are service times deterministic (like when you go to a soda machine, it takes exactly 6 seconds, say, for the can to drop down) or do service times follow a probability distribution, and if so, what is it? We will discuss only models having a probability distribution.

·  Does the speed of the service depend on how many people are waiting in line? When you go to a grocery store, oftentimes if there are no people waiting behind you, the clerk will check you out more slowly and chat with you a little. But if there are several people waiting behind you, they will check you out at their usual speed. Our models will assume that the service time does NOT depend on the number of people waiting in line behind you.

·  Is the order of service, first in first out, last in first out, or some other priority. We will assume all models have first in first out service. Of course there are many variations of arrival processes, waiting lines and service processes, so that the number of different types of queuing situations is virtually limitless.


Slide 8

·  There are several objectives one might have when designing or evaluating a queuing situation.

·  Among others, one might be

·  To maximize the total profit

·  Another might be to minimize the average waiting time of the customers.

·  Another might be to meet a desired service level.

Slide 9

·  When evaluating queues there are certain quantities that may be of interest to the decision maker.

·  One might be the average number of customers in the system. We designate this by L.

·  Another might be the average number of customers in the queue. We designate this by L sub Q.

·  We may be interested in the average time a customer spends in the system. The symbol used for this is W.

·  The average time a customer spends only in the queue is designated by W sub Q.

·  The probability that there are n customers at any one time in the system is p sub n.

·  And the Greek letter rho is used to designate the average number of busy servers.

Slide 10

·  Like the EOQ model for inventory, we begin with a simplistic model for queuing which we can tweak later. The simplest queuing models assume a Poisson arrival process.

·  This requires three things:

·  What is called orderliness

·  Which says that in any split second there will only be 0 or 1 arrival, not more.

·  Stationarity

·  Which means the parameters of the process do not change over the interval of interest

·  And independence

·  Which means the time to the next arrival does not depend on when the last arrival occurred.

Slide 11

·  If we can make these three assumptions

·  And we have an estimate for the average number of arrivals that occur in say an hour, which we denote by the Greek letter lambda, then

·  The formula that gives the probability of k arrivals in t hours is

·  Lambda t to the k-th power times e to the minus lambda t power over k factorial


Slide 12

·  If the average number of arrivals per hour is lambda

·  Then the average time between arrivals is 1 over lambda hours.

·  And the distribution for the time between arrivals for a Poisson process is an exponential distribution with density function

·  Lambda times e to the minus lambda t power

·  This means that

·  the probability the next arrival will not occur within the next t hours is e to the minus lambda t.

·  Which implies that the probability that the next arrival will occur within the next t hours is 1 minus e to the minus lambda t.

Slide 13

·  The basic queuing model also assumes a Poisson service process

·  Meaning

·  For orderliness

·  At most one customer will finish service in any split second – that’s okay.

·  For stationarity

·  The probability of completing n potential services in time intervals of equal length remains the same – that’s okay too.

·  But for independence this assumption means

·  The time to the completion of a service is independent of when it started. That means if the probability that your service would be completed within 30 minutes was .7, and an hour later you are still being served, the probability that your service will be completed within the next 30 minutes is still .7

·  Is this really a good assumption? Well, sometimes yes, but most of the time no. But we make it anyway to get things started. In many queuing models this is the first assumption that gets relaxed or changed.

Slide 14

·  If we do make these assumptions we can get a similar expression for the number of potential services in a time period, t.

·  We use the words “potential services” because, unlike an arrival process which requires nothing for an arrival to take place, for a service to take place there must have been arrivals. So we talk about potential services, if there were customers to serve.

·  The service rate, meaning the number of customers that could be served per hour by a server is designated by the Greek letter, mu.

·  The formula that gives the probability of k potential services in t hours is

·  Mu t to the k-th power times e to the minus mu t power over k factorial


Slide 15

·  If the service rate is mu

·  Then the average service time is 1 over mu hours.

·  And the distribution for the service time is an exponential distribution with density function

·  Mu times e to the minus mu t power

·  This means that

·  the probability it will take longer than t hours to complete a service is e to the minus mu t.

·  Which implies that the probability that the service will be completed within the next t hours is 1 minus e to the minus mu t.

Slide 16

·  It is important that we distinguish between what is called transient state and steady state when dealing with queuing models.

·  Steady state is the situation after the operation has been ongoing for a long time and represents the long term behavior of the system.

·  Until the system reaches steady state, it is said to be in a transient state – transiting to steady state. When a bank first opens for business on a Monday morning there are typically a lot of customers waiting to do business right away. But after a while, these customers are served and the system settles down to a more normal operation – this is its steady state.

·  It is this steady state behavior that we will keep track of.

Slide 17

·  Now in order for a system to reach steady state

·  The overall arrival rate must be less than the overall service rate or else the system will just continue to grow larger and larger indefinitely.