It is not everyday that a theory is based on an activity which has been seen by many to be a vice while others cannot live without it. However, while looking at the queuing theory one would be astounded to realize that the theory is strongly backed by the probability theory in mathematics (Sharma, 2006). In turn the probability theory has its roots from gambling. As noted by Stordhall (2007), different sports and other games are connected to gambling since it has always been hard to bet on a particular outcome of a game.
Gambling problems are said to have given rise to the mathematical theory of probability. Furthermore, the mathematical theory of probability created the basis for what is today known as the queuing theory (Stordhall, 2007). The pioneers who are credited to have established the queuing or teletraffic theory more than 200 years later after the gambling theory are Agner Krarup Erlang and Tore Olaus Engset respectively.
What is the Queuing Theory?
The queuing theory is simply described as the mathematical study of queues. By using the queuing theory it is possible for various processes to be examined using mathematics. The theory is based on the following processes which include arriving and waiting at a queue, and being served at the end of it (Bhat, 2008). Through the theory, several performance measures are generated and calculated.
They include the calculation of performance measures such as average waiting time in the queue and expected number waiting or receiving service (Bhat, 2008). It also calculates the probability of getting the system in different states such as full, empty and others (Anonymous). The queuing theory has been said to be convenient when dealing with probability distributions that carry an infinite property.
The Queuing Model
The simplest forms of the models are said to be based on the birth and death process. The process of birth is said to describe the inter arrival time (Stordhall, 2007). The inter arrival time is further described as the time between two arrivals to the queue. The death process is the service time while in the line up. The property of infinity is usually indicated using the Markov process.
The Markov process is named after a famous Russian mathematician by the name of Andrej Markov. According to the Markovian process, the probability distribution of future states of the process given the present state and past states is only dependent on the present state and not on the past states (Sharma, 2006). Due to this fact the models are usually created as Poisson processes by using exponential distribution.
The Poisson process was discovered by the French mathematician Simeon Denis Poisson (1781-1840) and it is a pure birth process. The Poisson distribution is described as being a discrete form of probability distribution (Stordhall, 2007). It has also been referred to as the simplest queue system and can be easily studied mathematically. It is also simply referred to as M/M/1 queue. The Poisson distribution has been said to describe the single channel queuing theory
Source: Telektronikk pp.130: 2007
The following equation is one that is mostly used in most literature discussing the queuing theory (Sharma, 2006).
Below are diagrams showing various models that are associated with the queuing process especially in service systems (Robertazzi, 2000).Also provided are examples of where the models may be applicable;
1. Model showing a single server, single queue model
From the model we see that one service station is involved and the customer has to wait until the service point is ready to take him for servicing (Businessmanagementcourses.org, 2011). Such models are also referred to as single server models. A good example of a single server facility is that of a student arriving at a library counter (Bocharov, 2004).
2. Model showing a single server-single queue
In the above model there are several queues but one service station. Thus the customer can choose which queue to join (Businessmanagementcourses.org, 2011). A good example is the selling of theatre tickets to individuals. The people can buy the tickets from different tellers and then enter the theatre.
3. Model showing several parallel servers and a single queue
Another model involves several parallel servers and a single queue. In this model the servers are many but the customers have to wait until one of the service channels is free (Businessmanagementcourses.org, 2011). A good example is that of customers calling a customer service help desk. They have to wait until one of the lines is free for them to have access to an agent.
4. Model showing several parallel servers and a single queue
Another model is the several parallel servers single queue model which has several servers and each has its own queue (Businessmanagementcourses.org, 2011). A good example of such a system is that of individuals using different tellers in a bank.
5. Model of multiple servers in a series
Lastly there is the model that shows the service facilities in a series. Here, the customer enters the first portion of service and can move to another station and get additional service. After completing the stations the customer leaves the station (Businessmanagementcourses.org, 2011). For example a product may require processing, manufacturing and packaging all of which occur in the same place but at different times.
Individuals involved in the development of the theory
A viable Queuing theory was first developed by S.D Poisson (1781-1840) who is a French Mathematician. Poisson used statistical approach in which he made a distribution which he used to predict the probability of an outcome after repetition of independent trials (Anonymous, 2011). Due to the statistical aspect which Poisson applied in the distribution, they could be used under whichever situation especially where struggles over limited resources are experienced. This theory was extensively used in 1800s by telephone countries in deciding the number of operators to place in a call station (Anonymous, 2011). Another strategy to determining the number of operators to place in a call station was developed by A.K Erlang who is a Danish mathematician. He did this by getting ideas from the work done by Poisson (Anonymous, 2011). In his development, he come up with formulas by which abandoned and held calls can stay in the queue up to the time they are answered. The formula for abandoned calls was Erlang-B while that of held calls was Erlang-C (Anonymous, 2011). When the Poisson and the Erlang works are combined, shed some light to how the telephone companies could operate (Anonymous, 2011).
The queuing theory was developed from the teletraffic theory. Therefore, the queuing theory is credited to have come about because of the telephone (Allen, 1990). With the emergence of the telephone a system was needed to be put in place that would help in increasing the flow of traffic between telephone users. Initially it had been a one to one telephone line and the next step was the development of the manual switching system that would work toward reducing the size of the mesh network.
The international Bell Telephone Company is known to have installed several switches and access networks around Europe. However, the telephone company charged exorbitant prices for the telephone service which hindered its evolution in Europe (Daigle, 2005). The Christania Telefonforening Company was later founded in 1881 and due to its affordable pricing brought forth the expansion of the telephone industry and the network. This in turn led to an increase in the number of telephone subscriptions.
This problem was especially significant in Norway such that by 1914 very few subscribers were connected to the telephone system (Stordhall, 2007).Due to increased traffic; a lot of complaints were realized regarding the telephone system. The system could not handle the large amounts of traffic such that at times the lines became blocked (Daigle, 2005). This led to subscribers having to be withdrawn from the telephone service.
Manual switches also proved inefficient to an extent since when the number of subscribers and traffic increased, the telephone companies had to invest in more phone operators. The Spanish flu of 1918 increased the problem since individuals could not go to work (Daigle, 2005).This saw the transition from manual switching systems to automatic switching systems in 1921.
Working on the Queuing theory
Fr.Johannsen used probability to show that the manual switching systems were not dimensional. Johannsen had noted that there was an overloading of subscribers in the telephone lines which resulted in extra expenses being incurred by the company. In order to develop better dimensioning he involved a fellow mathematician Agner Krarup Erlang in his work (Stordhall, 2007). Erlang’s work on the holding times in a phone switch showed that the number of telephone conversations that satisfied a Poisson distribution and the telephone holding time were dispensed exponentially.
Engset saw the need to extend the current telephone networks in order to reduce the instances of blocking and overflow (Stordhall, 2007).Thus he developed queuing models that could be used in the proper dimensioning of manual, semi-automatic and automatic telephone exchanges. Engset calculated the probability for having i lines in an occupied exchange and having given statistical balance based on individual inter arrival times and individual holding times for each of the N subscribers in the access area (Robertazzi, 2000).The model is based on using all permutations in getting I individual subscribers out of N.
The loss probability is calculated as a function of different sizes of K.K stands for the number of lines in an exchange. This approach was found valid for subscribers in different groups having different traffic behaviour (Stordhall, 2007). Engset’s general model has been substituted with the Engset distribution as seen below:
Source: (Stordhall, 2007)
Another individual Agner Krarup Erlang also devised a model that assumed that interarrival intensity was independent of the amount of subscribers serviced during an exchange. Although both Erlang and Engset have been criticized that their work was not valid because their models never assumed long holding times distribution, the critics have been said to be wrong. To date the models have proved to be valid for various holding time distributions as long as there is a different mean.
Erlang’s famous B formula is a simple form of Engset’s distribution. The B Formula has been used by many traffic engineers and Engset’s formula was never applied (Kalashnikov, 1994). This was partly due to the fact that it generated more complex calculations since it had an additional parameter (Daigle, 2005).The achievements of Erlang and Engset in the creation of an automatic switching system have formed the backbone for many other inventions (Stordhall, 2007).Due to their work it has been possible to communicate globally and today the old telephone have been replaced with mobile phones.
Allen. A. (1990).Probability, Statistics and Queuing Theory: with computer science applications. Boston: Gulf Professional Publishing.
Anonymous. (n.d). Systems modelling and Simulation. School of mechanical, manufacturing & Medical Engineering, 9.
Anonymous. (2011). Basic System Elements. Retrieved on June 14, 2011 from http://faculty.smu.edu/nbhat/chapter1.pdf
Bhat, N. (2008). An introduction to queuing theory: modelling and analysis in applications. New York: Springer.
Bocharov, P. P. (2004). Queuing theory. Netherlands: Brill Academic Publishers.
Businessmanagementcourses.org. (2011). Queueing Theory. Retrieved May 31, 2011, from businessmanagementcourses.org: businessmanagementcourses.org/Lesson21QueuingTheory.pdf
Daigle, J. N. (2005). Queuing theory with applications to packet telecommunication. New York: Springer.
Kalashnikov.V. (1994). Mathematical methods in queuing theory. New York: Springer.
Stordahl, K. (2007). The history behind the probability theory and the queuing theory. Telektranikk, 18.
Sharma .S. (2006).Operation Research: Inventory Control and Queuing Theory. India: Discovery Publishing House.
Robertazzi, T. G. (2000). Computer networks and systems: queuing theory and performance evaluation. New York: Springer.