Please I need a good seminar topic on queuing or any production management.

Thank you'

queuing theory paper

Abstract

This paper deals with the Queueing Theory and some mathematical models of queueing systems. Starting with the historical backgrounds it gives an overview of different solution methods and tools. Then the basic laws and formulas are introduced. It highlights several recent advances and developments of the theory and new applications fields are listed. It briefly summarizes the achievements of Hungarian researchers to the Queueing Theory and the most cited result of the author is mentioned. It ends with the References of the most important sources. Keywords: queueing theory, applications, finite-source models, telecommunication systems, operational research, manufacturing systems, teletraffic engineering MSC: 60K25[Queueing Theory], 68M20, 90B22

1. Introduction

As the reader will quickly discover, this article is a short survey - from my personal perspective - of 32 years of research, teaching on the modeling, analysis, and applications of queueing systems. My choice of topics is far from exhaustive; I have focused on those research achievements that I believe have been some of the most significant in their contributions to queueing theory and to its applications. They are the contributions that I have admired and appreciated the most over the course of my teaching and research activities. Another author would undoubtedly have made different choices, as they did in several survey papers on queueing theory. The selection has not been easy at all since there are so many nice results. My *Research is partially supported by Hungarian Scientific Research Fund-OTKA K 60698/2006. The work is supported by the TAMOP 4.2.1./B-09/1/KONV-2010-0007 project. The project is implemented through the New Hungary Development Plan, co-financed by the European Social Fund and the European Regional Development Fund.

Aim is very simple, I would like to draw the attention of readers to a very unpleasant activity, namely waiting. I have collected some sayings or Murphy’s Laws on Queueing. Here you are:

• "If you change queues, the one you have left will start to move faster than the one you are in now.
• Your queue always goes the slowest.
• Whatever queue you join, no matter how short it looks, will always take the longest for you to get served."

A queue is a waiting line (like customers waiting at a supermarket checkout counter); queueing theory is the mathematical theory of waiting lines. More generally, queueing theory is concerned with the mathematical modeling and analysis of systems that provide service to random demands. A queueing model of a system is an abstract representation whose purpose is to isolate those factors that relate to the system’s ability to meet service demands whose occurrences and durations are random. Typically, simple queueing models are specified in terms of the arrival process the service mechanism and the queue discipline. The arrival process specifies the probabilistic structure of the way the demands for service occur in time; the service mechanism specifies the number of servers and the probabilistic structure of the duration of time required to serve a customer, and the queue discipline specifies the order in which waiting customers are selected from the queue for service. Selecting or constructing a queueing model that is rich enough to reflect the complexity of the real system, yet simple enough to permit mathematical analysis) is an art. The ultimate objective of the analysis of queueing systems is to understand the behavior of their underlying processes so that informed and intelligent decisions can be made in their management. Then, the mathematical analysis of the models would yield formulas that presumably relate the physical and stochastic parameters to certain performance measures, such as average response/ waiting time, server utilization, throughput, probability of buffer overflow, distribution function of response/waiting time, busy period of server, etc. The art of applied queueing theory is to construct a model that is simple enough so that it yields to mathematical analysis, yet contains sufficient detail so that its performance measures reflect the behavior of the real system. In the course of modeling one could use analytical, numerical, asymptotic, and simulation methods integrated into performance evaluation tools. In the course of modeling we make several assumptions regarding the basic elements of the model. Naturally, there should be a mechanism by which these assumptions could be verified. Starting with testing the goodness of fit for the arrival and service distributions, one would need to estimate the parameters of the model and/or test hypotheses concerning the parameters or behavior of the system. Other important questions where statistical procedures play a part are in the determination of the inherent dependencies among elements and dependence of the system on time.

Starting with a congestion problem in teletraffic the range of applications has grown to include not only telecommunications and computer science, but also manufacturing, air traffic control, military logistics, design of theme parks, call centers, supermarkets, inventories, dams, hospitals, and many other areas that involve service systems whose demands are random. Queueing theory is considered to be one of the standard methodologies (together with linear programming, simulation, etc.) of operations research and management science, and is standard fare in academic programs in industrial engineering, manufacturing engineering, etc., as well as in programs in telecommunications, computer engineering, and computer science. There are dozens of books and thousands of papers on queueing theory, and they continue to be published at an ever-increasing rate. Searching the Google for "Queueing Theory" I have found 1880 hits.

This tremendous push for new results forced more and more academic journals to publish articles in queueing and even open new sections. In 1986, Baltzer Verlag, AG launched a new academic journal entitled Queueing Systems (edited by N.U. Prabhu), which is devoted entirely to queueing. Many other journals, in the field of probability, operational research, telecommunication, industrial engineering, computer science, management science publish articles on queueing extensively. The flow of new theories and methodologies in queueing has become very hard to keep up with. Surveys on the hottest topics in queueing and related areas are scattered over a large variety of scientific magazines. A sort of manual would be desirable, indicating where to find the hottest topics and where to concentrate one’s efforts should queueing become one’s interest. A careful elaboration of major themes would take many years of work after which the results would then be outdated!

After all these considerations I have decided to give a view of my personal perspectives of Queueing Theory and its Applications. I have been teaching and doing research on this topic for 32 years. I have realized that the applications of the theory became more and more important. In the following I would like to mention some of my favorite books on theory: Allen [1], Artalejo-Gomez-Corral [2], Bolch-Greiner-De Meer-Trivedi [4], Cooper [5], Gnedenko-Kovalenko [14], GrossShortle-Thompson-Harris [15], Khintchine [20], Kleinrock [21], Kobayashi-Mark [23], Takagi [30], Takács [32], Trivedi [35]. Some recent books on applications, mainly computer networks and telecommunications, due to web-based research are the following: Daigle [6], Giambene [13], Haghighi [17], Kleinrock [21]. Finally, I would like to mention some materials written by Hungarian authors: Györfi [16], Lakatos-Szeidl-Telek [24], Sztrik [29], and the Hungarian translation of the famous book by Kleinrock [22].

2. Origin and Developments

The history of Queueing Theory goes back nearly 100 years. It was born with the work of A. K. Erlang who published in 1909 his paper, The Theory of Probabilities and Telephone Conversations, [10]. His most important work, Solutions of Some Problems in the Theory of Probabilities of Significance in Automatic Telephone Exchanges , [11] was published in 1917, which contained formulas for loss and waiting probabilities which are now known as Erlang’s loss formula (or Erlang B-formula) and delay formula (or Erlang C-formula), respectively. Erlang’s loss model assumes Poisson arrivals of telephone calls, namely, the number of sources or subscribers is sufficiently large. If the number of sources is finite and not so large, then a more accurate loss formula is provided by the Engset’loss formula, which was published by the Norwegian mathematician Engset. We should mention that the Erlang and the Engset loss model and their loss formulas remained the most widely used results in telephone engineering.

Erlang laid the foundation for the place of Poisson (and hence, exponential)distribution in queueing theory. His papers written in the next 20 years contain some of the most important concepts and techniques; the notion of statistical equilibrium and the method of writing down balance of state equations (later called Chapman-Kolmogorov equations) are two such examples. Erlang’s motivation was to develop tools for the analysis and design of telephone systems) an application that continues to the present day to motivate research in queueing theory

It should be noted that in Erlang’s work, as well as the work done by others in the twenties and thirties, the motivation has been the practical problem of congestion. The trend toward the analytical study of the basic stochastic processes of the system continued, and queueing theory proved to be a fertile field for researchers who wanted to do fundamental research on stochastic processes involving mathematical models.

Mathematical modeling is a process of approximation. A probabilistic model brings it a little bit closer to reality; nevertheless it cannot completely represent the real world phenomenon because of involved uncertainties. Therefore, it is a matter of convenience where one can draw the line between the simplicity of the model and the closeness of the representation.

Renewed interest in queueing theory and its potential applications outside of telecommunications came with the codification of the field of operations research in the early 1950’s. And in the early 1960’ s queueing theory was rediscovered by researchers interested in the performance analysis of time-shared computer systems. The use of queueing theory as a tool for the performance evaluation of computer systems and components of computer systems is now well established with the result that most undergraduate computer science majors receive at least some exposure to its models and methodology.

By the mid-70’s researchers interested in modeling the performance of computer systems had discovered the Jackson network and its variants and come to appreciate the versatility and applicability of such models. In those days, the emphasis was on systems consisting of a mainframe computer with disk storage and satellite terminals, a precursor to what we would now call a local area network (LAN). The idea of a communication network tying together widely separated computers was just a gleam in the eye of Leonard Kleinrock and a few other visionaries. It was Kleinrock who, more than anyone else, was responsible for spreading the word among computer scientists about Jackson networks in particular and queueing theory in general.

Recently web-based research dominates the main directions. It is difficult to list all the main trends, but in my opinion the followings certainly belong to them: long-range dependence, numerical problems of stochastic processes, time-dependent solutions, modeling tools, retrial systems, approximations, simulations, statistical inference. For a more detailed discussions about ongoing research, see Dshalalow [8, 9]. Readers interested in the history of queueing theory are referred to, among others Dshalalow [8], Takagi [30] where extensive Bibliographies were collected involving numerous contributions of Russian experts lead by Khintcine, Gnedenko, Kovalenko, Bocharov, Rykov, too.

Research on queueing theory and its applications is very active, year-by-year different conferences, workshops are held. Just for illustration I would like to mention two of them Third Madrid Conference on Queueing Conference, June 28 - July 1, 2010 , and 22nd International Teletraffic Congress, September 7-9, 2010, Amsterdam.
Some topics are
• Performance of wireless/wired networks
• Business models for QoS
• Performance and reliability tradeoffs
• Performance models for voice, video, data and P2P applications
• Scheduling algorithms
• Simulation methods and tools

It is my feeling that at present queueing theory is divided into two directions. One is highly abstract and the other highly practical. It seems that this split will continue to grow wider and wider. Progress in the theory of stochastic processes (especially point, regenerative, and stationary processes) will influence new approaches to queueing theory. This may be in the form of new methods, new interpretations, and the development of new theories with wide applicability. Researchers in abstract probability usually do not have queueing theory in mind; different talents are required to find applicability of their results. Other examples, are diffusion approximation, the large deviations technique, and random fields. One may hope that the near future will bring applications of superprocesses, the object of current research in stochastic processes. Progress in technical developments of systems involving various forms of traffic created the need for mathematical analysis of performance of individual systems. This brings new problems which require new tools, and the search for these tools is of great practical importance. This is clearly visible not only in teletraffic theory, but also in other disciplines where queueing methods are used (biological and health studies, computers). As already mentioned, simulation and numerical analysis are frequently the only way to obtain approximate results. It is therefore hoped that the gap between these two directions may eventually be diminished. Idealistically, this could be achieved when theoreticians learn about practical problems and practitioners learn about theory. In present times of great specialization, this is highly unrealistic. Nevertheless, one could try to work in this direction, at least with our students in universities, by stressing the importance of theory and applications. Otherwise, researchers could not find a common language.

3. Kendall’s Notation

3.1. Components of a Queueing System
While analyzing a queueing system we can identify some basic elements of it. Namely,Input process: if the occurrence of arrivals and the offer of service are strictly according to schedule, a queue can be avoided. But in practice this does not happen. In most cases the arrivals are the product of external factors. Therefore, the best one can do is to describe the input process in terms of random variables which can represent either the number arriving during a time interval or the time interval between successive arrivals. If customers arrive in groups, their size can be a random variable as well.

Service mechanism: the uncertainties involved in the service mechanism are the number of servers, the number of customers getting served at any time, and the duration and mode of service. Networks of queues consist of more than one servers arranged in series and/or parallel. Random variables are used to represent service times, and the number of servers, when appropriate. If service is provided for customers in groups, their size can also be a random variable.

System capacity: at most how many customers can wait at a time in a queueing system is a significant factor for consideration. If the waiting room is large, one can assume that for all practical purposes, it is infinite. But our everyday experience with the telephone systems tells us that the size of the buffer that accommodates our call while waiting to get a free line is important as well.

Service discipline: all other factors regarding the rules of conduct of the queue can be pooled under this heading. One of these is the rule followed by the server in accepting customers for service. In this context, the rules such as First-Come, First-Served (FCFS), Last-Come, First-Served (LCFS), and Random Selection for Service (RS) are self-explanatory. In many situations customers in some classes get priority in service over others. There are many other queue disciplines which have been introduced for the efficient operation of computers and communication systems. Also, there are other factors of customer behavior such as balking, reneging, and jockeying, that require consideration as well.

3.2. Classification of Systems The following notation, known as Kendall’s notation , is widely used to describe elementary queueing systems:

A/B/m/K/N /Z,
where
• A indicates the distribution of the interarrival times,
• B denotes the distribution of the service times,
• m is the number of servers
• K is the capacity of the system, that is the maximum number of customers
staying at the facility (sometimes in the queue),
• N denotes the number of sources,
• Z refers to the service discipline.
As an example of Kendall’s notation, the expression
M/G/1 - LCFS preemptive resume (PR)

describes an elementary queueing system with exponentially distributed interarrival times, arbitrarily distributed service times, and a single server. The queueing discipline is LCFS where a newly arriving job interrupts the job currently being processed and replaces it in the server. The servicing of the job that was interrupted is resumed only after all jobs that arrived after it have completed service.

M/G/1/K/N

describes a finite-source queueing system with exponentially distributed source times, arbitrarily distributed service times, and a single server. There are N request in the system and they are accepted for service iff the number of requests staying at the server is less than K. The rejected customers return to the source and start a new source time with the same distribution. It should be noted that as a special case of this situation the M/G/1/N/N system could be considered. However, in this case we use the traditional M/G/1//N notation, that is the missing letter, as usual in this framework, means infinite capacity, and FCFS service rule. It is natural to extend this notation to heterogeneous requests, too. The case when we have different customers is denoted by →. So, the

M / ~ G/ ~ 1/K/N

denotes the above system with different arrival rates and service times.

4. Basic Formulas
This section is devoted to the most well-known formulas of queueing theory. The selection is subjective, but I think these are the ones from which many others have been derived.

4.1. Erlang’s Formulas

As we mentioned in the earlier section the whole theory started with a practical problem. Erlang’s task can be formulated as follows: What fraction of the incoming calls is lost because of the busy line at the telephone exchange office. Of course, the answer is not so simple, since we first should know the inter-arrival and service time distributions. After collecting data Erlang verified that the Poisson-process arrival and exponentially distributed service were appropriate mathematical assumptions. He considered the M/M/n/n and M/M/n cases, that is the system where the arriving calls are lost because all the servers are busy, and where the calls have to wait for service, respectively. Assuming that the arrival intensity is λ, service rate is µ he derived the famous formulas for loss and delay systems, called Erlang B and C ones, respectively.
4.2. Little’s Law
Little’s law, Little’s result, or Little’s theorem is perhaps the most widely used formula in queueing theory was published by J. Little [25] in 1961. It is simple to state and intuitive, widely applicable, and depends only on weak assumptions about the properties of the queueing system.

It says that the average number of customers in the system is equal to the average arrival rate of customer to the system multiplied by the average system time per customer. Historically, Little’s law has been written as

L = λW

and in this usage it must be remembered that W is defined as mean response time, the mean time spent in the queue and at the server, and not just simply as the mean time spent waiting to be served, L refers to the average number of customers in the system and λ is the mean arrival rate. Little’s law can be applied when we relate L to the average number of customers waiting to receive service, Lq and W to the mean time spent waiting for service, Wq, that is another well-known form is

Lq = λWq.

The same applies also to the servicing aspect itself. In other words, Little’s law may be applied individually to the different parts of a queueing facility, namely the queue and the server. It may be applied even more generally than we have shown here. For example, it may be applied to separate parts of much larger queueing systems, such as subsystems in a queueing network. In such a case, L should be defined with respect to the number of customers in a subsystem and W with respect to the total time in that subsystem. Little’s law may also refer to a specific class of customer in a queueing system, or to subgroups of customers, and so on. Its range of applicability is very wide indeed. Finally, we comment on the amazing fact that the proof of Little’s law turns out to be independent of

• specific assumptions regarding the arrival distribution A(t)
• specific assumptions regarding the service time distribution B(t)
• number of servers
• particular queueing discipline
Little’s law is important for three reasons:
• because it is so widely applicable (it requires only very weak assumptions),
it will be valuable to us in checking the consistency of measurement data
• for example, in studying computer systems we frequently will find that we
know two of the quantities related by Little’s law (say, the average number of
requests in a system and the throughput of that system) and desire to know
the third (the average system residence time, in this case)
• it is central to the algorithms for evaluating several queueing network models

Given a computer system, Little’s law can be applied at many different levels: to a single resource, to a subsystem, or to the system as a whole. The key to success is consistency: the definitions of population, throughput, and residence time must be compatible with one another. Over the past few years, it has become increasingly important in many fields of applications. For more discussions on this topic one may read, for example Jewel [19], Ramalhota-Amaral-Cochito [26], Wolf [36].

4.3. Pollaczek-Khintchine Formulas
This section deals with formulas of an M/G/1 queueing system at which the customers arrive according to a Poisson-process with parameter λ, the service time is arbitrarily distributed, there is no restriction to the number of customers staying in the system, and they are serviced according to the order of their arrivals, that is the service discipline is FCFS. These formulas are treated almost every book on queueing theory but the notation is quite different. Each author prefers his own designation and as a consequence it is very difficult to find the proper form. We make difference between the type of formulas, the mean value and transform ones. Of course, the first ones are much easier to obtain. Independently of each other, Pollaczek and Khintchine derived them in the period 1930-50.

5. Hungarian Contributions to the Theory of Queues
In this section I would like to mention several Hungarian researchers without discussing their main results in details. The selection is subjective and it is based on my information collected during my research activities.

5.1. Lajos Takács and his Work
There is no doubt that he is the most well-known,reputed and celebrated Hungarian in this field. In the second half of 1994, many scientific institutions (including the Institute of Mathematical Statistics, Operations Research Society of America, The Institute of Management Sciences, and Hungarian Academy of Sciences) celebrated his 70th birthday, which took place on August 21, 1994. In addition, a special volume, Studies in Applied Probability (31A of Journal of Applied Probability, edited by J. Galambos and J. Gani), [12], appeared in the first half of 1994 honoring Professor Takács. Another paper, [7] was devoted to his 70th birthday written by Dshalalow and Syski where we can read