Queueing theory (spelled queuing theory in the United States) is the mathematical study of waiting lines (or queues). There are several related processes, arriving at the back of the queue, waiting in the queue (essentially a storage process), and being served by the server at the front of the queue. It is applicable in transport and telecommunication. Occasionally linked to ride theory.
Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on queueing theory in 1909.
Kendall introduced a A/B/C queueing notation in 1953. It has since been extended to 1/2/3/(4/5/6) where the numbers are replaced with:
A code describing the arrival process. The codes used are:
M stands for "Markovian", implying exponential distribution for service times or inter-arrival times.
D stands for "degenerate" distribution, or "deterministic" service times.
A similar code representing the service process. The same symbols are used.
The Number of service channels.
The Priority order that jobs in the line are served:
First Come First Served (FCFS) (or First In First Out - FIFO),
Last Come First Served (LCFS) (or Last In First Out - LIFO),
Service In Random Order (SIRO)
The maximum size of the system. The maximum number of customers allowed in the system including those in service. When the number is at this maximum, further arrivals are turned away.
The size of calling source. The size of the population from which the customers come. This limits the arrival rate. As more jobs queue up there are fewer available to arrive into the system.
The word queue comes from the Latin cauda, meaning tail.
Queuingtheory may be extended to cover a wide variety of contention situations, such as how customer check-out lines form (and how they can be minimized), how many calls a telephone switch can handle, how many computer users can share a mainframe, and how many doors an office building should have.
Queuingtheory is the basis for traffic management—the maintenance of smooth traffic flow, keeping congestion and bottlenecks to a minimum.
The most important application of queuingtheory occurred during the late 1800s, when telephone companies were faced with the problem of how many operators to place on duty at a given time.
The main new feature of those, which is not covered by classical queuingtheory, clearly is the importance of the user location within the area that is served by the base stations of the network.
In the framework of queuingtheory, this opens up the natural extension of classical queuing models towards queues with a structured space in which users are served.
Furthermore, it is suitable as a textbook for advanced queuingtheory on the graduate or post-graduate level.
Feeds |
Contact