This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Overlap Times in the G​IB/G​I/∞GI^{B}/GI/\infty Queue

Sergio Palomo
Systems Engineering
Cornell University
[email protected]    Jamol Pender 111Corresponding Author
School of Operations Research and Information Engineering
Cornell University
[email protected]
Abstract

Overlap times have been studied as a way of understanding the time of interaction between customers in a service facility. Most of the previous analysis relies on the single jump assumption for arrivals, which implies the queue increases by one for each arrival epoch. In this paper, we relax the single arrival assumption and explore the impact of having batch arrivals. Unfortunately, with batch arrivals it is not clear how one measures an overlap time between batches of customers. Thus, we develop two ways of capturing the notion of an overlap time in a batch setting and derive exact results in the infinite server queue with batch arrivals. Finally, we derive new results for analyzing overlap times of more than two batches.

1 Introduction

The study of overlap times has emerged as a way of understanding how customers interact in service systems. Recently, overlap times have been analyzed in infinite server queues, single server queues, and multi-server queues in [7, 13, 14, 9] respectively. This has been done mostly in Markovian cases since the analysis is a bit easier. In [7] the overlap times were used as a way of computing a new R0R_{0} value for understanding infection rates in compartmentalized epidemic models in relation to COVID-19 transmission. Palomo and Pender [13] proves that the overlap distribution is exponential for the M/M/1 queue and [14] studies the overlap distribution for infinite server queues that have renewal arrivals and i.i.d service times from a renewal process. Finally, Ko and Xu [9] uses fluid limits to approximate the overlapping time of customers in multi-server queues with time varying arrival rates.

Beyond infectious disease transmission and design of service systems there are other applications where overlap times are important. One application is public transportation like buses and subways. In these transportation settings, several passengers get on the bus or subway in batches and ride for some time to their destination. Thus, it is important to study the impact of batch arrivals to get a better understanding of how infectious disease spreads in these transportation settings.

Fortunately, the study of batch arrival queues has increased significantly in recent years to due the emerging application of cloud-based data storage and processing. In this setting, the batches of jobs arriving to the system are collections of jobs submitted simultaneously by a user. These jobs are then served by each being processed individually and the results are returned to the user. For more discussion, see works such as Lu et al. [10], Pender and Phung-Duc [19], Xie et al. [23], Yekkehkhany et al. [24] and references therein. Another relevant application in the context of infectious disease modeling is modeling the number infections of COVID-19. See for example Kaplan [8], Morozova et al. [12], Palomo et al. [15]. In this setting, the results for patients who potentially have COVID-19 arrive in a large batch to be processed at a facility. Moreover, the data that we observe from COVID-19 is also of batch form as counts are made daily. Finally, an emerging application of batch queues is in context of autonomous vehicles moving in platoons (batches) down highways and roads, e.g. Mirzaeian et al. [11], Hampshire et al. [5]. Such applications also serve as the inspiration for the batch arrival queue staffing problem studied by Daw et al. [3].

In this work, we study overlap times for the G​IB/G​I/∞GI^{B}/GI/\infty queue. Our results on the G​IB/G​I/∞GI^{B}/GI/\infty queue also serve as approximations and lower bounds for systems of finite capacity such as the G​IB/G​I/CGI^{B}/GI/C queue. For example, consider the recent work on multi-server jobs, which are queueing systems where collections of jobs arrive together and also have a requirement that they must start together (see, e.g., Rumyantsev and Morozov [20], Pender and Ko [18], Afanaseva et al. [1], Grosof et al. [4], Weng and Wang [22], Hong and Wang [6], Wang et al. [21], and references therein). The simultaneous start requirement is a salient model feature relative to batch arrival many server queues, but if there were infinitely many servers available then these models reduce to one another. The multi-server setting model is known to be quite challenging to analyze, so we offer our following analysis in the unlimited server setting to understand the challenges and provide insights about more complicated models.

In what follows we describe the contributions of our work and how the rest of the paper is organized.

1.1 Contributions of the Paper

  • •

    We derive explicit expressions for the steady state distribution for the overlap time for individual customers that are exactly kk batches apart.

  • •

    We derive exact expressions for the tail distribution of the overlap time when we measure overlap in the first of each batch or last of each batch setting.

  • •

    We also derive explicit expressions for the tail distribution of the overlap time when there are more than two customers or two batches.

1.2 Organization of Paper

In Section 2, we describe the stochastic model that we will use in this work and the definition of overlap times. We derive an exact expression for describing the overlap times for a pair of individual customers in the infinite server queue with batch arrivals i.e the G​IB/G​I/∞GI^{B}/GI/\infty queue. We use this equation to compute the steady state distribution of the overlap time of customers that are kk batches apart. In Section 3, we also analyze the overlap times from a batch perspective. In particular we analyze two ways of comparing a batch. The first is the first of each batch to leave and the second is the last of each batch to leave. In Section 4, we analyze the overlap times of when there are more than two customers. Finally in Section 5, we provide a conclusion and some future research directions.

2 Infinite Server Overlap Times

In this section, we study the infinite server queue with the intention of understanding how much time do adjacent customers spend in the system together. A similar type of analysis has been completed Kang et al. [7], Palomo and Pender [13, 14]. Here we consider the G​IBGI^{B}/GI/∞\infty queue where we let AiA_{i} be the arrival time of the it​hi^{th} batch of customers, the inter-arrival time between the it​hi^{th} and (i+1)t​h(i+1)^{th} batches is given by Ai+1−AiA_{i+1}-A_{i}. We assume the inter-arrival times are i.i.d with cumulative distribution function (cdf) H​(x)H(x). For convenience, we define hk​(x)h_{k}(x) as the distribution of a sum of kk inter-arrival times. We also assume that S(i,j)S_{(i,j)} be the service time of the it​hi^{th} customer in the jt​hj^{th} batch and the service times are i.i.d with cdf G​(x)G(x). Thus, the departure time for the jt​hj^{th} customer in the nt​hn^{th} batch is given by the following expression

D(j,n)\displaystyle D_{(j,n)} =\displaystyle= S(j,n)+An.\displaystyle S_{(j,n)}+A_{n}. (1)

Given the arrival and departure time for each customer, it is possible to describe the overlap time between any pair of customers. The overlap time between the jt​hj^{th} customer in the nt​hn^{th} batch and ℓt​h\ell^{th} customer in the (n+k)t​h(n+k)^{th} batch is given by

O(j,n),(ℓ,n+k)\displaystyle O_{(j,n),(\ell,n+k)} =\displaystyle= (min⁡(D(j,n),D(ℓ,n+k))−An+k)+\displaystyle\left(\min(D_{(j,n)},D_{(\ell,n+k)})-A_{n+k}\right)^{+} (2)
=\displaystyle= (min⁡(An+S(j,n),An+k+S(ℓ,n+k))−An+k)+\displaystyle\left(\min(A_{n}+S_{(j,n)},A_{n+k}+S_{(\ell,n+k)})-A_{n+k}\right)^{+} (3)
=\displaystyle= ((D(j,n)−An+k)+∧S(ℓ,n+k))\displaystyle\left((D_{(j,n)}-A_{n+k})^{+}\wedge S_{(\ell,n+k)}\right) (4)
=\displaystyle= ((S(j,n)+An−An+k)+∧S(ℓ,n+k))\displaystyle\left((S_{(j,n)}+A_{n}-A_{n+k})^{+}\wedge S_{(\ell,n+k)}\right) (5)
=\displaystyle= ((S(j,n)−(An+k−An))+∧S(ℓ,n+k)).\displaystyle\left((S_{(j,n)}-\left(A_{n+k}-A_{n}\right))^{+}\wedge S_{(\ell,n+k)}\right). (6)
Theorem 2.1.

Let Oj,k,ℓO_{j,k,\ell} have the steady state distribution of O(j,n),(ℓ,n+k)O_{(j,n),(\ell,n+k)} in the G​IB/G​I/∞GI^{B}/GI/\infty queue, 𝒮\mathcal{S} and 𝒮~\tilde{\mathcal{S}} be two independent service times with cdf G​(x)G(x), and let ℙ​(B=j)=pj\mathbb{P}(B=j)=p_{j}, then the tail distribution of Oj,k,ℓ=limn→∞O(j,n),(ℓ,n+k)O_{j,k,\ell}=\lim_{n\to\infty}O_{(j,n),(\ell,n+k)} is given by

ℙ​(Oj,k,ℓ>t)={G¯​(t),for ​k=0,j=ℓ,ℓ≥1G¯​(t)2,for ​k=0,j≠ℓ,ℓ≥1G¯​(t)​∫0∞G¯​(t+x)​hk​(x)​𝑑x,for ​k>0,j≠ℓ,ℓ≥1}\mathbb{P}\left(O_{j,k,\ell}>t\right)=\left\{\begin{array}[]{lr}\overline{G}(t),&\text{for }k=0,j=\ell,\ell\geq 1\\ \overline{G}(t)^{2},&\text{for }k=0,j\neq\ell,\ell\geq 1\\ \overline{G}(t)\int^{\infty}_{0}\overline{G}\left(t+x\right)h_{k}(x)dx,&\text{for }k>0,j\neq\ell,\ell\geq 1\end{array}\right\}

where hk​(x)h_{k}(x) is the density of the sum of kk i.i.d inter-arrival times.

Proof.

In the first condition where we have k=0,j=ℓ,ℓ≥1k=0,j=\ell,\ell\geq 1, this corresponds to a self-overlap, which is precisely equal to the tail distribution of the service time. The second condition where we have k=0,j≠ℓ,ℓ≥1k=0,j\neq\ell,\ell\geq 1, this corresponds to an overlap of two customers in the same batch. Thus, the probability that they are both around by time tt is equal to the square of the tail distribution of the service time. Finally, the last condition is exactly similar to the case with no batches, which is given in Palomo and Pender [14]. This completes the proof. ∎

Theorem 2.1 provides the distribution of the case where we are comparing the overlap between individual customers. However, we might be interested in the overlap of a batch itself. In the sequel, we provide an analysis of this batch perspective.

3 The Batch Perspective

Unfortunately in the batch setting, there is not a unique way to define an overlap time between batches of customers. In what follows, we describe two ways to define an overlap between customers in a batch. Each one yields different expressions for calculating the tail distribution of the respective overlap time definition. We recognize that there are many more ways to define an interaction or overlap between a batch of customers, however, these two are quite natural. However, before we derive the overlap times for the batch queues, we prove a simple result about the tail distribution of the maximum and minimum of a random sequence of random variables.

Lemma 3.1.

Let BB be a discrete random variable on the positive integers i.e. {1,2,3​…}\{1,2,3...\} with probabilities {p1,p2,…​pnp_{1},p_{2},...p_{n}} and let X=(X1,X2,…,XB)X=(X_{1},X_{2},...,X_{B}) be a random vector with random size given by the random variable BB. Then, we have the following distributions for min⁡(X)\min(X) and max⁡(X)\max(X)

ℙ​(min⁡(X)>t)\displaystyle\mathbb{P}\left(\min(X)>t\right) =\displaystyle= ∑j=1∞pj​G¯​(t)j\displaystyle\sum^{\infty}_{j=1}p_{j}\overline{G}(t)^{j} (7)

and

ℙ​(max⁡(X)>t)\displaystyle\mathbb{P}\left(\max(X)>t\right) =\displaystyle= 1−∑j=1∞pj​G​(t)j.\displaystyle 1-\sum^{\infty}_{j=1}p_{j}G(t)^{j}. (8)
Proof.

For the minimum we have that

ℙ​(min⁡(X)>t)\displaystyle\mathbb{P}\left(\min(X)>t\right) =\displaystyle= ∑j=1∞ℙ​(min⁡(X)>t|B=j)⋅ℙ​(B=j)\displaystyle\sum^{\infty}_{j=1}\mathbb{P}\left(\min(X)>t|B=j\right)\cdot\mathbb{P}\left(B=j\right)
=\displaystyle= ∑j=1∞∏i=1jℙ​(Xi>t)⋅pj\displaystyle\sum^{\infty}_{j=1}\prod^{j}_{i=1}\mathbb{P}\left(X_{i}>t\right)\cdot p_{j}
=\displaystyle= ∑j=1∞pj​G¯​(t)j.\displaystyle\sum^{\infty}_{j=1}p_{j}\overline{G}(t)^{j}.

Finally, for the maximum we have that

ℙ​(max⁡(X)>t)\displaystyle\mathbb{P}\left(\max(X)>t\right) =\displaystyle= 1−ℙ​(max⁡(X)≤t)\displaystyle 1-\mathbb{P}\left(\max(X)\leq t\right)
=\displaystyle= 1−∑j=1∞ℙ​(max⁡(X)≤t|B=j)⋅ℙ​(B=j)\displaystyle 1-\sum^{\infty}_{j=1}\mathbb{P}\left(\max(X)\leq t|B=j\right)\cdot\mathbb{P}\left(B=j\right)
=\displaystyle= ∑j=1∞∏i=1jℙ​(Xi≤t)⋅pj\displaystyle\sum^{\infty}_{j=1}\prod^{j}_{i=1}\mathbb{P}\left(X_{i}\leq t\right)\cdot p_{j}
=\displaystyle= 1−∑j=1∞pj​G​(t)j.\displaystyle 1-\sum^{\infty}_{j=1}p_{j}G(t)^{j}.

∎

The reader should note two things. First, when the batch size is one with probability one, then this reduces to the directly to the tail distribution of the random variable and this holds for either the max or min since they are equivalent for one random variable. Second, we note that when the random variable BB has finite support, then the infinite sums reduce to finite ones. The finite support of the random variable BB is important from a computational perspective since it often can be the difference between an exact expression and an approximation of it.

3.1 Last of Each Batch to Leave

The first method for capturing overlap between customers in batches is called ”last of each batch to leave”. This method defines an overlap for a batch as any time that any of customers of each batch overlap. Mathematically, if we define D→nBn=(Dn,1,Dn,2,…,Dn,Bn)\vec{D}_{n}^{B_{n}}=(D_{n,1},D_{n,2},...,D_{n,B_{n}}) as the vector of departure times of the nt​hn^{th} batch and S→nBn=(Sn,1,Sn,2,…,Sn,Bn)\vec{S}_{n}^{B_{n}}=(S_{n,1},S_{n,2},...,S_{n,B_{n}}) as the vector of service times of the nt​hn^{th} batch, then we have the following expression of the overlap time of the ”last of each batch to leave”

On,n+k\displaystyle O_{n,n+k} =\displaystyle= (min⁡(max⁡(D→nBn),max⁡(D→n+kBn+k))−An+k)+\displaystyle\left(\min\left(\max\left(\vec{D}_{n}^{B_{n}}\right),\max\left(\vec{D}_{n+k}^{B_{n+k}}\right)\right)-A_{n+k}\right)^{+} (9)
=\displaystyle= ((max⁡(S→nBn)−(An+k−An))+∧max⁡(S→n+kBn+k)).\displaystyle\left(\left(\max\left(\vec{S}_{n}^{B_{n}}\right)-\left(A_{n+k}-A_{n}\right)\right)^{+}\wedge\max\left(\vec{S}_{n+k}^{B_{n+k}}\right)\right). (10)
Theorem 3.2.

Let OkO_{k} be the distribution of On,n+kO_{n,n+k} for all values of nn in the G​IB/G​I/∞GI^{B}/GI/\infty queue and let 𝒜k\mathcal{A}_{k}, be the sum of k i.i.d inter-arrival times from a renewal process with density hk​(x)h_{k}(x), then the tail distribution of OkO_{k} under the last of each batch to leave overlap process is given by

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= (1−𝔼​[G​(t+𝒜k)ℬ])⋅(1−𝔼​[G​(t)ℬ]).\displaystyle\left(1-\mathbb{E}\left[G\left(t+\mathcal{A}_{k}\right)^{\mathcal{B}}\right]\right)\cdot\left(1-\mathbb{E}\left[G(t)^{\mathcal{B}}\right]\right). (11)
Proof.

First, we need to decompose the overlap probability into two probabilities by using a property of the minimum of two independent random variables i.e.

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= ℙ​(((max⁡(S→nBn)−(An+k−An))+∧max⁡(S→n+kBn+k))>t)\displaystyle\mathbb{P}\left(\left(\left(\max\left(\vec{S}_{n}^{B_{n}}\right)-\left(A_{n+k}-A_{n}\right)\right)^{+}\wedge\max\left(\vec{S}_{n+k}^{B_{n+k}}\right)\right)>t\right)
=\displaystyle= ℙ​((max⁡(S→nBn)−(An+k−An))+>t)⋅ℙ​(max⁡(S→n+kBn+k)>t)\displaystyle\mathbb{P}\left(\left(\max\left(\vec{S}_{n}^{B_{n}}\right)-\left(A_{n+k}-A_{n}\right)\right)^{+}>t\right)\cdot\mathbb{P}\left(\max\left(\vec{S}_{n+k}^{B_{n+k}}\right)>t\right)
=\displaystyle= ℙ​(max⁡(S→nBn)>t+An+k−An)⋅ℙ​(max⁡(S→n+kBn+k)>t)\displaystyle\mathbb{P}\left(\max\left(\vec{S}_{n}^{B_{n}}\right)>t+A_{n+k}-A_{n}\right)\cdot\mathbb{P}\left(\max\left(\vec{S}_{n+k}^{B_{n+k}}\right)>t\right)
=\displaystyle= 𝔼​[1−∑j=1∞pj​G​(t+An+k−An)j]⋅(1−∑j=1∞pj​G​(t)j)\displaystyle\mathbb{E}\left[1-\sum^{\infty}_{j=1}p_{j}G\left(t+A_{n+k}-A_{n}\right)^{j}\right]\cdot\left(1-\sum^{\infty}_{j=1}p_{j}G\left(t\right)^{j}\right)
=\displaystyle= (1−∑j=1∞pj​𝔼​[G​(t+An+k−An)j])⋅(1−∑j=1∞pj​G​(t)j)\displaystyle\left(1-\sum^{\infty}_{j=1}p_{j}\mathbb{E}\left[G\left(t+A_{n+k}-A_{n}\right)^{j}\right]\right)\cdot\left(1-\sum^{\infty}_{j=1}p_{j}G\left(t\right)^{j}\right)
=\displaystyle= (1−∑j=1∞pj​(∫0∞G​(t+x)j​hk​(x)​𝑑x))⋅(1−∑j=1∞pj​G​(t)j)\displaystyle\left(1-\sum^{\infty}_{j=1}p_{j}\left(\int^{\infty}_{0}G\left(t+x\right)^{j}h_{k}(x)dx\right)\right)\cdot\left(1-\sum^{\infty}_{j=1}p_{j}G\left(t\right)^{j}\right)
=\displaystyle= (1−𝔼​[G​(t+𝒜k)ℬ])⋅(1−𝔼​[G​(t)ℬ]).\displaystyle\left(1-\mathbb{E}\left[G\left(t+\mathcal{A}_{k}\right)^{\mathcal{B}}\right]\right)\cdot\left(1-\mathbb{E}\left[G(t)^{\mathcal{B}}\right]\right).

This completes the proof. ∎

Corollary 3.3.

Let OkO_{k} be the distribution of On,n+kO_{n,n+k} for all values of nn in the Mℬ/M/∞M^{\mathcal{B}}/M/\infty queue, then the tail distribution of OkO_{k} under the last of each batch to leave setting is given by

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= (1−𝔼​[∑m=0ℬ(ℬm)​(−1)m​e−μ​t​m​(λλ+μ​m)k])⋅(1−𝔼​[(1−e−μ​t)ℬ]).\displaystyle\left(1-\mathbb{E}\left[\sum^{\mathcal{B}}_{m=0}{\mathcal{B}\choose m}(-1)^{m}e^{-\mu tm}\left(\frac{\lambda}{\lambda+\mu m}\right)^{k}\right]\right)\cdot\left(1-\mathbb{E}\left[(1-e^{-\mu t})^{\mathcal{B}}\right]\right). (12)
Proof.

Using the previous result in Theorem 3.2, we have that

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right)
=\displaystyle= (1−∑j=1∞pj​∫0∞(1−e−μ​(t+x))j​(λ​x)k−1(k−1)!​λ​e−λ​x​𝑑x)⋅(1−∑j=1∞pj​(1−e−μ​t)j)\displaystyle\left(1-\sum^{\infty}_{j=1}p_{j}\int^{\infty}_{0}\left(1-e^{-\mu(t+x)}\right)^{j}\frac{(\lambda x)^{k-1}}{(k-1)!}\lambda e^{-\lambda x}dx\right)\cdot\left(1-\sum^{\infty}_{j=1}p_{j}(1-e^{-\mu t})^{j}\right)
=\displaystyle= (1−∑j=1∞pj​∫0∞(∑m=0j(jm)​(−1)m​e−μ​(t+x)​m)​(λ​x)k−1(k−1)!​λ​e−λ​x​𝑑x)⋅(1−∑j=1∞pj​(1−e−μ​t)j)\displaystyle\left(1-\sum^{\infty}_{j=1}p_{j}\int^{\infty}_{0}\left(\sum^{j}_{m=0}{j\choose m}(-1)^{m}e^{-\mu(t+x)m}\right)\frac{(\lambda x)^{k-1}}{(k-1)!}\lambda e^{-\lambda x}dx\right)\cdot\left(1-\sum^{\infty}_{j=1}p_{j}(1-e^{-\mu t})^{j}\right)
=\displaystyle= (1−∑j=1∞pj​∑m=0j(jm)​(−1)m​∫0∞e−μ​(t+x)​m​(λ​x)k−1(k−1)!​λ​e−λ​x​𝑑x)⋅(1−∑j=1∞pj​(1−e−μ​t)j)\displaystyle\left(1-\sum^{\infty}_{j=1}p_{j}\sum^{j}_{m=0}{j\choose m}(-1)^{m}\int^{\infty}_{0}e^{-\mu(t+x)m}\frac{(\lambda x)^{k-1}}{(k-1)!}\lambda e^{-\lambda x}dx\right)\cdot\left(1-\sum^{\infty}_{j=1}p_{j}(1-e^{-\mu t})^{j}\right)
=\displaystyle= (1−∑j=1∞pj​∑m=0j(jm)​(−1)m​e−μ​t​m​(λλ+μ​m)k)⋅(1−∑j=1∞pj​(1−e−μ​t)j)\displaystyle\left(1-\sum^{\infty}_{j=1}p_{j}\sum^{j}_{m=0}{j\choose m}(-1)^{m}e^{-\mu tm}\left(\frac{\lambda}{\lambda+\mu m}\right)^{k}\right)\cdot\left(1-\sum^{\infty}_{j=1}p_{j}(1-e^{-\mu t})^{j}\right)
=\displaystyle= (1−𝔼​[∑m=0ℬ(ℬm)​(−1)m​e−μ​t​m​(λλ+μ​m)k])⋅(1−𝔼​[(1−e−μ​t)ℬ]).\displaystyle\left(1-\mathbb{E}\left[\sum^{\mathcal{B}}_{m=0}{\mathcal{B}\choose m}(-1)^{m}e^{-\mu tm}\left(\frac{\lambda}{\lambda+\mu m}\right)^{k}\right]\right)\cdot\left(1-\mathbb{E}\left[(1-e^{-\mu t})^{\mathcal{B}}\right]\right).

This completes the proof. ∎

Corollary 3.4.

Let OkO_{k} be the distribution of On,n+kO_{n,n+k} for all values of nn in the G​IB/D/∞GI^{B}/D/\infty queue, then the tail distribution of OkO_{k} under the last of each batch to leave setting is given by

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= 𝔽(k)​((Δ−t)+)\displaystyle\mathbb{F}^{(k)}\left((\Delta-t)^{+}\right) (13)

where 𝔽(k)​(⋅)\mathbb{F}^{(k)}(\cdot) is the kk-fold convolution of the inter-arrival distribution F​(x)F(x).

Proof.

Using the previous result in Theorem 3.2, we have that

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= ℙ​(((max⁡(S→nBn)−(An+k−An))+∧max⁡(S→n+kBn+k))>t)\displaystyle\mathbb{P}\left(\left(\left(\max\left(\vec{S}_{n}^{B_{n}}\right)-\left(A_{n+k}-A_{n}\right)\right)^{+}\wedge\max\left(\vec{S}_{n+k}^{B_{n+k}}\right)\right)>t\right)
=\displaystyle= ℙ​((Δ−(An+k−An))+>t)⋅ℙ​(Δ>t)\displaystyle\mathbb{P}\left(\left(\Delta-\left(A_{n+k}-A_{n}\right)\right)^{+}>t\right)\cdot\mathbb{P}\left(\Delta>t\right)
=\displaystyle= 𝔽(k)​((Δ−t)+).\displaystyle\mathbb{F}^{(k)}\left((\Delta-t)^{+}\right).

This completes the proof. ∎

3.2 First of Each Batch to Leave

The second method for capturing overlap between customers in batches is called ”first of each batch to leave”. This method defines an overlap for a batch as any time that all of the customers of each batch overlap. Mathematically, we have the following expression of the overlap time of the ”first of each batch to leave”

On,n+k\displaystyle O_{n,n+k} =\displaystyle= (min⁡(min⁡(D→nBn),min⁡(D→n+kBn+k))−An+k)+\displaystyle\left(\min\left(\min\left(\vec{D}_{n}^{B_{n}}\right),\min\left(\vec{D}_{n+k}^{B_{n+k}}\right)\right)-A_{n+k}\right)^{+} (14)
=\displaystyle= ((min⁡(S→nBn)−(An+k−An))+∧min⁡(S→n+kBn+k)).\displaystyle\left(\left(\min\left(\vec{S}_{n}^{B_{n}}\right)-\left(A_{n+k}-A_{n}\right)\right)^{+}\wedge\min\left(\vec{S}_{n+k}^{B_{n+k}}\right)\right). (15)
Theorem 3.5.

Let OkO_{k} be the distribution of On,n+kO_{n,n+k} for all values of nn in the G​IB/G​I/∞GI^{B}/GI/\infty queue and 𝒜k\mathcal{A}_{k}, be the sum of k i.i.d inter-arrival times from a renewal process with density hk​(x)h_{k}(x), then the tail distribution of OkO_{k} under the first of each batch to leave setting is given by

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= 𝔼​[G¯​(t+𝒜k)ℬ]⋅𝔼​[G¯​(t)ℬ].\displaystyle\mathbb{E}\left[\overline{G}(t+\mathcal{A}_{k})^{\mathcal{B}}\right]\cdot\mathbb{E}\left[\overline{G}(t)^{\mathcal{B}}\right]. (16)
Proof.

First, we need to decompose the overlap probability into two probabilities by using a property of the minimum of two independent random variables i.e.

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= ℙ​(((min⁡(S→nBn)−(An+k−An))+∧min⁡(S→n+kBn+k))>t)\displaystyle\mathbb{P}\left(\left(\left(\min\left(\vec{S}_{n}^{B_{n}}\right)-\left(A_{n+k}-A_{n}\right)\right)^{+}\wedge\min\left(\vec{S}_{n+k}^{B_{n+k}}\right)\right)>t\right)
=\displaystyle= ℙ​((min⁡(S→nBn)−(An+k−An))+>t)⋅ℙ​(min⁡(S→n+kBn+k)>t)\displaystyle\mathbb{P}\left(\left(\min\left(\vec{S}_{n}^{B_{n}}\right)-\left(A_{n+k}-A_{n}\right)\right)^{+}>t\right)\cdot\mathbb{P}\left(\min\left(\vec{S}_{n+k}^{B_{n+k}}\right)>t\right)
=\displaystyle= ℙ​(min⁡(S→nBn)>t+An+k−An)⋅ℙ​(min⁡(S→n+kBn+k)>t)\displaystyle\mathbb{P}\left(\min\left(\vec{S}_{n}^{B_{n}}\right)>t+A_{n+k}-A_{n}\right)\cdot\mathbb{P}\left(\min\left(\vec{S}_{n+k}^{B_{n+k}}\right)>t\right)
=\displaystyle= 𝔼​[∑j=1∞pj​G¯​(t+An+k−An)j]⋅(∑j=1∞pj​G¯​(t)j)\displaystyle\mathbb{E}\left[\sum^{\infty}_{j=1}p_{j}\overline{G}\left(t+A_{n+k}-A_{n}\right)^{j}\right]\cdot\left(\sum^{\infty}_{j=1}p_{j}\overline{G}\left(t\right)^{j}\right)
=\displaystyle= ∑j=1∞pj​𝔼​[G¯​(t+An+k−An)j]⋅(∑j=1∞pj​G¯​(t)j)\displaystyle\sum^{\infty}_{j=1}p_{j}\mathbb{E}\left[\overline{G}\left(t+A_{n+k}-A_{n}\right)^{j}\right]\cdot\left(\sum^{\infty}_{j=1}p_{j}\overline{G}\left(t\right)^{j}\right)
=\displaystyle= ∑j=1∞pj​𝔼​[G¯​(t+𝒜k)j]⋅(∑j=1∞pj​G¯​(t)j)\displaystyle\sum^{\infty}_{j=1}p_{j}\mathbb{E}\left[\overline{G}\left(t+\mathcal{A}_{k}\right)^{j}\right]\cdot\left(\sum^{\infty}_{j=1}p_{j}\overline{G}\left(t\right)^{j}\right)
=\displaystyle= ∑j=1∞pj​(∫0∞G¯​(t+x)j​hk​(x)​𝑑x)⋅(∑j=1∞pj​G¯​(t)j)\displaystyle\sum^{\infty}_{j=1}p_{j}\left(\int^{\infty}_{0}\overline{G}\left(t+x\right)^{j}h_{k}(x)dx\right)\cdot\left(\sum^{\infty}_{j=1}p_{j}\overline{G}\left(t\right)^{j}\right)
=\displaystyle= 𝔼​[G¯​(t+𝒜k)ℬ]⋅𝔼​[G¯​(t)ℬ].\displaystyle\mathbb{E}\left[\overline{G}(t+\mathcal{A}_{k})^{\mathcal{B}}\right]\cdot\mathbb{E}\left[\overline{G}(t)^{\mathcal{B}}\right].

This completes the proof. ∎

Corollary 3.6.

Let OkO_{k} be the distribution of On,n+kO_{n,n+k} for all values of nn in the MB/M/∞M^{B}/M/\infty queue and 𝒜k\mathcal{A}_{k}, be the sum of k i.i.d inter-arrival times from a renewal process with density hk​(x)h_{k}(x), then the tail distribution of OkO_{k} under the first of each batch to leave setting is given by

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= 𝔼​[e−μ​t​ℬ​(λλ+μ​ℬ)k]⋅𝔼​[e−μ​t​ℬ].\displaystyle\mathbb{E}\left[e^{-\mu t\mathcal{B}}\left(\frac{\lambda}{\lambda+\mu\mathcal{B}}\right)^{k}\right]\cdot\mathbb{E}\left[e^{-\mu t\mathcal{B}}\right]. (17)
Proof.

Using the previous result in Theorem 3.5, we have that

ℙ​(Ok>t)\displaystyle\mathbb{P}\left(O_{k}>t\right) =\displaystyle= 𝔼​[∑j=1∞pj​e−μ​j​(t+An+k−An)]⋅(∑j=1∞pj​e−μ​j​t)\displaystyle\mathbb{E}\left[\sum^{\infty}_{j=1}p_{j}e^{-\mu j(t+A_{n+k}-A_{n})}\right]\cdot\left(\sum^{\infty}_{j=1}p_{j}e^{-\mu jt}\right)
=\displaystyle= ∑j=1∞pj​e−μ​j​t​𝔼​[e−μ​j​(An+k−An)]⋅(∑j=1∞pj​e−μ​j​t)\displaystyle\sum^{\infty}_{j=1}p_{j}e^{-\mu jt}\mathbb{E}\left[e^{-\mu j(A_{n+k}-A_{n})}\right]\cdot\left(\sum^{\infty}_{j=1}p_{j}e^{-\mu jt}\right)
=\displaystyle= ∑j=1∞pj​e−μ​j​t​𝔼​[e−μ​j​𝒜]k⋅(∑j=1∞pj​e−μ​j​t)\displaystyle\sum^{\infty}_{j=1}p_{j}e^{-\mu jt}\mathbb{E}\left[e^{-\mu j\mathcal{A}}\right]^{k}\cdot\left(\sum^{\infty}_{j=1}p_{j}e^{-\mu jt}\right)
=\displaystyle= 𝔼​[e−μ​t​ℬ​(λλ+μ​ℬ)k]⋅𝔼​[e−μ​t​ℬ].\displaystyle\mathbb{E}\left[e^{-\mu t\mathcal{B}}\left(\frac{\lambda}{\lambda+\mu\mathcal{B}}\right)^{k}\right]\cdot\mathbb{E}\left[e^{-\mu t\mathcal{B}}\right].

This completes the proof. ∎

4 More Than A Pair Setting

Our above analysis for overlap times only characterizes the overlap for two customers or two batches. In some settings it may be interesting to characterize the behavior of more than a pair of customers or a pair of batches. We analyze the setting of more than two customers in what follows below.

4.1 Individual Customer Perspective

For our first result, we characterize the overlap time of an arbitrary number of customers in the G​I/G​I/∞GI/GI/\infty queue. In particular, the overlap time for a k-tuple of customers in the G​I/G​I/∞GI/GI/\infty queue, which is denoted by On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}}, can be computed by the following expressions

On1,n2,…,nk\displaystyle O_{n_{1},n_{2},\dots,n_{k}} =\displaystyle= (min⁡(Dn1,Dn2,⋯,Dnk)−Ank)+\displaystyle\left(\min(D_{n_{1}},D_{n_{2}},\cdots,D_{n_{k}})-A_{n_{k}}\right)^{+}
=\displaystyle= (min⁡(An1+Sn1,…,Anj+Snj,Ank+Snk)−Ank)+\displaystyle\left(\min(A_{n_{1}}+S_{n_{1}},\dots,A_{n_{j}}+S_{n_{j}},A_{n_{k}}+S_{n_{k}})-A_{n_{k}}\right)^{+}
=\displaystyle= (Sn1+An1−Ank)+∧⋯∧(Snj+Anj−Ank)+∧Snk.\displaystyle(S_{n_{1}}+A_{n_{1}}-A_{n_{k}})^{+}\bm{\wedge}\cdots\bm{\wedge}(S_{n_{j}}+A_{n_{j}}-A_{n_{k}})^{+}\bm{\wedge}S_{n_{k}}.

First, note that the distance between any two pairs of customers is arbitrary. Moreover, unlike the two customer case, we observe that the random variables are not independent anymore. This is because the inter-arrival times are connected in each of the customers except for the last one, which only has a service time. Nonetheless, in the exponential setting, we can still show that the arrival process only serves to determine the constants and not the functional form of the overlap distribution.

Theorem 4.1.

Let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the G​I/G​I/∞GI/GI/\infty queue, then the tail distribution of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= 𝔼​[∏j=1kG¯​(t+(Ank−Anj))].\displaystyle\mathbb{E}\left[\prod^{k}_{j=1}\overline{G}\left(t+(A_{n_{k}}-A_{n_{j}})\right)\right]. (18)
Proof.
ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right)
=\displaystyle= ℙ​((Sn1+An1−Ank)+∧⋯∧(Snj+Anj−Ank)+∧Snk>t)\displaystyle\mathbb{P}\left((S_{n_{1}}+A_{n_{1}}-A_{n_{k}})^{+}\bm{\wedge}\cdots\bm{\wedge}(S_{n_{j}}+A_{n_{j}}-A_{n_{k}})^{+}\bm{\wedge}S_{n_{k}}>t\right)
=\displaystyle= ℙ​(Sn1+An1−Ank>t,…,Snj+Anj−Ank>t,Snk>t)\displaystyle\mathbb{P}\left(S_{n_{1}}+A_{n_{1}}-A_{n_{k}}>t,\dots,S_{n_{j}}+A_{n_{j}}-A_{n_{k}}>t,S_{n_{k}}>t\right)
=\displaystyle= 𝔼​[∏j=1kG¯​(t+(Ank−Anj))].\displaystyle\mathbb{E}\left[\prod^{k}_{j=1}\overline{G}\left(t+(A_{n_{k}}-A_{n_{j}})\right)\right].

This completes the proof. ∎

Corollary 4.2.

Let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the G​I/M/∞GI/M/\infty queue, then the tail distribution of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= e−μ​k​t​𝔼​[∏j=1k−1e−μ​j​(Anj+1−Anj)].\displaystyle e^{-\mu kt}\mathbb{E}\left[\prod^{k-1}_{j=1}e^{-\mu j(A_{n_{j+1}}-A_{n_{j}})}\right]. (19)
Proof.

Using the result from Theorem 4.1, we have

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= ℙ​(Sn1+An1−Ank>t,…,Snj+Anj−Ank>t,Snk>t)\displaystyle\mathbb{P}\left(S_{n_{1}}+A_{n_{1}}-A_{n_{k}}>t,\dots,S_{n_{j}}+A_{n_{j}}-A_{n_{k}}>t,S_{n_{k}}>t\right)
=\displaystyle= e−μ​k​t​𝔼​[∏j=1k−1e−μ​(Ank−Anj)]\displaystyle e^{-\mu kt}\mathbb{E}\left[\prod^{k-1}_{j=1}e^{-\mu(A_{n_{k}}-A_{n_{j}})}\right]
=\displaystyle= e−μ​k​t​𝔼​[∏j=1k−1e−μ​j​(Anj+1−Anj)].\displaystyle e^{-\mu kt}\mathbb{E}\left[\prod^{k-1}_{j=1}e^{-\mu j(A_{n_{j+1}}-A_{n_{j}})}\right].

This completes the proof. ∎

Corollary 4.3.

Let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the M/M/∞M/M/\infty queue, then the tail distribution of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= e−μ​k​t​∏j=1k−1(λλ+μ​j)nj+1−nj.\displaystyle e^{-\mu kt}\prod^{k-1}_{j=1}\left(\frac{\lambda}{\lambda+\mu j}\right)^{n_{j+1}-n_{j}}. (20)
Proof.

Using the result from Theorem 4.1, we have

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= e−μ​k​t​𝔼​[∏j=1k−1e−μ​j​(Anj+1−Anj)]\displaystyle e^{-\mu kt}\mathbb{E}\left[\prod^{k-1}_{j=1}e^{-\mu j(A_{n_{j+1}}-A_{n_{j}})}\right]
=\displaystyle= e−μ​k​t​∏j=1k−1(λλ+μ​j)nj+1−nj.\displaystyle e^{-\mu kt}\prod^{k-1}_{j=1}\left(\frac{\lambda}{\lambda+\mu j}\right)^{n_{j+1}-n_{j}}.

This completes the proof. ∎

The first thing to notice is that our results match the two customer case and yield the previous results by Palomo and Pender [14]. We also observe that the functional form of the result is not affected by the arrival distribution and is completely governed by the service distribution, which is exponential in this case. Moreover, the more customers you want to overlap, the smaller the probability since the rate in the exponential is increased according to the number of overlapping customers.

4.2 First of Each Batch

Now that we have analyzed the k-tuple setting in the individual setting i.e. the batch size is equal to 1, we now move to the setting where batches can have an arbitrary size. We will also perform our analysis for the two batch settings we define in the previous sections i.e. first of each batch and last of each batch.

Theorem 4.4.

Under the first of each batch to leave setting, we let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the G​IB/G​I/∞GI^{B}/GI/\infty queue, then the tail distribution of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= 𝔼​[∏i=1kG¯​(t−(Ank−Ani))ℬ].\displaystyle\mathbb{E}\left[\prod^{k}_{i=1}\overline{G}\left(t-(A_{n_{k}}-A_{n_{i}})\right)^{\mathcal{B}}\right]. (21)
Proof.
ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right)
=\displaystyle= ℙ​((min⁡(S→n1Bn1)+An1−Ank)+∧⋯∧(min⁡(S→njBnj)+Anj−Ank)+∧min⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left((\min\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)+A_{n_{1}}-A_{n_{k}})^{+}\bm{\wedge}\cdots\bm{\wedge}(\min\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)+A_{n_{j}}-A_{n_{k}})^{+}\bm{\wedge}\min\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= ℙ​(min⁡(S→n1Bn1)+An1−Ank>t,…,min⁡(S→njBnj)+Anj−Ank>t,min⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left(\min\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)+A_{n_{1}}-A_{n_{k}}>t,\dots,\min\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)+A_{n_{j}}-A_{n_{k}}>t,\min\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= ℙ​(min⁡(S→n1Bn1)>t+Ank−An1,…,min⁡(S→njBnj)>t+Ank−Anj,min⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left(\min\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)>t+A_{n_{k}}-A_{n_{1}},\dots,\min\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)>t+A_{n_{k}}-A_{n_{j}},\min\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= 𝔼​[∏i=1k(∑j=1∞pj⋅G¯​(t−(Ank−Ani))j)]\displaystyle\mathbb{E}\left[\prod^{k}_{i=1}\left(\sum^{\infty}_{j=1}p_{j}\cdot\overline{G}\left(t-(A_{n_{k}}-A_{n_{i}})\right)^{j}\right)\right]
=\displaystyle= 𝔼​[∏i=1kG¯​(t−(Ank−Ani))ℬ].\displaystyle\mathbb{E}\left[\prod^{k}_{i=1}\overline{G}\left(t-(A_{n_{k}}-A_{n_{i}})\right)^{\mathcal{B}}\right].

This completes the proof. ∎

Corollary 4.5.

Under the first of each batch to leave setting, we let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the G​IB/M/∞GI^{B}/M/\infty queue, then the tail distribution of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= 𝔼​[e−μ​k​t​ℬ​∏i=1k−1e−μ​ℬ​(Ank−Ani)].\displaystyle\mathbb{E}\left[e^{-\mu kt\mathcal{B}}\prod^{k-1}_{i=1}e^{-\mu\mathcal{B}(A_{n_{k}}-A_{n_{i}})}\right]. (22)
Proof.

Using the result from Theorem 4.4, we have that

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= 𝔼​[∑j=1∞pj​(∏i=1k−1e−μ​j​(t+Ank−Ani)⋅e−μ​j​t)]\displaystyle\mathbb{E}\left[\sum^{\infty}_{j=1}p_{j}\left(\prod^{k-1}_{i=1}e^{-\mu j(t+A_{n_{k}}-A_{n_{i}})}\cdot e^{-\mu jt}\right)\right]
=\displaystyle= ∑j=1∞pj⋅e−μ​j​k​t​𝔼​[∏i=1k−1e−μ​j​(Ank−Ani)]\displaystyle\sum^{\infty}_{j=1}p_{j}\cdot e^{-\mu jkt}\mathbb{E}\left[\prod^{k-1}_{i=1}e^{-\mu j(A_{n_{k}}-A_{n_{i}})}\right]
=\displaystyle= 𝔼​[e−μ​k​t​ℬ​∏i=1k−1e−μ​ℬ​(Ank−Ani)].\displaystyle\mathbb{E}\left[e^{-\mu kt\mathcal{B}}\prod^{k-1}_{i=1}e^{-\mu\mathcal{B}(A_{n_{k}}-A_{n_{i}})}\right].

This completes the proof. ∎

Corollary 4.6.

Under the first of each batch to leave setting, we let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the G​IB/M/∞GI^{B}/M/\infty queue, then the mean of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

𝔼​[On1,n2,…,nk]\displaystyle\mathbb{E}\left[O_{n_{1},n_{2},\dots,n_{k}}\right] =\displaystyle= 1μ​k​𝔼​[ℬ−1​∏i=1k−1e−μ​ℬ​(Ank−Ani)].\displaystyle\frac{1}{\mu k}\mathbb{E}\left[\mathcal{B}^{-1}\prod^{k-1}_{i=1}e^{-\mu\mathcal{B}(A_{n_{k}}-A_{n_{i}})}\right]. (23)
Proof.

Using the result from Theorem 4.4, we have that

𝔼​[On1,n2,…,nk]\displaystyle\mathbb{E}\left[O_{n_{1},n_{2},\dots,n_{k}}\right] =\displaystyle= ∫0∞ℙ​(On1,n2,…,nk>t)​𝑑t\displaystyle\int^{\infty}_{0}\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right)dt
=\displaystyle= ∫0∞𝔼​[e−μ​k​t​ℬ​∏i=1k−1e−μ​ℬ​(Ank−Ani)]​𝑑t\displaystyle\int^{\infty}_{0}\mathbb{E}\left[e^{-\mu kt\mathcal{B}}\prod^{k-1}_{i=1}e^{-\mu\mathcal{B}(A_{n_{k}}-A_{n_{i}})}\right]dt
=\displaystyle= 1μ​k​𝔼​[ℬ−1​∏i=1k−1e−μ​ℬ​(Ank−Ani)].\displaystyle\frac{1}{\mu k}\mathbb{E}\left[\mathcal{B}^{-1}\prod^{k-1}_{i=1}e^{-\mu\mathcal{B}(A_{n_{k}}-A_{n_{i}})}\right].

This completes the proof. ∎

4.3 Last of Each Batch

Theorem 4.7.

Under the last of each batch to leave setting, we let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the G​IB/G​I/∞GI^{B}/GI/\infty queue, then the tail distribution of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= 𝔼​[∏i=1k(1−G​(t−(Ank−Ani))ℬ)].\displaystyle\mathbb{E}\left[\prod^{k}_{i=1}\left(1-G\left(t-(A_{n_{k}}-A_{n_{i}})\right)^{\mathcal{B}}\right)\right]. (24)
Proof.
ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right)
=\displaystyle= ℙ​((max⁡(S→n1Bn1)+An1−Ank)+∧⋯∧(max⁡(S→njBnj)+Anj−Ank)+∧max⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left((\max\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)+A_{n_{1}}-A_{n_{k}})^{+}\bm{\wedge}\cdots\bm{\wedge}(\max\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)+A_{n_{j}}-A_{n_{k}})^{+}\bm{\wedge}\max\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= ℙ​(max⁡(S→n1Bn1)+An1−Ank>t,…,max⁡(S→njBnj)+Anj−Ank>t,max⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left(\max\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)+A_{n_{1}}-A_{n_{k}}>t,\dots,\max\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)+A_{n_{j}}-A_{n_{k}}>t,\max\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= ℙ​(max⁡(S→n1Bn1)>t+Ank−An1,…,max⁡(S→njBnj)>t+Ank−Anj,max⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left(\max\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)>t+A_{n_{k}}-A_{n_{1}},\dots,\max\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)>t+A_{n_{k}}-A_{n_{j}},\max\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= 𝔼[∏i=1k(1−∑j=1∞pj((1−G¯(t−(Ank−Ani)))j)]\displaystyle\mathbb{E}\left[\prod^{k}_{i=1}\left(1-\sum^{\infty}_{j=1}p_{j}\left((1-\overline{G}(t-(A_{n_{k}}-A_{n_{i}}))\right)^{j}\right)\right]
=\displaystyle= 𝔼​[∏i=1k(1−G​(t−(Ank−Ani))ℬ)].\displaystyle\mathbb{E}\left[\prod^{k}_{i=1}\left(1-G\left(t-(A_{n_{k}}-A_{n_{i}})\right)^{\mathcal{B}}\right)\right].

This completes the proof. ∎

Corollary 4.8.

Under the last of each batch to leave setting, we let On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} be the distribution of the overlap time for customers within distance nk−n1n_{k}-n_{1} in the G​IB/M/∞GI^{B}/M/\infty queue, then the tail distribution of On1,n2,…,nkO_{n_{1},n_{2},\dots,n_{k}} is given by the following formula

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right) =\displaystyle= 1−𝔼​[(∏i=1k(1−e−μ​ℬ​(t+Ank−Ani)))].\displaystyle 1-\mathbb{E}\left[\left(\prod^{k}_{i=1}\left(1-e^{-\mu\mathcal{B}\left(t+A_{n_{k}}-A_{n_{i}}\right)}\right)\right)\right]. (25)
Proof.

Using the result from Theorem 4.7, we have that

ℙ​(On1,n2,…,nk>t)\displaystyle\mathbb{P}\left(O_{n_{1},n_{2},\dots,n_{k}}>t\right)
=\displaystyle= ℙ​((max⁡(S→n1Bn1)+An1−Ank)+∧⋯∧(max⁡(S→njBnj)+Anj−Ank)+∧max⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left((\max\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)+A_{n_{1}}-A_{n_{k}})^{+}\bm{\wedge}\cdots\bm{\wedge}(\max\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)+A_{n_{j}}-A_{n_{k}})^{+}\bm{\wedge}\max\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= ℙ​(max⁡(S→n1Bn1)+An1−Ank>t,…,max⁡(S→njBnj)+Anj−Ank>t,max⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left(\max\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)+A_{n_{1}}-A_{n_{k}}>t,\dots,\max\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)+A_{n_{j}}-A_{n_{k}}>t,\max\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= ℙ​(max⁡(S→n1Bn1)>t+Ank−An1,…,max⁡(S→njBnj)>t+Ank−Anj,max⁡(S→nkBnk)>t)\displaystyle\mathbb{P}\left(\max\left(\vec{S}_{n_{1}}^{B_{n_{1}}}\right)>t+A_{n_{k}}-A_{n_{1}},\dots,\max\left(\vec{S}_{n_{j}}^{B_{n_{j}}}\right)>t+A_{n_{k}}-A_{n_{j}},\max\left(\vec{S}_{n_{k}}^{B_{n_{k}}}\right)>t\right)
=\displaystyle= 1−𝔼​[∑j=1∞pj​(∏i=1k(1−e−μ​j​(t+Ank−Ani)))]\displaystyle 1-\mathbb{E}\left[\sum^{\infty}_{j=1}p_{j}\left(\prod^{k}_{i=1}\left(1-e^{-\mu j\left(t+A_{n_{k}}-A_{n_{i}}\right)}\right)\right)\right]
=\displaystyle= 1−𝔼​[(∏i=1k(1−e−μ​ℬ​(t+Ank−Ani)))].\displaystyle 1-\mathbb{E}\left[\left(\prod^{k}_{i=1}\left(1-e^{-\mu\mathcal{B}\left(t+A_{n_{k}}-A_{n_{i}}\right)}\right)\right)\right].

This completes the proof. ∎

5 Conclusion

In this paper, we consider the overlap times for customers in the G​IB/G​I/∞GI^{B}/GI/\infty queue. We provide an analysis from an individual and a batch perspective. Despite our analysis, there are many avenues for additional research. First, as we mentioned before, there are several ways to analyze the batch perspective. One such way would be to explicitly analyze the order statistics of each batch. In particular one might be interested in when a certain percentage of customers have departed from each batch.

Second, one can also extend our work by considering generalizations such as dependent arrivals or service times like in Pang and Whitt [16, 17], Daw and Pender [2]. In particular, dependent service times would impact the tail distribution quite significantly since it no longer splits into a product of individual distributions. It would also be interesting to consider the situation where there are a finite number of servers or abandonments to assess the impact on the tail distribution of the overlap time, see for example Ko and Xu [9]. Finally, we are also interested in designing queueing systems to minimize overlap times under some cost criterion. We hope to consider these important extensions in future work.

Acknowledgements

Jamol Pender would like to acknowledge the gracious support of the National Science Foundation DMS Award # 2206286. Sergio Palomo would like to acknowledge the gracious support of the Sloan Foundation for supporting his graduate studies.

References

  • Afanaseva et al. [2020] Larisa Afanaseva, Elena Bashtova, and Svetlana Grishunina. Stability analysis of a multi-server model with simultaneous service and a regenerative input flow. Methodology and Computing in Applied Probability, 22(4):1439–1455, 2020.
  • Daw and Pender [2018] Andrew Daw and Jamol Pender. Queues driven by hawkes processes. Stochastic Systems, 8(3):192–229, 2018.
  • Daw et al. [2021] Andrew Daw, Robert C Hampshire, and Jamol Pender. How to staff when customers arrive in batches. arXiv preprint arXiv:1907.12650, 2021.
  • Grosof et al. [2020] Isaac Grosof, Mor Harchol-Balter, and Alan Scheller-Wolf. Stability for two-class multiserver-job systems. arXiv preprint arXiv:2010.00631, 2020.
  • Hampshire et al. [2020] Robert C Hampshire, Shan Bao, Walter S Lasecki, Andrew Daw, and Jamol Pender. Beyond safety drivers: Applying air traffic control principles to support the deployment of driverless vehicles. PLoS one, 15(5):e0232837, 2020.
  • Hong and Wang [2021] Yige Hong and Weina Wang. Sharp waiting-time bounds for multiserver jobs. arXiv preprint arXiv:2109.05343, 2021.
  • Kang et al. [2021] Kang Kang, Sherwin Doroudi, Mohammad Delasay, and Alexander Wickeham. A queueing-theoretic framework for evaluating transmission risks in service facilities during a pandemic. arXiv preprint arXiv:2103.13441, 2021.
  • Kaplan [2020] Edward H Kaplan. OM forum—COVID-19 scratch models to support local decisions. Manufacturing & Service Operations Management, 22(4):645–655, 2020.
  • Ko and Xu [2022] Young Myoung Ko and Jin Xu. Overlapping time of a virtual customer in time-varying many-server queues. arXiv preprint arXiv:2211.03962, 2022.
  • Lu et al. [2011] Yi Lu, Qiaomin Xie, Gabriel Kliot, Alan Geller, James R Larus, and Albert Greenberg. Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services. Performance Evaluation, 68(11):1056–1071, 2011.
  • Mirzaeian et al. [2021] Neda Mirzaeian, Soo-Haeng Cho, and Alan Scheller-Wolf. A queueing model and analysis for autonomous vehicles on highways. Management Science, 67(5):2904–2923, 2021.
  • Morozova et al. [2020] Olga Morozova, Zehang Richard Li, and Forrest W Crawford. A model for COVID-19 transmission in connecticut. medRxiv, 2020.
  • Palomo and Pender [2021a] Sergio Palomo and Jamol Pender. Measuring the overlap with other customers in the G/G/1 queue. In KH Bae, B Feng, S Kim, S Lazarova-Molnar, Z Zheng, T Roeder, and R Thiesing, editors, Submitted to the Proceedings of the 2021 Winter Simulation Conference, pages 2595–2605. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers, Inc., 2021a.
  • Palomo and Pender [2021b] Sergio Palomo and Jamol Pender. Overlap times in the infinite server queue. Probability in the Engineering and Informational Sciences To Appear, 2021b.
  • Palomo et al. [2020] Sergio Palomo, Jamol Pender, William Massey, and Robert C Hampshire. Flattening the curve: Insights from queueing theory. arXiv preprint arXiv:2004.09645, 2020.
  • Pang and Whitt [2012] Guodong Pang and Ward Whitt. The impact of dependent service times on large-scale service systems. Manufacturing & Service Operations Management, 14(2):262–278, 2012.
  • Pang and Whitt [2013] Guodong Pang and Ward Whitt. Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Systems, 73(2):119–146, 2013.
  • Pender and Ko [2017] Jamol Pender and Young Myoung Ko. Approximations for the queue length distributions of time-varying many-server queues. INFORMS Journal on Computing, 29(4):688–704, 2017.
  • Pender and Phung-Duc [2016] Jamol Pender and Tuan Phung-Duc. A law of large numbers for m/m/c/delayoff-setup queues with nonstationary arrivals. In International conference on analytical and stochastic modeling techniques and applications, pages 253–268. Springer, 2016.
  • Rumyantsev and Morozov [2017] Alexander Rumyantsev and Evsey Morozov. Stability criterion of a multiserver model with simultaneous service. Annals of Operations Research, 252(1):29–39, 2017.
  • Wang et al. [2021] Weina Wang, Qiaomin Xie, and Mor Harchol-Balter. Zero queueing for multi-server jobs. In Abstract Proceedings of the 2021 ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, pages 13–14, 2021.
  • Weng and Wang [2020] Wentao Weng and Weina Wang. Achieving zero asymptotic queueing delay for parallel jobs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(3):1–36, 2020.
  • Xie et al. [2017] Qiaomin Xie, Mayank Pundir, Yi Lu, Cristina L Abad, and Roy H Campbell. Pandas: Robust locality-aware scheduling with stochastic delay optimality. IEEE/ACM Transactions on Networking (TON), 25(2):662–675, 2017.
  • Yekkehkhany et al. [2018] Ali Yekkehkhany, Avesta Hojjati, and Mohammad H Hajiesmaili. GB-PANDAS:: Throughput and heavy-traffic optimality analysis for affinity scheduling. ACM SIGMETRICS Performance Evaluation Review, 45(2):2–14, 2018.