This entry has been abandoned, as I no longer study computer science, and hence have no desire to finish the entry. Perhaps some other researcher will turn this entry into a finished product, but that researcher isn't me!

Queueing systems occur any time you have a number of things arriving, in some way, and a server or a number of servers moving through a queue of everyone who has arrived so far and not been left with. Because of their versatility they are possibly the most common model used for real life systems. They are even used for all sorts of things that you wouldn't immediately think of related to queues, such as conversations.

Describing Them

To fully categorise queueing systems, you might need the following information:

• Arrival Process - How do people arive? how are they distributed? Are their arrival times independant, like cars at a car wash, or dpendant, like customers to a restaurant?
• Service Process - How long does it take to service somebody?
• Storage Capacity - How many people can we fit in the queue? What happens when the queue gets full?
• How many servers are there? How many potential customers are there?
• What types of customer and server are there? Big jobs, little jobs, fast servers, slow servers...
• What queueing discipline is used? Is it First Come First Served, Last Come First Served, Best Looking First Served¹, or something else?
• Other details: is there jockeying? balking? bribing?...

And more besides that, in a particularly complicated system. Describing each of these features absolutely precisely could take a page, so various forms of notation have sprung up to make the job easier.

Kendall Notation

Kendall Notation helps to reduce some of this complexity, by replacing most of the common features with symbols, time is freed up to concentrate on the unusual features of a particular system. The notation is the following:

A/B/m/k/l

A is the distribution of arrival times, and B is the distribution of service times. These are selected from one of M, E_r, H_r, and D for standard distributions. Alternatively if the distribution is non-standard, then G for General is used.

m is the number of servers available in the system - this might be 1 for your local corner store, and 50 for your local supermarket. k is the limit on the queue length, and l is the limit on the population size, both of which can be left blank if there is no limit.

Queueing Networks

If you have a large number of queuing systems, with the output from one queue linking to the input to another queue, you have a queueing network. An example might be in a particularly nasty beauracracy, where to get the pink form you need the red form, but the red form requires an amber form, and nobody knows where you get the amber form from because 'It's not my department, love'.

The best way to describe a queueing network is to draw a diagram showing how customers move between queues, and give the Kendall Notation for each node (barring the arival distribution, which would depend on other parts of the system.

Queueing networks can be open, closed, or feed-forward. Closed networks have a fixed number of customers which remain in the system 'forever'. Open networks allow customers to join and exit. Feed-forward networks are a special type of open networks, where a customer only visits each queue at most once.