In this paper we present algorithms for the perfect sampling of single-server time-varying queues with periodic Poisson arrivals under the first come first served (FCFS) discipline. The service durations have periodically time-dependent exponential (\(\mathrm M _t/\mathrm M _t/1\)) or homogeneous general (\(\mathrm M _t/\mathrm G /1\)) distributions. Assuming a cycle length of 1, we construct discrete dominating processes at the integer instants \(n \in \{0, \pm 1, \ldots \}\). Perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue is obtained using dominated CFTP (Kendall and Møller 2000) when the system is relatively lightly loaded or with the regenerative method (Sigman 2012) in the general case. For the \(\mathrm M _t/\mathrm G /1\) queue, perfect sampling is achieved with dominated CFTP.
1 Introduction
Time-varying queueing models are more realistic than time-homogeneous queues, but they are not usually mathematically tractable [17, p. 697]. As noted by [14], computational methods and approximation techniques involved in time-varying queueing problems have long been regarded as challenging.
In this paper we consider cases in which the time-dependent stochastic processes follow periodic patterns. Hasofer [10] showed that the Laplace-Stieltjes Transform (LST) of virtual waiting time in the \(\mathrm M _t/\mathrm G /1\) queue is asymptotically periodic in time. Harrison and Lemoine [9] proved that the virtual waiting time at any given time has its own limiting distribution, and there is one such distribution for each point within the period of the queue. Asmussen and Thorisson [4] extended the context to more general cases, where the inter-arrival times and service durations both depend on the arrival instant within the time period. They proved that with more conditions (such as Harris ergodicity [1, p. 202] of the phase parameter which the inter-arrival time and service duration depend on), the virtual waiting time and queue length also have time-dependent limiting distributions in periodic patterns.
Advertisement
Due to the complexity of the time-varying systems, only asymptotic solutions have been developed, and this has happened gradually over recent decades. By assuming some state at time 0, [22] and [13] found the transient distributions of the number of customers in the system (\(Q_t\)) in \(\mathrm M _t/\mathrm M _t/1\) and \(\mathrm M _t/\mathrm M _t/c\) queues, respectively, using generating functions and Volterra integral equations. Zeifman et al. [21] approximated the limiting mean value (\(\mathbb {E}(Q_t)\)) of the \(\mathrm M _t/\mathrm M _t/1\) queue with the transient distribution of the truncated time-varying birth and death processes by restricting their difference to some controllable extent. The asymptotic periodic solutions for \(\mathrm M _t/\mathrm M _t/1\) and \(\mathrm M _t/\mathrm M _t/c\) systems were achieved by Margolius [14], where distributions and moments are given in terms of integral equations.
If we could draw samples directly from the steady-state distribution, statistical inference would become straightforward. Perfect sampling is an approach to draw a sample directly from the steady-state distribution without explicitly solving for it. The first well-known perfect sampling algorithm is commonly referred to as coupling from the past (CFTP), introduced by [15]. “Dominated CFTP” [11] is an important extension of CFTP. It enables the coupling of Markov chains with unbounded state spaces by reducing the number of past chains that need to be simulated.
Recently, [18] applied dominated CFTP to achieve perfect sampling of an \(\mathrm M /\mathrm G /c\) queue with a “super stable” (i.e., \(\rho < 1/c\)) condition. The backward simulation of an \(\mathrm M /\mathrm G /1\) queue was implemented by running the coupled \(\mathrm M /\mathrm G /1\) Processor-sharing (PS) model, which is time reversible. Connor and Kendall [7] showed how to generalize the dominated CFTP idea used by [18] to relax the super stable restriction to \(\rho < 1\). They further proposed a sandwiching dominated CFTP algorithm for the perfect sampling of the \(\mathrm M /\mathrm G /c\) queue. It significantly reduces the expected runtime. However, in the time-varying circumstance (\(\mathrm M _t/\mathrm G /1\)), it is hard to construct a dominating process which empties, or whose upper and lower envelopes coalesce.
Other methods are also available for perfect sampling. In [2, p. 420] the perfect sampling of regenerative processes was described and then applied to the \(\mathrm M /\mathrm G /c\) queue by [19]. A special case is perfect sampling of the \(\mathrm GI /\mathrm G /1\) queue [2, p. 437], assuming that the Exponential Change of Measure (ECM) [1, p. 352] exists for the underlying random walk.
Advertisement
In practice, dominating processes are key elements for perfect sampling. They are processes defined on the same probability space, which bound the states of the target process, reducing the range of unknown values to a bounded set. In this paper, dominating processes are constructed by modifying the arrival instants or potential departure instants on each periodic cycle of the time-varying queues. In the \(\mathrm M _t/\mathrm M _t/1\) queue, we can simulate the steady-state draw of the dominating process using the ECM method mentioned above for the \(\mathrm GI /\mathrm G /1\) queue. For the \(\mathrm M _t/\mathrm G /1\) queue, we estimate the upper bound of the dominating process based on a coupled homogeneous queue.
In Sect. 2, we present our assumptions and notation. Section 3 presents perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue in both the relatively lightly loaded and more general cases. In Sect. 4, we use dominated CFTP to achieve perfect sampling for the \(\mathrm M _t/\mathrm G /1\) queue. Section 5 concludes the paper.
2 Assumptions and notation
To ensure consistency and clarity, we present our assumptions and notation which we will require in the subsequent analyses.
Define \(\mathbb {Z}=\{0,\pm 1, \pm 2, \ldots \}\), \(\mathbb {N}=\{1,2, \ldots \}\), \(\mathbb {R} = (-\infty ,\infty )\) and \(\mathbb {R}^-=(-\infty ,0]\). Let \(x^+\) be the non-negative part of \(x\); i.e., if \(x>0\), then \(x^+\) equals \(x\); otherwise it is 0.
All queueing systems involved in this paper are work conserving and non preemptive. Queueing disciplines are generally presumed to be First Come First Served (FCFS) unless described otherwise.
Arrivals to the queue form a time-varying Poisson process, with non-trivial periodic arrival rate \(\lambda (t) \ge 0\). Without loss of generality, assume the length of the period is 1. We also assume that “potential service events” form a time-varying Poisson process with periodic rate \(\mu (t) \ge 0\), also with period 1. These are the departures that would occur if the system were to remain busy; there may be fewer actual departures if the queue empties. Both \(\lambda (t) > 0\) and \(\mu (t) > 0\) except possibly at discrete points, so their integrals are strictly increasing. Time “0” is congruent with our time point of interest. For both \(\lambda (t)\) and \(\mu (t)\), \(t\) is measured in clock time:
$$\begin{aligned} \bar{\lambda }&= \int _0^1 \lambda (t) dt, \bar{\mu }= \int _0^1 \mu (t) dt, \hbox { as well as }\nonumber \\ F_{\lambda }(t)&= \frac{\int _0^t \lambda (s)ds}{\bar{\lambda }}, \hbox { and } F_{\mu }(t)=\frac{\int _0^t \mu (s)ds}{\bar{\mu }} \end{aligned}$$
(2.1)
for \(t \in (0,1]\). These functions are strictly increasing on the defined interval, according to the definitions above of \(\lambda (t)\) and \(\mu (t)\). Therefore their inverse functions exist, and are denoted by \(F_{\lambda }^{-1}(x)\) and \(F_{\mu }^{-1}(x), x \in (0,1]\), respectively.
To ensure the stability of the \(\mathrm M _t/\mathrm M _t/1\) queue, the occupancy \(\rho \) must be less than unity; i.e.,
The \(N^D_k\)’s also constitute an i.i.d. sequence of r.v.’s, and they are independent of the \(N_k^A\)’s.
When the server is idle, potential departure events have no effect.
In the algorithms that follow we will couple homogeneous queues to the time-varying queues that we are studying. Denote by \(Q_t^N\) and \(Q_t^H\) the numbers of customers at time \(t\) in the time-varying and homogeneous queues, respectively. Similarly, let \(V_t^N\) and \(V_t^H\) be the unfinished workloads in these two systems, respectively. These processes are all right continuous in \(t\).
3 Perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue
In this section, we present perfect sampling for the \(\mathrm M _t/\mathrm M _t/1\) queue using one of two methods, depending upon the occupancy level in the queue. For the lightly loaded case where the minimum service rate is greater than the maximum arrival rate, dominated CFTP works as a straightforward solution. In the general setting, where we only have \(\bar{\lambda } < \bar{\mu }\), we achieve the perfect sampling using an ECM to sample from the \(\mathrm GI /\mathrm G /1\) queue and the regenerative method to extend this to the time-varying queue.
3.1 Perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue with \(\inf \mu (t) > \sup \lambda (s)\)
Let \(\mu _l = \inf \mu (t)\) and \(\lambda _u = \sup \lambda (t)\). Assume
A stable \(\mathrm M /\mathrm M /1\) queue can be generated with arrival and service rates of \(\lambda _u\) and \(\mu _l\), respectively, since \(\mu _l > \lambda _u\). Based on its homogeneous arrival and potential departure events, the time-varying inputs of the coupled \(\mathrm M _t/\mathrm M _t/1\) queue are simulated as follows:
The time-varying arrival events are filtered from the homogeneous arrivals using the thinning method [17, p. 697, Method 1], thinning arrivals to rate \(\lambda (t) \le \lambda _u\).
Time-varying potential departure events are reproduced based on the homogeneous ones by supplementing the homogenous events with events from a time-varying Poisson process at rate \(\mu (t)-\mu _l\). These extra events are generated with the inter-event time method [17, p. 702, Method 3]. Thus, the composite potential departure process is a superposition of the homogeneous and the time-varying parts, due to the aggregation property of independent Poisson processes.
Under the coupling scheme described above, it is easy to see that the coupled \(\mathrm M /\mathrm M /1\) queue dominates the time-varying one in \(Q_t\) (the number of customers in the system), because the arrivals in the time-varying queue are a subset, and the potential departures a superset, of those in the coupled \(\mathrm M /\mathrm M /1\) queue.
Conceptually, we start the dominating homogeneous queue and the coupled time-varying queue infinitely long ago. At time 0, both of them are in steady state. In a past time \(\tau \in \mathbb {R}^-\), if \(Q^H_{\tau }=0\), then the coupled time-varying queue must also be empty at this time. By running it forward with the time-varying events generated as above, we get a steady-state draw of the time-varying queue at time 0.
In practice, only a finite number of values are needed. The algorithm is described as follows:
1.
We simulate the \(\mathrm M /\mathrm M /1\) dominating queue’s stationary value at time 0. In stationarity \(Q^H_{0} \sim \hbox {Geom}(1-\rho _0)\), where \(\rho _0=\lambda _u/\mu _l\) [12, p. 96].
2.
Simulate the \(\mathrm M /\mathrm M /1\) queue backwards with parameters \(\lambda _u\) and \(\mu _l\) until it becomes idle at time \(\tau \in \mathbb {R}^-\), where \(\tau = \sup \{t: t \in \mathbb {R}^-, Q^H_{t} =0 \}\). This step is implemented based on the time reversibility of the \(\mathrm M /\mathrm M /1\) queue [17, p. 399, Proposition 6.5]. (See Algorithm 1 for the pseudocode for steps 1 and 2.) Record the times of the arrival and departure instants of the time-homogeneous queue on the interval \([\tau , 0)\).
If \(\tau =0\), return \(Q^N_0=0\). Otherwise, continue.
3.
Filter the arrival events generated by step 2 above by thinning as follows: an arrival event at time \(\zeta \) is retained with probability \(\lambda (\zeta ) / \lambda _u\), otherwise it is deleted from the collection of arrival events.
4.
Supplement the potential departures according to a Poisson process with rate \(\mu (t) - \mu _l\). Based upon our assumptions in Sect. 2, since \(\int _0^1 \mu (t) dt = \bar{\mu } < \infty \), we can proceed as follows:
Let \(t_0 = \tau \), and repeat the two sub-steps below for \(n=0,1,\ldots , N\), where \(t_{N} = \max \{t_k: t_k < 0, k = 0, 1, \ldots \}\).
(1)
Simulate \(X_{t_n}\) from the distribution with c.d.f.
where the subscript \(t_n\) indicates that \(F_{t_n}(x)\) depends on \(t_n\).
(2)
Assign \(t_{n+1} = t_n + X_{t_n}\).
If \(N > 0\), then append \(\{t_1,\ldots ,t_N\}\) to the collection of potential departure events, and sort these in ascending order, yielding the aggregate collection of potential departure events for the time-varying queue.
5.
Starting from the empty state at time \(\tau -\) with the set of arrival and potential departure instants generated in the previous two steps, run the time-varying system forward until time 0 and output the state \(Q^N_0\) as a steady-state draw at an integral time for the \(\mathrm M _t/\mathrm M _t/1\) queue.
×
3.2 Perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue: general case
In this section, we use the regenerative method to perform perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue with the general stationary condition, i.e., \(\bar{\lambda }<\bar{\mu }\).
We start with a general description of the regenerative method to obtain a stationary draw from our distribution of interest, which we adapt from [19] in what follows. Let \(X_n\), \(n=0,1,\ldots \) denote the number of customers in a stable queue just before the \((n+1)^{st}\) arrival, with \(X_0=0\). Then \(\{ X_n \}_{n \ge 0}\) is a positive recurrent non-delayed discrete-time regenerative process with \(X_n=0\) as the regenerative setting. Assume its cycle length is \(T \in \mathbb {N}\), with \(\mathbb {E}(T) < \infty \), where the cycle length is defined as
$$\begin{aligned} T = \min \{n: n \ge 1, X_n=0\} \end{aligned}$$
with \(X_0=0\).
Explicitly, a generic cycle with length \(T\) can be defined as
$$\begin{aligned} C = \{ X_n: 0 \le n < T \}. \end{aligned}$$
It is easy to simulate i.i.d. cycles and the sequentially generated ones are denoted by
Denote by \(T^e\) a random variable which has the equilibrium distribution of the cycle length. Suppose we can sample \(T^e\), and let \(J = \min \{ j \ge 1: T^{(j) } \ge T^e \}\), then we have a steady-state draw of \(\{X_n\}_{n \ge 0}\) as
$$\begin{aligned} X^{(J)}_{T^e}. \end{aligned}$$
(Note that, if \(T^{(J)} = T^e\), then \(X=0\).) The interested reader will find a proof of the correctness of the regenerative method to generate a stationary draw in [19]. More details on regenerative methods can be found in [2, p. 420] and [3].
The key to our algorithm is to construct a dominating process which can be simulated in steady-state. If we start with a realization of the time-varying system, and concentrate all arrivals to the end of the interval \((k-1,k], k\in \mathbb {N}\), and all potential departures to the beginning of it, the modified process would dominate the original one in the sense that at whole integer times it will have at least as many customers waiting. Intuitively, since more potential departure events might be lost to an empty queue due to the postponing of the arrival events, there would tend to be more customers remaining in the system after the arrivals than at the same instant in the original process. This idea is explicitly stated by the following proposition.
Proposition 1
Construct a process by modifying a simulation of a stable \(\mathrm M _t/\mathrm M _t/1\) queue as follows. On each interval \((k-1,k], k \in \mathbb {Z}\), let the number of arrivals in the \(\mathrm M _t/\mathrm M _t/1\) queue be \(N^A_k\), and the number of potential departures be \(N^D_k\). In the modified queue let \(N^A_k\) customers arrive as a batch just before time \(k\), and let \(N^D_{k+1}\) potential departures occur just after time \(k\). Denote by \(L_k\) the number of customers counted at time \(k\) of the modified process, and by \(Q^N_k\) that in the corresponding \(\mathrm M _t/\mathrm M _t/1\) queue. If \(L_{k_0} = Q^N_{k_0} = 0\) for some \(k_0\), then the modified system dominates the original one in the number of customers at all integer times after \(k_0\):
$$\begin{aligned} L_k \ge Q^N_k, \ \forall k \ge k_0. \end{aligned}$$
$$\begin{aligned} L_k \ge N^A_k, \forall k \in \mathbb {Z}, \end{aligned}$$
since no matter what the system’s state is, the \(N^A_k\) arrivals provide a lower bound.
It is clear that when \(k=k_0\) the inequality is true. Assume that when \(k=m, m \ge k_0, m \in \mathbb {Z}\), the inequality holds, then when \(k = m+1\) we have one of the following situations:
1.
If \(\exists t \in (m,m+1) \hbox { such that } Q^N_t = 0\), then \(Q^N_{m+1} \le N^A_{m+1} \le L_{m+1}\).
2.
Otherwise, \(Q^N_t > 0, \forall t \in (m,m+1)\) (i.e., the time-varying queue keeps busy on this interval), so that
Thus in both cases, the inductive step is established, and the result follows. \(\square \)
It is clear that \(\{L_k\}_{k\ge 0}\) is a non-delayed regenerative process with \(L_k = 0\) as the regenerative setting. So its cycle length can be defined as
$$\begin{aligned} T = \min \{k: k\ge 1, L_k=0 \}, \end{aligned}$$
(3.2)
with \(L_0=0\). The generic cycle is defined as
$$\begin{aligned} C = \{ L_k: k=0,\ldots ,T-1 \}. \end{aligned}$$
(3.3)
The cycle starts with value zero and lasts through the subsequent positive values of \(L_k\). For example, the \(L_k\) sequence \(\{0,3,1,0,\ldots \}\) yields \(C=\{0,3,1\}\) with length 3 and \(\{0,0,3,\ldots \}\) yields \(C=\{0\}\) with unit-length.
It is clear that \(N^A_k \) is independent of \(\fancyscript{L}_k\), since \(\fancyscript{L}_k\) is determined by \(N^A_i (i < k)\) and \(N^D_i (i\le k)\), and \(N^A_k\) is independent of these r.v.’s as defined in Sect. 2. The limiting random variable \(L_\infty \) is defined by \(\lim _{k \rightarrow \infty } L_k\). A segment of a sample path of the dominating process is shown in Fig. 1. It resembles the Late Arrival System discrete queue of [6], but the differences preclude us from using the LAS model directly. Instead, we exploit the form of (3.5) directly.
Fig. 1
Construction of the dominating process of the \(\mathrm M _t/\mathrm M _t/1\) queue
×
3.2.1 Sampling from the steady-state of the dominating process
Equation (3.5) has the form of Lindley’s equation of the waiting time in a \(\mathrm GI /\mathrm G /1\) queue, and it leads to a special perfect sampling algorithm as shown by [2, p. 437] and [8]; we repeat the algorithm below, for reasons of completeness.
Let \(Z_k = N^A_{k-1} - N^D_k\), \(k \in \mathbb {N}\). The differences \(Z_k\) constitute an i.i.d. sequence, which we generically denote by \(Z = N^A - N^D\). In light of (3.5) we find
Starting from \(\fancyscript{L}_0=0\), \(S_0=0\), define \(S_k = \sum _{i=1}^k Z_i, k \in \mathbb {N}\). Then \(\{S_k\}_{k \ge 0}\) is a random walk with negative drift, since \(\mathbb {E}(Z) = \mathbb {E}(N^A) - \mathbb {E}(N^D) = \bar{\lambda }-\bar{\mu }< 0\). It is shown in [2, p. 3] that
Let \(g(\theta )=\bar{\lambda }e^\theta +\bar{\mu }e^{-\theta }-\bar{\lambda }-\bar{\mu }\). Since \(g(0)=0\), \(g^\prime (0)=\bar{\lambda }-\bar{\mu } < 0\), so \(\exists \theta ^*>0, \hbox { such that } g(\theta ^*)<0\). Since \(\lim _{\theta \rightarrow \infty }g(\theta )=\infty \), it follows that \(g(\theta )=0\) has a positive root on the interval \((\theta ^*,\infty )\). Furthermore, \(g^{\prime \prime }(\theta )=\bar{\lambda }e^\theta +\bar{\mu }e^{-\theta } > 0\), so \(g(\theta )\) is convex, and \(\gamma \) is the unique root of \(g(\theta )=0\) on \((\theta ^*,\infty )\).
Assume non-negative integers \(a\) and \(d\) are the observations of \(N^A\) and \(N^D\), respectively. Let \(z = a - d\) represent the corresponding observation of \(Z\). Since \(N^A\) and \(N^D\) are independent, it follows that
Hence under the measure \(\mathbb {P}_\gamma \), \(Z\) can be treated as the difference of two Poisson r.v.’s: \(N^{A*}\) and \(N^{D*}\), which satisfy
due to the convexity of \(g(\theta )\) as shown above. This implies that \(\{S_k\}_{k\ge 0}\) becomes a random walk with positive drift under the measure of \(\mathbb {P}_\gamma \).
So \(Z\) (under the measure \(\mathbb {P}_\gamma \)) can be simulated by generating \(N^{A*}\) and \(N^{D*}\) from their respective distributions, and then taking the difference.
Now using \(\mathbb {P}_\gamma \), define a strictly increasing process with ladder heights \(S_{\tau (n)}, n=0,1,\ldots \), where
Let \(\fancyscript{L}= \sup \{ S_{\tau (n)}: S_{\tau (n)} \le V \}\), where \(V \sim \hbox {Exp}(\gamma )\). Then \(\fancyscript{L}\) is a stationary draw of \(\fancyscript{L}_\infty \). Thus the stationary draw of \(L_\infty \) given by
where \(N^A \sim \hbox {Poi}(\bar{\lambda })\), and \(N^A\) is independent of \(\fancyscript{L}\).
3.2.2 Algorithm for perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue
Based on the constructed dominating process, whose stationary state can be simulated, the perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) queue is available using the regenerative method.
1.
Simulate a random variable (denoted by \(T^e\)) from the equilibrium distribution of the cycle length (3.2) of the regenerative process of \(\{L_k\}_{k \ge 0}\), which dominates the queue length process in the time-varying queue at the integer time points.
We obtain \(T^e\) as follows. At time 0, sample a stationary draw of the dominating process, denoted by \(L_0\), using the method presented in the previous subsection. Continue simulating this process forward until it becomes 0. According to equations (3.5) and (3.6), we have \( L_k = (L_{k-1}-N^D_k)^+ + N^A_k, k \in \mathbb {N}. \) So
Sequentially simulate generic cycles \(C^{(j)}=\{ L_k^{(j)}: 0 \le k < T^{(j)} \}, j=1,2,\ldots \), of the dominating process, where \(T^{(j)}\) is the length of the \(j^{th}\) cycle. Record \(N^A_k\) and \(N^D_k\)\((1 \le k \le T^{(j)})\), until \(T^{(J)} \ge T^e\), where
Use the order statistics method of simulating the time-varying Poisson process (see [17, p. 700, Method 2]) to construct time-varying events (arrival and potential departure instants) according to \(N^A_k\) and \(N^D_k\)\((1 \le k \le T^{(J)})\) generated in cycle \(C^{(J)}\).
The coupling scheme specified in Proposition 1 implies that the time-varying instant can be generated by shifting the coupled homogeneous one on each interval \((k-1,k]\). Let \(t^N\) and \(t^H\) be the instants in the time-varying and homogeneous systems, respectively, on this interval. For each such instant of a homogeneous arrival or service event on the interval, we know that independent of all other events, it will be uniformly distributed on \((k-1,k]\). The corresponding time-varying instant can be computed as
where \(F^{-1}\) corresponds to the inverse of functions \(F_\lambda (t)\) or \(F_\mu (t)\) defined in equation (2.1).
From time 0, where the system is empty, simulate forward with these inputs to restore the time-varying queue. Output \(Q^N_{T^e}\) as the stationary draw of the number of customers in the \(\mathrm M _t/\mathrm M _t/1\) queue at integer time points.
Remark 1
(1)
According to the regenerative method, \(L^{(J)}_{T^e}\) is a steady-state draw from the dominating process. Since it is coupled with the time-varying queue, at this time point (\(T^e\)), the corresponding sample of \(Q^N_{T^e}\) is also stationary.
(2)
At time 0, even if the stationary draw of \(L_0\) equals zero, we still continue simulating forward.
(3)
Since \(\{L_k\}_{k\ge 0}\) is the dominating process, we can also directly output \(Q^N_0=0\) if \(L_0=0\). But in this case, the condition of stopping the generic cycle simulation becomes
Unfortunately the regenerative method has infinite expected runtime [5, 20]. Thus some runs may take so long that a practitioner would abort them, introducing a bias into the simulation.
These parameters are the same as those used by [14], and have \(\bar{\lambda }=1\) and \(\bar{\mu }=4\).
The regenerative method described in the previous subsection has been applied for the simulation. On a unit cycle, we chose 100 points at equal spacing from 0 to 1 and generated 10,000 samples for each point. Since only \(Q^N_0\) is generated in each trial, to get the samples at different points we changed the phases of the sinusoid functions in each run. For every point we repeated the algorithm 10,000 times. Although it is time consuming (around 100 times more than simulating the successive 99 points by continuing running the system after sampling the first point with the regenerative method), the simulation shows that our method works quite well. In this example, we did not need to abort any long runs. Since the occupancy (\(0.25\)) is quite small, they are very rare.
The idle probability and expected number of customers at time \(t \in (0,1)\) of the time-varying queue are illustrated in Fig. 2. The gray areas indicate pointwise 95 % confidence intervals. The time average of \(Q^N_t\) is around 0.383. The simulated values match very well with the analytical results derived by [14, Section 3], which involve solving a Volterra equation of the second kind numerically.
Fig. 2
Idle probabilities and expected numbers in the \(\mathrm M _t/\mathrm M _t/1\) queue for one period. 100 points were chosen on it with equal intervals. 10,000 samples were drawn for each point
×
For a more efficient simulation, we could repeat the algorithm 10,000 times for just one phase, and continue simulating the process through a whole cycle using standard forward simulation methods. In this case, samples at different time points in the simulation would be correlated and could be studied as draws from their joint distribution.
4 Perfect sampling of the \(\mathrm M _t/\mathrm G /1\) queue
In this section, we present a perfect simulation algorithm with a service time distribution that does not vary with time. Service durations (denoted by \(B\)) are drawn from some general distribution \(G(\cdot )\). We require that \(\mathbb {E}(B^2) < \infty \) in order to ensure that the algorithm for the backward simulation of the coupled \(\mathrm M /\mathrm G /1\) queue has finite expected runtime. Since the service requirement of a customer can be considered to be known at an arrival instant, we can take the perspective of analyzing the unfinished workload to explore this time-varying system. As a result, this case is easier to handle than the \(\mathrm M _t/\mathrm M _t/1\) queue.
As was the case before, the first step is to find a dominating process. In the next subsection we construct a process which dominates the time-varying queue in the unfinished workload. Using dominated CFTP [11] we achieve perfect sampling of the \(\mathrm M _t/\mathrm G /1\) queue.
4.1 The dominating process
Proposition 2
Construct a coupled homogeneous queue (\(\mathrm M /\mathrm G /1\)) by modifying a stable \(\mathrm M _t/\mathrm G /1\) queue as follows. On each interval of \((k-1,k], k \in \mathbb {Z}\), let the number of arrivals in the \(\mathrm M _t/\mathrm G /1\) queue be \(N^A_k\). In the homogeneous queue let \(N^A_k\) customers arrive uniformly on this interval. Let the service durations in the homogeneous queue be the same values in the same order as those in the time-varying queue. Denote by \(V^H_k\) the unfinished workload at time \(k\) in the homogeneous queue, and by \(V^N_k\) that in the time-varying queue. Assume both of them are initially idle at time \(t_0 \in \mathbb {Z}\). Then
We use mathematical induction to prove this proposition. Clearly \(V^N_k \le V^H_k+1\) for \(k = t_0\), since both are 0. For larger \(k\), let \(\xi _k\) be the additional workload that arrives during the interval \((k-1,k]\) (the same for both queues). Let \(\eta _k^N\) be the amount of work done on these new customers during the interval \((k-1,k]\) in the time-varying queue, and let \(\eta _k^H\) be the counterpart in the homogeneous queue.
On the interval \((k-1,k]\), unless the server finishes the remaining workload (carried from previous intervals) within that cycle, it cannot direct any capacity to serve the new arrivals on this interval. Therefore we obtain
Note that \(\eta _k^N \in [0,1)\), and that \(\eta _k^N=0\) if \(V_{k-1}^N > 1\), as there remains earlier work in the system to be done. \(V^N_{k-1} + \eta _k^N \le 1\) if \(V_{k-1}^N \le 1\), since the earlier work has been finished within a unit interval. Similar constraints hold for \(\eta _k^H\).
4.2 Backward simulation of the \(\mathrm M /\mathrm G /1\) queue
The previous subsection established that the upper bound of the dominating process can be estimated with the unfinished workload of the coupled homogeneous \(\mathrm M /\mathrm G /1\) queue. To perform the dominated CFTP algorithm, we simulate the \(\mathrm M /\mathrm G /1\) queue backwards using the time reversibility of its Processor-sharing (PS) variant. (Under the PS discipline, the customers share the server, i.e., when \(n\) customers are present, the server devotes \(1/n\) of its capacity to each. The customers attain service at rate \(1/n\). The first such customer leaves the system once the attained service reaches the minimum of the residual service times, unless another customer arrives first in which case the rates are reduced to \(1/(n+1)\) [1, p. 63].)
Ross [16, p. 280] showed that the \(\mathrm M /\mathrm G /1\) PS model is time reversible and at stationarity the number of customers (\(Q\)) in the system has the geometric distribution
where \(\rho \) is the occupancy; the completed (or unfinished) workload of the \(\mathrm M /\mathrm G /1\) PS queue is
$$\begin{aligned} V = \sum _{i=1}^Q Y_i, \end{aligned}$$
where the \(Y_i\)’s are i.i.d. and they follow the equilibrium distribution of the service duration.
Since the sample paths of the unfinished workload for the \(\mathrm M /\mathrm G /1\) FCFS queue are identical to those of the \(\mathrm M /\mathrm G /1\) PS model, we can use the latter to achieve the backward simulation of the \(\mathrm M /\mathrm G /1\) FCFS queue. Sigman [18, Algorithm1.1, Step1] described this algorithm, which we restate as follows for the sake of completeness:
1.
Simulate a steady-state draw from the \(\mathrm M /\mathrm G /1\) PS queue at time 0: \(Q, Y_1, \ldots , Y_Q\) as specified above.
If \(Q=0\), return 0 as the sampled state, otherwise continue as follows.
2.
Simulate the \(\mathrm M /\mathrm G /1\) queue forward in time with the PS discipline until the server becomes idle; denote this time by \(\zeta \). In this process, record the departure instants and associated service requirements for all customers.
3.
Reverse time: treat each departure as an arrival, changing the signs of their times of occurrence and looking backwards in time, implement the FCFS variant of the \(\mathrm M /\mathrm G /1\) queue.
Details can be found in Algorithm 2, where \(H(\cdot )\) stands for the spread distribution (the length-biased distribution of a randomly selected service duration) of the generic service duration \(B\). It has c.d.f. [18, Remark 1.1].
In Algorithm 2, the vector \(\textsc {Instants}\) is used to store the departure instants (when running the PS model forward) and arrival instants (after being reversed), and \(\textsc {Services}\) the associated service requirements. They are initially empty. When looking backwards, \(\zeta \) is the stationary age of the busy period of the \(\mathrm M /\mathrm G /1\) FCFS queue.
×
It is well known (for example, [12, pp. 213–214]) that
so we need the existence of \(\mathbb {E}(B^2)\) in order for this algorithm to work in finite time.
4.3 Algorithm for perfect sampling of the \(\mathrm M _t/\mathrm G /1\) queue
The perfect sampling of the \(\mathrm M _t/\mathrm G /1\) queue is performed using dominated CFTP. Imagine that an \(\mathrm M _t/\mathrm G /1\) queue and the coupled dominating process \(\{V^H_k + 1\}_{k\in \mathbb {Z}}\), specified in Proposition 2, were started from infinitely long ago, i.e. \(t_0=-\infty \), with empty states, so that at time 0, they must be in steady-state. Since the coupled \(\mathrm M /\mathrm G /1\) queue can be simulated backwards (Sect. 4.2), this algorithm can be described as follows:
1.
Starting from time 0, simulate backwards the \(\mathrm M /\mathrm G /1\) queue until it becomes idle for the first time. Denote this time by \(-\zeta \in \mathbb {R}\).
2.
Continue simulating the \(\mathrm M /\mathrm G /1\) queue backwards until time \(-\zeta _1\), determined as follows. It should be the start of a busy cycle, and the summation of the lengths of the idle periods on the interval \((\lceil -\zeta _1 \rceil , \lfloor -\zeta \rfloor )\) should exceed 2.
Record the homogeneous arrival instants and service durations on the interval \((\lceil -\zeta _1 \rceil , 0)\).
3.
Use equation (3.8) to determine the corresponding time-varying arrival instants on the interval \((\lceil -\zeta _1 \rceil ,0)\) from the arrival instants recorded above.
4.
Starting from \(\lceil -\zeta _1 \rceil \) with unfinished workload \(V^N_{\lceil -\zeta _1 \rceil }=V^H_{\lceil -\zeta _1 \rceil }+1\), run the time-varying queue forward with the collection of time-varying arrival instants and the service durations from the previous steps, and output \(V^N_0\) as a stationary draw of the unfinished workload at time 0 of the \(\mathrm M _t/\mathrm G /1\) queue.
Proposition 3
By following the algorithm for simulating the \(\mathrm M _t/\mathrm G /1\) queue specified above, the output of \(V^N_0\) is a stationary draw of the unfinished workload at time 0.
Proof
Assume an \(\mathrm M _t/\mathrm G /1\) queue and an \(\mathrm M /\mathrm G /1\) queue were started infinitely long ago and coupled in the way described in Proposition 2. So \(V^N_k \le V^H_k+1, \forall k \in \mathbb {Z}\).
The algorithm as constructed above ensures that there exists idle time on interval \((\lceil -\zeta _1 \rceil , \lfloor -\zeta \rfloor )\) in the coupled time-varying queue. When mapping the homogeneous arrivals to time-varying ones, the maximum work originally finished after \(\lfloor -\zeta \rfloor \) that could be rearranged prior to \(\lfloor -\zeta \rfloor \) is \(V^H_{\lfloor -\zeta \rfloor }\). However, since \(V^H_t\) becomes zero on the interval \([\lfloor -\zeta \rfloor ,\lfloor -\zeta \rfloor + 1)\), it follows that \(V^H_{\lfloor -\zeta \rfloor } < 1\). According to the dominance, it follows that \(V^N_{\lceil -\zeta _1 \rceil } \le V^H_{\lceil -\zeta _1 \rceil }+1\). Thus based on the homogeneous system the extra work introduced from the customers arriving prior to \(\lceil -\zeta _1 \rceil \) is no greater than 1. Consequently, the 2 units of idle time on interval \((\lceil -\zeta _1 \rceil , \lfloor -\zeta \rfloor )\) are guaranteed by the algorithm to be sufficient to ensure that there is idle time for the time-varying queue on this interval.
Finally, this idle time existence ensures the coalescence of all possible chains of the time-varying queue. At time \(\lceil -\zeta _1 \rceil \), all possible chains of the \(\mathrm M _t/\mathrm G /1\) queue have unfinished workload ranging from 0 to \(V^H_{\lceil -\zeta _1 \rceil }+1\). They are driven by the same arrival instants and associated homogeneous service durations, and it is easy to see that this coupling is monotone. So when the upper bound chain (corresponding to \(V^N_{\lceil -\zeta _1 \rceil }=V^H_{\lceil -\zeta _1 \rceil }+1\)) becomes zero, so do all the coupled chains, ensuring coalescence. The usual CFTP argument then establishes our result. \(\square \)
4.4 Examples
Here we illustrate sampling the stationary unfinished workload in the \(\mathrm M _t/\mathrm G /1\) queue with Pareto and Erlang distributions of the service durations. In both cases, the arrival rates are
The average unfinished workload and 95 % confidence intervals are illustrated in Fig. 3. It is evident from the figure that they behave in periodic patterns with the same periodic lengths as the arrival processes.
Fig. 3
Average unfinished workloads and 95 % confidence intervals (areas in gray shadow) in two \(\mathrm M _t/\mathrm G /1\) queues with Pareto and Erlang distributions of the service durations. They involve 2 cycles and 100 points are drawn in each cycle. For each point we generate 10,000 samples
×
5 Conclusions
In this paper, we have presented algorithms for perfect sampling of the \(\mathrm M _t/\mathrm M _t/1\) and \(\mathrm M _t/\mathrm G /1\) queues, where the time-varying ingredients have periodic patterns. The stationary queue length and virtual waiting time (unfinished workload) have time-dependent distributions.
For the \(\mathrm M _t/\mathrm M _t/1\) queue with relatively light load, i.e. \(\sup \lambda (s) < \inf \mu (t)\), we implemented perfect sampling with the dominated CFTP by constructing a homogeneous \(\mathrm M /\mathrm M /1\) queue with arrival and service rates of \(\sup \lambda (s)\) and \(\inf \mu (t)\), respectively. In the general case where \(\bar{\lambda } < \bar{\mu }\), we constructed a discrete dominating process, and applied the regenerative method to get the time-dependent steady-state draws of the time-varying queue.
Perfect sampling of the \(\mathrm M _t/\mathrm G /1\) queue was achieved using dominated CFTP. The dominating process was computed based on the unfinished workload of the coupled homogeneous queue (\(\mathrm M /\mathrm G /1\)), which can be simulated backwards using its Processor-sharing variant. Unlike most CFTP implementations, our algorithm allows direct calculation of the (random) starting time in the past, rather than the usual trial and error approach. This is in common with the dominated CFTP algorithm for the \(\mathrm M _t/\mathrm M _t/1\) queue, and also with the dominated CFTP algorithm by [18]. As with other CFTP algorithms, it yields a draw from the stationary distribution at time 0. Other time points in the cycle are simulated simply by adjusting the origin of the clock.
Acknowledgments
This work was supported by NSERC Discovery Grants to Drs. Murdoch and Stanford.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
