Queues are an aspect of modern life that we continually encounter in our daily activities. In a supermarket counter, accessing the Metro, in Banks, etc., the phenomenon of queues arises when shared resources need to be accessed to serve a high number of jobs or clients.
The study of queues is important because it provides both a theoretical basis for the type of service that we can expect from a given resource, and the way in which said resource can be designed to provide a certain degree of service to its customers.
Due to the aforementioned, the development of a tool that is capable of giving an answer about the characteristics of a certain queue model is considered very useful.
Initial definitions
The queuing theory is the mathematical study of the behavior of waiting lines. This occurs when "clients" arrive at a "place" demanding a service from a "server", which has a certain attention span. If the server is not immediately available and the client decides to wait, then the waiting line is formed.
A queue is a waiting line and queuing theory is a collection of mathematical models that describe particular waiting line systems or queuing systems. The models are used to find a good compromise between system costs and average waiting line times for a given system.
The queuing systems are models of systems providing service. As a model, they can represent any system where jobs or clients arrive looking for a service of some kind and leave after that service has been attended. We can model systems of this type either as simple queues or as a system of interconnected queues forming a network of queues. In the following figure we can see an example of a simple queue model. This model can be used to represent a typical situation in which clients arrive, wait if servers are busy, are served by an available server, and leave when the required service is obtained.
The problem is determining which capacity or service rate provides the correct balance. This is not easy, since a client does not arrive at a fixed time, that is, it is not known exactly when the clients will arrive. Also the service time does not have a fixed schedule.
The problems of "queues" are permanently present in daily life: a study in the US concluded that, on average, an average citizen spends five years of his life waiting in different queues, and of them almost six months standing at traffic lights.
Introduction to Queuing Theory
On many occasions in real life, a very common phenomenon is the formation of queues or waiting lines. This usually occurs when the actual demand for a service exceeds the capacity that exists to provide that service. Real examples of this situation are: the crossings of two traffic routes, traffic lights, a highway toll, ATMs, customer service in a commercial establishment, the breakdown of electrical appliances or other types of devices that must be repaired by a technical service, etc.
Even more frequent, if possible, are waiting situations in the context of information technology, telecommunications and, in general, new technologies. Thus, for example, the processes sent to a server for execution form waiting queues while they are not attended, the information requested, through the Internet, from a Web server may be received with delay due to congestion in the network or in the server itself. In other words, we can receive the signal from busy lines if the control unit on which our mobile phone depends is collapsed at that moment, etc.
Origin:
The origin of the Queuing Theory is in the effort of Agner Kraup Erlang (Denmark, 1878 - 1929) in 1909 to analyze the telephone traffic congestion with the aim of meeting the uncertain demand for services in the Copenhagen telephone system. His research led to a new theory called the queuing or waiting line theory. This theory is now a valuable business tool because a large number of problems can be characterized, such as arrival-departure congestion problems.
Queuing model.
In queuing issues, customers are often spoken of, such as people waiting for phone lines to be vacated, waiting for machines to be repaired, and planes waiting to land and service stations, such as tables in a restaurant., operators in a repair shop, runways at an airport, etc. Queuing problems often contain a variable rate of arrival of customers requiring a certain type of service, and a variable rate of service delivery at the service station.
When talking about waiting lines, they refer to those created by customers or by service stations. Customers may wait in line simply because existing facilities are inadequate to meet the demand for service; in this case, the queue tends to be explosive, that is, to be longer and longer as time passes. Service stations may be waiting because existing facilities are excessive in relation to customer demand; in this case, the service stations could remain idle most of the time. Clients may temporarily wait, even though service facilities are adequate, because previously arriving clients are being served. Gas stations may find temporary when,Although the facilities are adequate in the long term, there is an occasional shortage of demand due to a temporary event. These last two cases typify a balanced situation constantly tending towards equilibrium, or a stable situation.
In queuing theory, a group of physical units, integrated in such a way that they can operate in unison with a series of organized operations, is generally called a system. Queuing theory seeks a solution to the waiting problem by first predicting the behavior of the system. But a solution to the problem of waiting is not only to minimize the time that customers spend in the system, but also to minimize the total costs of those who request the service and those who provide it.
Queue theory includes the mathematical study of queues or waiting lines and provides a large number of mathematical models to describe them.
An economic balance must be achieved between the cost of the service and the cost associated with waiting for that service
Queuing theory itself does not solve this problem, it only provides information for decision making
Objectives of the Queuing Theory
The objectives of queuing theory consist of:
- Identify the optimal level of system capacity that minimizes the overall cost of the system Evaluate the impact that possible alternatives to modify the system's capacity would have on the total cost of the system Establish a balanced (“optimal”) balance between the considerations quantitative costs and qualitative services. We must pay attention to the time spent in the system or in the queue: the "patience" of customers depends on the type of specific service considered and that can make a customer "abandon" the system.
Existing elements in a queue model
Source of entry or potential population: It is a group of individuals (not necessarily living beings) that can request the service in question. We can consider it finite or infinite. Although the case of infinity is not realistic, it does allow (oddly enough) to solve more easily many situations in which, in reality, the population is finite but very large. This assumption of infinity is not restrictive when, even though the potential population is finite, its number of elements is so large that the number of individuals who are already requesting the aforementioned service practically does not affect the frequency with which the potential population generates new requests. of service.
Client: It is every individual from the potential population requesting service. Assuming that the arrival times of consecutive customers are 0 <t 1 <t 2 <…, it will be important to know the probability pattern according to which the entry source generates customers. The most common is to take as a reference the times between the arrivals of two consecutive customers: consecutive: consecutive customers: T {k} = tk - t k-1, setting their probability distribution. Normally, when the potential population is infinite, it is assumed that the probability distribution of the T k (which will be the so-called distribution of the times between arrivals) does not depend on the number of customers who are waiting to complete their service, while in the case the input source is finite,the distribution of the T k will vary according to the number of clients in the process of being served.
Queue capacity: It is the maximum number of clients that can be queuing (before starting to be served). Again, it can be assumed finite or infinite. The simplest thing, for the sake of simplicity in the calculations, is to assume it to be infinite. Although it is obvious that in most of the real cases the capacity of the queue is finite, it is not a great restriction to assume it to be infinite if it is extremely unlikely that clients cannot enter the queue because that limit number has been reached in the queue..
Queue discipline: It is the way in which customers are selected to be served. The most common disciplines are:
The FIFO (first in first out) discipline, also called FCFS (first come first served): according to which the customer who has arrived first is served first.
The LIFO (last in first out) discipline, also known as LCFS (last come first served) or stack: which consists of serving first the customer who has arrived last.
RSS (random selection of service), or SIRO (service in random order), which selects customers at random.
Service mechanism: It is the procedure by which service is provided to customers who request it. To fully determine the service mechanism, we must know the number of servers of said mechanism (if said number were random, its probability distribution) and the probability distribution of the time it takes each server to provide a service. In case the servers have different skills to provide the service, the distribution of the service time must be specified for each one.
The queue, properly speaking, is the set of clients that wait, that is, clients that have already requested the service but have not yet passed to the service mechanism.
The queue system: it is the set made up of the queue and the service mechanism, together with the discipline of the queue, which is what indicates the criteria of which client in the queue to choose to go to the service mechanism. These elements can be seen more clearly in the following figure:
A queuing system model must specify the probability distribution of service times for each server.
The most used distribution for service times is the exponential l, although it is common to find the degenerate or deterministic distribution (constant service times) or the Erlang (Gamma) distribution.
Kendall's notation
By convention, the models used in queuing theory are labeled
The distributions used are:
- M: Exponential distribution (Markovian) D: Degenerate distribution (constant times) E k: Erlang distribution G: General distribution
M / M / s : Model where both the times between arrival and the service times are exponential and there are s servers.
M / G / 1: Exponential times between arrival, general service times and 1 server only
Terminology
Usually it is always common to use the following standard terminology:
- System status: Number of clients in the system. Queue length: Number of clients waiting for service. N (t): Number of clients in the queuing system at time t (t ³0). P n (t): Probability that exactly n customers are in the system at time t, given the number at time zero. s: Number of servers in the queue system. ln: Average arrival rate (expected number of arrivals per unit of time) of new customers when there are n customers in the system. m n: Average service rate for the entire system (expected number of clients completing their service per unit of time) when there are n clients in the system.
Note: mn represents the combined rate at which all busy servers manage to terminate their services
ln : When ln is constant for all n
m n : When mn is constant for all n ³ 1
It can also be interpreted as the average number of people being cared for
Note: For the queuing systems that we will analyze we will make the assumption that the system is in the steady state condition.
Demonstration
For s = 1
r: expected fraction of time that individual servers are busy).
l = 12 / hour ® 1 / l = 5 minutes
m = 15 / hour ® 1 / m = 4 minutes
The server is working 4 out of every 5 minutes, that is, it is working 80% of the time
r : Average number of people being served
Average number = 0 * P0 + 1 * P1
Average number = P1
Average number = 1 / m / 1 / l
Average number = r
The following notation assumes the steady state condition:
- P n: Probability that there are exactly n clients in the system L: Expected number of clients in the system. L q: Expected length of the queue (excludes clients that are in service). W : Waiting time in the system for each client W: E (W) W q : Waiting time in the queue for each client. W q : E (W q)
Relations between L, W, Lq and Wq
Suppose that l n is a constant l for all n:
L = l W Lq = l Wq
Suppose the mean service time is a constant 1 / m for all n ³ 1
W = Wq + 1 / m L = Lq + r
These relationships are fundamental because they allow us to determine the four fundamental quantities L, W, Lq, Wq, as soon as the value of one of them is analytically found.
Key features.
There are two basic kinds of time between arrivals:
Deterministic, in which successive customers arrive in the same time interval, fixed and known. A classic example is that of an assembly line, where items arrive at a station at invariable intervals of time (known as time cycles).
Probabilistic, in which the time between successive arrivals is uncertain and variable. Probabilistic times between arrivals are described by a probability distribution.
In the probabilistic case, determining the real distribution is often difficult. However, one distribution, the exponential distribution, has proven to be reliable in many of the practical problems. The density function, for an exponential distribution depends on a parameter, say l (Greek letter lambda), and is given by:
f (t) = (1 / l) e- l t
where l (lambda) is the average number of arrivals in a unit of time.
With an amount, T, of time, the density function can be used to calculate the probability that the next customer will arrive within the following T units from the previous arrival, as follows:
P (time between arrivals <= T) = 1-e- l t
The service process.
The service process defines how customers are served. In some cases, there may be more than one station in the system in which the required service is provided. Banks and supermarkets, again, are good examples of the above. Each window and each register are stations that provide the same service. Such structures are known as multi-channel queuing systems. In such systems, the servers may be identical, in the sense that they provide the same kind of service just as quickly, or they may not be identical. For example, if all tellers in a bank have the same experience, they can be considered identical.
As opposed to a multi-channel system, consider a production process with a workstation providing the required service. All products must go through that work station; in this case it is a single channel queuing system. It is important to note that even in a single channel system there can be many servers that together perform the necessary task. For example, a single station car wash business may have two employees working on a car simultaneously.
Another characteristic of the service process is the number of clients served at the same time in a station. In banks and supermarkets (single channel system), only one customer is served at a time. On the contrary, passengers waiting at a bus stop are served in groups, depending on the capacity of the arriving bus.
Another characteristic of a service process is whether or not priority is allowed, that is, can a server stop the process with the client it is serving to give rise to a client that has just arrived? For example, in an emergency room, priority occurs when a doctor, who is treating a case that is not critical, is called to attend a more critical case. Whatever the service process, you need to have an idea of how long it takes to complete the service. This amount is important because the longer the service lasts, the longer arriving customers will have to wait. As in the case of the arrival process, this time can be deterministic or probabilistic. With a deterministic service time,each customer requires precisely the same known amount of time to be served. With a probabilistic service time, each customer requires a different and uncertain amount of service time. Probabilistic service times are mathematically described by a probability distribution. In practice it is difficult to determine what the real distribution is, however, a distribution that has proven reliable in many applications is the exponential distribution. In this case, its density function depends on a parameter, say (the Greek letter my) and is given byIn practice it is difficult to determine what the real distribution is, however, a distribution that has proven reliable in many applications is the exponential distribution. In this case, its density function depends on a parameter, say (the Greek letter my) and is given byIn practice it is difficult to determine what the real distribution is, however, a distribution that has proven reliable in many applications is the exponential distribution. In this case, its density function depends on a parameter, say (the Greek letter my) and is given by
s (t) = (1 / m) e - m t
in which:
m = average number of clients served per unit of time, so that:
1 / m = average time spent serving a customer
In general, the service time can follow any distribution, but before you can analyze the system, the distribution needs to be identified.
Performance measures for evaluating a queuing system
The ultimate goal of queuing theory is to answer administrative questions pertaining to the design and operation of a queuing system. A bank manager may want to decide whether to schedule three or four tellers during lunchtime. In a production structure, the manager may want to evaluate the impact of purchasing a new machine that can process products more quickly.
Any queuing system goes through two basic phases. For example, when the bank opens in the morning, there is no one in the system, so the first customer is served immediately. As more customers arrive, the queue slowly builds up and the amount of time they have to wait begins to increase. As the day progresses, the system reaches a condition where the effect of the initial customer shortage has been eliminated and the waiting time for each customer has reached fairly stable levels.
Some common performance measures
There are many different performance measures that are used to evaluate a steady-state queuing system. In designing and operating a queuing system, administrators are generally concerned with the level of service a customer receives, as well as the proper use of the company's service facilities. Some of the measures used to evaluate performance arise from asking the following questions:
Time-related, customer-focused questions such as:
- What is the average time a newcomer customer has to wait in line before being served? The associated performance measure is the average wait time, represented by Wq. What is the time a customer spends on the entire system, including waiting time and service time? The associated performance measure is the average time in the system, denoted by W
Quantitative questions related to the customer number, such as:
- On average, how many customers are waiting in line to be served? The associated performance measure is the average length of the queue, represented by Lq What is the average number of clients in the system? The associated performance measure is the average number in the system, represented by L
Probabilistic questions that involve both clients and servers, for example:
- What is the probability that a customer will have to wait to be served? The associated performance measure is the blocking probability, which is represented by, pw At any particular time, what is the probability that a server is busy? The associated performance measure is utilization, denoted by U. This measure also indicates the fraction of time that a server is busy. What is the probability that there are n clients in the system? The associated performance measure is obtained by calculating the probability Po that there are no customers in the system, the probability Pi that there is a customer in the system, and so on. This results in the state probability distribution, represented by Pn, n = 0.1 …… If the waiting space is finite,What is the probability that the queue is full and that an arriving customer is not served? The associated performance measure is the probability of denial of service, represented by Pd
Questions related to costs, such as:
- What is the cost per unit of time to operate the system? How many workstations are needed to be more cost effective?
The specific calculation of these performance measures depends on the class of queuing system. Some of these measures are interrelated. Knowing the value of a measure allows you to find the value of a related measure.
Relationships between performance measures
The calculation of many of the performance measures depends on the arrival and service processes of the specific queuing system. These processes are mathematically described by arrival and service distributions. Even without knowing the specific distribution, the relationships between some of the performance measures can be obtained for certain queuing systems, only by using the following parameters of the arrival and service processes.
l = average number of arrivals per unit of time
m = average number of clients served per unit of time in a section
Assume an infinite customer population and a limited amount of waiting space in line. The total time that a customer spends in the system is the amount of time invested in the queue plus the time during which it is attended:
Average time on system = Waiting time + Service time
Average time in the system and average wait time are represented by the quantities W and Wq, respectively. Average service time can be expressed in terms of & parameters. For example, if & is 4 clients per hour, then, on average, each client requires 1/4 to be served. In general, the service time is 1 / &, which leads us to the following relationship:
W = Wq + 1 / m
Let us now consider the relationship between the average number of clients in the system and the average time each client spends in the system. Let's imagine that a customer has just arrived and is expected to remain in the system for an average of half an hour. During this half hour, other customers keep arriving at a rate, say twelve per hour? When the customer in question leaves the system, after half an hour, he leaves behind an average of (1/2) * 12 = 6 new customers.
That is, on average, there are six clients in the system at any given time. So:
Average time of clients = Number of arrivals X * Average time in the system.
so that:
L = l * W
Using similar logic, the relationship between the average number of customers waiting in queue and the average waiting time in line is obtained:
Average customer time = Number of arrivals X Time unit in queue
so that:
Lq = l * Wq
CONCLUSION
Queue theory is the mathematical study of queues or waiting lines. Queuing is, of course, a common phenomenon that occurs whenever the effective demand for a service exceeds the effective supply.
Businesses often have to make decisions about the amount of services they should be prepared to offer. However, many times it is impossible to predict exactly when the customers who demand the service will arrive and / or how long it will take to provide that service; That is why these decisions involve dilemmas that must be solved with little information. Being prepared to offer any service that is requested of us at any time may imply maintaining idle resources and excessive costs. But, on the other hand, lacking sufficient service capacity causes excessively long queues at certain times. When customers have to wait in line to receive our services, they are paying a higher cost, on time, than they expected.Long waiting lines are therefore also expensive for the company as they cause loss of prestige and loss of customers.
The theory of queues in itself does not directly solve the problem, but it contributes with the vital information that is required to make the pertinent decisions by predicting some characteristics about the waiting line: probability of forming, average waiting time.
But if we use the concept of "internal customers" in the organization of the company, associating it with the theory of queues, we will be approaching the "just in time" business organization model in which we try to minimize the cost associated with the idleness of resources in the production chain.
BIBLIOGRAPHY
- Arbonas, ME Industrial Optimization (I): Distribution of resources. Productica Collection No. 26. Marcombo SA, 1989.Arbonas, ME Industrial Optimization (II): Resource programming. Productical Collection No. 29. Marcombo SA, 1989. Moskowitz, H. and Wright GP Operations Research. Prentice_Hall Hispanoamericana SA 1991.Buffa, E: Operations Management: Problems and Models. Revolutionary Edition, Havana, 1968.
