research on queuing model

Traffic and Granular Flow '15 pp 201–208 Cite as

How Do People Queue? A Study of Different Queuing Models

• Angelika Kneidl 3  
• Conference paper
• First Online: 11 December 2016

1659 Accesses

3 Citations

Whenever there are crowded spaces, queuing occurs. Many different situations force people to queue: Waiting for a service counter, lining up for a train or bus, queuing in front of bottlenecks or simply waiting at a supermarket checkout. Such queuing evolves in many different ways, depending on the situation, the reason for queuing, the culture, the geometry and many more. Simulation models have to cope with such different situations and behaviours. This paper gives an overview on different queuing situations and corresponding models that exist for pedestrian modelling. Additionally, it introduces a new queuing model for organised queuing without demarcation tapes. First visual validations are shown.

This is a preview of subscription content, log in via an institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

https://commons.wikimedia.org/wiki/File:Warteschlange_vor_dem_Eiffelturm.jpg .

Arita, C., Schadschneider, A.: The dynamics of waiting: the exclusive queueing process. Transp. Res. Procedia 2 , 87–95 (2014)

Article   Google Scholar  

Davidich, M., Geiss, F., Mayer, H.G., Pfaffinger, A., Royer, C.: Waiting zones for realistic modelling of pedestrian dynamics: a case study using two major German railway stations as examples. Transp. Res. Part C 37 (Complete), 210–222 (2013)

Google Scholar  

Hartmann, D.: Adaptive pedestrian dynamics based on geodesics. New J. Phys. 12 (4), 043, 032 (2010)

Hartmann, D., Mille, J., Pfaffinger, A., Royer, C.: Dynamic medium scale navigation using dynamic floor fields. In: Pedestrian and Evacuation Dynamics 2012, pp. 1237–1249. Springer (2014)

Kneidl, A., Hartmann, D., Borrmann, A.: Generation and use of sparse navigation graphs for microscopic pedestrian simulation models. Adv. Eng. Inf. 26 , 669–680 (2012)

Köster, G., Zönnchen, B.: Queuing at bottlenecks using a dynamic floor field for navigation. Transp. Res. Procedia 2 , 344–352 (2014)

Okazaki S., Matsushita, S.: A study of simulation model for pedestrian movement with evacuation and queuing. In: International Conference on Engineering for Crowd Safety, pp. 271–280 (1993)

Seitz, M., Köster, G.: Natural discretization of pedestrian movement in continuous space. Phys. Rev. E 86 (4), 046108–046116 (2012)

Seitz, M., Köster, G., Pfaffinger, A.: Pedestrian group behavior in a cellular automaton. In: Pedestrian and Evacuation Dynamics 2012, pp. 807–814. Springer (2014)

Sethian, J.A.: Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science, vol. 3. Cambridge university press (1999)

Download references

Author information

Authors and affiliations.

accu:rate, Institute for Crowd Simulation, Munich, Germany

Angelika Kneidl

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Angelika Kneidl .

Editor information

Editors and affiliations.

Transport & Planning, Delft University of Technology, Delft, The Netherlands

Victor L. Knoop

Winnie Daamen

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper.

Kneidl, A. (2016). How Do People Queue? A Study of Different Queuing Models. In: Knoop, V., Daamen, W. (eds) Traffic and Granular Flow '15. Springer, Cham. https://doi.org/10.1007/978-3-319-33482-0_26

Download citation

DOI : https://doi.org/10.1007/978-3-319-33482-0_26

Published : 11 December 2016

Publisher Name : Springer, Cham

Print ISBN : 978-3-319-33481-3

Online ISBN : 978-3-319-33482-0

eBook Packages : Mathematics and Statistics Mathematics and Statistics (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• Search Search Please fill out this field.

What Is Queuing Theory?

• How It Works

Special Considerations

• Applications

The Bottom Line

• Marketing Essentials

Queuing Theory Definition, Elements, and Example

Investopedia / Ellen Lindner

Queuing theory is a branch of mathematics that studies how lines form, how they function, and why they malfunction. Queuing theory examines every component of waiting in line, including the arrival process and the number of customers among others, which might be people, data packets, cars, or anything else.

Real-life applications of queuing theory cover a wide range of businesses. Its findings may be used to provide faster customer service, increase traffic flow, improve order shipments from a warehouse, or design data networks and call centers .

Key Takeaways

• Queuing theory is the study of the movement of people, objects, or information through a line.
• Studying congestion and its causes in a process is used to help create more efficient and cost-effective services and systems.
• Often used as an operations management tool, queuing theory can address staffing, scheduling, and customer service shortfalls.
• Some queuing is acceptable in business. If there's never a queue, it's a sign of overcapacity.
• Queuing theory aims to achieve a balance that is efficient and affordable.

How Queuing Theory Works

Queuing theory aims to design balanced systems that serve customers quickly and efficiently but do not cost too much to be sustainable. As a branch of operations research, queuing theory can help inform business decisions on how to build more efficient and cost-effective workflow systems.

The origin of queuing theory can be traced to the early 1900s in a study of the Copenhagen telephone exchange by Agner Krarup Erlang, a Danish engineer, statistician, and mathematician. His work led to the Erlang theory of efficient networks and the field of telephone network analysis.

At its most basic level, queuing theory involves the analysis of arrivals at a facility, such as a bank or a fast-food restaurant , and an analysis of the processes currently in place to serve them. The end result is a set of conclusions that aim to identify any flaws in the system and suggest how they can be ameliorated. The fundamental unit of telecommunications traffic in voice systems is called the Erlang.

Queuing theory as an operations management technique is commonly used to determine and streamline staffing needs, scheduling, and inventory in order to improve overall customer service. It is often used by Six Sigma practitioners to improve processes.

Queues are not necessarily a negative aspect of a business, as their absence suggests overcapacity.

In queuing theory, the process being studied is broken down into six distinct parameters. These include the following:

Queues can occur whenever resources are limited. Some queuing is tolerable in any business since a total absence of a queue would suggest a costly overcapacity .

The psychology of queuing is related to queuing theory. This is the component of queuing that deals with the natural irritation felt by many people who are forced to queue for service, whether they're waiting to check out at the supermarket or waiting for a website to load.

A call-back option while waiting to speak to a customer representative by phone is one example of a solution to customer impatience. A more old-fashioned example is the system used by many delis, which issues customer service numbers to allow people to track their progress to the front of the queue.

Supositorio.com offers free online queuing theory calculators with a choice of queuing models.

Applications of Queuing Theory

The queuing theory can be used and applied in a number of different situations. For instance, it can be applied to:

• Business logistics
• Banking and finance
• Telecommunications
• Project management
• Emergency services, such as fire, police, and ambulance

How it works and how involved it may be depends on the complexity of the case involved.

Example of Queuing Theory

A paper by Stanford Graduate School of Business Professor Lawrence Wein et al. used queuing theory to analyze a variety of possible emergency responses to an airborne bioterrorism attack in a public place. The model pointed to specific actions that could be taken to reduce the wait time for emergency care, thus decreasing the potential number of deaths.

Queuing theory is useful, if not quite so urgent, in guiding the logistics of many businesses. The operations department for a delivery company, for example, is likely to use queuing theory to help it smooth out the kinks in its systems for moving packages from a warehouse to a customer. In this case, the line being studied is comprised of boxes of goods waiting to be delivered to customers.

By applying queuing theory, a business can develop more efficient systems, processes, pricing mechanisms, staffing solutions, and arrival management strategies to reduce customer wait times and increase the number of customers that can be served.

How Do You Use Queuing Theory?

Queuing theory is used to identify and correct points of congestion in a process. The queue may consist of people, things, or information. In any case, they are being forced to wait for service. That is inefficient, bad for business, and annoying (when the queue consists of people). Queuing theory is used to analyze the existing process and map out alternatives with a better result.

Who Invented Queuing Theory?

Agner Krarup Erlang, a Danish mathematician, statistician, and engineer, is credited with creating not only queuing theory but the entire field of telephone traffic engineering.

In the early 20th century, Erlang was head of a technical laboratory at the Copenhagen Telephone Co. His extensive studies of wait time in automated telephone services and his proposals for more efficient networks were widely adopted by telephone companies.

What Are the Basic Elements of Queuing Theory?

A study of a line using queuing theory would break it down into six elements: the arrival process, the queue or service capacity, the number of servers available, the size of the client population, the queuing discipline (such as first-in, first-out), and the departure process. Creating a model of the entire process from start to finish allows the cause or causes of congestion to be identified and addressed.

Queuing theory is a mathematic discipline that looks at lines—specifically, how they form, how they work, and why they sometimes don't work. Queuing is an unavoidable facet of doing business, with customers apt to contend with physical or digital lines, depending on what they are trying to purchase. Queuing has an impact on manufacturing, inventory, shipping, and distribution. As a result, queuing impacts profits and revenues. Findings from queuing theory can be used to improve customer service, traffic flow, and order shipments, among other aspects of running a business.

A.K. Erlang via McGill Faculty of Medicine and Sciences. “ The Theory of Probabilities and Telephone Conversations .”  Nyt Tidsskrift for Matematik B , vol 20, 1909, p.33.

Wein Lawerence M., David Craft, and Edward Kaplan via Stanford Business School of Graduate " Emergency Response to Anthrax Attack ," National Academy of Sciences of the United States of America, vol. 100, issue 7, April 2003, Pages 4346–4351.

• Terms of Service
• Editorial Policy
• Privacy Policy
• Your Privacy Choices

• Continuing Education
• Career Center
• Career Fair
• Certified Analytics Professional
• Pro Bono Analytics
• Analytics Body of Knowledge
• INFORMS Academic Program Database
• Resources for Educators
• Resources for Government Officials
• Resources for Organizations
• Speakers Program
• Student Union
• Video Library
• Annual Meeting
• Analytics Conference
• International Conference
• Healthcare Conference
• Security Conference
• Conference Calendar
• Community Conference Calendar
• Sponsors & Exhibitors
• Past Conferences
• INFORMS Journals
• OR/MS Today
• Analytics Magazine
• OR/MS Tomorrow
• Journal Subscriptions
• INFORMS Analytics Collections
• Member Benefits
• Member Directory
• Self-Service Center
• INFORMS Strategic Plan
• Advertising & Sponsorship Opportunities
• my Communities
• History of O.R. Excellence
• O.R. Methodologies

Queueing Models

The history of the analysis of queues and waiting lines, introduction.

A leading subject of study in operations research, queueing theory is the mathematical study of queues and waiting lines. Today’s queueing theory is indebted to the emergence and growth of operations research after 1945 yet the origins of the field predate those of operations research, extending back by some measures to Siméon Denis Poisson’s 1837 work on criminal cases. A more generally accepted starting date is the early 20 th century, when university-trained Danish and Norwegian mathematicians first began using probability theory while working at telephone companies. This essay takes the latter perspective, tracing the history of queueing theory from the pioneering work of Agner Krarup Erlang, through the events of the Cold War, to the present.

Queueing theory’s greatest successes in real-world applications have been in telecommunications and data networking. While there have been vigorous attempts to adapt and extend the model to solve for a variety of queueing problems, the complexity of calculations, challenges adapting stochastic methods to various real-world queues, and the need to have useable, timely results have all limited the practical adoption of queueing theory. Despite these challenges the field has achieved a prominent place in ORMS practice today.

Queueing Theory's Origins: 1900 to 1917

The origins of modern queueing analysis lie in the growth of telephone systems in Denmark and Norway during the early 20 th century. There, telephone engineers (themselves university-trained mathematicians) used statistical techniques to estimate capacity requirements for automatic telephone exchanges. With little prior experience on which to base design choices, these engineers used mathematics, especially probabilities, as an aid to their work. The Copenhagen Telephone Company (CTC), formed in 1882, employed a thriving community of university-trained mathematicians thanks to the efforts of its chief engineer, Johan Ludwig Jensen , perhaps best known for “Jensen’s Inequality.” Jensen himself had studied physics, chemistry, and mathematics at Denmark’s College of Technology. As the president of the Danish Mathematical Society, Jensen attracted young mathematics to the CTC, among them Agner Krarup Erlang . While studying problems of estimating telephone exchange capacity requirements under Jensen’s direction, Erlang showed that inbound calls to a switch followed a Poisson distribution, and that a system of lines and calls would achieve statistical equilibrium. In 1917, Erlang published “Solution of Some Problems in the Theory of Probabilities of Significance in Automatic Telephone Exchanges,” which described three formulas used to model call activity. Two of those, the Erlang B (or “blocking” formula) and Erlang C (the “delay” or queueing formula; sometimes called Erlang D) are still in use today. Under the Erlang B regime, a customer who finds all servers (telephone lines) busy, departs never to return. Under the Erlang C regime, a customer who finds all servers busy, waits in queue until a server is available.

In neighboring Norway, Erlang’s contemporary Tore Olaus Engset also studied physics and mathematics, earning a degree in 1894 from the University of Oslo. At the state-owned Telegrafverket (today’s Telenor), Engset worked on planning for an aggressive expansion of Telegrafverket’s phone service to all Norwegians, as mandated by an 1899 national law. As part of that work he developed a blocking formula, and also addressed other concerns, including customer departures, traffic variations, traffic grading, and the finite source of the customer population. While Engset’s blocking formula found some adoption outside Telegrafverket, his other contributions (which are described in a 1915 report) did not. Other telephone engineers appear to have preferred Erlang’s simpler model and formulas to Engset’s both due to their being easier to calculate as well as the former’s tendency to give results which tended to be more conservative, that is, over-estimate switch capacity requirements.

Congestion Theory and Its Diffusion, 1917-1945

From its beginnings in Denmark and Norway queueing theory (or what was then called the study of congestion problems) spread with the growth of telephone systems in Europe, the United States, and the Soviet Union. Telephone engineers in those nations, seeking mathematical approaches to estimating phone switch capacity, translated Erlang’s articles into English, French, German, and Russian. Before English translations were available, one engineer at Bell Labs learned Danish in order to study Erlang’s work. Much of the work on congestion theory from 1917 to 1927, such as that completed by C. D. Commelin and G. F. O’Dell , centered around confirming the results of Erlang’s formulas with empirical findings. Others, including E.C. Molina and Thornton C. Fry , advocated using Erlang’s formulas - and probability theory in general - to the management of phone systems in the United States. Erlang’s formulae have long been used in setting staffing levels in in-bound telephone call centers, see for example the description by Bruce Andrews and Henry Parsons at the retailer, L. L. Bean.

Modelling work remained limited until after World War II, but there were several key contributions made during the 1930s. Conny Palm studied caller abandonment. Felix Pollaczek and Aleksandr Yakovlevich Khinchin independently arrived at formulas to calculating the mean waiting time of a queueing model with an arbitrary service time distribution (their work eventually led them to form a friendship in the years before the war). There were also some attempts to apply congestion theory to problems outside teletraffic, with T.C. Fry ’s The Theory of Probability as Applied to Problems of Congestion (1928) being one example. As tensions turned to open hostilities in Europe, however, the use of probability theory to analyze congestion problems was still limited to telephone system engineering work. The blossoming of queueing theory out of the study of congestion in telephone systems would have to wait for the events of World War II to create a fertile ground.

Operations Research and the "Golden Age" of Queueing Theory, 1945-1975

The rise of operations research during World War II marked a new phase in the history of queueing theory. A new generation of practitioners became interested in the mathematical study of queues. The formation of professional associations, conferences, and survey texts demonstrated a maturing field. The twenty-year long period of economic expansion after the war also seemed to offer numerous opportunities for operations researchers to apply queueing theory in industry, urban planning, highway construction, jet travel, and recreation. These events led some to reflect on the decade and a half after World War II as a “golden age” of queueing theory. However, this enthusiasm was tempered by the fact that, outside of communications, real-world application of queueing theory remained limited.

A key figure in the postwar era is the Oxford-trained mathematician David George Kendall . The Berlin Airlift of 1948-1949 inspired Kendall to consider how probability theory could be used to solve queueing problems. He published several papers on the topic that significantly shaped the future of queueing theory, including the “A/B/C” shorthand notation for describing queues, embedded Markov chains, and the first use of the phrase “queueing system” to describe the mathematical model. In Kendall’s A/B/C notation, the A argument identifies the arrival process, e.g., M for Markovian or exponentially distributed interarrival times. The B identifies the service distribution, e.g., M for exponential, and G for general.  The third argument denotes the number of servers. Kendall also published one of the first comprehensive bibliographies covering work on teletraffic, congestion theory, and queues. Through this bibliography-building work of Kendall and others, the new generation of operations researchers “rediscovered” the work of earlier teletraffic engineers. For example, while studying road traffic problems in the late 1950s Frank Haight came across Conny Palm’s 1937 work on queueing abandonment.

Model building took off in the decade and a half after 1945. Alan Cobham (1954) wrote one the first well known paper on priority queueing systems. Cobham was a polymath. His 1965 paper, “The intrinsic computational difficulty of functions,” was one of the first on the unrelated topic of computational complexity. A common use of priorities is to give priority to short jobs ( think express lanes in a supermarket). At heavy loads this can substantially reduce average wait time at a modest expense for long jobs. J.F.C. Kingman and Linus Schrage published work on queue service disciplines, including “First in, First Out” (FIFO) and Shortest Remaining Processing Time. Several practitioners including H. White and  L.S. Christie (1958), Avi-Itzhak and  Naor (1961), Miller and  Gaver (1962), and Kielson and  Kooharian studied server breakdown. In 1961, John D. C. Little put forward the eponymous Little’s law, which would later significantly impact operations management and computer architecture. This law states that for service systems that are, loosely speaking, stable, the average number of customers in system equals the average arrival rate times the average time in system, or in shorthand notation, N = λ *T . Lajos Takács made several contributions to time-dependent queueing processes, including queue feedbacks, priority queues, and balking. In 1956 Paul J. Burke noted that if the input to a queue is Poisson, then under certain circumstances, e.g., M/M/c, then so is the output. This observation is now called Burke’s theorem. A year later James R. Jackson , while studying ways to improve machine shop job scheduling, built on Burke’s work to develop the idea of networks of queues. This modeling work helped motivate a parallel effort to ease the increasing complexity of calculations involved. Jackson showed that there are certain classes of networks, now so-called Jackson networks, for which one can analyze each node independently to correctly compute expected wait times and other measures. Takács demonstrated the utility of combinatorics and showed how other innovations (such as Bertrand’s ballot theorem) could help solve queueing problems. A particular area of focus was in the use of transforms. In 1954, W. Lederman and G.E. Reuter , showed how spectral theory could be useful; and Norman T.J. Bailey demonstrated generating functions.

Several textbooks published during this time demonstrate a rapidly maturing field. Included among them are the first text by Philip McCord Morse (1958), and Lajos Takács (1962). In the United States, Thomas L. Saaty ’s 1961 Elements of Queueing Theory , the second English-language book on the subject, became a standard, accessible textbook used to teach queueing theory up through the early 1980s. Saaty’s book is also noteworthy for including an exhaustive bibliography.

Most queueing theory publications during this era were devoted to modeling rather than applications. In 1966, Saaty noted that “real life queues are still primitive,” an assertion which prompted U. Narayan Bhat to undertake a historical review of queueing theory literature. As Bhat concluded in his 1969 article “Sixty Years of Queueing Theory,” the complex calculations involved were a chief factor contributing to queueing theory’s limited applications. In the case of road traffic queues, stochastic methods were not easily adapted to the behavior of vehicular traffic, thus dissuading practitioners from using queueing theory over other available techniques. Clients also doubted the value of large-scale queueing theory-based systems to solve for particular challenges. The 1964-1965 New York World’s Fair Corporation, for example, rejected a proposal from Arthur D. Little, Inc. to implement a crowd control system based on a system of priority queues. At the same time, however, Fair management did solicit IBM’s Service Bureau Corporation to complete a queueing theory simulation of turnstile requirements for the Fair’s main gates. John Magee, in his oral history interview, described how queueing theory was used by the Arthur D. Little  consulting firm to help American Airlines design the first computerized on-line reservations system, SABRE. Using queueing theory, Magee and his colleagues were able to show that one expensive communication modem could serve multiple reservation agents. The catalog merchant, L.L. Bean, used the M/M/c queueing model to set customer service agent staffing levels at its inbound call center, see Andrews and Parsons.

Yet the problem of finding applied uses of queueing theory may also be one of the historical record. Many published articles, for example, were concerned with demonstrating the relevance, rather than reviewing applied examples, of particular models. 

Queueing Theory in the Soviet Union after 1945

In the Soviet Union, where operations research did not have a foothold as it did in the United States and the United Kingdom, the mathematical study of queues continued thanks to the efforts of Alexander Khinchin .  In Russia, queueing theory went by the name of the theory of mass service. Khinchin become a key force in sustaining the interest in the use of mathematics to solve queueing problems east of the Iron Curtain. He published a well-regarded, highly readable study in 1954, “Mathematical methods of theory of queues” in the proceedings of the Steklov Institute of Mathematics. This accessible work achieved widespread popularity in the Soviet Union, setting the paradigm for further developments of queueing analysis within the Soviet Block.

The 1970s Onward

Queueing theory’s history from the 1970s is one marked by shifting national priorities in the United States and the United Kingdom, which along with deregulation and the development of new markets created new opportunities for model building and real-world applications. Federal spending in the United States moved away from military to domestic initiatives, leading to a shift among practitioners studying military queueing problems to ones in urban service delivery, including fire suppression, emergency medical services, and law enforcement. New journals and professional societies forming after 1980 also show a strong, sustained interest in queueing theory. The 1990s saw further real-world applications of queueing theory outside of communications systems. Practitioners used Little’s law, for example, to help inform staffing level decisions at hospital emergency rooms, operations management, and computer architecture. Despite these achievements, however, as recently as 2009 some still lamented that outside demands reduce the quality of queueing models.

Model-building continued, albeit with some important changes. Perhaps the biggest shift was away from what had been a long-standing stochastic, top-down orientation. Gordon Newell ’s 1971 book Applications of Queueing Theory notably took this new direction to queueing theory, stressing the use of deterministic models over stochastic ones, and diffusion approximations. In 1987, Richard Larson published “Psychology of Queueing and Social Justice,” which brought attention to how the customer experiences queues as a factor in queue design and helped define a new subfield. In 1990 Larson also proposed the idea of a “Queue Inference Engine,” which helped enable bottom-up model building through the analysis of transactional data associated with a queue’s functioning.

One of queueing theory’s greatest real-world achievements began during the 1970s, when the work of Leonard Kleinrock and his students became fundamental to the design of what would become today’s data communications technologies, and the Internet. Kleinrock began working on queueing systems in 1960, building on the work of Burke and J.R.R. Jackson. Kleinrock published a two-volume collection in 1975 and 1976 and sponsored a series of lectures to disseminate the ideas presented in the two books.

Queueing theory’s institutional supports continued to grow through the twenty-five years of the twentieth century. New journals and books also helped reshape the field. 1986 saw the first issue of the journal, Queueing Systems . In 1985, Donald Gross and Carl M. Harris released a revised edition of Fundamentals of Queueing Theory , a book that has since been widely used to teach the subject (a fourth edition was published in 2008).

The year 2009 saw the publication of Optimal Design of Queueing Systems by Shaler Stidham .  In a 1964 article, Fred Hillier introduced the idea of optimization in a queueing system to choose parameters such as the best service rate (faster processors cost more money but reduce customer wait time) or arrival rate (think of an expressway on-ramp with red-green lights to limit arrival rate).  Stidham’s book surveyed subsequent research, including the use of tolls or prices in networks of queues, the distinction between individual and system optima in queues, and how tolls can be used to achieve a system optimum, as well as applications to flow control in communication networks.

Optimal control of queueing systems extends the idea of optimization to dynamically varying service rates, arrival rates, and other variables.  Research has emphasized the application of dynamic programming among other optimization methods to establish the structure of optimal control policies, e.g., admit fewer arriving customers when the queue is longer.

The first Canadian Queueing Conference, or “ CanQueue ,” was held in 1999. Innovations in calculation continued, with Marcel Neuts showing how matrix methods could solve queueing problems in 1981. In the early 2000s, Joseph Abate and Ward Whitt proposed a framework for easing calculations.

In the 2000s, the U.S. journal Operations Research and the UK’s Operations Research Society celebrated their fiftieth anniversaries. In commemoration of these events both Operations Research and The Journal of Operations Research released special issues in January 2002 and May 2009, respectively, collecting articles reflecting on the field’s history. Several contributors discussed the history of queueing theory. Shaler Stidham’s chapter in the 50th anniversary issue of Operations Research includes a comprehensive survey of work done up through the year 2000 on optimal design and control of queueing systems.

Compiled by James Skee.

Edited by Linus Schrage.

Links and References

“Agner Krarup Erlang (1878 - 1929),” +plus Magazine . https://plus.maths.org/content/agner-krarup-erlang-1878-1929

“Aleksandr Yakovlevich Khinchin,” MacTutor History of Mathematics archive, School of Mathematics and Statistics, University of St Andrews, Scotland, Created by John J O'Connor and Edmund F Robertson, http://www-history.mcs.st-andrews.ac.uk/Biographies/Khinchin.html, accessed 26 April 2019.

“An Interview with Leonard Kleinrock,” OH 190, Conducted by Judy O’Neill on 3 April 1990, Los Angeles, CA, Charles Babbage Institute, The Center for the History of Information Processing, University of Minnesota, Minneapolis, https://conservancy.umn.edu/bitstream/handle/11299/107411/oh190lk.pdf?sequence=1&isAllowed=y , Accessed 8 July 2019.

Andrews, Bruce and Henry Parsons, "Establishing Telephone-Agent Staffing Levels through Economic Optimization," Interfaces, Vol. 23, No. 2 (Mar - Apr, 1993), pp. 14-20.

Bailey, Norman T.J., “A Continuous Time Treatment of a Simple Queue Using Generating Functions,” Journal of the Royal Statistical Society. Series B (Methodological), Vol. 16, No. 2 (1954), pp. 288-291.

Basharin, G. P., K. E. Samouylov, N. V. Yarkina, and I. A. Gudkova, “A New Stage in Mathematical Teletraffic Theory,” trans from Russian, Automation and Remote Control, 2009, Vol. 70, No. 12, pp. 1954-1964.

Beneš, V.E., Review of Saaty Elements of Queueing Theory, with Applications , The Annals of Mathematical Statistics , Vol. 34, No. 4 (Dec., 1963), pp. 1610-1612.

Bhat, U. Narayan, “Sixty Years of Queueing Theory,” Management Science, Vol. 15, No. 6, Application Series (Feb., 1969), pp. B280-B294.

Bingham, N. H., “A Conversation with David Kendall,” Statistical Science, Vol. 11, No. 3, (Aug., 1996), pp. 159-188, Institute of Mathematical Statistics,

Cobham, Alan, “The Intrinsic Computational Difficulty of Functions,” in Y. Bar-Hillel, ed., Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress, North-Holland Publishing Company, Amsterdam, 1965, pp. 24-30.

Cobham, Alan, (1954) “Priority Assignment in Waiting Line Problems,” Journal of the Operations Research Society of America 2(1):70-76.

“History of Queueing Theory,” https://web2.uwindsor.ca/math/hlynka/qhist.html (accessed 8 May 2019)

“Johan Ludwig William Valdemar Jensen,” MacTutor, http://www-history.mcs.st-andrews.ac.uk/Biographies/Jensen.html .

“Lajos Takács”, https://www.informs.org/content/view/full/271236 ,

“Leo Félix Pollaczek,” MacTutor History of Mathematics archive, School of Mathematics and Statistics, University of St Andrews, Scotland, Created by John J O'Connor and Edmund F Robertson, http://www-history.mcs.st-andrews.ac.uk/Biographies/Pollaczek.html , accessed 26 April 2019.

Daganzo, Carlos F., “In Memoriam: Gordon F. Newell, 1925–2001,” Transportation Science, Vol. 35, No. 2 (May 2001), pp. iii-v

Daley, D. J. and D. Vere-Jones, “David George Kendall and Applied Probability,” Journal of Applied Probability , Vol. 45, No. 2 (Jun., 2008), pp. 293-296.

Erlang, A.K., Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges,” 1917, reprinted in Telektronikk, Volume 91 No. 2/3 - 1995, 42-49.

Grimmett, Geoffrey, “Obituary: David George Kendall, 1918-2007” Journal of the Royal Statistical Society. Series A (Statistics in Society), Vol. 172, No. 1 (Jan., 2009), pp. 275-278.

Gross, Donald, John Shortle, James Thompson, and Carl Harris, Fundamentals of Queueing Theory , 4 th ed., Wiley, 2008.

Haight, Frank A., "Queueing with Balking," Biometrika 44, 360-69 (1957); also, Rand Report P-995 (1956).

Haight, Frank A., “Two Queues in Parallel,” Biometrika , Vol. 45, No. 3/4 (Dec., 1958), pp. 401-410.

Hillier, Fred, “The application of waiting-line theory to industrial problems,” J. Industrial Engineering, Vol. 15, pp. 3-8, (1964).

INFORMS, “Leonard Kleinrock,” https://www.informs.org/Explore/History-of-O.R.-Excellence/Biographical-Profiles/Kleinrock-Leonard

Jackson, Jim, “How Networks of Queues Came About,” Operations Research, Vol. 50, No. 1, 50th Anniversary Issue (Jan. - Feb., 2002), pp. 112-113.

Jackson J. (2002) How Networks of Queues Came About. Operations Research , 50(1): 112-113. ( link )

Kendall, David G., “Some Problems in the Theory of Queues,” Journal of the Royal Statistical Society . Series B (Methodological), Vol. 13, No. 2 (1951), pp. 151-185.

Kleinrock, Leonard, “Creating a Mathematical Theory of Computer Networks,” Operations Research, Vol. 50, No.1, January–February 2002, pp. 125–131

Kleinrock, Leonard, “Time-shared Systems: A Theoretical Treatment” 1961.

Larson, Richard C., “Perspectives on Queues: Social Justice and the Psychology of Queueing.” Operations Research, Vol. 35, No. 6 (Nov. - Dec., 1987), pp. 895-905.

Larson, Richard C., “The Queue Inference Engine: Deducing Queue Statistics from Transactional Data,” Management Science, Vol. 36, No. 5 (May, 1990), pp. 586-601.

Lathrop, John B., “Reviewed Works: Elements of Queueing Theory with Applications by Thomas L. Saaty; Stochastic Service Systems by John Riordan; Introduction to the Theory of Queues by Lajos Takács; Elements of the Theory of Markov Processes and Their Applications by A. T. Bharucha-Reid,” Operations Research , Vol. 11, No. 2 (Mar. - Apr., 1963), pp. 290-293

Little, John D. C., “Little’s Law as Viewed on Its 50th Anniversary,” Operations Research, Vol. 59, No. 3, May–June 2011, pp. 536–549.

Malyshev, V. A.,  “On Mathematical Models of the Service Networks,” translated from Russian, Automation and Remote Control, 2009, Vol. 70, No. 12, pp. 1947-1953.

Miranti, Paul J. Jr., “Corporate Learning and Traffic Management at the Bell System, 1900-1929: Probability Theory and the Evolution of Organizational Capabilities,” The Business History Review, Vol. 76, No. 4 (Winter, 2002), pp. 733-765.

Myskya, Arne, “The man behind the formula - Biographical Notes on Tore Olaus Engset,” Telektronikk Vol 94 No 2 1998, 154-164.

Myskya, Arne, “A Tribute to A.K. Erlang,” Telektronikk , Volume 91 No. 2/3 - 1995, 41-49.

New York World’s Fair 1964-1965 Corporation Records, New York Public Library Special Collections.

Newell, G.F., “Memoirs on Highway Traffic Flow Theory in the 1950s,” Operations Research, Vol. 50, No.1, January–February 2002, pp.173-178.

Saaty, Thomas L., Elements of Queueing Theory, with Applications , McGraw-Hill Book Company, New York: 1961.

Shimshak, Daniel G., “Reviewed Work:  Fundamentals of Queueing Theory  by Donald Gross, Carl M. Harris,” Interfaces , Vol. 17, No. 2 (Mar. - Apr., 1987), pp. 121-122.

Simpson, N. C. and P. G. Hancock, “Fifty Years of Operational Research and Emergency Response,” The Journal of the Operational Research Society, Vol. 60, Supplement 1: Milestones in OR (May, 2009), pp. s126-s139.

Stidham, S. (2002) Analysis, Design, and Control of Queueing Systems. Operations Research (2002)  Vol, 50(1), pp. 197-216 ( link)

Stidham, S., Optimal Design of Queueing Systems , CRC Press, (2009).

Switzer, Paul, “Editor's Note Regarding the Interview with Professor David Kendall, August 1996 Issue,” Statistical Science, Vol. 12, No. 3 (Aug., 1997), p. 220, Institute of Mathematical Statistics.

Worthington, D., “Reflections on Queue Modelling from the Last 50 Years,” The Journal of the Operational Research Society , Vol. 60, Supplement 1: Milestones in OR (May, 2009), pp. s83-s92.

Wright, Sarah H., “Avenue Queue: One long wait inspired career shift,” MIT News, https://news.mit.edu/2008/eureka-larson-tt0206 , accessed 16 July 2019.

Yashkov, S. F., Foreword to the Thematical Issue “Centenary of the Queuing Theory” trans from Russian, Automation and Remote Control, 2009, Vol. 70, No. 12, pp. 1941–1946.

Associated Historic Individuals

Choose a language:

Queuing theory: definition, history & real-life applications & examples.

Queuing theory is a powerful tool to analyze the daily phenomenon of waiting in line. Discover how to define queuing theory, how it started, why it’s important, and how it can be applied to real-life situations. 

1. What is queuing theory? 2. How did queuing theory start? 3. What are the different types of queuing systems? 4. Why is queuing theory important? 5. The application of queuing theory & queuing theory examples 6. How does queue psychology impact queuing?

1. What is queuing theory?

Queuing theory refers to the mathematical study of the formation, function, and congestion of waiting lines, or queues. It’s also referred to as queueing theory, queue theory, and waiting line theory.

At its core, a queuing situation involves two parts:

• Someone or something that requests a service—usually referred to as the customer, job, or request.
• Someone or something that completes or delivers the services—usually referred to as the server.

To illustrate, let’s take two examples. First, when looking at the queuing situation at a bank, the customers are people seeking to deposit or withdraw money, and the servers are the bank tellers.

Second, when looking at the queuing situation of a printer, the customers are the requests that have been sent to the printer, and the server is the printer.

Queuing theory scrutinizes the entire system of waiting in line, including elements like the customer arrival rate, number of servers, number of customers, capacity of the waiting area, average service completion time, and queuing discipline.

Queuing discipline refers to the rules of the queue, for example whether it behaves based on a principle of first-in-first-out , last-in-first-out, prioritized, or serve-in-random-order.

2. How did queuing theory start?

Queuing theory was first introduced in the early 20 th century by Danish mathematician and engineer Agner Krarup Erlang .

Erlang worked for the Copenhagen Telephone Exchange and wanted to analyze and optimize its operations.

He sought to determine how many circuits were needed to provide an acceptable level of telephone service, for people not to be “on hold” (or in a telephone queue) for too long. He was also curious to find out how many telephone operators were needed to process a given volume of calls.

His mathematical analysis culminated in his 1920 paper “Telephone Waiting Times”, which contained some of the first queuing models and served as the foundation of applied queuing theory.

The international unit of telephone traffic is called the Erlang in his honor.

Image via Reddit

3. What are the different types of queuing systems?

Queuing theory uses the Kendall notation to classify the different types of queuing systems, or nodes. Queuing nodes are classified using the notation A/S/c/K/N/D where:

• A is the arrival process
• S is the mathematical distribution of the service time
• c is the number of servers
• K is the capacity of the queue, omitted if unlimited
• N is the number of possible customers, omitted if unlimited
• D is the queuing discipline, assumed first-in-first-out if omitted

For example, think of an ATM. It can serve:

• One customer at a time
• In a first-in-first-out order
• With a randomly-distributed arrival process and service distribution time
• Unlimited queue capacity
• Unlimited number of possible customers.

Queuing theory would describe this system as a M/M/1 queuing model (“M” here stands for Markovian , a statistical process to describe randomness).

Queuing theory calculators out there often require choosing a queuing model from the Kendall notation before calculating inputs.

4. Why is queuing theory important?

Waiting in line is a part of everyday life because as a process it has several important functions. Queues are a fair and essential way of dealing with the flow of customers when there are limited resources. Negative outcomes arise if a queue process isn’t established to deal with overcapacity.

For example, when too many visitors navigate to a website, the website will slow and crash if it doesn’t have a way to change the speed at which it processes requests or a way to queue visitors .

Related: What is an Online Queue System?

Or, imagine planes waiting for a runway to land. When there is an excess of planes, the absence of a queue would have real safety implications as planes all tried to land at the same time.

The importance of queuing theory comes from the fact that it helps describe features of queues, like average wait time, and provides the tools for optimizing queues. From a business sense, queuing theory in operation research informs the construction of efficient and cost-effective workflow systems.

5. The application of queuing theory

Queuing theory is powerful because the ubiquity of queue situations means it has countless and diverse applications.   

Queuing theory has been applied, just to name a few, to:

• Telecommunications
• Transportation
• Emergency services
• Industrial engineering
• Project management
• Operation research

Before we look at some specific applications, it’s helpful to understand Little’s Law, a formula that helps to operationalize queuing theory in many of these applications.

Do you know the 6 simple rules of queue psychology?

Little’s Law

Little’s Law connects the capacity of a queuing system, the average time spent in the system, and the average arrival rate into the system without knowing any other features of the queue. The formula is quite simple and is written as follows:

or transformed to solve for the other two variables so that:

• L is the average number of customers in the system
• λ (lambda) is the average arrival rate into the system
• W is the average amount of time spent in the system

Project management processes like Lean and Kanban wouldn’t exist without the Little’s Law queuing models. They’re critical for business applications, in which Little’s Law can be written in plain English as:

Queuing theory examples & types of queuing models

Little’s Law gives powerful insights because it lets us solve for important variables like the average wait of in a queue or the number of customers in queue simply based on two other inputs.

A line at a cafe

For example, if you’re waiting in line at a Starbucks, Little’s Law can estimate how long it would take to get your coffee.

Assume there are 15 people in line, one server, and 2 people are served per minute. To estimate this, you’d use Little’s Law in the form:

Showing that you could expect to wait 7.5 minutes for your coffee.

Image by John Yorke

A line in a virtual waiting room

At Queue-it, we show visitors their wait time in the online queue using a queuing model based on Little’s Law, adding in factors to account for no-shows and re-entries:

• L is the number of users ahead in line
• λ (lambda) is rate of redirects to the website or app, in users per minute
• N is the no-show ratio
• R is the re-entry rate to the queue
• W is the estimated wait time, in minutes

Military process optimization

We can look at a process optimization example from the military, courtesy of Process.st .

In this real-life example , the military needed to determine the ideal amount of time B-2 stealth bombers would be in maintenance. There are only 20 B-2 aircraft and they need to be ready at a moment’s notice. But they require frequent maintenance, which can range anywhere from 18 to 45 days.

Using Little’s Law helps find the balance of aircraft in use versus aircraft under maintenance.

Image by skeeze from Pixabay

Based on flight schedule analysis, it was calculated that three B-2 bombers would be under maintenance at any given time. The rate at which bombers entered maintenance was also calculated to be roughly every 7 days. So:

• L = number of items in WIP (maintenance) = 3
• A = arrival/departure rate = 1 every 7 days = 1/7 days
• W = the average amount of time spent in maintenance = ???

Put into Little’s Law, this leaves us with:

Therefore, the target lead time for B-2 bomber maintenance needed to be 21 days to meet the demands of both available aircraft and the regular flight schedules.

6. How does queue psychology impact queuing?

Queuing theory is helpful in explaining the math behind how queues run. But when queues involve humans, queue psychology is important to understand the queue experience as well.

Queue psychology research shows it’s not the length of the wait that determines how positive or negative the queue experience is, but rather how people feel while waiting.

Related: The Psychology of Queuing Revealed in 6 Simple Rules

For example, unoccupied time feels longer than occupied time. Distractions or the ability to do something else while in line makes time feel like it goes by faster. And uncertain waits feel longer than known, finite waits.

That’s why the callback option on customer service lines is so popular. You can feel the anxiety go down when you get the option to be called back in 10 minutes, freeing you to do something else instead of listening to that terrible muzak for an unknown amount of time.

For queuing situations involving people—like websites that use an online queuing system —the psychological rules governing the queues are just as important as the mathematical ones.

(This blog has been updated since it was written in 2020).

Queue Management System

Manage, serve and track your customers across multiple locations.

Service Intelligence

Track service data and measure staff performance.

Appointment Scheduling NEW

Easily receive bookings and manage changes in real-time.

Success Stories

See how other businesses in your industry are using Qminder.

List of Features

Learn about Qminder’s features and pricing options.

Qminder API

Use it to integrate with other apps such as CRMs, support software, backend systems, or patient management apps.

Watch a demo

Book a live demo

See how Qminder works while talking to one of our queue management experts.

Patient Check-in for hospitals, clinics, test centres, and more.

Visitor Management for City Halls, DMVs, courthouses, and more.

Queuing for students and student admission offices in colleges, high schools, and more.

Customer queue management for wholesale, tech shops, dispensaries, and more.

Customer queueing for banks, credit unions, and more.

Click and Collect

Remote queuing for curbside pick up, click and collect, and e-commerce businesses.

Help Center

Learn how to install, configure, and use Qminder.

Service Intelligence Podcast

Listen to our podcast and learn from some of the top customer service experts in the world.

Qminder Blog

Level up your knowledge about customer service, queue management, and more.

Qminder API Documentation

Learn how to integrate Qminder with other applications.

The Beginner’s Guide to Queuing theory

The queuing theory studies and models the inner dynamics of queues, and ways in which lines could be managed more efficiently.

It is a massive topic, which includes many different facets of the waiting experience, such as:

Waiting behavior

Queuing and servicing models

Queuing disciplines

The definition of queuing theory.

Queuing theory is the mathematical study of the formation and function of waiting lines. Queuing theory assesses the arrival process, service process, customer flow and other components of the waiting experience.

The application of queuing theory helps businesses improve the satisfaction of customers and employees, increase customer flow.

The history of queuing theory

The first paper on queuing theory was The Theory of Probabilities and Telephone Conversations by Agner Krarup Erlang, published in 1909.

Erlang worked with the Copenhagen Telephone Company and wanted to determine how many telephone circuits were necessary to prevent customers from waiting too long.

Erlang’s findings were applicable to many other fields, as telecommunications wasn’t the only industry suffering from long waiting times. This realization prompted him to develop his theory further into what later became known as the modern queuing theory.

Erlang’s role in developing the queuing theory has been recognized by naming the international unit for telephone traffic the erlang (E) in his honor.

A single cord circuit has the capacity to be used for 60 minutes in one hour. Whole 60 minutes of traffic constitute 1 erlang.

Why is queuing theory important?

Queues are a way of dealing with the imbalance between supply and demand. As long as demand (the number of customers) exceeds supply (capacity and the number of service points)

Queuing theory provides the tools and understanding for optimizing queues. As such, it has applications in many different industries, including but not limited to:

Telecommunications

Transportation

Finance and banking

Project management

No matter the industry, as long as there is some waiting involved, businesses tend to bank on queuing theory.

Especially in customer-facing industries, managing waiting lines is becoming an increasingly bigger part of the experience package.

Because although not many customers admit to it, queues are among the biggest deciding factors when it comes to satisfaction. Waiting experiences can even impact the overall impression from the interaction with a business.

Understanding the underlying mechanism of queues gives businesses the opportunity to better prepare for customers and optimize their processes.

Understanding the queuing theory

When looking at queues through the lens of the queuing theory, it’s not enough to only talk about the length of the queue.

The queuing process can be broken down into four equally vital components:

Arrival , which refers to the arrival of customers who are first in line.

Capacity , which refers to the system’s limit with regards to the number of customers in line.

Service , which refers to service points where service occurs.

Departure or output, which refers to customers leaving the system after receiving service.

In turn, all of these aspects of queuing can be further broken down into smaller segments, i.e. arrival and departure rates, average service completion times, queuing discipline, number of servers, etc.

The system has one or more servers which manage customers from their arrival to their departure. The classic example of such a design is a cashier at a supermarket.

Little’s theorem

John Little came up with a law that describes the relationship between the distribution rate of customers and time spent by them in the system.

Little’s theorem can be summarized in this short equation:

The average number of customers ( L ) is calculated from the average customer arrival rate ( λ ) multiplied by the average service time for a customer ( W ).

To understand this dynamic, consider your typical restaurant:

If the arrival rate doubles but the service time remains constant, the number of customers will rise twofold.

By the same logic, should the average service time double without the arrival rate changing, the number of customers will double, as well.

If customers arrive at the rate of 10 per hour and stay in the restaurant for an hour (1), the average numbers of customers at any time will be 10.

L = 10*1 = 10

Kendall’s notation

Queuing theory studies the behavior of single queues, also called queuing nodes. David George Kendall proposed a system for classifying these queuing nodes — the so-called Kendall’s notation .

According to Kendall’s notation, queuing nodes are described as A/S/c/K/N/D :

A for the arrival process.

S for the mathematical distribution of the service time.

c for the number of servers.

K for the capacity of the queue (if not unlimited).

N for the number of possible customers (if not infinite).

D for the queuing discipline (first-in, first-out by default).

Depending on the theoretical model used, the last three nodes can be omitted from the equation, making it a more manageable A/S/c .

Based on how each of the parameters is specified, we get different queuing models. Some of the more well-known models are M/M/1, M/M/c (also called Erlang-C model), M/G/1, M/D/1 and more.

These models deal with the mathematical theory of probability and are used to describe models of distribution in computation and logistics.

Unless you know what a Poisson process is, you shouldn’t worry about studying these models for your business.

In case you’re wondering: the M in the name refers to a Markov chain — a model describing a sequence of possible events whose probability depends on the state attained in a previous event.

In simpler terms, the future and past states of the system are independent. What happens tomorrow depends on today’s state and nothing else.

(Again, don’t bother learning that. It’s not necessary for serving customers.)

Queuing models

To determine the queuing model we’re dealing with, we need to look at two main parameters: the number of channels (or servers) and the number of phases of service . Think of channels as the number of stations where you receive service, and phases as the number of steps you need to get full service.

Each parameter can take two values: single (one), or multi (several). Different combinations of channels and phases give us four distinct types of queue management:

1. Single Channel, Single Phase

A single-channel, single-phase business has only one server. As soon as a customer is attended to, they receive full service.

Example: an automated car wash.

2. Single Channel, Multi Phase

A single-channel, multi-phase business has one server and a multi-step servicing process.

Example: retail banking, with different counters for withdrawals, deposits, new accounts, etc.

**3. Multi Channel, Single Phase **

A multi-channel, single-phase business has several servers and a one-step servicing process.

Example: airline ticket counter with separate queues for business class and economy class passengers.

4. Multi Channel, Multi Phase

A multi-channel, multi-phase business has several servers and a multi-step servicing process.

Example: a laundromat with several washers and dryers.

Read more: The Definitive Guide to Queue Management Systems

A queuing discipline refers to the method of choosing which customers to serve in which order.

First-in, first-out queuing

A FIFO queue is a queue that operates on the first-in, first-out principle, hence the name. This is also referred to as the first-come, first-serve principle.

FIFO queuing refers to a queuing discipline where customers are served in the exact order in which they arrive. The first to join the line is the first one to leave it, all other factors being equal.

FIFO queuing is the predominant method of queuing, as it promotes fairness and its rules are universally understood. You can see it almost everywhere: banks, post offices, DMVs, retail, etc.

Read more: Understanding FIFO: First-In, First-Out in Queue Management

Last-in, first-out queuing

Although the principle of last-in, first-out sounds illogical at first, there might be some power to it.

Professor Lars Peter Osterdal of the University of Southern Denmark thinks that LIFO actually has the edge over FIFO : “The problem with a regular queue where you serve first those who arrive first is that people tend to arrive too early.”

LIFO forces people to come at staggered times, resulting in shorter queues. Coming early poses more risks, which is why in Osterdal’s experiment people chose to come later and spend as little time in the queue as possible.

Since this system rewarded late-comers, it wasn’t popular with people who were more accustomed to a traditional way of queuing.

There was nothing stopping some customers from leaving the queue and rejoining it to gain advantage, which had a negative effect on people trying to play by the rules.

That’s why LIFO is usually reserved for solving transportation and logistical problems, rather than issues of customers standing in line.

Priority queuing

In priority queuing, some customers have a special status which allows them to skip the usual means of queuing.

This type of queuing is most commonly seen in industries where there can be emergency cases — for example, healthcare. A patient with a severe case is naturally treated ahead of everyone else.

In non-healthcare industries, this type of queuing is usually called VIP queuing. For instance, business class passengers board the airplane before others.

The same goes for clubs, restaurants and similar venues.

The drawback of this system is that it may appear unfair unless it was clearly communicated in advance. After all, getting jumped ahead of you sounds infuriating if you weren’t aware that the business had priority queuing in place.

Queuing psychology and its impact on queuing theory

One of the problems of any theoretical model that tries to describe human behavior is that actions can appear illogical.

Queuing theory is helpful when it comes to explaining the benefits of a certain queuing flow, but it does ignore another important aspect of queuing: how customers feel while waiting.

Thankfully, there has been scientific research done in this area, as well. Queuing experts have determined that:

Unoccupied time feels longer than occupied time.

Unexplained waits are perceived as longer than they really are.

Unfairness of the queue, be it real or perceived, impacts how customers feel.

To learn more about queuing behavior, its application and benefits to your business, refer to our guide to wait time psychology .

Try Qminder for free

Sign up for a 14-day free trial. No credit card required.

I have read and agree to the privacy policy of Qminder

Why You Should Listen to Your Customers (And Why You Shouldn’t)

Introducing qminder's new and improved service view.

Talk to our experts

1800-120-456-456

• Queuing Theory

What is Queuing Theory?

The study of all the varied dynamics of lines or queues, as well as how they might be altered to run more efficiently, is the focus of queueing theory. Queuing theory is an area of mathematics that analyses and models the act of queueing. It is essentially the study of how people act when they have to wait in line to make a purchase or receive a service, as well as what sorts of queue structure move people through lines the most efficiently, and how many people can a specific queuing arrangement process through the line in a particular time frame.

The queuing models have two aspects at its core.

The customer, job, or request are all terms used to describe someone or something who demands a service.

The server refers to the person or thing that completes or provides the services.

Let's look at queuing theory in operation research examples. 

Consumers trying to deposit or withdraw money are the customers, and bank tellers are the servers in a bank queuing situation. The customers in a printer's queue scenario are the requests that have been made to the printer, and the server is the printer.

Queuing theory in operation research examines the entire system of standing in line, including factors such as customer arrival rate, number of servers, number of customers, waiting room capacity, average service completion time, and queuing discipline. The rules of the queue, such as whether it operates on a first-in-first-out, last-in-first-out, prioritised, or serve-in-random-order basis, are referred to as queuing discipline.

[Image will be uploaded soon]

History of Queuing Theory

Agner Krarup Erlang, a Danish mathematician and engineer, was the first to establish queueing theory in the early twentieth century.

Erlang was employed by the Copenhagen Telephone Exchange, and he intended to examine and improve the company's processes. He wanted to know how many circuits were required to offer an acceptable level of telephone service, with people not having to wait too long on hold or in a phone queue. He also wanted to know how many telephone operators were required to handle a certain volume of calls.

His mathematical research culminated in the paper Telephone Waiting Times, published in 1920, which became the foundation for the applied queuing theory. In his honour, the Erlang is the international telephone traffic unit.

Basics of Probability and Queuing theory

Queuing theory is primarily a tool for calculating costs. Most firms would find it excessively expensive, or symptomatic of a lack of customers, to run in such a way that none of their customers or clients ever had to wait in line.

To give a simple example, a movie theatre would need to add fifty to one hundred ticket booths to avoid the situation of people needing to wait in line to purchase a movie ticket. The theatre, on the other hand, could clearly not afford to compensate a hundred ticket salespeople.

As a result, businesses employ queuing theory information to set up their operational operations in order to strike a balance between the cost of supplying clients and the difficulty caused by having to wait in line.

The individuals in line and the performance of the service they are waiting for are the fundamentals of queuing models.

Queuing theory problems are commonly divided into four groups in studies on the subject:

Arrival: The procedure for getting customers to the front of the line or a queue.

Queue: That is, the character or operation of the queue itself. How does the line advance?

Service: The process of providing a customer with the service they have requested. For example, when being seated and then served in a restaurant, the restaurant must consider the dynamics of two independent queues: the line of people waiting to be seated and the line of people who have already been seated and are waiting to be served. The latter can be divided into two lines: the line to have your order taken and the line to have your food delivered to your table.

Leaving: The act of departing from a queue position. Businesses that provide a drive-through service, for example, must consider how customers exiting the drive-through may affect customers entering the parking lot.

Now let us discuss in details the four groups of queuing theory in operation research.

Arrival 

The average number of individuals who arrive during a specific time frame, such as one hour, is one factor to consider when it comes to the arrival of individuals at the queuing location.

Significant variations in the volume of traffic or arrivals that occur at different times of the day, or on different days of the week or month, are a related factor.

For example, grocery stores know that on Friday mornings between 10 a.m. and noon, they require more personnel than on Wednesday mornings between 10 a.m. and noon to avoid queues getting backed up.

How does the line progress? Is it better for a bank to have a single line of customers waiting for the next available teller or cashier, or is it better to have distinct queues for each teller? When presenting such a question, human behaviour characteristics become an integral aspect of queuing theory. 

While feeding one line of clients to four different teller stations rather than four separate lines at each teller station may not have a substantial impact on the speed or efficiency with which customers are served, it may have a major impact on customer satisfaction.

While ultimately, regardless of the line arrangement, the wait time to be served can be approximately the same, customers may feel or perceive that they are served more quickly if only two or three people waiting in line behind each distributor station having their own queue rather than having to stand behind 10 or 12 individuals where one customer line is fed into all four teller stations.

There are also some basic considerations to make: Will using only one line result in a line that stretches all the way out the door if the business office is small? Many individuals may be put off from conducting business there if they witness a situation like that. They might instead go to a competitor who appears to have a shorter wait time.

In reality, doing business with a competitor may entail roughly the same amount of time spent in line. The only difference could be that the competition picked distinct lines for each service station rather than a single line for all of them, avoiding a wait that stretches all the way out the door. You can see that, in addition to any operational efficiency concerns, queue aesthetics must be considered.

Variables exist in regard to the actual providing of service as well. 

The express lane in grocery shops, which is allocated for people buying a modest number of items, is a good example. Customers satisfaction is improved by allowing customers who are only buying a few items to check out more quickly, rather than having to wait in line behind other customers with full carts of food, according to grocery businesses that use queuing theory.

The average time it takes to serve each customer or client, the number of servers required for maximum operational and cost-effectiveness, and the rules dictating the order in which clients are served are all elements that have an impact on actually providing service. While most queues work on a first-come, first-served basis, this isn't always the best option for some firms.

A classic example is the emergency room waiting area at a hospital. Patients are served according to the severity of their illness or damage, rather than on a first-come, first-served basis. It demands the addition of a service step called triage, in which a nurse assesses each patient's emergency severity to determine where that patient should be placed in the service line.

Basic logistical issues are frequently related to clients leaving a queue area.

Businesses having drive-through operations, for example, must consider how customers exiting the drive-through may affect incoming traffic to the facility, as mentioned above.

Another departure-related factor is a restaurant's decision on whether to have servers present bills and collect payment at a customer's table or have customers pay their bill to a cashier as they leave.

Importance of Queuing Theory

Waiting in line is a common occurrence in everyday life because it serves various key functions as a process. When there are limited resources, queues are a fair and necessary manner of dealing with the flow of clients. If there isn't a queuing process in place to deal with overcapacity, bad things happen.

For example, if a website has too many visitors, it will slow down and fail if it does not include a mechanism to adjust the speed at which requests are processed or a mechanism to queue visitors. Consider planes waiting to land on a runway. When there are too many planes to land at once, the lack of a queue has actual safety issues when jets try to land at the same time.

Queuing theory is significant because it helps to describe queue characteristics such as average wait time and gives tools for queue optimization. 

Queuing theory influences the design of efficient and cost-effective workflow systems from a commercial standpoint.

Applications of Queuing Theory

Queuing theory finds its application in various sectors. Few are listed below:

Telecommunications

Transportation

Emergency services

Industrial engineering

Project management

Little’s Law

Little's law developed by John Little asserts that the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system in queueing theory. Little’s law is a topic within the mathematical probability and queuing theory.

L is the average number of customers in the system.

λ is the average arrival rate into the system.

W is the average amount of time spent in the system.

Although it appears to be a simple result, it is rather surprising because the link is unaffected by the arrival process distribution, service distribution, service order, or virtually everything else.

Little's law holds true for every system, but it is especially true for systems inside systems. So, in a bank, the client queue could be one subsystem, and each of the tellers could be another, and Little's result could be applied to both. The sole requirements are for the system to be stable and non-preemptive; this eliminates transition states like initial setup and shutdown.

In some circumstances, not only can the average number in the system be mathematically related to the average wait, but the complete probability distribution of the number in the system can also be mathematically related to the wait.

Queuing models can assist explain the math behind how queues work. When it comes to human lineups, however, queue psychology is crucial to comprehend the experience. According to queue psychology studies, it's not how long individuals wait that affects whether they have a great or negative line experience, but how they feel while waiting. Little's Law is useful because it allows us to solve important variables such as the average wait time in a queue or the number of customers in a queue using only two other inputs.

FAQs on Queuing Theory

1. What is Queuing Theory?

Ans: The mathematical study of waiting lines, or queues, is known as queueing theory. A queueing model is created in order to anticipate queue lengths and waiting times. Because the results are frequently employed for making business choices regarding the resources needed to offer a service, queuing theory is widely considered a branch of operations research.

2. What are the Four Groups of Queuing Theory?

Ans: The four groups of queuing models are:

3. What is Little’s Law and Its Importance in Probability And Queuing Theory?

Ans: Without knowing any other properties of the line, Little's Law relates the capacity of a queuing system, the average time spent in the system, and the average arrival rate into the system. Without Little's Law, project management techniques like Lean and Kanban would not exist. Little's Law is useful because it allows us to solve for crucial variables such as the average wait time in a queue or the number of consumers in a queue using only two additional inputs.

An official website of the United States government

The .gov means it’s official. Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

The site is secure. The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

• Publications
• Account settings

Preview improvements coming to the PMC website in October 2024. Learn More or Try it out now .

• Advanced Search
• Journal List
• J Healthc Eng
• v.2020; 2020

This article has been retracted.

Optimization of markov queuing model in hospital bed resource allocation.

1 The Affiliated Changshu Hospital of Soochow University, Changshu, Jiangsu 215500, China

Jianqiang Wang

Xiaodong peng.

2 The Office of Medical and Health Association, Changshu, Jiangsu 215500, China

Associated Data

The labeled dataset used to support the findings of this study are available from the corresponding author upon request.

Bed resources are the platform in which most medical and health resources in the hospital play a role and carry the core functions of the health service system. How to improve the efficiency of the use of bed resources through scientific management measures and methods and ultimately achieve the optimization of overall health resources is the focus of hospital management teams. This paper analyzes the previous research models of knowledge related to queuing theory in medical services. From the perspective of the hospital and the patient, several indicators such as the average total number of people, the utilization rate of bed resources, the patient stop rate, and the patient average waiting time are defined to measure the performance of the triage queue calling model, which makes the patient queue more reasonable. According to the actual task requirements of a hospital, a Markov queuing strategy based on Markov service is proposed. A mathematical queuing model is constructed, and the process of solving steady-state probability based on Markov theory is analyzed. Through the comparative analysis of simulation experiments, the advantages and disadvantages of the service Markov queuing model and the applicable scope are obtained. Based on the theory of the queuing method, a queuing network model of bed resource allocation is established in principle. Experimental results show that the queuing strategy of bed resource allocation based on Markov optimization effectively improves resource utilization and patient satisfaction and can well meet the individual needs of different patients. It does not only provide specific optimization measures for the object of empirical research but also provides a reference for the development of hospital bed resource allocation in theory.

1. Introduction

Health resources, as a major component of the provision of medical services, are extremely limited. How to rationally allocate and efficiently use health resources has become an urgent problem in the field of hospital management. Beds are one of the important resources for in-hospital emergency integration. Considering that other conditions will also affect indicators, such as staffing or bed allocation, we assume that these conditions are the same. If a hospital increases beds, it will increase investment of idle waste; on the contrary, if we reduce beds, the waiting time will be too long, and the patient satisfaction will decline. With the continuous deepening of medical reform, the competition between hospitals becomes more and more fierce. Hospital managers must consider how to strike a balance between the two in order to improve service quality, maximize returns, maintain a competitive advantage, and take into account social benefits [ 1 – 3 ].

With the continuous advancement and implementation of healthcare reform, scientifically and reasonably shortening the average hospitalization day, optimizing bed utilization has become a core issue that hospital management is paying close attention to. In the current medical environment, major domestic hospitals are exploring management models suitable for their own development, including refined management, target management, clinical path management, day wards, medical prepayment systems, and pay-by-case systems [ 4 – 6 ]. Relevant scholars have explored the use of their beds, mainly using prospective cohort studies [ 7 , 8 ]. The conclusions show that the regularity and uninterruptedness of patient consultations, physician transfers, and discharges of physician consultations can be maintained from Monday to Sunday, which can effectively improve bed utilization. The researchers elaborated on three aspects of patient waiting time and service utilization analysis, system design, and appointment system [ 9 ]. They summarized the research of different scholars on the queuing theory applied to the medical system and applied the research results to personal clinics, medical facilities, and regional medical systems. Relevant scholars use a hospital as an example to classify patients into critically ill patients, general patients, and patients without appointments [ 10 – 12 ]. They combined the knowledge of queuing theory to simulate the patient flow in the emergency room and analyzed the specific situation of the hospital. When evaluating bed utilization in US hospitals, researchers built a simulation model with Simscript 11.5, which takes into account a series of indicators such as patient diagnosis, admission classification, length of stay, type of bed, and gender [ 13 , 14 ]. The macroinfluencing factors of bed utilization are mainly related to the hospital or the country's policies [ 15 ]. At the microscale, they involve how the beds are configured, how the patients are placed, and how patients are admitted to the hospital. Relevant scholars have investigated and evaluated bed utilization efficiency in a certain area in Canada [ 16 , 17 ]. The study found that, of the 2007 patient study subjects, 14.2% of patients did not meet the admission criteria, and the total length of hospital stay was 14,194 days, of which 22.8% were unreasonable. The study evaluated the unreasonable length of hospital stay and found that 49.2% of the unreasonable time was related to the doctor's job [ 18 ]. Although the average length of stay in the region decreased from 5.7 days to 5.39 days in 4 years, the average length of stay in 10.5% of hospitals still exceeded national standards [ 19 – 21 ]. This study shows that improper use of beds can lead to inefficient hospital operations or reduced alternative services. Some scholars believe that the hospital bed size is a nonlinear structure, and its management assessment is affected by uncertain environmental changes [ 22 , 23 ]. At present, the calculation of bed size is a simple and modeled calculation method [ 24 ].

In theory, the common queuing problem in hospitals has always been a hotspot for domestic and foreign experts and scholars. Queue theory and corresponding improved model have been widely used to solve this problem. This study enriches the theoretical optimization of queuing problems in hospital management and provides an analysis and decision-making method for improving the queuing theory of hospitals and improving the efficiency of medical services. Specifically, the technical contributions of this paper are summarized as follows.

First, from the perspective of the hospital and the patient, several indicators such as the average total number of people, the utilization rate of bed resources, the patient's stopping rate, and the patient's waiting time are defined to measure the advantages and disadvantages of the triage queue calling model so that the queue is more reasonable. According to the actual task requirements of a hospital, a Markov queuing strategy based on Markov service is proposed, a mathematical queuing model is constructed, and simulation experiments are performed on the queuing model. Through experimental comparison and analysis, the advantages and disadvantages and applicable scope of the service Markov queuing model in this paper are obtained.

Second, this paper carried out a simulation experiment of 132 units of time on the simulation system and obtained the simulation results. The dynamic queue time and queue length obtained by simulating the queuing generated when matching the experts in each department and the queuing generated in each clinic are analyzed to find the congestion point of the queuing network system. After the parameter setting of the congestion point is improved, the result is compared with the original parameter state.

The rest of this paper is arranged as follows. Section 2 discusses related theories and methods. In Section 3 , Markov's hospital bed queuing strategy is studied. Section 4 gives the simulation results and analysis. Finally, Section 5 summarizes the full text.

2. Related Theories and Methods

2.1. refined management theory of hospital bed resources.

Refined management is not only an important way for hospitals to carry out ordinary management activities but also an important foundation for improving the overall management level of hospitals. The implementation of this management form in hospitals can significantly optimize hospital service procedures and improve service levels and patient satisfaction, which is of great significance to hospital development.

The refined management of hospital human resources is a management activity that takes full advantage of human resources in order to better complete the various tasks of the hospital. As a reasonable development and allocation of human resources, fine management effectively uses the combination of scientific management system, laws, and methods and refines classification management, level correspondence, and organizational structure.

Refined management includes outpatient emergency management, first-aid management, and discharge management within the medical procedures. It rationally connects the management of the above links. At the same time, it promotes the management of hospital departments and considers the patient as the center based on medical safety. It focuses on the key points, strengthens management, and improves the efficiency of service process operations. The system architecture of the hospital information platform is shown in Figure 1 .

The system architecture of the hospital information platform.

2.2. Features of the Queuing System

The following six basic characteristics are usually used to describe the queuing system:

• Patient arrival mode
• The time interval for patients to arrive in the queuing system is deterministic or random. Most patients in the hospital queuing system arrive randomly. Common input processes include Poisson input, fixed-length input, and Erlang input. Among them, Poisson input is most widely used in queuing systems. If the patient arrival interval follows a negative exponential distribution, then the number of patients who arrive within a certain time interval obeys the Poisson distribution. At this time, the arrival rule of the patients arriving in the system is called Poisson arrival. This situation is also the focus of queue theory.
• Service model
• Patient service hours are deterministic or random, and most service hours are random. The time rule of patients receiving services is often described by probability distribution. Generally, the probability distributions of random service hours are fixed-length distribution, negative exponential distribution, Erlang distribution, and so on. The service time of the queuing system usually follows a negative exponential distribution; that is, the time for each patient to receive the service is independently and identically distributed, and its distribution function is
•   where u  > 0 is a constant, representative of the average service rate per unit time, and 1/ u is the average service time. Service methods are divided into single or batch.
• (3) Queuing rules
•   The most common queuing rules are first-come-first-served services, such as medical appointments and queuing for medication. Under the first-come-first-served service rule, patients receive services in the order of arrival. General service systems use this queuing rule. Other queuing rules include first-come-first-served, nonpreemptive priority, and preemptive priority. First-come-first-served services include hospitals for emergency patients. Preemptive priority means that when a patient with higher priority arrives at the system, the patient who is receiving the service must stop the service and be replaced to serve such patients, like the hospital emergency room for critically ill patients. Nonpreemptive priority means that when a higher priority patient arrives at the service system, the patient who is receiving the service must wait for the service to be completed before receiving the service, such as a care number.
• (4) Serviceability
•   Generally, the queuing system has a queuing upper limit. When the queuing upper limit is exceeded, the patients who arrive will be rejected, which is a loss system. There is no upper limit for waiting. The hybrid system is a queuing service rule that combines the loss system and the waiting system. There are both waiting and loss situations. For example, the patient decides to stay in consideration of the length of the queue and the length of the waiting time. There are two main types of mixed systems. One is the limitation of the length of the team; that is, when the number of patients waiting in line for service exceeds the prescribed number, the subsequent patients automatically leave. The second is the limited waiting time; that is, when patients wait in line for more than a certain time, they will automatically leave.
• (5) Number of bed resources
•   The main attribute of the service window is the number of bed resources, and its type is a single bed resource or multiple bed resources. If it is a multibed resource system, it can be divided into three types: parallel system, series system, and hybrid type. The most basic type is the parallel multibed resource. There are many queuing situations in the hospital's queuing network.
• (6) Service stage

Schematic diagram of the hospital triage system.

2.3. Markov Model Analysis

According to the characteristics of the probability distribution, from one state to another state in the Markov chain, it can also maintain the current state. The random change between states is called transition, and the probability of changing between different states is called transition probability. The Markov chains X 1 , X 2 , X 3 ,… describe a state time series, where each state value is related to a limited number of states before the current state. The Markov chain reflects a series of variables with Markov properties. The set of all possible values is the range of the variable, which is the state space, and the value of X n represents the state at time n .

A Markov chain can be represented by a probability distribution. The probability distribution P ( X n +1 = X n ) is called the “one-step transition probability” in a random process. The multistep transition probability can be derived from the one-step transition probability; that is,

Markov process is a typical stochastic process, which is applicable to both interval and time series. This theory is mainly to study the state and transition of sequences. Markov model is a prediction method that performs random analysis on time series. The Markov model is a prediction method that predicts whether an object may be in a certain state in the future according to the initial probability of different objects in different states and the transition probability between different states.

3. Hospital Bed Queuing Strategy Based on Markov

3.1. steps to build a system transition probability matrix.

For multidimensional state space, it will be more complicated if you use manual calculation. The classic matrix geometry algorithm is more suitable for solving two-dimensional state space. For 3D state space, other methods need to be found for solving. In this paper, a computer-based method is used to solve the transition probability matrix of a multidimensional Markov chain. The steps are as follows.

•   Step 1 . We sort all the multidimensional state spaces with a dictionary sorting method and study the form of the state.
•   Step 2 . We define a functioning state ( p ) to describe the p th element in the sorted state space. In the proposed Markov model, the way the state is formed is very important; it has a great influence on the constructor state ( p ). Different formation methods will produce different functions. However, we find that, in most multidimensional Markov models, the state space is formed layer by layer. Therefore, state ( p ) will be constructed in the following way.
•   Step 3 . We construct the transition probability function transition ( n , A ) between states A and B . Because the transition situation designed in this paper is more complicated, the transition probability should be determined according to the specific problem.
•   Step 4 . We obtain the state transition matrix Q according to the transition probability between states.

3.2. Experimental Design

3.2.1. definition and solution of the queuing model.

Assume that there are two bed resources S 1 and S 2 in the system, where S 1 serves C1 patients, the patients arrive at λ 1 , the service rate is u 1, and the formed team length is n 1 ; S 2 serves C 2 patients, the patients arrive at λ 2 , the service rate is u 2, and the length of the formed team is n 2 , of which λ 1 > λ 2 . When n 1  =  F 1 , C 1 patients leave the queuing system; when n 2  =  F 2 , C 2 patients leave the queuing system, where F 1  >  F 2 .

(1) State Space . We define n 1 ( t ) as the total queue length of S 1 bed resources and n 2 ( t ) as the total queue length of S 2 bed resources, and then each instantaneous state space can be expressed as

where n 1 ( t ) represents the total queue length of bed resource S 1 at time t and n 2 ( t ) represents the total queue length of bed resource S 2 at time t .

(2) Transfer Process . The transition relationship between all states in the state space obeys the continuous Markov process. Predecessors have studied the laws that such a transition process meets. The birth and death process of the system is given in the following. According to Markov theory, the system transition probability is

According to the transition probability between states, a state transition matrix Q is obtained.

3.2.2. Performance of the Queuing Model

Using steady-state probability and transition probability matrix, we can obtain the following performance characteristics.

(1) The Average Total Number of People in the System . When the system is in a steady state, the total number of people in each state in the state space is multiplied by the steady-state probability of the state, and the summed value is the average total number of people in the system:

(2) The Average Number of People Waiting in the System . When the system is in a steady state, the value of the waiting number can be computed using the total number of people minus the number of patients receiving services, and the value multiplied by the steady-state probability is the system's average waiting number.

(3) Resource Utilization Rate of Each Bed . According to the definition of steady-state probability, that is, the probability that the system is in various states after an infinite time tends to stabilize, this probability also includes the meaning of the time component in each state. Therefore, the probability that each bed resource is busy during steady state is equal to their respective utilization rates. Therefore, the utilization rate of each bed resource can be obtained as follows.

The utilization rate of bed resource is S 1, that is, the probability that S 1 is in a busy period when S 1 reaches steady state. The probability when there is always a patient in cohort n 1 is

The utilization rate of bed resource is S 2, that is, the probability that S 2 will be busy when S 2 reaches steady state. The probability that patients in the n 2 cohort will always exist is

(4) Patient Waiting Time in the System . Patient waiting time is the average time that all patients wait for service in the system under steady-state conditions. When the system is in a steady state, the waiting time for a patient is the number of all patients in front of it multiplied by the time required for a single patient to receive service. Among them, the time required for a single patient to receive service is 1/ u . If there is only one patient receiving service in a certain state, the waiting time is 1/ u . If there are i patients before, the waiting time is ( i  − 1)/ u . Then the waiting time in each state is multiplied by its steady-state probability and summed, which is the average waiting time of the patient in the system.

The waiting time for the C 1 patient in the system is

The waiting time for C 2 patients in the system is

The total patient waiting time in the system is the average of the waiting time of the C 1 patient in the system and the waiting time of the C 2 patient in the system, as shown in the following formula:

3.3. Results Analysis

3.3.1. average total number of people.

From Table 1 , it can be seen that the total number of people in both queuing systems increases with the increase of F 1 . This shows that the higher the tolerance of C 1 patients, the more crowded the system, and the more waiting people in the system measure the advantages and disadvantages. At the same time, it can be seen in the table that the change gradually slows down, indicating that the increase in the number of people tends to moderate with the increase of F 1 . This shows that the system itself is buffered against tolerance changes. At the same time, the number of people that the system can accept is also limited. When the patient's impatience reaches a certain level, the number of people in the system will reach the limit and no longer increase.

Change of the average patient number of the system with F 1 .

In addition, it can be seen from the table that the number of waiting people in the queuing system using the sharing strategy is smaller than that in the queuing system that does not adopt this strategy, and the difference between the two becomes larger and larger as F 1 increases. This is because when the tolerance limit of C 1 patients becomes larger, more patients will enter the S 1 system and wait for services. The queuing system using the sharing strategy can effectively divert C 1 patients who are waiting to receive services. Some C 1 patients can enter the S 2 bed resource to receive services and leave the system. Therefore, the waiting number of the queuing systems using the sharing strategy is smaller than that of the ordinary system. At the same time, as the patient's tolerance changes, F 1 increases, which will cause more C 1 patients to enter the system to wait for services, and the waiting number of nonshared systems will continue to rise. After adopting the sharing strategy, because the arrival rate of C 2 patients is relatively low, more C 1 patients can use the S 2 bed resources to complete the service and leave the system. Therefore, as F 1 increases, the gap between the two systems continues to grow.

3.3.2. Bed Resource Utilization

Comparing the utilization of S 1 bed resources, it can be seen from Table 2 that, for S 1 bed resources, the utilization rate of the system using the sharing strategy is lower than that of the system not using the sharing system. This is because, after adopting the sharing strategy, some C 1 patients will enter the S 2 bed resources to receive services, thus resulting in lower utilization of the S 1 bed resources.

Change of resource utilization of S 1 beds with F 1 .

For comparison of S 2 bed resource utilization, from the analysis of S 1 bed resource utilization analysis, it can be concluded that, after the sharing strategy is adopted, some C 1 patients enter S 2 bed resources to receive services, which will inevitably lead to the improvement of S 2 bed resource utilization. As shown in Table 3 , it can be seen from the table that the utilization of S 2 bed resources has improved significantly.

Change of resource utilization of S 2 beds with F 1 .

3.3.3. Probability of Patient Stopping

Table 4 shows the change of the stopping probability of different patients in the two-system model to the tolerance limit of C 1 patients. It can be seen in the table that the increase of the tolerance limit of C 1 patients is very effective in reducing the probability of stopping. As the patient's tolerance limit increases, the probability of stopping is greatly reduced. From the perspective of system analysis, the stopping probability of C 1 patients in the sharing system is significantly lower than that of the ordinary model. This is because the sharing strategy has a significant shunt effect on C 1 patients, which makes more patients enter the system to receive services. But the stopping probability of C 2 patients is not sensitive to changes in the tolerance limit of C 1 patients. The reason is that, in the general model, C 1 patients do not have any effect on C 2 patients, so the stopping probability of C 2 patients does not change. However, in the sharing system, because C 1 patients will enter the S 2 cohort to receive services, affecting some C 2 patients, they will not be able to enter the system to receive services, resulting in a higher probability of stopping. Therefore, we can see that the stopping probability of C 2 patients in the sharing system is higher than that of the ordinary system. But its own changes are not sensitive to the tolerance limit of C 1 patients.

Variation of patient's stopping probability with F 1 .

3.3.4. Patient Waiting Time

Table 5 shows the comparison of waiting time for C 1 patients in the two queuing system models. It can be clearly seen from the table that, as the tolerance limit of C 1 patients increases, their waiting time also shows an upward trend. However, in the system without the sharing strategy, the waiting time of C 1 patients increased faster and significantly higher than the system with the sharing strategy, while the waiting time of the sharing strategy system did not change much and was at a low level. This is because in the ordinary system, as the tolerance endurance of C 1 patients increases, more and more C 1 patients enter the S 1 queue waiting to receive services, so their waiting time continues to increase. After adopting the sharing strategy, because some C 1 patients entering the S 1 queue can be transferred to the S 2 queue to receive services, there is no need to wait too long to get services to leave the system. Therefore, the waiting time of C 1 patients in the sharing system is lower than that of the ordinary system, and it can be seen that the sharing strategy has a significant effect on reducing the waiting time of C 1 patients.

C 1 patient waiting time as a function of F 1 .

Table 6 shows a comparison of waiting times for C 2 patients. First, it can be seen from the table that the waiting time of C 2 patients in both systems is relatively stable, indicating that the tolerance limit of C 1 patients has little effect on the waiting time of C 2 patients. The waiting time in the system model using the sharing strategy is higher than the ordinary model without this strategy. This is because some C 1 patients enter the S 2 cohort to receive services in the system model of the sharing strategy, thus increasing the waiting time of some C 2 patients. Judging from the waiting time of C 2 patients alone, the split strategy system model has no advantage. But because the queuing system designed in this paper contains two bed resources and has two queues and two types of patients, it is necessary to consider the advantages and disadvantages of this queuing strategy from the perspective of the system as a whole.

C 2 patient waiting time as a function of F 1 .

Table 7 shows the overall patient waiting time in both types of systems. The total patient waiting time is the sum of the waiting time of the C 1 patient and the waiting time of the C 2 patient in the system. It can be seen from the table that the overall waiting time of patients in the common model without the sharing strategy is higher than that of the system model with the sharing strategy. And with the increase of the tolerance limit of C 1 patients, the waiting time of patients under the common system model also increases rapidly, and the gap between the system models after adopting the sharing strategy is increasing. Therefore, from the perspective of the overall waiting time of patients in the system, the queuing system model using the sharing strategy is better than the ordinary model, and the greater the tolerance limit of C 1 patients, the more obvious the effect.

Patient overall waiting time with F 1 .

4. Simulation Results and Analysis

4.1. queuing system optimization.

The purpose of establishing a queuing model is to obtain the optimal parameter combination by changing the service parameters and measuring the service cost and the waiting cost in order to obtain the length and duration of the queuing team under the steady state of the system. In the bed resource allocation queuing system in this paper, the purpose of optimization is to obtain the best combination of the number of experts r in each department and the number of bed resource allocations s .

We take z as the average of the total cost per unit time in a steady state:

Among them, c s ′ is the service cost for each bed resource unit time, c w is the cost of each patient staying in the system, s is the number of bed resource allocations, and L is the average queue length. We think of z as a function of s , write z  =  z ( s ), and find s ∗ that minimizes z ( s ).

Because s can only take integers and z ( s ) is not a continuous function, it cannot be calculated by calculus. According to the characteristic that z ( s ∗ ) should be the smallest, we get

We bring z into the above formula and simplify it:

We solve the value of L when r  = 1, 2, 3,…, and s  = 1, 2, 3,…, in turn, and calculate the difference between two adjacent L values. Since cs ′/ cw is a known number, the optimal s ∗ can be obtained according to which inequality related to s falls.

4.2. Simulation Results

Because the hospital's application for the allocation of bed resources is completed during working hours, it is assumed that 6 hours of the day can be applied for the allocation of bed resources at the basic level hospitals, 22 working days per month and 132 hours per month. Based on the previous parameters set, this paper simulates 132 units of time for a one-month bed resource allocation queuing system. In the end, 2224 cases of bed resource allocation applications were generated, and 1,716 cases were completed. The service rate of bed resource allocation applications reached 79.9%.

4.3. Analysis of Queuing Results

In order to allow the system to configure the applicant service for more bed resources, the performance of the system can be tested by adjusting parameters. Through the above analysis, in order to improve the system's pass rate, the congestion problem of the Department of Internal Medicine is mainly needed to be solved. The main cause of the congestion is that the probability of primary medical departments applying for the Department of Internal Medicine is very high, accounting for 53.46% of the total application, the preset Department of Internal Medicine has 14 experts, and the number is small, so it is envisaged that the number of experts in the Department of Internal Medicine can be increased to reduce the queue length and duration and improve the service rate of the entire queuing system.

Because the parameter combinations of the entire system are related to each other, if you want to comprehensively analyze the impact of each parameter on the entire queuing system, you need to obtain a 7-dimensional array, that is, the parameters of the 3 medical departments, the number of consultation rooms, and the length and duration of the queuing team. It is also not easy to analyze. It can be seen from the preset queuing system of the clinic that only the Department of Internal Medicine has the greatest influence on the entire queuing system. Therefore, this paper only conducts an experimental analysis of the combination of parameters of the number of experts and the number of clinics in the Department of Internal Medicine. On the premise that all other parameters are unchanged, by adjusting the number of experts in the Department of Internal Medicine, under the condition of different numbers of clinics, the queuing time and the queue length of the Department of Internal Medicine of each queuing system are simulated. We get the data in Table 8 .

Length and duration of the queuing team under the parameters of the number of experts and the number of consultation rooms in the Department of Internal Medicine.

The number of experts in the medical department does affect the length and duration of the queue. When the number of consultation rooms is insufficient, the length and duration of the queue can be appropriately reduced. However, when the number of consultation rooms is sufficient, it has little effect on the queuing system. On the whole, the number of experts in the medical department has a limited impact on the queue length and waiting time of the system.

The medical resource allocation of bed resources mentioned in this paper mainly refers to consultation rooms and experts. General resource allocation optimization considers the cost of input resources and the benefits generated by the system from an economic perspective. However, the allocation of bed resources is a key project supported by the state, and the social benefits generated cannot be simply measured from an economic perspective. Therefore, this paper only optimizes the queuing system from the perspective of improving service efficiency.

5. Conclusion

This paper analyzes the previous research models of related knowledge of queuing theory in medical services and summarizes the advantages and disadvantages of the queuing model so that it can be used as a constraint in the subsequent queuing optimization model. From the perspective of the hospital and the patient, several indicators such as the average total number of people, the utilization rate of bed resources, the patient stop rate, and the patient waiting time are defined to measure the advantages and disadvantages of the triage queue calling model, which makes the patient queue more reasonable. According to the actual task requirements of a hospital, a Markov queuing strategy based on Markov service is proposed. A mathematical queuing model is constructed, the process of solving the steady-state probability based on Markov theory is analyzed, and a simulation experiment is performed on the queuing model. Through experimental comparison and analysis, the advantages and disadvantages and applicable scope of the service Markov queuing model in this paper are obtained. This paper proposes the use of queuing theory to model and analyze the allocation of bed resources and uses simulation to obtain a dynamic waiting time length and waiting time change chart, which avoids that the theoretical derivation cannot be closer to the actual situation and also avoids cumbersome operations when solving related quantitative indicators. According to the parameters, the queuing system is simulated, and the dynamic queuing time length and queuing time map during the allocation of bed resources are found. It is found that the internal medical queuing is relatively congested. By analyzing the number of consultation rooms and the experts of the Department of Internal Medicine, the influence of the queuing team length and time is obtained. It comes to the conclusion that experts in the Department of Internal Medicine do not need much change. Based on the time-series prediction of the bed resource allocation based on the bed resource allocation data, the approximate bed resource allocation in the next few months is obtained. The bed resource allocation queuing model established in this paper can still be applied well. In the future, some advanced machine learning technologies can be used to further improve the performance of the bed resource allocation queuing model.

Acknowledgments

This work was supported by the Health Commission of Changshu City under Grant csws201818.

Data Availability

Conflicts of interest.

The authors declare no conflicts of interest.

Queuing Models - M/M/1 Queuing System

In this section and the subsequent sections of this chapter, we explain several Queuing models .

In presenting the models below, we start slowly and provide several examples, so that you can acquire a better feeling for waiting line models . Be patient and give yourself plenty of time to study these sections; otherwise, you may easily get confused.

"With time and patience the mulberry leaf becomes a silk gown." -Chinese Proverb

M/M/1 Queuing System (∞/FIFO)

It is a queuing model where the arrivals follow a Poisson process, service times are exponentially distributed and there is only one server. In other words, it is a system with Poisson input, exponential waiting time and Poisson output with single channel.

Queue capacity of the system is infinite with first in first out mode. The first M in the notation stands for Poisson input, second M for Poisson output, 1 for the number of servers and ∞ for infinite capacity of the system.

On small screens, scroll horizontally to view full calculation

Students arrive at the head office of Universal Teacher Publications according to a Poisson input process with a mean rate of 40 per hour. The time required to serve a student has an exponential distribution with a mean of 50 per hour. Assume that the students are served by a single individual, find the average waiting time of a student.

Given λ = 40/hour, μ = 50/hour

New Delhi Railway Station has a single ticket counter. During the rush hours, customers arrive at the rate of 10 per hour. The average number of customers that can be served is 12 per hour. Find out the following:

• Probability that the ticket counter is free.
• Average number of customers in the queue.

Given λ = 10/hour, μ = 12/hour

At Bharat petrol pump, customers arrive according to a Poisson process with an average time of 5 minutes between arrivals. The service time is exponentially distributed with mean time = 2 minutes. On the basis of this information, find out

• What would be the average queue length?
• What would be the average number of customers in the queuing system?
• What is the average time spent by a car in the petrol pump?
• What is the average waiting time of a car before receiving petrol?

Use Horizontal Scrollbar to View Full Calculation

Universal Bank is considering opening a drive in window for customer service. Management estimates that customers will arrive at the rate of 15 per hour. The teller whom it is considering to staff the window can service customers at the rate of one every three minutes.

Assuming Poisson arrivals and exponential service find

• Average number in the waiting line.
• Average number in the system.
• Average waiting time in line.
• Average waiting time in the system.

Given λ = 15/hour, μ = 3/60 hour or 20/hour

Chhabra Saree Emporium has a single cashier. During the rush hours, customers arrive at the rate of 10 per hour. The average number of customers that can be processed by the cashier is 12 per hour. On the basis of this information, find the following:

• Probability that the cashier is idle
• Average number of customers in the queuing system
• Average time a customer spends in the system
• Average number of customers in the queue
• Average time a customer spends in the queue

Share This Article

Operations Research Simplified Back Next

Transportation Problem Linear programming Simplex Method Assignment Problem

AI Index Report

Welcome to the seventh edition of the AI Index report. The 2024 Index is our most comprehensive to date and arrives at an important moment when AI’s influence on society has never been more pronounced. This year, we have broadened our scope to more extensively cover essential trends such as technical advancements in AI, public perceptions of the technology, and the geopolitical dynamics surrounding its development. Featuring more original data than ever before, this edition introduces new estimates on AI training costs, detailed analyses of the responsible AI landscape, and an entirely new chapter dedicated to AI’s impact on science and medicine.

Read the 2024 AI Index Report

The AI Index report tracks, collates, distills, and visualizes data related to artificial intelligence (AI). Our mission is to provide unbiased, rigorously vetted, broadly sourced data in order for policymakers, researchers, executives, journalists, and the general public to develop a more thorough and nuanced understanding of the complex field of AI.

The AI Index is recognized globally as one of the most credible and authoritative sources for data and insights on artificial intelligence. Previous editions have been cited in major newspapers, including the The New York Times, Bloomberg, and The Guardian, have amassed hundreds of academic citations, and been referenced by high-level policymakers in the United States, the United Kingdom, and the European Union, among other places. This year’s edition surpasses all previous ones in size, scale, and scope, reflecting the growing significance that AI is coming to hold in all of our lives.

Steering Committee Co-Directors

Ray Perrault

Steering committee members.

Erik Brynjolfsson

John Etchemendy

Katrina Ligett

Terah Lyons

James Manyika

Juan Carlos Niebles

Vanessa Parli

Yoav Shoham

Russell Wald

Staff members.

Loredana Fattorini

Nestor Maslej

Letter from the co-directors.

A decade ago, the best AI systems in the world were unable to classify objects in images at a human level. AI struggled with language comprehension and could not solve math problems. Today, AI systems routinely exceed human performance on standard benchmarks.

Progress accelerated in 2023. New state-of-the-art systems like GPT-4, Gemini, and Claude 3 are impressively multimodal: They can generate fluent text in dozens of languages, process audio, and even explain memes. As AI has improved, it has increasingly forced its way into our lives. Companies are racing to build AI-based products, and AI is increasingly being used by the general public. But current AI technology still has significant problems. It cannot reliably deal with facts, perform complex reasoning, or explain its conclusions.

AI faces two interrelated futures. First, technology continues to improve and is increasingly used, having major consequences for productivity and employment. It can be put to both good and bad uses. In the second future, the adoption of AI is constrained by the limitations of the technology. Regardless of which future unfolds, governments are increasingly concerned. They are stepping in to encourage the upside, such as funding university R&D and incentivizing private investment. Governments are also aiming to manage the potential downsides, such as impacts on employment, privacy concerns, misinformation, and intellectual property rights.

As AI rapidly evolves, the AI Index aims to help the AI community, policymakers, business leaders, journalists, and the general public navigate this complex landscape. It provides ongoing, objective snapshots tracking several key areas: technical progress in AI capabilities, the community and investments driving AI development and deployment, public opinion on current and potential future impacts, and policy measures taken to stimulate AI innovation while managing its risks and challenges. By comprehensively monitoring the AI ecosystem, the Index serves as an important resource for understanding this transformative technological force.

On the technical front, this year’s AI Index reports that the number of new large language models released worldwide in 2023 doubled over the previous year. Two-thirds were open-source, but the highest-performing models came from industry players with closed systems. Gemini Ultra became the first LLM to reach human-level performance on the Massive Multitask Language Understanding (MMLU) benchmark; performance on the benchmark has improved by 15 percentage points since last year. Additionally, GPT-4 achieved an impressive 0.97 mean win rate score on the comprehensive Holistic Evaluation of Language Models (HELM) benchmark, which includes MMLU among other evaluations.

Although global private investment in AI decreased for the second consecutive year, investment in generative AI skyrocketed. More Fortune 500 earnings calls mentioned AI than ever before, and new studies show that AI tangibly boosts worker productivity. On the policymaking front, global mentions of AI in legislative proceedings have never been higher. U.S. regulators passed more AI-related regulations in 2023 than ever before. Still, many expressed concerns about AI’s ability to generate deepfakes and impact elections. The public became more aware of AI, and studies suggest that they responded with nervousness.

Ray Perrault Co-director, AI Index

Our Supporting Partners

Analytics & Research Partners

Stay up to date on the AI Index by subscribing to the  Stanford HAI newsletter.

Princeton University

Princeton engineering, can language models read the genome this one decoded mrna to make better vaccines..

By Scott Lyon

April 8, 2024

Princeton researchers led by Mengdi Wang have developed a language model to home in on partial genome sequences and optimize those sequences to improve function for the development of mRNA vaccines and other therapies. Illustration from Adobe Stock.

The same class of artificial intelligence that made headlines coding software and passing the bar exam has learned to read a different kind of text — the genetic code.

That code contains instructions for all of life’s functions and follows rules not unlike those that govern human languages. Each sequence in a genome adheres to an intricate grammar and syntax, the structures that give rise to meaning. Just as changing a few words can radically alter the impact of a sentence, small variations in a biological sequence can make a huge difference in the forms that sequence encodes.

Now Princeton University researchers led by machine learning expert Mengdi Wang are using language models to home in on partial genome sequences and optimize those sequences to study biology and improve medicine. And they are already underway.

In a paper published April 5 in the journal Nature Machine Intelligence, the authors detail a language model that used its powers of semantic representation to design a more effective mRNA vaccine such as those used to protect against COVID-19.

Found in Translation

Scientists have a simple way to summarize the flow of genetic information. They call it the central dogma of biology. Information moves from DNA to RNA to proteins. Proteins create the structures and functions of living cells.

Messenger RNA, or mRNA, converts the information into proteins in that final step, called translation. But mRNA is interesting. Only part of it holds the code for the protein. The rest is not translated but controls vital aspects of the translation process.

Governing the efficiency of protein production is a key mechanism by which mRNA vaccines work. The researchers focused their language model there, on the untranslated region, to see how they could optimize efficiency and improve vaccines.

After training the model on a small variety of species, the researchers generated hundreds of new optimized sequences and validated those results through lab experiments. The best sequences outperformed several leading benchmarks for vaccine development, including a 33% increase in the overall efficiency of protein production.

Increasing protein production efficiency by even a small amount provides a major boost for emerging therapeutics, according to the researchers. Beyond COVID-19, mRNA vaccines promise to protect against many infectious diseases and cancers.

Wang, a professor of electrical and computer engineering and the principal investigator in this study, said the model’s success also pointed to a more fundamental possibility. Trained on mRNA from a handful of species, it was able to decode nucleotide sequences and reveal something new about gene regulation. Scientists believe gene regulation, one of life’s most basic functions, holds the key to unlocking the origins of disease and disorder. Language models like this one could provide a new way to probe.

Wang’s collaborators include researchers from the biotech firm RVAC Medicines as well as the Stanford University School of Medicine.

The Language of Disease

The new model differs in degree, not kind, from the large language models that power today’s AI chat bots. Instead of being trained on billions of pages of text from the internet, their model was trained on a few hundred thousand sequences. The model also was trained to incorporate additional knowledge about the production of proteins, including structural and energy-related information.

The research team used the trained model to create a library of 211 new sequences. Each was optimized for a desired function, primarily an increase in the efficiency of translation. Those proteins, like the spike protein targeted by COVID-19 vaccines, drive the immune response to infectious disease.

Previous studies have created language models to decode various biological sequences, including proteins and DNA, but this was the first language model to focus on the untranslated region of mRNA. In addition to a boost in overall efficiency, it was also able to predict how well a sequence would perform at a variety of related tasks.

Wang said the real challenge in creating this language model was in understanding the full context of the available data. Training a model requires not only the raw data with all its features but also the downstream consequences of those features. If a program is designed to filter spam from email, each email it trains on would be labeled “spam” or “not spam.” Along the way, the model develops semantic representations that allow it to determine what sequences of words indicate a “spam” label. Therein lies the meaning.

Wang said looking at one narrow dataset and developing a model around it was not enough to be useful for life scientists. She needed to do something new. Because this model was working at the leading edge of biological understanding, the data she found was all over the place.

“Part of my dataset comes from a study where there are measures for efficiency,” Wang said. “Another part of my dataset comes from another study [that] measured expression levels. We also collected unannotated data from multiple resources.” Organizing those parts into one coherent and robust whole — a multifaceted dataset that she could use to train a sophisticated language model — was a massive challenge.

“Training a model is not only about putting together all those sequences, but also putting together sequences with the labels that have been collected so far. This had never been done before.”

The paper, “A 5′ UTR Language Model for Decoding Untranslated Regions of mRNA and Function Predictions,” was published in Nature Machine Learning. Additional authors include Dan Yu, Yupeng Li, Yue Shen and Jason Zhang, from RVAC Medicines; Le Cong from Stanford; and Yanyi Chu and Kaixuan Huang from Princeton.

Related News

Episode 2: That Magic Touch

Episode 3: Haydn Seek

Episode 1: Stanley Jordan Pulls Out All the Stops

Personalizing ChatGPT can make it more offensive, researchers find

Princeton IP Accelerator funding awarded to support promising new technologies

Built for AI, this chip moves beyond transistors for huge computational gains

Mengdi Wang

Bioengineering and Health

Data Science

Related departments and centers.

Electrical and Computer Engineering

Omenn-Darling Bioengineering Institute

A decoder-only foundation model for time-series forecasting

February 2, 2024

Posted by Rajat Sen and Yichen Zhou, Google Research

Time-series forecasting is ubiquitous in various domains, such as retail, finance, manufacturing, healthcare and natural sciences. In retail use cases, for example, it has been observed that improving demand forecasting accuracy can meaningfully reduce inventory costs and increase revenue. Deep learning (DL) models have emerged as a popular approach for forecasting rich, multivariate, time-series data because they have proven to perform well in a variety of settings (e.g., DL models performed well in the M5 competition ).

At the same time, there has been rapid progress in large foundation language models used for natural language processing (NLP) tasks, such as translation , retrieval-augmented generation , and code completion . These models are trained on massive amounts of textual data derived from a variety of sources like common crawl and open-source code that allows them to identify patterns in languages. This makes them very powerful zero-shot tools; for instance, when paired with retrieval , they can answer questions about and summarize current events.

Despite DL-based forecasters largely outperforming traditional methods and progress being made in reducing training and inference costs , they face challenges: most DL architectures require long and involved training and validation cycles before a customer can test the model on a new time-series. A foundation model for time-series forecasting, in contrast, can provide decent out-of-the-box forecasts on unseen time-series data with no additional training, enabling users to focus on refining forecasts for the actual downstream task like retail demand planning .

To that end, in “ A decoder-only foundation model for time-series forecasting ”, we introduce TimesFM, a single forecasting model pre-trained on a large time-series corpus of 100 billion real world time-points. Compared to the latest large language models (LLMs), TimesFM is much smaller (200M parameters), yet we show that even at such scales, its zero-shot performance on a variety of unseen datasets of different domains and temporal granularities come close to the state-of-the-art supervised approaches trained explicitly on these datasets. Later this year we plan to make this model available for external customers in Google Cloud Vertex AI .

LLMs are usually trained in a decoder-only fashion that involves three steps. First, text is broken down into subwords called tokens. Then, the tokens are fed into stacked causal transformer layers that produce an output corresponding to each input token (it cannot attend to future tokens). Finally, the output corresponding to the i -th token summarizes all the information from previous tokens and predicts the ( i +1)-th token. During inference, the LLM generates the output one token at a time. For example, when prompted with “What is the capital of France?”, it might generate the token “The”, then condition on “What is the capital of France? The” to generate the next token “capital” and so on until it generates the complete answer: “The capital of France is Paris”.

A foundation model for time-series forecasting should adapt to variable context (what we observe) and horizon (what we query the model to forecast) lengths, while having enough capacity to encode all patterns from a large pretraining dataset. Similar to LLMs, we use stacked transformer layers (self-attention and feedforward layers) as the main building blocks for the TimesFM model. In the context of time-series forecasting, we treat a patch (a group of contiguous time-points) as a token that was popularized by a recent long-horizon forecasting work . The task then is to forecast the ( i +1)-th patch of time-points given the i -th output at the end of the stacked transformer layers.

However, there are several key differences from language models. Firstly, we need a multilayer perceptron block with residual connections to convert a patch of time-series into a token that can be input to the transformer layers along with positional encodings (PE). For that, we use a residual block similar to our prior work in long-horizon forecasting . Secondly, at the other end, an output token from the stacked transformer can be used to predict a longer length of subsequent time-points than the input patch length, i.e., the output patch length can be larger than the input patch length.

Consider a time-series of length 512 time-points being used to train a TimesFM model with input patch length 32 and output patch length 128. During training, the model is simultaneously trained to use the first 32 time-points to forecast the next 128 time-points, the first 64 time-points to forecast time-points 65 to 192, the first 96 time-points to forecast time-points 97 to 224 and so on. During inference, suppose the model is given a new time-series of length 256 and tasked with forecasting the next 256 time-points into the future. The model will first generate the future predictions for time-points 257 to 384, then condition on the initial 256 length input plus the generated output to generate time-points 385 to 512. On the other hand, if in our model the output patch length was equal to the input patch length of 32 then for the same task we would have to go through eight generation steps instead of just the two above. This increases the chances of more errors accumulating and therefore, in practice, we see that a longer output patch length yields better performance for long-horizon forecasting

Pretraining data

Just like LLMs get better with more tokens, TimesFM requires a large volume of legitimate time series data to learn and improve. We have spent a great amount of time creating and assessing our training datasets, and the following is what we have found works best:

Synthetic data helps with the basics. Meaningful synthetic time-series data can be generated using statistical models or physical simulations. These basic temporal patterns can teach the model the grammar of time series forecasting.

Real-world data adds real-world flavor. We comb through available public time series datasets, and selectively put together a large corpus of 100 billion time-points. Among these datasets there are Google Trends and Wikipedia Pageviews , which track what people are interested in, and that nicely mirrors trends and patterns in many other real-world time series. This helps TimesFM understand the bigger picture and generalize better when provided with domain-specific contexts not seen during training.

Zero-shot evaluation results

We evaluate TimesFM zero-shot on data not seen during training using popular time-series benchmarks. We observe that TimesFM performs better than most statistical methods like ARIMA , ETS and can match or outperform powerful DL models like DeepAR , PatchTST that have been explicitly trained on the target time-series.

We used the Monash Forecasting Archive to evaluate TimesFM’s out-of-the-box performance. This archive contains tens of thousands of time-series from various domains like traffic, weather, and demand forecasting covering frequencies ranging from few minutes to yearly data. Following existing literature, we inspect the mean absolute error (MAE) appropriately scaled so that it can be averaged across the datasets. We see that zero-shot (ZS) TimesFM is better than most supervised approaches, including recent deep learning models. We also compare TimesFM to GPT-3.5 for forecasting using a specific prompting technique proposed by llmtime(ZS) . We demonstrate that TimesFM performs better than llmtime(ZS) despite being orders of magnitude smaller.

Most of the Monash datasets are short or medium horizon, i.e., the prediction length is not too long. We also test TimesFM on popular benchmarks for long horizon forecasting against a recent state-of-the-art baseline PatchTST (and other long-horizon forecasting baselines). In the next figure, we plot the MAE on ETT datasets for the task of predicting 96 and 192 time-points into the future. The metric has been calculated on the last test window of each dataset (as done by the llmtime paper). We see that TimesFM not only surpasses the performance of llmtime(ZS) but also matches that of the supervised PatchTST model explicitly trained on the respective datasets.

We train a decoder-only foundation model for time-series forecasting using a large pretraining corpus of 100B real world time-points, the majority of which was search interest time-series data derived from Google Trends and pageviews from Wikipedia. We show that even a relatively small 200M parameter pretrained model that uses our TimesFM architecture displays impressive zero-shot performance on a variety of public benchmarks from different domains and granularities.

Acknowledgements

This work is the result of a collaboration between several individuals across Google Research and Google Cloud, including (in alphabetical order): Abhimanyu Das, Weihao Kong, Andrew Leach, Mike Lawrence, Alex Martin, Rajat Sen, Yang Yang, Skander Hannachi, Ivan Kuznetsov and Yichen Zhou.

• Machine Intelligence

Other posts of interest

April 12, 2024

• Machine Intelligence ·
• Sound & Accoustics

April 11, 2024

• Natural Language Processing ·
• Responsible AI

March 28, 2024

• Algorithms & Theory ·
• Open Source Models & Datasets