100 Years of Erlang Models: The Past and the FutureA Centennial CelebrationThe Erlang Centennial Conference was held in Copenhagen, Denmark from April 1st, 2009 to April 3rd, 2009. During those days, conference attendees gathered in the 500 year-old University of Copenhagen, a mere 50 meters from where the great Agner K. Erlang performed his seminal work on teletraffic models for the Copenhagen Telephone Company. For this work, Erlang is considered to be the "Father of Queueing Theory" (see several pictures of him here). This conference celebrated the 100th anniversary of the publication of his paper "The Theory of Probabilities and Telephone Conversations." This, along with Erlang's subsequent works, spawned an entire area of applied mathematics.
Although much work in queueing theory is quite analytical nowadays, Erlang himself was an engineer through and through (apparently he was not averse to crawling into manholes to obtain experimental data). He was interested in solving practical problems and most of the mathematical expositions in his papers are not completely rigorous. Furthermore, many Danes know Erlang not through his work on telephony, but for the logarithm tables he has constructed. Until the widespread use of calculators, nearly every Danish school child used his logarithm tables.
The most complete repository of information on Erlang (including all his papers, plus a bio) can be found here.
The ABC's of Teletraffic - Erlang's Formulas Live!For practitioners, Erlang's most enduring legacies are the various Erlang's formulae. Perhaps the most well-known formula is Erlang Blocking Formula, or simply the Erlang-B Formula, which gives the probability that a call is blocked in a system in which there is a fixed number of agents but no buffer for waiting calls. Click here for more details on this formula and an online calculator.
A small anecdote, to follow, indicates the pervasiveness of the Erlang-B formula. I was in a park with my kids not long ago and struck up a conversation with someone who was managing the contact center for an e-trading firm in Austin. When he heard that I was a professor in Operations Research, he said:
"Do you by any chance know the Erlang blocking formula?"
I told him I was well-acquainted with the result. He then proceeded to plumb the depths of my analytical knowledge of queueing:
"Do you know why the formula works well for us when we apply it for 30 minute intervals, but does not work well for 15 minute intervals?"
(The Erlang-B formula is usually applied to call center data by estimating parameters over fixed intervals during the day, e.g., over 30 minute intervals). Hint: the formula assumes that service center statistics do not change over time, i.e., the arrival rate is the same at any time during the day.
In any case, it is comforting to know that Erlang is alive and well, in the cubicles and parks of Austin and elsewhere.
The State of the Art in Erlang's Models - Sir John SpeaksAs for the conference, many talks were quite mathematical and somewhat removed from everyday applications. (I'll let the reader ponder the uses of the results in the lecture on "Queues with Levy processes and Hysteretic Control.") However, there were some interesting insights for model development.
The conference opened up with a talk by an academic lion of queueing research: Sir John Kingman of the University of Bristol, who was knighted in 1985 by Queen Elizabeth II. Kingman, who is now 69 years old, did seminal work during the 60's on approximations of queueing systems. His results are still widely used in manufacturing and production models (see, for example Hopp and Spearman's book Factory Physics. Kingman gave a one hour, entirely extemporaneous, talk entitled "The First Erlang Century - and the Next."
One of his primary observations is that most standard queueing models have been trapped by the assumption of simplistic assumptions on the arrivals of calls. The typical assumptions posit that the times between the arrivals to a system (calls to a customer contact center, hits to a website, packets to an Internet node) are statistically independent and identically distributed. The "identically distributed" parts hold in some regimes, but it is not reasonable when the arrival rates to a system are varying rapidly with time. Similarly, the assumption of independence does not hold good when arrivals are correlated across time, as is the case of a good portion of Internet traffic. Kingman implored the audience to further the development of models with more general assumptions on arrival processes.
Zwart's Teletraffic TourAnother excellent talk was the "Erlang's Prize lecture: An encounter with Erlang, Gauss, Poisson and Ramanujan" delivered by Bert Zwart of the Centrum Wiskunde & Informatica in the Netherlands. Dr. Zwart's talk revolved around a popular approximation to the Erlang-C formula, which gives the probability that a customer must wait on hold in a system having multiple agents and a large buffer for waiting calls. For those who are curious, yes, there is also an Erlang-A formula!
The Erlang-C formula and its approximations are embedded in algorithms which perform optimal staffing calculations for contact centers operating under QoS (Quality of Service) constraints. Dr. Zwart presented improved approximations for the waiting probability in such systems. Such approximations could be directly fed into optimization algorithms for staffing contact centers. As his lecture title implies, the formulae involve results by Erlang, Gauss, Poisson, and are also related to a nearly 100 year-old conjecture by the great Indian mathematician Ramanujan.
Other applications mentioned in the conference included controlling file-sharing processes, managing intensive care units, and estimating the structure of the Internet via probing. My own personal, highly biased opinion is that the state of the theory and application of queueing models is as strong (and necessary!) as ever even as we look into the next century.
Professor John Hasenbein John Hasenbein is an Associate Professor in the Operations Research and Industrial Engineering Group in the Department of Mechanical Engineering in the University of Texas at Austin. His specialty area is stochastic models, with a focus on queueing networks. John has worked extensively with the semiconductor industry on scheduling in wafer fabs and integrating scheduling with advanced process control. His research has been funded by the National Science Foundation, the Semiconductor Research Corporation, International Sematech, AMD, Samsung, and Harris Semiconductor. John can be contacted at jhas@mail.utexas.edu.
|
