Unit 6 Queuing Theory - Lecture notes 3 PDF

Preview

Summary

Download Unit 6 Queuing Theory - Lecture notes 3 PDF

Description

SCHOOL OF BUSINESS, ECONOMICS AND MANAGEMENT BF360 Operations Research

Unit 6: Queuing Theory

Moses Mwale e-mail: [email protected]

BF360 Operations Research

Contents Unit Six: Queuing Theory

3

6.0 Introduction ................................................................................................................. 3 6.1 Elements of Waiting Line Analysis ............................................................................ 3 6.2 The Single-Server Waiting Line System .................................................................... 4 6.2.1 The Queue Discipline ..................................................................................... 5 6.2.2 The Calling Population ................................................................................... 6 6.2.3 The Arrival Rate ............................................................................................. 6 6.2.4 The Service Rate ............................................................................................ 6 6.2.5 The Single-Server Model ............................................................................... 7 6.2.6 The Effect of Operating Characteristics on Managerial Decisions .............. 10 6.3 Finite Queue Length ................................................................................................. 13

BF360 Operations Research

Unit Six: Queuing Theory 6.0 Introduction

Queueing theory is the mathematical study of waiting lines, or queues. In queueing theory a model is constructed so that queue lengths and waiting time can be predicted.

Waiting in queues—waiting lines—is one of the most common occurrences in everyone’s life. Anyone who has gone shopping or to a movie has experienced the inconvenience of waiting in line to make purchases or buy a ticket. Not only do people spend a significant portion of their time waiting in lines, but products queue up in production plants, machinery waits in line to be serviced, planes wait to take off and land, and so on. Because time is a valuable resource, the reduction of waiting time is an important topic of analysis. The improvement of service with respect to waiting time has also become more important in recent years because of the increased emphasis on quality, especially in service-related operations. Increasing service capacity in this manner has a monetary cost, and therein lies the basis of waiting line analysis: the trade-off between the cost of improved service and the cost of making customers wait. Like decision analysis, queuing analysis is a probabilistic form of analysis, not a deterministic technique. Thus, the results of queuing analysis, referred to as operating characteristics, are probabilistic. These operating statistics (such as the average time a person must wait in line to be served) are used by the manager of the operation containing the queue to make decisions. A number of different queuing models exist to deal with different queuing systems. We will discuss two of the most common types of systems—the single-server system and the multiple-server system.

6.1 Elements of Waiting Line Analysis Waiting lines form because people or things arrive at the servicing function, or server, faster than they can be served. However, this does not mean that the service operation is understaffed or does not have the overall capacity to handle the influx of customers. In fact, most businesses and organizations have sufficient serving capacity available to handle their customers in the long run. Waiting lines result because customers do not arrive at a constant, evenly paced rate, nor are they all served in an equal amount of time. Customers arrive at random times, and the time required to serve them individually is not the same.

3

4

Unit Six: Queuing Theory

Thus, a waiting line is continually increasing and decreasing in length (and is sometimes empty), and it approaches an average rate of customer arrivals and an average time to serve the customer in the long run. For example, the checkout counters at a grocery store may have enough clerks to serve an average of 100 customers in an hour, and in any particular hour only 60 customers might arrive. However, at specific points in time during the hour, waiting lines may form because more than an average number of customers arrive, and they make more than an average number of purchases. Decisions about waiting lines and the management of waiting lines are based on these averages for customer arrivals and service times. They are used in queuing formulas to compute operating characteristics, such as the average number of customers waiting in line and the average time a customer must wait in line. Different sets of formulas are used, depending on the type of waiting line system being investigated. For example, a bank drive-up teller window that has one bank clerk serving a single line of customers in cars is different from a single line of passengers at an airport ticket counter that is served by three or four airline agents. In the next section we present the different elements and components that make up waiting lines before we look at queuing formulas in the following sections.

6.2 The Single-Server Waiting Line System A single server with a single waiting line is the simplest form of queuing system. As such, it will be used to demonstrate the fundamentals of a queuing system. As an example of this kind of system, consider Fast Shop Market. Fast Shop Market has one checkout counter and one employee who operates the cash register at the checkout counter. The combination of the cash register and the operator is the server (or service facility) in this queuing system; the customers who line up at the counter to pay for their selections form the waiting line, or queue. The configuration of this example queuing system is shown in Figure 6.1 below.

BF360 Operations Research

The most important factors to consider in analyzing a queuing system such as the one in Figure 6.1 are the following:

Figure 6.1

1. The queue discipline (in what order customers are served) 2. The nature of the calling population (where customers come from) 3. The arrival rate (how often customers arrive at the queue) 4. The service rate (how fast customers are served) We will discuss each of these items as it relates to our example.

6.2.1 The Queue Discipline The queue discipline is the order in which waiting customers are served. Customers at Fast Shop Market are served on a “first-come, first-served” basis. That is, the first person in line at the checkout counter is served first. This is the most common type of queue discipline. However, other disciplines are possible. For example, a machine operator might stack in-process parts beside a machine so that the last part is on top of the stack and will be selected first. This queue discipline is referred to as “last-in, first-out.” Or the machine operator might simply reach into a box full of parts and select one at random. In this case, the queue discipline is random.

5

6

Unit Six: Queuing Theory

Often customers are scheduled for service according to a predetermined appointment, such as patients at a doctor’s or dentist’s office or diners at a restaurant where reservations are required. In this case, the customers are taken according to a prearranged schedule, regardless of when they arrive at the facility. One final example of the many types of queue disciplines is when customers are processed alphabetically according to their last names, such as at school registration or at job interviews.

6.2.2 The Calling Population The calling population is the source of the customers to the market, which in this case is assumed to be infinite. In other words, there is such a large number of possible customers in the area where the store is located that the number of potential customers is assumed to be infinite. Some queuing systems have finite calling populations. For example, the repair garage of a trucking firm that has 20 trucks has a finite calling population. The queue is the number of trucks waiting to be repaired, and the finite calling population is the 20 trucks. However, queuing systems that have an assumed infinite calling population are more common.

6.2.3 The Arrival Rate The arrival rate is the rate at which customers arrive at the service facility during a specified period of time. This rate can be estimated from empirical data derived from studying the system or a similar system, or it can be an average of these empirical data. For example, if 100 customers arrive at a store checkout counter during a 10-hour day, we could say the arrival rate averages 10 customers per hour. However, although we might be able to determine a rate for arrivals by counting the number of paying customers at the market during a 10hour day, we would not know exactly when these customers would arrive on the premises. In other words, it might be that no customers would arrive during one hour and 20 customers would arrive during another hour. In general, these arrivals are assumed to be independent of each other and to vary randomly over time. Given these assumptions, it is further assumed that arrivals at a service facility conform to some probability distribution. Although arrivals could be described by any distribution, it has been determined (through years of research and the practical experience of people in the field of queuing) that the number of arrivals per unit of time at a service facility can frequently be defined by a Poisson distribution.

6.2.4 The Service Rate The service rate is the average number of customers who can be served during a specified period of time. For our Fast Shop Market example, 30 customers can be checked out (served) in 1 hour. A service rate is similar to an arrival rate in that it is a random variable. In other words, such factors as different sizes of customer purchases, the amount of change the

BF360 Operations Research

cashier must count out, and different forms of payment alter the number of persons that can be served over time. Again, it is possible that only 10 customers might be checked out during one hour and 40 customers might be checked out during the following hour. The description of arrivals in terms of a rate and of service, in terms of time is a convention that has developed in queuing theory. Like arrival rate, service time is assumed to be defined by a probability distribution. It has been determined by researchers in the field of queuing that service times can frequently be defined by a negative exponential probability distribution. However, to analyze a queuing system, both arrivals and service must be in compatible units of measure. Thus, service time must be expressed as a service rate to correspond with an arrival rate.

6.2.5 The Single-Server Model The Fast Shop Market checkout counter is an example of a single-server queuing system with the following characteristics: 1. An infinite calling population 2. A first-come, first-served queue discipline 3. Poisson arrival rate 4. Exponential service times These assumptions have been used to develop a model of a single-server queuing system. However, the analytical derivation of even this simplest queuing model is relatively complex and lengthy. Thus, we will refrain from deriving the model in detail and will consider only the resulting queuing formulas. The reader must keep in mind, however, that these formulas are applicable only to queuing systems having the foregoing conditions. Given that λ = the arrival rate (average number of arrivals per time period) μ = the service rate (average number served per time period) and that (customers are served at a faster rate than they arrive), we can state the following formulas for the operating characteristics of a singleserver model. The probability that no customers are in the queuing system (either in the queue or being served) is 𝜆 𝑃0 = (1 − ) 𝜇 The probability that n customers are in the queuing system is 𝜆 𝑛 𝜆 𝑛 𝜆 𝑃𝑛 = ( ) ⋅ 𝑃0 = ( ) (1 − ) 𝜇 𝜇 𝜇

7

8

Unit Six: Queuing Theory

The average number of customers in the queuing system (i.e., the customers being serviced and in the waiting line) is 𝐿=

𝜆 𝜇−𝜆

The average number of customers in the waiting line is 𝐿𝑞 =

𝜆2 𝜇(𝜇 − 𝜆)

The average time a customer spends in the total queuing system (i.e., waiting and being served) is 𝑊=

𝐿 1 = 𝜇−𝜆 𝜆

The average time a customer spends waiting in the queue to be served is 𝑊𝑞 =

𝜆 𝜇(𝜇 − 𝜆)

The probability that the server is busy (i.e., the probability that a customer has to wait), known as the utilization factor, is 𝑈=

𝜆 𝜇

The probability that the server is idle (i.e., the probability that a customer can be served) is 𝐼 = 1−𝑈= 1− 𝜆

𝜆 𝜇

This last term, 1 − is also equal to 𝑃0 . That is, the probability of no 𝜇

customers in the queuing system is the same as the probability that the server is idle. We can compute these various operating characteristics for Fast Shop Market by simply substituting the average arrival and service rates into the foregoing formulas. For example, if λ = 24 customers per hour arrive at checkout counter μ = 30 customers per hour can be checked out

then 

The probability of no customers in the system is: 𝜆 24 𝑃0 = (1 − ) = (1 − ) = 0.20 30 𝜇



The average number of customers in the queuing system is: 𝐿=



24 𝜆 = =4 𝜇 − 𝜆 30 − 24

The average number on customers in the waiting line is:

BF360 Operations Research

𝐿𝑞 = 

The average time in the system per customer is: 𝑊=



(24)2 𝜆2 = 3.2 = 𝜇(𝜇 − 𝜆) 30(30 − 24) 1

𝜇−𝜆

1

= 30−24 = 0.167 hr (10 mins)

The average time in the waiting line per customer is: 𝜆

𝑊𝑞 = 𝜇(𝜇−𝜆) = 

= 0.133 hr (8 mins)

The probability that the server will be busy and the customer must wait is: 𝑈=



24

30(30−24)

𝜆 24 = = 0.8 𝜇 30

The probability that the server will be idle is: 𝐼 = 1 − 𝑈 = 1 − 0.8 = 0.20

Several important aspects of both the general model and this particular example will now be discussed in greater detail. First, the operating characteristics are averages. Also, they are assumed to be steady-state averages. Steady state is a constant average level that a system realizes after a period of time. For a queuing system, the steady state is represented by the average operating statistics, also determined over a period of time. Related to this condition is the fact that the utilization factor, U, must be less than one: 𝑈...