Question

Consider a single-server queueing system in which customers arrive in accordance with a renewal process. Each customer brings in a random amount of work, chosen independently according to the distribution \(G\). The server serves one customer at a time. However, the server processes work at rate \(i\) per unit time whenever there are \(i\) customers in the system. For instance, if a customer with workload 8 enters service when there are three other customers waiting in line, then if no one else arrives that customer will spend 2 units of time in service. If another customer arrives after 1 unit of time, then our customer will spend a total of \(1.8\) units of time in service provided no one else arrives. Let \(W_{i}\) denote the amount of time customer \(i\) spends in the system. Also, define \(E[W]\) by $$ E[W]=\lim _{n \rightarrow \infty}\left(W_{1}+\cdots+W_{n}\right) / n $$ and so \(E[W]\) is the average amount of time a customer spends in the system. Let \(N\) denote the number of customers that arrive in a busy period. (a) Argue that $$ E[W]=E\left[W_{1}+\cdots+W_{N}\right] / E[N] $$ Let \(L_{i}\) denote the amount of work customer \(i\) brings into the system; and so the \(L_{i}, i \geqslant 1\), are independent random variables having distribution \(G\). (b) Argue that at any time \(t\), the sum of the times spent in the system by all arrivals prior to \(t\) is equal to the total amount of work processed by time \(t .\) Hint: Consider the rate at which the server processes work. (c) Argue that $$ \sum_{i=1}^{N} W_{i}=\sum_{i=1}^{N} L_{i} $$ (d) Use Wald's equation (see Exercise 13\()\) to conclude that $$ E[W]=\mu $$ where \(\mu\) is the mean of the distribution \(G .\) That is, the average time that customers spend in the system is equal to the average work they bring to the system.

Short answer

In this single-server queueing system, we derived important relationships and used Wald's Equation to show that the average time customers spend in the system (\(E[W]\)) is equal to the average work they bring to the system (\(\mu\)). Using the definitions of busy periods and the fact that the server processes work at a rate depending on the number of customers, we established that the total amount of time spent in the system is equal to the total work brought by customers.

Step-by-step solution

Deriving E[W] relationship

Based on the given information, we are provided the definition of \(E[W]\): $$ E[W]=\lim _{n \rightarrow \infty}\left(W_{1}+\cdots+W_{n}\right) / n $$ Now, we need to show that: $$ E[W]=E\left[W_{1}+\cdots+W_{N}\right] / E[N] $$ We know that \(W_i\) denotes the time customer \(i\) spends in the system. Based on the definition of a busy period, we will have \(N\) customers by the end of a single busy period. So, if we calculate the sum of the amount of time spent by all \(N\) customers and divide it by the total number of customers \(N\), we get the average time spent by a customer (which is \(E[W]\)). Therefore, we get: $$ E[W]=E\left[W_{1}+\cdots+W_{N}\right] / E[N] $$

Equal Time Spent and Work Processed

We are given that \(L_i\) denotes the amount of work customer \(i\) brings into the system, and the server processes work at a rate \(i\) per unit time whenever there are \(i\) customers in the system. Since the customers are served one at a time and the server processing rate depends on the number of customers, we can argue that the sum of the times spent in the system by all arrivals prior to \(t\) is equal to the total amount of work processed by time \(t\).

Deriving Relationship between Time Spent and Work Brought

Now we want to show that: $$ \sum_{i=1}^{N} W_{i}=\sum_{i=1}^{N} L_{i} $$ Since both the time spent \(W_i\) and the work brought \(L_i\) are accumulated, we can say that the total time spent in the system up to the \(N\) customers is equal to the total work brought by \(N\) customers to the system.

Using Wald's Equation

Now we will use Wald's Equation to derive the relationship between \(E[W]\) and \(\mu\), the mean of distribution \(G\). Wald's Equation states that for a sequence of IID random variables \(X_i\) and a stopping time \(N\): $$ E\left[\sum_{i=1}^{N} X_{i}\right] = E[N]E[X_1] $$ We can modify Wald's Equation in terms of W and L: $$ E\left[\sum_{i=1}^{N} W_{i}\right] = E\left[\sum_{i=1}^{N} L_{i}\right] $$ Then, we divide both sides by \(E[N]\) and get: $$ E[W]=\frac{E\left[\sum_{i=1}^{N} W_{i}\right]}{E[N]}=\frac{E\left[\sum_{i=1}^{N} L_{i}\right]}{E[N]}=\mu $$ where \(\mu\) is the mean of the distribution \(G\). Thus, we have shown that \(E[W]=\mu\), meaning the average time customers spend in the system is equal to the average work they bring to the system.