Tag Archives: Queueing theory

Queues and Migration Processes

Posted on by
1

Simple Queues

A queue generally has the form of a countable state-space Markov Chain. Here we assume that customers are served in the order they arrive (often referred to as: FIFO – First In First Out). The standard Kendall notation is M/M/C/K. Here the Ms stand for Markov (or memoryless) arrivals, and service times respectively, possibly replaced by G if the process admits more general distributions. C is the number of servers, and K the capacity of the system.

The first example is a M/M/C/C queue, motivated by a telephone network. Here, there are c lines, and an arriving call is lost if all lines are busy at the arrival time. We assume arrivals are a PP(\lambda) process, and the call times are iid Exp(\mu) RVs. We record the number of busy lines, which is a continuous-time Markov chain on state-space [0,c]. As usual, we assume the system operates in equilibrium, and so in particular we must have \lambda<\mu c. It is easy to find the equilibrium distribution. The only non-zero transition probabilities are

q(i-1,i)=\lambda, \quad q(i,i-1)=\mu i\quad i=1,\ldots,c

and so can that that \pi_i=\frac{\nu_i}{i!}\pi_0 satisfies the DBEs where \nu:=\frac{\lambda}{\mu}, sometimes called the traffic intensity. This gives

\pi_c=\mathbb{P}(c\text{ lines busy})=\frac{\nu^c}{c!}\left(\sum_{k=0}^c \frac{\nu^k}{k!}\right)^{-1}

and we define this to be E(\nu,c), Erlang’s formula.

Note that if (X(t),t\in\mathbb{R}) is a MC in equilibrium, (X(-t),t\in\mathbb{R}) is a MC with the same ED, modulo style of discontinuities (ie whether transitions are left-continuous or right-continuous). Therefore, in any queue where all customers get served, eg an M/M/1 queue, for which \lambda<\mu (otherwise the MC is transient, so no ED!), the departure process is the same (in distribution) as the arrivals process.

We can check that this holds for a series of M/M/1 queues, and that in equilibrium, the sizes of the queues are independent. This is merely an extension of the observation that future arrivals for a given queue are independent of the present, and likewise past departures are independent of the future, but the argument is immediately obvious.

Migration Processes

We consider a closed migration process on J colonies, with populations described by a vector n=(n_1,\ldots,n_J). We say that the instantaneous rate of movement of an individual from colony j to colony k is q(n,T_{jk}n)=\lambda_{jk}\phi_j(n_j), for some functions \phi_j(0)=0. We can describe the ED of this system in terms of the distribution obtained when a single individual performs a random walk through the state space, with \phi_j(1) taken to be 1 for each j. We call the DBEs for this case the traffic equations, with solutions (\alpha_j,j\in J). Then, by checking the PBEs, it is clear that the equilibrium distribution of the original migration process satisfies

\pi(n)\propto \prod_{j=1}^J \frac{\alpha_j^{n_j}}{\prod_{r=1}^{n_j}\phi_j(r)}

This is important, as it would have been computationally difficult to solve the original equations for an ED.

The same result holds for an open migration process, where individuals can enter and leave the system, arriving at colony j at rate \nu_j, and leaving at rate \mu_k\phi_k(n_k). Note that this has the same form as if each colony was served by a PP(\alpha_j\lambda_j), with departures at rate \lambda_j\phi_j(n_j):=(\mu_j+\sum_k\lambda_{jk})\phi_j(n_j). But (obviously) this interpretation is not equivalent to the model

The time reversal is also an OMP. One has to check that the transition rates have the correct form, and so the exit process from each colony (in equilibrium, naturally), is PP(\alpha_j\mu_j)$. Most importantly, given a communicating class, we can think of the restriction to this class as an OMP, so in particular, rates of transition between classes are Poisson.

Little’s Law

Informally, the mean number of customers should be equal to the arrival rate multiplied by the mean sojourn time in the system of a customer. This is easiest to formalise by taking an expectation up to a regeneration time. This is T, the first time the system returns to its original state (assumed to be 0 customers), an a.s. finite stopping time.

Set L:=\mathbb{E}\frac{1}{T}\int_0^Tn(s)ds, the average number of customers, and W:=\frac{\mathbb{E}\sum_1^N W_n}{\mathbb{E}N} where N is the number of customers arriving in [0,T], and W_n is the waiting time of the n-th customer.

Little’s Law asserts that L=\lambda W. Note that for a Markov Chain in equilibrium, can define L more simply as \mathbb{E}n and similarly for W.

It is easiest proved by considering the area between the arrivals process and the departure process in two ways: integrating over height and width. Note that working up to a regeneration time is convenient because at that time the processes are equal.

The migration processes above are said to be linear if \phi_j(n_j)=n_j. This process has the form of a Markov chain, and so even in a more general state space, the distribution of points in disjoint subsets of the state-space are independent Poisson processes.

Often though, we start with no individuals in the system, but still the distribution is given by a time-inhomogenous Poisson random measure. The mean is specified by

M(t,E)=\nu\int_0^t P(u,E)du

where \nu is the net arrival rate, and P(u,E) is the probability that an individual is in E, a time interval of u after arriving.

As one would suspect, this is easiest to check through generating functions, since independence has a straightforward generating function analogue, and the expression for a Poisson RV is manageable.

Related articles

One queue or many queues?

Posted on by
4

You have N counters serving customers. What is a better arrangement? To have N queues, one for each counter, as in a supermarket (in the heady days before self-checkout, when ‘something unexpected in the bagging area’ might necessitate a trip to the doctor); or a single queue feeding to counters when they become free, as at a train station, or airport passport control?

Queueing is a psychologically intense process, at least in this country. Here are some human points:

– When you have to choose your line, you might, if you have nothing better to do, spend your time in the queue worrying about whether you chose optimally; whether Fortune has given a customer who arrived after you an advantage. (*)

– A single queue feels long, but conversely gives its users the pleasing feeling of almost constant progress. A particularly difficult customer doesn’t have as great an effect.

Interestingly, we can qualify these remarks in purely mathematical terms. We shall see that the mean waiting times are the same, but that, as we might expect, the variance is less for the single queue.

So to begin, we assume that the arrival process is Poisson, and the service times are exponential. These assumptions are very much not required, but it makes it easier to set up the model as a Markov chain. We do need that \lambda, the arrival rate, is less than \mu N, where \mu is the service rate. Why? Well, otherwise the number of customers waiting to be served will almost surely grow to infinity. When supply is greater than demand, as we specify, we know that there will (almost surely) be infinitely many times when there are no customers in the system. This shows that the Markov chain is recurrent, and so it is meaningful to talk about a mean waiting time.

We assume that in the N-queues arrangement, if a counter is free but the corresponding queue is empty, then a customer from a non-zero queue will take the place if possible. We do not worry about how this customer is chosen. Indeed, we do not concern ourselves with how the customers choose a queue, except to ask that the choice algorithm is previsible. That is, they cannot look into the future and optimise (or otherwise) accordingly. This assumption is standard and reasonable by considering the real-world situation.

Now if we set things up in the right way, we can couple the two processes. Precisely, we start with no customers, and define

0<A_1<A_2<\ldots

to be the sequence of arrival times (note that almost surely no two customers arrive at the same time). Now say that

0<D_1<D_2<\ldots

are the times at which a customer starts being served, that is, moves from the queue to the counter. Say S_1,S_2,\ldots are the service times of the customers, where S_i is the service time of the customer who leaves the queue at time D_i.

The important point is that service times are independent of the queueing process, and are i.i.d. This is where we use the fact that the queue choice strategies are previsible. So, in fact all we need to examine is how customers spend in the queue. Concretely, take Q the queueing time, and S the service time. These are independent so:

\mathbb{E}[Q+S]=\mathbb{E}Q+\mathbb{E}S

and \text{Var} (Q+S)=\text{Var } Q+\text{Var } S.

Observe that A_i,S_i have the same meanings and distributions in both queue models. It is not obvious that D_i does. We notice that for both models, if we define

C_n(t)=\#\{i:D_i+S_i\geq t\} on [D_n,\infty),

the number of the first n customers being served at time t, we have

D_{n+1}=A_{n+1}\vee \inf\{t\geq D_n: C_n(t)\leq N-1\}.

Therefore, by induction on n, we have that (D_i) is well-defined as the same function of (A_i,S_i) for both models. This fact was given as implicitly obvious by many of the remarks on this topic which I found. In my opinion, it is no more obvious than the solution to the original problem.

We can also define, for both models, the number of customers served before the queue is empty again as:

\inf\{N:\exists \epsilon>0\text{ s.t. }c_N(A_{N+1}-\epsilon)=0\},

ie, the least N for which the queue is empty just before the N+1-th customer arrives. As previously discussed, N is a.s. finite. The processes are Markov chains, the first time the queue is empty is a stopping time, and it is meaningful to consider the average waiting time of the N customers before the queue is empty again. There is an expectation over N implicit here too, but this won’t be necessary for our result.

We can now finish the proof. This mean waiting time is

\frac{1}{N}\sum_{i=1}^N(D_i-A_i)

for the single queue. For multiple queues, suppose the i-th customer to arrive is the \sigma(i)-th to be served, where \sigma\in S_N is a permutation. Then the waiting time is

\frac{1}{N}\sum_{i=1}^N (D_{\sigma(i)}-A_i),

which is clearly equal to the previous expression as we can reorder a finite sum.

For variance, we have to consider

\frac{1}{N}\sum_{i=1}^N (D_{\sigma(i)}-A_i)^2.$

Observe that for a\leq b\leq c\leq d, we have 0\leq(d-c)(b-a) and so

(c-a)^2+(d-b)^2\leq (d-a)^2+(c-b)^2,

which we can then apply repeatedly to show that

\sum_{i=1}^N(D_{\sigma(i)}-A_i)^2\geq\sum_{i=1}^N(D_i-A_i)^2,

with equality precisely when \sigma=\text{id}. So we conclude that the variance is in general higher when there are N queues. And the reason is not that different to what we had originally suspected (*), namely that customers do not necessarily get served in the same order as they arrive when there are multiple queues, and so the variance of waiting time is greater.

References

This problem comes from Examples Sheet 1 of the Part III course Stochastic Networks. An official solution of the same flavour as this is also linked from the course page.

Related articles