3
$\begingroup$

This question was originally asked on Math Stack Exchange. It is probably better suited here.


Introduction

When one thinks about a queue, it is natural to want to find a policy that minimises the average long-run delay (time spent in buffer) per customer $\bar{\mathcal{D}}_{n}$. However, most problems focus on minimising the average long-run holding cost per unit time $\bar{\mathcal{H}}_{t}$. This is arguably a quantity which is much easier to work with e.g. only record customers in queue $n(\tau)$ at arrival and departures epochs as well as the time-stamp $\tau$ of the epoch. It also allows for Markov Decision Processes to solve policy over state-space $n \in \mathbb{N}_{0}$.

Problem & Motivation

It would seem like there is a dilemma: trade in the more natural objective function for a more convenient one. However, minimising both is perhaps equivalent. This is like saying if $\bar{\mathcal{D}}_n$ has a global minimum under a policy $\pi$ and sample path $\omega$ such that $\bar{\mathcal{D}}_n(\omega,\pi) \leq \bar{\mathcal{D}}_n(\omega_i,\pi_i)$ then $\bar{\mathcal{H}}_t(\omega,\pi) \leq \bar{\mathcal{H}}_t(\omega_i,\pi_i)$. This can happen if the two are related by a constant of proportionality e.g. $\bar{\mathcal{H}}_t = \phi \bar{\mathcal{D}}_n$.

I would like to try and show this to be true (this result probably already exists somewhere). To do this one would need to to the following:

  1. Show long-run delay $\mathcal{D}$ to be equivalent or proportional to long-run holding cost $\mathcal{H}$.
  2. Use $\mathcal{H}$ (or $\mathcal{D}$) and show its time-average $\bar{\mathcal{H}}_t $ to be proportional to its customer-average $\bar{\mathcal{H}}_n$.

Hence $\bar{\mathcal{D}}_n \propto \bar{\mathcal{H}}_t$.

Please assist me in either establishing whether my work holds true or where mistakes have been made. Let's proceed.

Proposed solution

Part 1: $\mathcal{H} = \mathcal{D}$

Define total holding cost at time $t$ as $$\mathcal{H}(t) = c\int_{0}^{t}n(\tau) \, d\tau $$ where $c$ is some cost weight. Without loss of generality, assume that $c=1$. Delay is a bit more tricky. Let $T_i = t_i^D - t_i^A $ denote the time spent in the buffer for the $i^{th}$ customer where $t_i^A$ denotes the instance of arrival and $t_i^D$ the instance it departs the queue (enters service). Hence, $T_i$ is the delay that the $i^{th}$ customer will experience. The issue is that at time $t$, all departed customers $i \in \{D(t)\}$ will have experienced their full delay whereas some will not: arrived but not not departed $\{A(t)\}\setminus \{D(t)\}$. Note that A(t) is the total amount of arrivals and D(t) the total departures such that $n(t) = A(t) - D(t)$ whereas $\{A(t)\}$ and $\{D(t)\}$ denotes sets that records arrived and departed customers, respectively. Note that $\forall t \in \mathbb{R}_{\geq 0}: A(t) \geq D(t)$

Hence, total delay at time $t$ is $$ \mathcal{D}(t) = c\left(\sum_{i \in \{D(t)\}} T_i + \sum_{i \in \{A(t)\}\setminus \{D(t)\}} t - t_i^A \right) $$ From the below image that has been borrowed from the cited book, the expression for total delay should be clear.

Delay in open system/queue

We know derive $\mathcal{D}(t)$ from $\mathcal{H}(t)$ (Recall $c=1$).

$$ \begin{align} \mathcal{H}(t) & = \int_{0}^t A(\tau) - D(\tau)\, d\tau \\ & = \int_{0}^t \{ A(\tau)\} \setminus \{ D(\tau) \}\, d\tau \\ & = \sum_{i \in \{A(t)\}} \int_{0}^t \boldsymbol{1}_{\{t_i^A \leq \tau \leq t_i^D \}} \, d\tau \\ & = \sum_{i \in \{A(t)\}} T_i \boldsymbol{1}_{\{t_i^D \leq t\}} + (t-t_i^A)\boldsymbol{1}_{\{t_i^D > t\}} \\ & = \sum_{i \in \{D(t)\}} T_i + \sum_{i \in \{A(t)\}\setminus \{D(t)\}} t - t_i^A\\ & = \mathcal{D}(t) \end{align} $$ That concludes part 1. I hope we have achieved equivalence in the right way without errors. From now one, we choose to work with $\mathcal{H}(t)$.

Part 2: $ \bar{\mathcal{H}}_t \propto \bar{\mathcal{H}}_n$

The average long-run holding cost per unit time is $$ \bar{\mathcal{H}}_t = \lim_{T \to \infty} \frac{1}{T} \int_{0}^T \mathcal{H}(\tau) \, d\tau $$ whereas the average long-run holding cost per customer is $$ \bar{\mathcal{H}}_n = \lim_{T \to \infty} \frac{1}{A(T)} \int_{0}^T \mathcal{H}(\tau) \, d\tau $$ where $A(T)$ is interpreted as the total customers the system has seen. Next, the following time-average result holds for an ergodic system (this can be found on page 97 of the cited book): $$ \lambda = \lim_{T\to \infty} \frac{A(T)}{T} $$ where $\lambda$ is the mean arrival rate. Using this result and assuming the system to be ergodic $$ \begin{align} \bar{\mathcal{H}}_n & = \lim_{T \to \infty} \frac{T}{A(T)} \times \lim_{T \to \infty} \frac{1}{T}\int_{0}^T \mathcal{H}(\tau) \, d\tau \\ & = \frac{\bar{\mathcal{H}}_t}{\lambda} \end{align} $$ Hence, $\bar{\mathcal{H}}_t = \lambda \bar{\mathcal{H}}_n$ such that $\bar{\mathcal{H}}_t \propto\bar{\mathcal{H}}_n$ along with the constant of proportionality having a convenient interpretation. This is probably a variant of Little's Law (chapter 6 of the book).

Conclusion

We see that a proportional relationship holds $\bar{\mathcal{H}}_t = \lambda \bar{\mathcal{H}}_n$ under the assumptions that the system is ergodic and that the long-term average effective arrival rate be a constant (time-homogeneous system).

Thank you for your time. Please feel free to also suggest improvements.


References

Harchol-Balter, Mor, Performance modeling and design of computer systems. Queueing theory in action, Cambridge: Cambridge University Press (ISBN 978-1-107-02750-3/hbk; 978-1-139-60396-6/ebook). xxiii, 548 p. (2013). ZBL1282.68007.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.