The notion of overlap time has become a new metric for describing the complex dynamics of how customers interact in service systems. Overlap times were first developed in the work of [13,23] as an important metric in the context of COVID-19 and infectious disease spread. In fact, the work of [13,23] provided a foundation for others to also explore overlap times in more complicated queueing models and has inspired a large number of recent papers on the topic, see for example [4,9,10,11,12,15,16,24,26,27].

Recent work [25] considers the M/M/1 queue and derives the steady-state distribution of the maximum overlap time. The maximum overlap time, the longest amount of time a customer spends with any other customer in the system, serves as an important metric for understanding infectious disease spread as it quantifies the longest duration during which an individual interacts with another customer within a service system. This metric not only aids in identifying potential exposure periods but also plays a pivotal role in deriving both lower or upper bounds on infection probabilities within the M/M/1 queue.

In this work, we generalize the work of [25] to the G/G/1 queue. Our approach uses two steps. The first step is to leverage a new decomposition of the maximum overlap time into the waiting time plus an independent random variable. This important observation was not noticed in [25]. The second step is to use the Laplace-Stieltjes transform (LST) of the waiting time as given by [7] to compute the LST of the maximum overlap distribution. We are able to invert the distribution in some special cases to explicitly characterize the maximum overlap time distribution.

Theminimum adjacent overlap time a customer experiences is also a useful metric for understanding infectious disease spread; it measures the least amount of time a customer is going to spend with its two adjacent customers in a service system. In this context, the minimum adjacent overlap time is relevant for spatial purposes as well. Presumably the nearest customers are those adjacent and one can define infection processes based on spatial proximity as well. For example, in [1], queues are defined in terms of spatial proximity. In this paper, we derive a novel relationship between the maximum overlap and minimum adjacent overlap to analyze the steady-state distribution of the minimum adjacent overlap. This is quite straightforward in the M/M/1 queue, however, it is more complicated in the G/G/1 queue. Thus, we develop a new methodology for analyzing the steady-state maximum overlap distribution and the minimum adjacent overlap distribution. Our approach for the G/G/1 queue is to analyze the\(G/\mathcal{P}\mathcal{H}_{ME}/1\) and the\(\mathcal{P}\mathcal{H}_{ME}/G/1\) queues where the\(\mathcal{P}\mathcal{H}_{ME}\) is the class of finite mixtures of Erlang distributions with the same intensity (cf. Sect. 2.3). Since the class\(\mathcal{P}\mathcal{H}_{ME}\) is dense in the class of distributions of non-negative random variables, see for example Theorem 4.2 of [2], this serves as a good approximation to the G/G/1 queue.

1.1Contributions of our work

In this paper, we make the following contributions to the literature:

• We derive the (Laplace-Stieltjes transform of the) steady state distribution of the maximum overlap time of any customer.

• We derive the (Laplace-Stieltjes transform of the) steady state distribution of the minimum adjacent customer overlap time of any customer.

• We also obtain moments for these two performance measures and provide inverse Laplace-Stieltjes transforms in some special cases.

1.2Notation

First some key random variables:

• \(S_n\) represents the service time of the\(n^{th}\) customer, andS a generic service time.

• \(A_n\) represents the inter-arrival time between the\(n^{th}\) and\((n+1)^{st}\) customers, andA a generic inter-arrival time.

• \(W_n\) represents the waiting time of the\(n^{th}\) customer, and\(W_\infty \) the steady-state waiting time.

• \(M_n\) represents the maximum overlap time of the\(n^{th}\) customer, and\(M_\infty \) the steady-state maximum overlap time.

• \(V_n\) represents the minimum adjacent overlap time of the\(n^{th}\) customer, and\(V_\infty \) the steady-state minimum adjacent overlap time.

• \(\{\cdot \}\) denotes an indicator function.

• \(X^+=\max (X,0)\) and\(X^-=\min (X,0)\).

• \(\lambda \) is the arrival rate if the arrival process is given by a Poisson process as in the\(M_{\lambda }\)/G/1 queue.

• \(\mu \) is the service rate if the service distribution is exponential as in the G/\(M_{\mu }\)/1 queue.

Finally,\(f_X(\cdot )\),\(F_X(\cdot )\) and\(\mathcal {L}_X(\theta )\) denote the density, distribution and Laplace-Stieltjes transform of random variableX. We shall in particular use this notation withA orS taken forX.

1.3Organization of the paper

The remainder of the paper is organized as follows. Section 2 contains our main results for computing the tail distribution of the steady-state maximum overlap time. The moments and LST are also calculated for the steady-state maximum overlap time. In Sect. 3, we replicate the analytical approach employed in the previous section to investigate the minimum overlap among adjacent customers. Lastly, in Sect. 4, we conclude the paper and propose novel directions for future research.

In this section, we derive our main results for the maximum overlap time. First we derive a novel representation of the steady-state maximum overlap time in terms of the steady-state waiting time. Then, we use the representation to write the LST of the maximum overlap time as a product of the LST of the steady-state waiting time and the LST of\((S-A)^+\). In Subsections 2.1 and2.2, we work this out for the M/G/1 and G/M/1 queue. In Subsection 2.3, we obtain the LST of the steady state maximum overlap time for the\(\mathcal{P}\mathcal{H}_{ME}/G/1\) and\(G/\mathcal{P}\mathcal{H}_{ME}/1\) queue, the class\(\mathcal{P}\mathcal{H}_{ME}\) lying dense in the class of all distributions of non-negative random variables. We have chosen to treat M/G/1 and G/M/1 in separate subsections because these are important queueing models for which the waiting time LST is well known and quite tractable, while the results for\(\mathcal{P}\mathcal{H}_{ME}/G/1\) and\(G/\mathcal{P}\mathcal{H}_{ME}/1\) are mathematically more involved.

To make the paper self-contained, we start with a definition of an overlap time. The overlap time between customern and customer\(n+k\) is defined as\(O_{n,n+k}\), and represents the time that both customers spend in the system simultaneously. Following [25], we can represent the overlap time between customern and\(n+k\) as

where\(D_n\) represents the departure time of the\(n^{th}\) customer. As proven in [23], we have the intuitively obvious result that\(O_{n,n+k}\) is decreasing ink, and, accordingly, that also\(O_{n-k,n}\) is decreasing ink. Hence the maximum overlap time of customern equals the maximum of\(O_{n-1,n}\) and\(O_{n,n+1}\). As shown in [25],

and hence

This has led [25] to the following result.

Proposition 2.1

( [25]) Let\(M_n\) be the maximum overlap time for customern in the G/G/1 queue. Then\(M_n\) is equal to

Next observe that we can write\(M_n\) as sum of two independent components\(W_n\) and\(\left( S_n - A_n \right) ^+\). This will be helpful in describing the LST of the maximum overlap in the sequel. We prove this in the Lemma.

Lemma 2.2

The maximum overlap time has the following decomposition into two independent terms, viz., the waiting time and max-plus difference of a service time and inter-arrival time:

Proof

The proof follows by combining (2) with the obvious independence of\(W_n\) and\((S_n,A_n)\).\(\square \)

The independence of\(W_n\) and\((S_n-A_n)^+\) now implies:

Lemma 2.3

The LST, mean and second moment of the maximum overlap time have the following expressions:

furthermore,

and

With\(f_A(\cdot )\) and\(F_A(\cdot )\) the density and distribution of inter-arrival time\(A_n\), and\(\overline{F}_A(y) = 1 - F_A(y)\), and with\(f_S(\cdot )\) and\(F_S(\cdot )\) the density and distribution of service time\(S_n\), we can derive the following expression.

We now specify these expressions for the\(M_{\lambda }\)/G/1 and G/\(M_{\mu }\)/1 queues.

2.1The\(M_{\lambda }\)/G/1 queue

In this section, we specialize our results to the\(M_{\lambda }\)/G/1 queue. We start with a lemma that calculates the LST of the max-plus difference of a service time and inter-arrival time, as well as its moments.

Lemma 2.4

For the\(M_{\lambda }\)/G/1 queue, we have that

Proof

Using (8), we have:

Thek-th moment,\(k=1,2,\dots \), is calculated in the following way:

\(\square \)

Now with Lemma 2.4 we provide our first main result, which is the LST of the steady-state maximum overlap time of the\(M_{\lambda }/G/1\) queue, as well as its mean and variance. Here and in the sequel,\(\rho \) denotes the load of the server, i.e., mean service time divided by mean inter-arrival time.

Theorem 2.5

Let\(M_\infty \) be the steady-state maximum overlap time for the\(M_{\lambda }/G/1\) queue, then the LST of\(M_\infty \) is equal to

with mean

and second moment

Proof

To derive (11), we first note that the steady-state waiting time and the difference of the service and arrival random variables are independent. Thus, the LST of the sum is the product of the individual expressions. We then combine Lemmas 2.3 and 2.4, and use the Pollaczek-Khinchin formula for the LST of the steady-state waiting time of the\(M_{\lambda }/G/1\) queue (cf. p. 256 of [7]). The expressions for the moments follow from (6) and (7), using (10). It is important to observe that the first term in the right-hand side of (12) equals\(\mathbb {E}[W_\infty ]\), while the two terms on the right in the first line of (13) equal\(\mathbb {E}[W_\infty ^2]\).\(\square \)

Remark

Observe that the sum of the first two terms in the right-hand side of (12) equals the mean sojourn time in the\(M_\lambda /G/1\) queue. As expected,\(\mathbb {E}[M_\infty ]\) is smaller than this mean sojourn time.

Here we give three examples that provide more insight into our results for the\(M_{\lambda }/G/1\) queue in special cases where the service times are Erlang, Deterministic, and Hyper-Exponential.

Example 2.1

IfS is Erlang-k distributed with mean\(k/\mu \), so\(\mathcal {L}_S(\theta ) = (\frac{\mu }{\mu +\theta })^k\), then the expression in Theorem 2.5 reduces to

Inspection of (14) shows that (i)\(\theta = \lambda \) is not a pole; (ii)\(\theta =0\) is not a pole; and (iii) there arek poles\(\theta _1,\dots ,\theta _k\), and these are exactly the poles of\(\mathcal {L}_{W_\infty }(\theta )\). Hence we know that all\(\theta _i\) lie in the left-half\(\theta \)-plane. In general, these\(\theta _i\) have to be determined numerically. This can be efficiently done using numerical software such as Maple, Mathematica, or Python; see also the discussion in the introduction of [3]. To invert this transform, first observe that it can be rewritten as

Secondly, notice that the last fraction can be written as\(\theta ^k + \sum _{i=0}^{k-1} a_i \theta ^i\), where the constants\(a_0,\dots ,a_{k-1}\) have to be determined. Thirdly, rewrite (15) into

for certain\(b_0,\dots ,b_{k-1}\). Finally, a partial fraction decomposition yields, for constants\(C_1,\dots ,C_k\):

Inversion yields that

It should be noticed that\((1-\rho ) \left( \frac{\mu }{\mu +\lambda } \right) ^k\) represents\(\mathbb {P}(M_\infty =0)\), as could also have been obtained by letting\(\theta \rightarrow \infty \) in (14), or by realizing that

For smallk-values, the\(\theta _i\) can be explicitly determined. E.g., for\(k=1\) we have\(\theta _1=\lambda -\mu \). For\(k=2\) we have\(\theta _{1,2} = \frac{1}{2} [\lambda -2\mu \pm \sqrt{\{\lambda ^2 + 4 \lambda \mu \}}]\). In that\(M/E_2/1\) case, (15) becomes

so that we have in (16) that

The last term inside the square brackets in (20) can be rewritten as\(\frac{D_1}{\theta -\theta _1} + \frac{D_2}{\theta -\theta _2}\), where\(D_1+D_2=2\lambda \) and\(-D_1\theta _2 -D_2 \theta _1 = \lambda ^2 + 4\lambda \mu \), so that we have in (18) that

It is readily checked that

The latter result is as expected; let\(x \rightarrow \infty \) in (18).

The above reasoning holds more generally, in the sense that\(\theta =0\) and\(\theta =\lambda \) are not poles of the right-hand side of (11), while poles of\(\mathcal {L}_S(\theta )\) in the left-half\(\theta \)-plane are compensated by the\(\mathcal {L}_S(\theta )\) term in the first part of that right-hand side. Hence, for any service time distribution, the poles of\(\mathcal {L}_{M_\infty }(\theta )\) and of\(\mathcal {L}_{W_\infty }(\theta )\) in the left-half\(\theta \)-plane coincide. Accordingly, the tail\(\mathbb {P}(M_\infty > t)\), for larget, exhibits the same behavior as the tail\(\mathbb {P}(W_\infty >t)\); both are determined by the pole in the left-half\(\theta \)-plane with largest real part.

Example 2.2

IfS is deterministic, i.e.,\(S_n \equiv D\), we have

Example 2.3

IfS is Hyper-exponential(\(\vec {\mu }, \vec {p}\)), i.e.,\(M_{\lambda }/H_k/1\), a mixture of exp(\(\mu _i\)) with probabilities\(p_i \in (0,1)\):

Simulation vs. Formula for the Maximum Overlap Time in the M/M/1 queue (left) with parameters\(\lambda =.8, \mu =1\) and the M/\(E_k\)/1 queue with parameters\(\lambda =.8, \mu = 2, k = 2\)

Full size image

In Fig. 1, we plot the cumulative distribution function of the maximum overlap time for the M/M/1 queue with parameters\(\lambda =.8, \mu =1\) and the M/\(E_k\)/1 queue with parameters\(\lambda =.8, \mu = 2, k = 2\). We find that the cdf for the maximum overlap time for the M/M/1 queue is greater than or equal to the cdf for the M/\(E_k\)/1 queue. This is mainly because of the decreased variability in the Erlang service times. Moreover, we see that our formulas for the cdf match those by simulation.

2.2The G/\(M_{\mu }\)/1 queue

In this section, we specialize our results to the\(G/M_{\mu }/1\) queue. We again start with a lemma. It calculates the LST of the max-plus difference of a service time and inter-arrival time, as well as its moments.

Lemma 2.6

For the\(G/M_{\mu }/1\) queue, we have that

Proof

Again using (8), we have:

Alternatively, simply use the memoryless property twice to obtain

and

To prove (28), again use the memoryless property:

\(\square \)

Now with Lemma 2.6 we provide our second main result, which is the LST of the steady-state maximum overlap time of the\(G/M_{\mu }/1\) queue.

Theorem 2.7

Let\(M_\infty \) be the steady-state maximum overlap time for the\(G/M_{\mu }/1\) queue, then the LST of\(M_\infty \) is equal to

where\(\rho ^*\) is the unique solution to\(\rho ^* = \mathcal {L}_A(\mu - \mu \rho ^*)\). Furthermore,

Proof

To derive (30), combine Lemmas 2.3 and2.6, and use the known result for the LST of the steady-state waiting time (cf. p. 230 of [7]; as is well known, the waiting time distribution is exponential, with an atom at zero). The moment expressions follow from (6) and (7), using (28); further use that\(\mathbb {E}[W_\infty ] = \frac{\rho ^*}{\mu (1-\rho ^*)}\) and\(\mathbb {E}[W_\infty ^2] = \frac{2 \rho ^*}{\mu ^2(1-\rho ^*)^2}\).\(\square \)

Remark

A careful inspection of (30) shows that\(\theta = - \mu \) isnot a pole; we can rewrite (30) as

and inversion yields:

Hence, in the\(G/M_{\mu }/1\) queue,\(M_\infty \) is exponentially distributed (with the same exponent as\(W_\infty \)) with an atom at zero. For\(M_{\lambda }/M_{\mu }/1\), we have\(\rho ^*=\rho = \frac{\lambda }{\mu }\) and (34) reduces to Theorem 3.3 of [25]:

Remark

In the case where the arrival process is an Erlang(2,\(\lambda \)), yielding an\(E_2/M_{\mu }/1\) queue, we have the fixed point for\(\rho ^* = \frac{\lambda }{\mu } + \frac{1}{2} - \sqrt{\frac{\lambda }{\mu } + \frac{1}{4}}\). Moreover, when the arrival process is deterministic, yielding a\(D/M_{\mu }/1\) queue, we have the fixed point for\(\rho ^* = -\frac{W_{-1}( - e^{-\Delta \mu } \Delta \mu )}{\Delta \mu }\) where\(W_{-1}(x)\) is defined as the principal branch of the LambertW function when\(-1/e \le x \le 0\). This is the case because

Now by a generalization of the LambertW function given in [18], we have the above result for\(\rho ^*\).

Simulation vs. Formula for the Maximum Overlap Time in the\(E_k\)/M/1 queue (left) with parameters\(\lambda =.8, \mu =1, k =2\) and the D/M/1 queue (right) with parameters\(\Delta = 1.25, \mu =1\)

Full size image

In Fig. 2, we plot the cumulative distribution function of the maximum overlap time for the\(E_k\)/M/1 queue with parameters\(\lambda =.8, \mu = 1, k = 2\) and the D/M/1 queue with parameters\(\Delta = 1.25, \mu =1\). First, we observe that our formulas for the cdf match those given by stochastic simulation. Second, we observe that the\(\rho ^*\) value for the D/M/1 queue is smaller than the\(\rho ^*\) for the\(E_k\)/M/1 queue. This has two consequences. The first is the probability that the maximum overlap time is equal to zero is greater in the D/M/1 queue than the\(E_k\)/M/1. The second is that the distribution of the maximum overlap time for the D/M/1 queue is skewed toward values near zero while the\(E_k\)/M/1 is skewed less.

2.3The maximum for the G/G/1 queue

In this subsection, we generalize Theorems 2.5 and2.7 to the case of the\(\mathcal{P}\mathcal{H}_{ME}/G/1\) and\(G/\mathcal{P}\mathcal{H}_{ME}/1\) queues.\(\mathcal{P}\mathcal{H}_{ME}\) is the class of finite mixtures of Erlang distributions with the same intensity, i.e., their density has the form

where\(n(j) \in \mathbb {N}\),\(p_j>0\) for all\(j=1,\dots ,k\) and\(\sum _{j=1}^k p_j =1\); we take\(n(1)<n(2)< \dots < n(k)\).

According to Theorem 4.2 of Asmussen [2], this class lies dense, in the sense of weak convergence, in the set of all probability distributions on\((0,\infty )\); the implication is that we can approximate any such probability distribution arbitrarily closely by a\(\mathcal{P}\mathcal{H}_{ME}\) distribution.

Our first observation, cf. Lemma 2.3, is that

Our second observation is that the Laplace transform of the density given in (36) equals

Let us now successively determine the two components in the right-hand side of (37) for\(\mathcal{P}\mathcal{H}_{ME}/G/1\) and\(G/\mathcal{P}\mathcal{H}_{ME}/1\).

2.3.1The\(\mathcal{P}\mathcal{H}_{ME}/G/1\) queue

We take

Furthermore, we consider the zeroes of

As proven in p. 329 of Cohen [7] using Rouché’s theorem, for\(\rho < 1\) there are exactly\(n(k)+1\) such zeroes\(\delta _j\), with\(\delta _1=0\) and\(\textrm{Re}~ \delta _j > 0\) for\(j=2,\dots ,n(k)+1\). We can now use Formula (II.5.204) of [7] to obtain an explicit expression for the LST of\(W_\infty \).

Lemma 2.8

For the\(\mathcal{P}\mathcal{H}_{ME}/G/1\) queue with inter-arrival time density given by (36) with\(\zeta = \lambda \), the LST of the steady-state waiting time is given by

We next turn to the LST of\(\left( S-A \right) ^+\).

Lemma 2.9

For the\(\mathcal{P}\mathcal{H}_{ME}/G/1\) queue,

where\(\mathcal {L}_S^{(i)}(\lambda )\) denotes the\(i^{th}\) derivative of\(\mathcal {L}_S(\theta )\), evaluated at\(\theta = \lambda \).

Proof

With\(f_A(\cdot )\) the density ofA, we can write:

The result follows by observing that\(\int _{x=0}^{\infty } x^i \textrm{e}^{-\lambda x} \textrm{d}S(x) = (-1)^i \mathcal {L}_S^{(i)}(\lambda )\).\(\square \)

Combining (37) with Lemmata 2.8 and2.9, we obtain the following result.

Theorem 2.10

The steady-state maximum overlapping time LST in the\(\mathcal{P}\mathcal{H}_{ME}/G/1\) queue is given by the product of the expressions in the right-hand sides of (40) and (41).

2.3.2The\(G/\mathcal{P}\mathcal{H}_{ME}/1\) queue

We now take

Furthermore, consider the zeroes of

Cohen [7], p. 323, proves that it has exactly\(n(k)+1\) zeroes\(\xi _i\),\(i=1,\dots ,n(k)+1\), with\(\textrm{Re}~\xi _i <0\). From (II.5.190) of [7], we now immediately conclude the following.

Lemma 2.11

For the\(G/\mathcal{P}\mathcal{H}_{ME}/1\) queue with service time density given by (36) with\(\zeta =\mu \), the LST of the steady state waiting time is given by

Notice that the waiting time distribution apparently is a mixture of\(n(k)+1\) exponential terms, plus an atom at zero. ForG/M/1, we have\(n(k)=n(1)=0\), resulting in the well-known exponential waiting time distribution with an atom at zero.

We next turn to the LST of\((S-A)^+\).

Lemma 2.12

For the\(G/\mathcal{P}\mathcal{H}_{ME}/1\) queue,

Proof

Start from the identity\(\textrm{e}^{-\theta (x)^+} + \textrm{e}^{-\theta (x)^-} = \textrm{e}^{-\theta x} + 1\), replacingx by\(S-A\) and taking expectations on both sides. Subsequently, observe that\((S-A)^- = - (A-S)^+\). Finally, determine\(\mathbb {E}[\textrm{e}^{-\theta (S-A)^-}] = \mathbb {E}[\textrm{e}^{\theta (A-S)^+}]\) from Lemma 2.9 by there replacing\(\theta \) by\(-\theta \),\(\lambda \) by\(\mu \) and\(\mathcal {L}_S(\cdot )\) by\(\mathcal {L}_A(\cdot )\).\(\square \)

Combining (37) with Lemmata 2.11 and2.12, we obtain the following theorem.

Theorem 2.13

The steady-state maximum overlapping time LST in the\(G/\mathcal{P}\mathcal{H}_{ME}/1\) queue is given by the product of the expressions in the right-hand sides of (44) and (45).

In this section, we study the minimum of the overlap times of a tagged customer, say customern, with the previous customer and the next customer. This clearly amounts to the minimum of the waiting times\(W_n\) and\(W_{n+1}\). Hence we have

Lemma 3.1

Below we give an expression for the LST of the steady-state minimum overlap time\(V_{\infty }\) and for its distribution.

Theorem 3.2

The LST of the steady-state minimum overlap time\(V_{\infty }\) is given by

The distribution of\(V_\infty \) can be expressed in the distribution of\(W_\infty \) in the following way:

Proof

It follows from (46) that, in steady state,

Now observe that

Combining (46), (49) and (50), and using that

and

we obtain:

and (47) follows.

Equation (48) follows from the reasoning below, where (46) is used to get the first equality:

\(\square \)

Remark

Notice that if we add the distribution of the minimum and the maximum, we obtain twice the distribution of the waiting time. In fact this is a remarkable result on its own, which we show directly below.

Lemma 3.3

Proof

Taking the limit\(n \rightarrow \infty \) gives the result.\(\square \)

We now specify these results for the\(M_{\lambda }/G/1\) and\(G/M_{\mu }/1\) queues.

Theorem 3.4

The LST of the steady-state minimum overlap time\(V_{\infty }\) in the\(M_{\lambda }/G/1\) queue is given by

Proof

The term outside the brackets in (47) is given by the Pollaczek-Khinchin formula that appears outside the large brackets in (55). That the term inside the brackets in (47) is given by the expression inside the large brackets in (55) follows by observing that\(\mathbb {P}(S>A) = 1 - \mathcal {L}_S(\lambda )\) and that

Alternatively, we could have used (53), which implies that\(\mathcal {L}_{M_\infty }(\theta ) + \mathcal {L}_{V_{\infty }}(\theta ) = 2 \mathcal {L}_{W_\infty }(\theta )\).\(\square \)

Remark

The moments of\(V_{\infty }\) immediately follow from those of\(M_\infty \), in combination with Lemma 3.3.

Theorem 3.5

The LST of the steady-state minimum overlap time\(V_{\infty }\) in the\(G/M_{\mu }/1\) queue is given by

Proof

The result follows from (47) by using the first part of the right-hand side of (30) for the LST of\(W_\infty \) in the\(G/M_{\mu }/1\) queue, in combination with (use the memoryless property forS twice)\(\mathbb {P}(S>A) = \mathcal {L}_A(\mu )\) and\(\mathbb {E}[\textrm{e}^{-\theta (S-A)^+}|S>A] = \frac{\mu }{\mu +\theta }\). Alternatively, we could again have used (53) and the result for\(\mathcal {L}_{M_\infty }(\theta )\).\(\square \)

Remark

Either by inversion of the LST expression in (58), or by using (48), we obtain the following expression for the distribution of\(V_{\infty }\):

We only demonstrate the latter approach. From (48) and the fact that, in\(G/M_{\mu }/1\), we have\(\mathbb {P}(W \le t) = 1 - \rho ^* \textrm{e}^{-\mu (1-\rho ^*)t}\), it follows that

The double integral can be evaluated in a fairly straightforward manner. It is not surprising that\(V_{\infty }\) in\(G/M_{\mu }/1\) is exp(\(\mu (1-\rho ^*)\)) distributed with an atom at zero, because that also holds for\(W_\infty \) while, moreover, the sojourn time\(W_\infty +S\) is purely exp(\(\mu (1-\rho ^*)\)) (cf. Chapter II.3 of Cohen [7]). The latter implies, in particular, that\(\mathbb {P}(W_\infty +S-A>t|W_\infty +S>A) = \textrm{e}^{-\mu (1-\rho ^*)t}\). Incidentally, to prove that\(\rho ^* -(1-\rho ^*)\mathcal {L}_A(\mu )\), featuring in (59), is positive, observe that we can replace the first\(\rho ^*\) by\(\mathcal {L}_A(\mu (1-\rho ^*))\), while that term is larger than\(\mathcal {L}_A(\mu )\).

Remark

For\(M_{\lambda }/M_{\mu }/1\) it readily follows, from each of the two above theorems, that

in agreement with Theorem 4.2 of [25].

We close this section by briefly outlining how theM/G/1 result can be generalized to\(PH_{ME}/G/1\), and theG/M/1 result to\(G/PH_{ME}/1\). Using Lemma 3.3, we can immediately conclude that

For\(PH_{ME}/G/1\) we can now use Lemma 2.8 and Theorem 2.10 to obtain\(\mathcal {L}_{V_{\infty }}(\theta )\). Alternatively, we can use (47) and observe that\(\mathbb {E}[\textrm{e}^{-\theta [S-A]^+} \cdot \{S > A\}]\) and\(\mathbb {P}(S>A)\) are given by the first double integral in the right-hand side of (42) (taking\(\theta =0\) for the latter probability).

For\(G/PH_{ME}/1\) we can use Lemma 2.11 and Theorem 2.13 to obtain\(\mathcal {L}_{V_{\infty }}(\theta )\). Alternatively, we can use (47) and derive that

and (take\(\theta =0\) in the above formula)

As an other alternative, we could have taken Equation (48) for the distribution of\(V_{\infty }\), and have used (see (44)) that the distribution of\(W_\infty \) is a mixture of\(n(k)+1\) exponentials plus an atom at zero. That allows us to explicitly evaluate the term\(\mathcal {P}(W_\infty +S-A>t, S \le A)\) in (48) by evaluating the double integral over the densities ofS andA. Thus, from the LST expression, it is seen that\(V_{\infty }\), too, is distributed as a sum of\(n(k)+1\) exponentials plus an atom at zero.

In this paper, we analyze the maximum overlap time in the G/G/1 queue. We first analyze the maximum overlap in the\(M_{\lambda }\)/G/1 and G/\(M_{\mu }\)/1 queues and find the exact steady state distribution in some special cases. We also extend these results to the\(G/\mathcal{P}\mathcal{H}_{ME}/1\) and\(\mathcal{P}\mathcal{H}_{ME}/G/1\) queues using a mixture of Erlangs, which are dense in the space of distributions of non-negative random variables. We also leverage a new relationship between the maximum overlap time and the minimum adjacent overlap time to calculate the LST for the steady-state distribution of the minimum adjacent overlap time. Certainly it would be great to obtain explicit LST formulas for the G/G/1, however, this seems to be out of reach until the LST of the waiting time of the G/G/1 queue can be computed explicitly.

In future work, we shall analyze the maximum overlap time in the\(M_\lambda /G/1/k\) queue with a finite waiting room. The\(M_{\lambda }/G/1/k\) queue is also interesting since the maximum overlap time of customern is not necessarily equal to the maximum overlap time of the adjacent customers since the\((n-1)^{th}\) or\((n+1)^{th}\) customer might get blocked from service. Thus, the maximum overlap time of customern could, e.g., involve customer\(n-2\) or\(n+2\) if they were not blocked.

It is also of interest to compute the maximum overlap time of multi-server queues like the Erlang-A queue, see for example [16,22]. In this context, it would be interesting to analyze overlap times in queues with self-exciting arrivals or time varying arrivals like in [5,6,8,14,17,19,20,21]. Finally, we would like to explore overlap times in queues with different types of service disciplines. In particular, priority queues, processor sharing and shortest remaining processing time would be practically relevant. However, the analysis of these disciplines is non-trivial because we do not have the property that the maximum overlap is with either the customer on the left or on the right. The maximum overlap can be with any customer in the system.