Deutsch
English
The basic model of queuing theory
The queuing theory uses a simple basic model to describe operation of systems. It consists of the so-called service station which has one or more parallel operating similar machines or operators, and a waiting room. The clients arrive at individual random times at the service station. A newly arrived customer is served, if at least one of the operating units is available, otherwise ha has to wait in the queue.
The basic model can be varied in many ways:
- Customers are not served individually, but in groups (waiting systems with batch operation). Application: producing batches in a production plant
- Some customers leave the system before they are served (waiting systems with time restrictions). Application: storage of perishable goods
- Not all service devices are available for all customer (service systems with limited accessibility). Application: production lines with dedicated machines, switching arrangements in a telephone network.
- Some customers reject to enter the queueing system, because they the queue appears to too long for them (queueing systems with impatient customers). Application: common customer behavior at a post office, bank or ticket office
- A customer with a higher priority displaces customers lower priority from the service process (service systems with priority control). Application: Express lanes in a manufacturing process
- A customer who can not be served immediately upon his arrival, is lost (loss systems). Application: telephone calls in a telephone network
The flow of incoming requests is described by a so-called renewal process. For this purpose we imagine all requests are numbered in the in the order of their arrival. The time span In between the arrival of the (n-1)-th and the n-th customer is called inter-arrival time. The random variables In, n = 1, 2, ..., are assumed to be distributed stochastically independent and identical with the distribution function Fl(x), the expected value E[I] and the variance D[I]. The reciprocal
is called the service rate and indicates the average number of customers that can be served by the operating system per time unit. If there are several parallel and similar service devices, the service rate increases according to the number of devices.
The service rule determines the order in which the waiting customers are to be processed. The following rules and designations are commonly used:
| FIFO (FCFS) | First In, First Out (First Come, First Served). Customers are served in the order in which they arrive. | |
| LIFO (LCFS) | Last In, First Out (Last Come, First Served). Service is provided in the reverse order of arrivals. | |
| SIRO | Selection In Random Order. The next customer is selected at random. | |
| Non-preemptive priority | Relative priority. Some customers are given priority over other customers. However, the ongoing service process is not interrupted. | |
| Preemptive priority | Absolute priority. If the new incoming customer has a higher priority than the other customers in the system, the current service process is interrupted and continued with the new request. The old request is put on hold. | |
| RR | Round Robin. Each customer can only use the operator for a specific time interval. Customers who require more time to be processed must therefore join the queue several times in succession. |
D.G. Kendall and B.W. Gnedenko used the notation
A / B / c /m
was introduced. The letters A and B mark the distribution type of the intermediate arrival times and the service times. The letter c stands for the number of parallel operators and m denotes the capacity of the waiting room.
The following abbreviations are commonly used for the distribution type:
| D | Deterministic distribution |
| M | Exponential distribution |
| Ek | Erlang distribution with parameter k (k = 1, 2, ...) |
| Hk | Hyperexponential distribution with parameter k (k = 1, 2, ...) |
| PH | Phase type distribution |
| G | General distribution |
Example: The notation M/G/3/5 characterizes a service system with exponentially distributed intermediate arrival times, arbitrarily distributed service times, three parallel operators and a waiting room in which a maximum of 5 customers can wait.
The performance evaluation of service systems is based on the following processes:
- Number of customers in the system (Nt)t>0. This process indicates how many customers are in the serving system at time t.
- The process of successive dwell times (or throughput times)(Vn)n in N. The random variable Vndenotes the time that the nth customer spends in the operating system
Various methods from the theory of stochastic processes can be used to calculate the parameters. The suitability of a method depends very much on which distribution types are used for the inter-arrival and service times and whether time-dependent or stationary variables are to be calculated. Even the basic model of queuing theory is so complicated that it cannot be solved exactly under general distribution assumptions. However, there are approximation formulas that have proven themselves quite well in practice and that make the stochastic functioning of operating systems transparent. According to a formula by Allen-Cunnen, the following applies to the average number of customers in the stationary case: