2
$\begingroup$

This question has now been asked on Operations Research Stack Exchange as it is probably better suited there.


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$
2
  • 1
    $\begingroup$ You might be better off moving this to or.stackexchange.com (don't cross post without linking). $\endgroup$ Jul 30, 2021 at 19:56
  • $\begingroup$ Thank you @MarkL.Stone for your advice and guidance. Progress can be found at OR Stack Exchange. $\endgroup$ Jul 31, 2021 at 14:58

0

You must log in to answer this question.

Browse other questions tagged .