3.2 Kendall's Notation
3.2 Kendall’s Notation
As is apparent from Section 2.1 and Section 3.1, the construction of a queueing process for a single station involves a few main elements: the distribution of inter-arrival times for jobs, the distribution of service times, the number of servers present to process jobs, and the number of jobs that arrive and can be served simultaneously as a batch.
We will often use Kendall’s abbreviation \(A^{B}/Y^{C}/c/K\) to characterize the type of queueing process. Here, \(A\) is the distribution of times between consecutive batch arrivals, \(B\) the size of the batch1That is, the number of items in the batch. at an arrival, \(Y\) the distribution of service-batch durations, \(C\) the number of items that can be served at once, \(c\) the number of servers available, and \(K\) the maximal number of items that the system can contain. We assume that the inter-arrival times, service durations, arrival batch sizes, and service batch sizes each form an iid sequence, and that these four sequences are mutually independent. Finally, the service discipline is assumed to be FIFO. When \(B\equiv 1,\) jobs arrive individually and \(B\) is omitted. Similarly, when \(C\equiv 1,\) jobs are served individually and \(C\) is omitted. Likewise, if the system is unbounded, \(K\) is omitted. Moreover, service is assumed to be work-conserving, which means that a server cannot be idle when there is a job in queue that it can serve.2Thus, when service is work-conserving, capacity is not wasted. The most important inter-arrival and service distributions are the exponential distribution, denoted with the shorthand3M: Markov or Memoryless. \(M,\) and the general distribution, denoted \(G.\) We write \(D\) for a deterministic rv.
Important examples include the \(M/M/1\) queue, with exponentially distributed inter-arrival times and service times; the \(M/G/1\) queue, with exponential inter-arrival times and general service times; and the \(G/G/c\) queue, where both the inter-arrival and service times are unspecified.
A common model for determining the number of beds required in a hospital ward is the \(M/M/c/c\) queue. By the arguments of Section 1.4 patient inter-arrival times are exponentially distributed, and as there are many patients with various reasons for occupying a bed, the recovery times are (roughly) exponentially distributed. There are \(c\) beds available, and since each bed serves one patient,4In a hospital patients typically don’t share beds. the hospital is `full’ when all \(c\) beds are occupied. Therefore \(K=c.\) The hospital’s problem is to determine the number \(c\) of beds needed such that the blocking probability is below some threshold, say \(1\%.\)
The discrete-time model that corresponds to the recursion (2.1.1) can be represented as a \(D^{B}/D^{C}/1\) queue in which \(a_{k}\sim B\) and \(c_{k}\sim C.\)
An inventory under base-stock control with \(S=0\) is a \(D^{B}/D/\infty\) queue: the total demand in a period is \(~B,\) and each demand is delivered (served) after the lead time, hence it can be seen as if each demand receives its own server.
TF 1.
Consider an \(M^2/G/c/K\) queue, with \(K\geq c.\) Claim: Exactly one of the following statements is false.
- Jobs arrive in pairs of two.
- Service times can be deterministic.
- The queue shared among \(c\) parallel servers cannot contain more than \(K-c\) jobs.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. All three statements are true, so it is not the case that exactly one is false. The first two statements are evident. For the third, \(K\) is the capacity of the system, not the queue capacity. Hence, the queue cannot contain more than \(K-c\) jobs.
TF 2.
In the \(D/M/1\) queue, jobs have deterministic service times.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. Service times are iid and exponential.
TF 3.
Consider a check-in desk at an airport. One desk is dedicated to business customers. However, when this desk is idle (i.e., no business customer in service or in queue), it also serves economy class customers. The other \(c\) desks are reserved for economy class customers. The queueing process perceived by the economy class customers can be modeled as an \(M/M/(c+1)\) queue.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The service for business customers follows a priority queue. Therefore, one of the \(c+1\) servers, as perceived by the economy customers, works differently.
TF 4.
Claim: The \(M/G/1\) queue has Poisson arrivals, general service times, and a single server.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. In Kendall’s notation, \(M\) stands for memoryless (Poisson/exponential), \(G\) for general, and \(1\) for a single server.
TF 5.
Claim: In an \(M/M/c/K\) queue, the \(K\) denotes the number of servers.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The \(c\) denotes the number of servers. The \(K\) denotes the system capacity, i.e., the maximum number of jobs allowed in the system.