1. INTRODUCTION
A typical polling system consists of a number of queues, attended by a single server in a cyclic fashion. There is a huge body of literature on polling systems that has developed since the late 1950s, when the work of Mack [Reference Mack12] and Mack, Murphy, and Webb [Reference Mack, Murphy and Webb13] concerning a patroling repairman model for the British cotton industry were published. Rather than giving a partial overview of the literature, we refer the interested reader to the following books, surveys, and papers on polling systems: Takagi [Reference Takagi17–Reference Takagi and Takagi19], Boxma and Groenendijk [Reference Boxma and Groenendijk5], Levy and Sidi [Reference Levy and Sidi11], Yechiali [Reference Yechiali, Donatiello and Nelson26], Borst [Reference Borst4], Eliazar and Yechiali [Reference Eliazar and Yechiali10], and Nakdimon and Yechiali [Reference Nakdimon and Yechiali14].
Polling systems have been used as a central model for the analysis of a wide variety of applications in the areas of repair problems [Reference Mack12,Reference Mack, Murphy and Webb13], telecommunication systems [Reference Cooper and Murray9], road traffic control [Reference Stidham15], computer networks [Reference Wang and Morris25], multiple access protocols [Reference Bernabéu-Aubán, Ammar and Ahamad3], multiplexing schemes in ISDN [Reference Twu and Chen21], satellite systems [Reference Altman and Kushner1], flexible manufacturing systems [Reference Van Vuuren and Winands24], and the like.
In many of these applications, as well as in most polling models, it is customary to control the amount of service given to each queue during the server's visit. Common service policies are the exhaustive, gated, globally gated, and limited regimes. Under the exhaustive regime, at each visit, the server attends the queue until it becomes completely empty, and only then is the server allowed to move on. Under the gated regime, the only customers served during a visit are the ones who are present when the server enters (polls) the queue, and customers arriving when the queue is attended will be served during the next visit. The globally gated regime, introduced by Boxma, Levy and Yechiali [Reference Boxma, Levy and Yechiali6], is a modification of the gated one: The only customers served during a visit are those who are present at the beginning of a cycle. Finally, under the k-limited service discipline, only a limited number of jobs (at most k) are served at each server's visit to each queue. These service policies imply that the duration of the visit time in a polled queue is a function of the number of customers present there at a given moment (such as the beginning of the cycle or the moment the server enters the queue).
In this article, we analyze a polling system that differs in two ways from the classical polling model. Rather than considering a single server providing service to customers at the various queues, we assume that an infinite number of servers are moving as a single group between the queues. Moreover, the service policy we study is independent of the queue length. We assume that the group of servers visits each queue for an (possibly random) amount of time that is independent of everything else and that has a distribution that might vary per queue. We further assume that the arrival process of customers to each queue is Poisson and that the service-time distribution for customers in each queue is general. To the best of our knowledge, this article is the first in which an M/G/∞-type polling system is analyzed.
The specific application that raised our attention and led us to this model is in the field of road traffic control. Polling models for road traffic are typically along the lines of the classical polling system; namely they involve a single server rotating around a number of queues. Other assumptions that are typically being made for such models include deterministic service times (i.e., the amount of time that a car needs to pass a traffic light after possibly standing in the queue) and deterministic visit times (i.e., the time the traffic light remains green); see, for example, van der Heijden, van Harten, and Ebben [Reference van der Heijden, van Harten and Ebben22]. Although these models provide fairly good approximations of reality, such assumptions fail to capture the variation both in service times and in visit times. Cars do not need the same amount of time to cross a segment of the road: The ones standing ahead in the queue will inevitably need less time and those that arrive while the queue is empty and the traffic light is still green will not even require the additional time incurred by acceleration. Moreover, recent developments in the technology of traffic lights has led to the design of traffic lights that do not turn green unless a queue is formed, and they turn red either when the queue is empty or after a maximum amount of time, which might also vary within a day. As a result, in this article we provide a framework for studying road traffic control under less restrictive assumptions. We propose an infinite-server polling system, which models the behavior of traffic: While the traffic light is green, all cars present in the queue or approaching the traffic light proceed (receive service) and the time they need to complete service is assumed to be a random variable following a general distribution. Furthermore, we assume that the time the traffic light is green (visit time) is random, although our results are directly applicable in the case of deterministic visit times or, more generally, in the case that the visit times follow a discrete distribution taking positive values.
A common approximation to road traffic is to consider the traffic as fluid passing through the road. This approximation is fairly accurate when the traffic is relatively high. Mathematically, high traffic can be modeled by assuming that the arrival rate of customers at each of the queues tends to infinity. The study of such a model provides insights at the queue length (and thus the congestion of a junction) under a heavy load. In this article though we do not study the evolution of the system under a heavy load. We assume that the arrival rate at each queue is fixed. This assumption is usually made for the standard polling systems and provides a reasonable approximation to normal traffic conditions.
The rest of the article is organized as follows. Section 2 introduces the model, gives further notation, and describes formally the evolution of the system. In Section 3 we compute recursively the first moment and the probability generating function of the queue length distributions at a polling instant. Later, in Section 4 we derive the mean and the Laplace–Stieltjes transform of the sojourn time of a customer arriving at queue i, and we show how these expressions simplify in the special case where both the service time and the visit time at queue i are exponentially distributed. Based on the results derived up to that point, in Section 5 we give some numerical results. Specifically, we examine numerically the effect of the first two moments of the visit and service times on the sojourn time of an arbitrary customer. These numerical results indicate that there is an optimal value for the mean visit time to the various queues that minimizes the mean sojourn time of an arbitrary customer. In Section 6 we investigate how we can optimize the visit order of the servers at the various queues so that the expected throughput of the system is maximized. It emerges that even when considering semidynamic control policies, in which the group of servers plans a new route for each cycle, the optimal visiting order that maximizes the expected throughput per cycle is fixed for all cycles. In other words, because of the infinite number of servers, information regarding the queue lengths of all queues at the beginning of a cycle has no effect on the choice of the optimal strategy.
2. MODEL DESCRIPTION AND NOTATION
We consider a polling system with N ⩾ 2 infinite-buffer queues attended by a group of ample number of servers that visits the queues in a fixed cyclic fashion. We index the queues by i = 1, 2, … , N in the order of the servers' movement. We will refer to the polling instant of queue i as the moment when the servers enter that queue. When visiting queue i, the group of servers continues working at this queue for V i units of time and acts there as an M/G/∞ queue. We assume that the visit times are independent and identically distributed (i.i.d.) random variables.
Customers arrive at all queues according to independent homogeneous Poisson processes with rate λi for queue i. After completing their service time, customers leave the system. The service time of each individual customer at queue i is denoted by B i. It is assumed that all service times in one queue are i.i.d. random variables, which are mutually independent of all service times at any other queue. At the end of a visit to queue i, the group of servers moves to queue i + 1, incurring a switch-over time D i and a realization of V i+1 is drawn. We assume that {D i} is a sequence of independent random variables. The total switch-over time during a full cycle is D = ∑i=1ND i, and the length of a full cycle is denoted by the random variable C. We assume that all random variables so far are mutually independent.
During the visit time of the group of servers to queue i, a customer present at queue i at the polling instant of that queue will successfully complete his service with probability p i(V i) = ℙ[B i⩽V i | V i]. We assume that if the service of a customer of queue i is not completed during a single visit, then at the next visit, a new service time will be drawn from the service time distribution of B i for that particular customer.
For a generic random variable Y i, we denote its first two moments by 𝔼[Y i] and 𝔼[Y i2], respectively. Thus, for example, 𝔼[V i] is the mean visit time of the servers at queue i. By convention, ∑i≠j
, and similarly for the product operator. All further notation will be introduced when it is first used.
2.1. Law of Motion
Let X ij, i, j = 1, 2, … , N, denote the number of customers in queue j at the moment when queue i is polled and let A j(t) denote the number of Poisson arrivals to queue j during a time interval of length t. The law of motion describing the evolution of the system when the server moves from queue i to queue i + 1 connects X i+1j to X ij and is given by
where for all k, A j,k(t) is an i.i.d. copy of A j(t), Binom(n, p) is a binomial random variable with parameters n and p, and Poisson(Λi(t)) is a Poisson random variable with rate
Note that from (2.1) we see that for all j, the random variables X ij are independent of V i and D i, which is evident, considering that the number of customers in a queue at the beginning of a visit does not depend on the length of the upcoming visit time or switch-over time.
The relation for j ≠ i is straightforward. The number of customers at queue j at the polling instant of queue i + 1 equals the number of customers that were there at polling instant of queue i plus all customers that arrived during the visit time of queue i and the switch-over time from queue i to queue i + 1.
For j = i, the relation is more involved. When the servers start polling queue i, they encounter X ii customers. After V i time units, only a binomial number of customers out of the initial X ii is still present. The probability that a single customer does not complete his service after V i time units is 1 − p i(V i) = ℙ[B i > V i | V i]. In addition, there is a stream of new arrivals to queue i. The number of customers present at time t in an M/G/∞ queue (starting with zero customers at time t = 0) is Poisson distributed with rate Λi(t), as is given earlier; see Takács [Reference Takács16]. The last term on the right-hand side of (2.1) incorporates the customers that arrived at the queue during the switch-over time from queue i to queue i + 1.
We will employ this relation to derive the mean queue length and the probability generating function of all queues at a polling instant.
3. QUEUE LENGTHS AT POLLING INSTANTS
One of the main tools used in the analysis of polling systems is the derivation of a set of multidimensional probability generating functions of the number of jobs present in the various queues at a polling instant of queue i. The common method is to derive the probability generating function of a given queue at some polling instant in terms of the probability generating function of the same queue at the previous polling instant. Then, from the set of N (implicit) dependent equations of the unknown probability generating functions, one can obtain expressions that allow for numerical calculation of the mean queue length at each queue. These equations simplify significantly for several cases of the distribution of the visit times. In this section, we use the law of motion (buffer occupancy), which is given by (2.1) and apply this technique to compute recursively the first moment and the probability generating function of the queue length distributions at a polling instant.
3.1. Mean Queue length
From (2.1) we have the following relation for the mean queue length of queue j at two consecutive polling instants:
where p i = ℙ[B i⩽V i] = 𝔼[p i(V i)]. Summing (3.1) over i, we obtain
Indeed, in steady state, the mean number of jobs in queue j at a polling instant equals the fraction of jobs (1 − p j)𝔼[X jj] left behind at the end of the previous visit, plus the mean number of arrivals during the cycle time out of queue j, which is λj(∑i≠j 𝔼[V i] + 𝔼[D]), plus the mean number of customers in a M/G/∞ queue at time V j. The mean queue length of queue j at the polling instant of queue i is easily derived from (3.1), yielding
For example, suppose that B j is exponentially distributed with parameter μj. Then
Thus, 𝔼[Λj(V j)] = λj(1 − 𝔼[e −μjV j])/μj. So, in particular, if V j is also exponentially distributed with parameter γj, then we have that 𝔼[Λj(V j)] = λj/(γj + μj), and the mean queue length of each queue can now easily be computed recursively from (3.3).
3.2. Recursive Relation for the Generating Function
Define the generating function of the queue length of all queues at polling instants of queue i as G i(z) = 𝔼[∏j=1Nz jX ij]. Then, from (2.1), we have that
![G_{i+1}\lpar {\bf z}\rpar ={\open E}\left[\matrix{\displaystyle \prod_{j\ne i} z_j^{X_i^j+A_{j\comma 1}\lpar V_i\rpar +A_{j\comma 2}\lpar D_i\rpar} \hfill z_i^{{\rm Binom}\lpar X_i^i\comma\; 1-p_i\lpar V_i\rpar \rpar +{\rm Poisson}\lpar \Lambda_i\lpar V_i\rpar \rpar +A_i\lpar D_i\rpar }}\right].](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn5.gif?pub-status=live)
By conditioning on the vector (X i1, … , X iN), on V i, and on D i, (4.1) becomes
![\eqalign {G_{i+1}\lpar {\bf z}\rpar =\, &{\open E}\left[\, \prod_{j\ne i} z_j^{X_i^j} {\open E}\left[\, \prod_{j\ne i} z_j^{A_{j\comma 1}\lpar V_i\rpar } \, \vert\, V_i\right]{\open E}\left[\, \prod_{j=1}^N z_j^{A_{j\comma 2}\lpar D_i\rpar } \, \vert\, D_i\right]\right. \cr & \times\; {\open E}\left[ z_i^{{\rm Binom}\lpar X_i^i\comma\; 1-p_i\lpar V_i\rpar \rpar } \, \vert\, X^i_i\comma V_i \right]{\open E}\left[ z_i^{{\rm Poisson}\lpar \Lambda_i\lpar V_i\rpar \rpar } \, \vert\, V_i\right]\vphantom{1 \over}\Bigg].}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn6.gif?pub-status=live)
Since the number of arrivals at any queue during a fixed amount of time is independent of the number of arrivals at any other queue during the same given period, we have that
![\eqalign{{\open E}\left[\,\prod_{j=1}^N z_j^{A_j\lpar D_i\rpar } \, \vert\, D_i=x\right]&={\open E}\left[\,\prod_{j=1}^N z_j^{A_j\lpar x\rpar }\right]\cr & =\prod_{j=1}^N{\open E}\left[z_j^{A_j\lpar x\rpar }\right]=\prod_{j=1}^N \sum_{n=0}^\infty z_j^n {\lpar \lambda_j x\rpar ^n \over n!} e^{-\lambda_j x}\cr & =\prod_{j=1}^N e^{-\lambda_j x \lpar 1-z_j\rpar }.}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqnU3.gif?pub-status=live)
Therefore, we have
![{\open E}\left[\,\prod_{j=1}^N z_j^{A_j\lpar D_i\rpar } \, \vert\, D_i\right]=e^{-D_i \sum_{j=1}^N \lambda_j \lpar 1-z_j\rpar }.](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn7.gif?pub-status=live)
Likewise, we obtain that
![{\open E}\left[\, \prod_{j\ne i} z_j^{A_j\lpar V_i\rpar } \, \vert\, V_i\right]=e^{-V_i \sum_{j\ne i} \lambda_j \lpar 1-z_j\rpar }.](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn8.gif?pub-status=live)
Moreover,
![\eqalign{{\open E}\left[z_i^{{\rm Binom}\lpar X_i^i\comma\; 1-p_i\lpar V_i\rpar \rpar } \, \vert\, X_i^i=k\comma\; V_i=x\right] & ={\open E}\left[z_i^{{\rm Binom}\lpar k\comma1-p_i\lpar x\rpar \rpar }\right] \cr & =\sum_{\ell=0}^{k} z_i^\ell \left(\matrix{k \cr \ell}\right)\lpar 1-p_i\lpar x\rpar \rpar ^\ell p_i\lpar x\rpar ^{k-\ell}\cr & =\lpar\, p_i\lpar x\rpar +z_i\lsqb 1-p_i\lpar x\rpar \rsqb \rpar ^{k}\semicolon }](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqnU4.gif?pub-status=live)
in other words,
![{\open E}\left[z_i^{{\rm Binom}\lpar X_i^i\comma\; 1-p_i\lpar V_i\rpar \rpar } \, \vert\, X_i^i\comma\; V_i\right] =\lpar\, p_i\lpar V_i\rpar +z_i\lsqb 1-p_i\lpar V_i\rpar \rsqb \rpar ^{X_i^i}.](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn9.gif?pub-status=live){kind=small}
For the last term of the right-hand side of (3.5) we have that
![\eqalign{{\open E}\left[z_i^{{\rm Poisson}\lpar \Lambda_i\lpar V_i\rpar \rpar }\, \vert\, V_i=x\right] &={\open E}\left[ z_i^{{\rm Poisson}\lpar \Lambda_i\lpar x\rpar \rpar }\right] \cr & =\sum_{n=0}^\infty z_i^n {\lpar \Lambda_i\lpar x\rpar \rpar ^n \over n!}\, e^{-\Lambda_i\lpar x\rpar }=e^{-\Lambda_i\lpar x\rpar \lpar 1-z_i\rpar }\comma }](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqnU5.gif?pub-status=live)
which yields that
![{\open E}\left[z_i^{{\rm Poisson}\lpar \Lambda_i\lpar V_i\rpar \rpar }\, \vert\, V_i\right]=e^{-\Lambda_i\lpar V_i\rpar \lpar 1-z_i\rpar }.](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn10.gif?pub-status=live){kind=small}
Substituting (3.6)–(3.9) into (3.5), we obtain
![G_{i+1}\lpar {\bf z}\rpar ={\open E}\left[\,{\prod_{j\ne i}} z_j^{X_i^j} e^{-V_i \sum_{j\ne i} \lambda_j \lpar 1-z_j\rpar e^{-D_i \sum_{j=1}^N \lambda_j \lpar 1-z_j\rpar } \lpar \, p_i\lpar V_i\rpar +z_i\lsqb 1-p_i\lpar V_i\rpar \rsqb\rpar ^{X_i^i} e^{-\Lambda_i\lpar V_i\rpar \lpar 1-z_i\rpar }\hfill}\right].](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn11.gif?pub-status=live)
![\eqalignno{G_{i+1}\lpar {\bf z}\rpar & ={\open E}\left[e^{-D_i \sum_{j=1}^N \lambda_j \lpar 1-z_j\rpar }\right]\cr & \qquad \qquad\times\; {\open E}\left[\,{\prod_{j\ne i}}z_j^{X_i^j} e^{-V_i \sum_{j\ne i} \lambda_j \lpar 1-z_j\rpar } \lpar\, p_i\lpar V_i\rpar +z_i\lsqb 1-p_i\lpar V_i\rpar \rsqb \rpar ^{X_i^i} e^{-\Lambda_i\lpar V_i\rpar \lpar 1-z_i\rpar}\hfill\right].}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn12.gif?pub-status=live)
![\eqalign{G_{i+1}\lpar {\bf z}\rpar & =\tilde{D}_i \left(\sum_{j=1}^N \lambda_j \lpar 1-z_j\rpar \right)\cr & \times {\open E}\left[\matrix{e^{-V_i \sum_{j\ne i} \lambda_j \lpar 1-z_j\rpar } e^{-\Lambda_i\lpar V_i\rpar \lpar 1-z_i\rpar }\cr G_i\lpar z_1\comma z_2\comma \ldots\comma z_{i-1}\comma p_i\lpar V_i\rpar \cr +\lsqb 1-p_i\lpar V_i\rpar \rsqb z_i\comma z_{i+1}\comma \ldots\comma z_N\rpar }\right]\comma}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn13.gif?pub-status=live)
where D˜i(s) = 𝔼[e −sD i] denotes the Laplace–Stieltjes transform of the random variable D i. Evidently, if V i follows a discrete distribution, the above expression simplifies significantly. Note that the mean queue length at a polling instant (3.3) can also be obtained by differentiating (3.12).
Remark 1
Applying similar techniques, we can also derive the probability generating function of the number of customers at the end of a visit at queue i + 1. If we denote by Y ij the number of customers in queue j = 1, … , N at the moment when the service at queue i = 1, …, N is completed, then the law of motion describing the evolution of the system is given by
Also note that the expected value of Y ij can be easily computed from (3.3) by observing that for all j ≠ i, Y ij = X ij + A j(V i), whereas for the ith queue, we have that Y ii = Binom(X ii, 1 − p i(V i)) + Poisson(Λi(V i)).
4. SOJOURN TIME
Let the sojourn time of a customer at queue i be denoted by S i. We compute its expected value (and thus, by Little's law, also the mean queue length of queue i at an arbitrary moment), and we derive the Laplace–Stieltjes transform of S i. As stated earlier, for each queue we assume that if the service of a customer is not completed during a visit, then for the next visit at that queue, a new service time will be resampled for the same customer from the service-time distribution of that queue.
4.1. Mean Sojourn Time
Recall that the cycle time is given by C = ∑i=1N (V i + D i). In order to derive the mean sojourn time of a customer arriving at queue i, we will need some further notation. Denote by V ires the residual visit time of the group of servers at queue i and by C /i the cycle time except the time spent serving queue i (i.e., C /i = C − V i). Similarly, C /ires represents the residual cycle time excluding the visit time of queue i; that is, C /ires measures the length of time from a random moment after leaving queue i until the next polling instant of queue i. Furthermore, let {C m} be a family of i.i.d. random variables distributed like C and let N i be a (shifted) geometric random variable with success probability p i = 𝔼[p i(V i)] = ℙ[B i⩽V i] (i.e., ℙ[N i = n] = (1 − p i)np i), for all integer n ⩾ 0. One should observe here that N i + 1 is a stopping time, as it is the first time when the service time of a customer in queue i is less than or equal to the visit time at that queue; that is, N i + 1 = inf{k : B i,k ⩽ V i,k}, where B i,k and V i,k are i.i.d. copies of B i and V i respectively. Similarly, a second index is added to a random variable, every time that we explicitly need to indicate that an independent copy is considered. Then the sojourn time of a customer at queue i is given by
Note that the probability of an arrival occurring during the visit time of queue i is 𝔼[V i]/𝔼[C] (i.e., the expected visit time of queue i over the expected cycle time) and similarly for the other two events. Therefore, from (4.1) we obtain that the expected sojourn time of a customer of queue i is given by
![\eqalignno{{\open E}\lsqb S_i\rsqb &={{\open E}\lsqb V_i\rsqb \over {\open E}\lsqb C\rsqb } {\open P}\lsqb B_i \le V_i^{\rm res}\rsqb {\open E}\lsqb B_i \vert B_{i} \le V_{i}^{\rm res}\rsqb \cr & +{{\open E}\lsqb V_i\rsqb \over {\open E}\lsqb C\rsqb } {\open P}\lsqb B_i\gt V_i^{\rm res}\rsqb {\open E}\left[\matrix{V_{i\comma 0}^{\rm res}+\displaystyle\sum_{m=1}^{N_i} C_m +C_{/i}\cr +B_{i\comma N_i+1} \vert B_{i\comma 0} \ge V_{i\comma 0}^{\rm res}}\right]\cr & +{{\open E}\lsqb C_{/i}\rsqb \over {\open E}\lsqb C\rsqb } {\open E}\left[C_{/i}^{\rm res}+ \sum_{m=1}^{N_i} C_m +B_{i\comma N_i+1}\right].}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn16.gif?pub-status=live)
In order to compute the second conditional expectation appearing at the right-hand side of the above equation, we think as follows. For N i cycles, the service of the customer is not completed during that visit because for every visit B i > V i, while at the (N i + 1)st visit, the service is completed within that cycle. Therefore, define
and observe that
![{\open E}\left[\sum_{m=1}^{N_i+1} {\bar C}_m\right]={\open E}\left[\sum_{m=1}^{N_i} {C_m}+C_{/i}+B_{i}\right].](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqnU7.gif?pub-status=live)
Thus,
![\eqalignno{& {\open E}\left[V_{i\comma 0}^{\rm res} + \sum_{m=1}^{N_i} C_m +C_{/i} +B_{i\comma N_i+1} \, \, \vert\,\, B_{i\comma 0} \ge V_{i\comma 0}^{\rm res}\right]\cr &\quad ={\open E}\lsqb V_{i}^{\rm res}\, \vert\, B_{i} \ge V_{i}^{\rm res}\rsqb +{\open E}\left[\sum_{m=1}^{N_i+1} {\bar C}_m\right]\cr &\quad ={\open E}\lsqb V_{i}^{\rm res}\, \vert\, B_{i} \ge V_{i}^{\rm res}\rsqb +{\open E}\lsqb N_i+1\rsqb {\open E}\lsqb {\bar C}_m\rsqb \cr &\quad ={\open E}\lsqb V_{i}^{\rm res}\, \vert\, B_{i} \ge V_{i}^{\rm res}\rsqb +{\open E}\lsqb N_i+1\rsqb \lpar {\open E}\lsqb C_{/i}\rsqb +{\open E}\lsqb \min\lpar B_{i}\comma V_{i}\rpar \rsqb \rpar \comma}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn17.gif?pub-status=live)
where in the second equality we used Wald's equation.
For the third conditional expectation appearing at the right-hand side of (4.2), we have that
![\eqalignno{& {\open E}\left[C_{/i}^{\rm res}+ \sum_{m=1}^{N_i} C_m +B_{i\comma N_i+1}\right]\cr &\quad ={{\open E}\lsqb C_{/i}^2\rsqb \over 2{\open E}\lsqb C_{/i}\rsqb }+{\open E}\left[\sum_{m=1}^{N_i} \lpar C_{/i\comma m}+V_{i\comma m}\rpar +B_{i\comma N_i+1}\right]\cr & \quad ={{\open E}\lsqb C_{/i}^2\rsqb \over 2{\open E}\lsqb C_{/i}\rsqb }+{\open E}\left[\sum_{m=1}^{N_i} C_{/i\comma m}\right]+{\open E}\left[\sum_{m=1}^{N_i+1} \min\lpar B_{i\comma m}\comma V_{i\comma m}\rpar \right]\cr &\quad ={{\open E}\lsqb C_{/i}^2\rsqb \over 2{\open E}\lsqb C_{/i}\rsqb }+{\open E}\lsqb {N_i}\rsqb {\open E}\lsqb C_{/i}\rsqb +{\open E}\lsqb N_i+1\rsqb {\open E}\lsqb \min\lpar B_{i}\comma V_{i}\rpar \rsqb.}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn18.gif?pub-status=live)
Summarizing the above, we have that
In Section 5 we will illustrate through an example the effect of the first two moments of the visit time and the service time on the mean sojourn time of an arbitrary customer.
4.2. The Laplace–Stieltjes Transform
We now derive the Laplace–Stieltjes transform of the sojourn time of a customer of queue i. We first rewrite (4.1) in terms of the Laplace–Stieltjes transforms of all variables involved (cf. (4.5)), and thus we get that
![\eqalignno{{\open E}\lsqb e^{-s S_i}\rsqb & ={{\open E}\lsqb V_i\rsqb \over {\open E}\lsqb C\rsqb } {\open P}\big[ B_i \le V_i^{\rm res}\big] {\open E}\big[ e^{-s B_i}\, \, \vert\,\, B_{i} \le V_{i}^{\rm res}\big] \cr &\quad +{{\open E}\lsqb V_i\rsqb \over {\open E}\lsqb C\rsqb } {\open P}\big[ B_i\gt V_i^{\rm res}\big] {\open E}\big[ e^{-s V_i^{\rm res}}\, \vert\, B_{i} \gt V_{i}^{\rm res}\big] {\open E}\Bigg[ e^{-s \sum_{m=1}^{N_i+1} {\bar C}_m} \Bigg] \cr & \quad +{{\open E}\lsqb C_{/i}\rsqb \over {\open E}\lsqb C\rsqb } {\open E}\left[ e^{-s C_{/i}^{\rm res}}\right] {\open E}\Bigg[ e^{-s {\sum}_{m=1}^{N_i} C_{/i\comma m}}\Bigg] {\open E}\Bigg[ e^{-s \sum_{m=1}^{N_i+1} \min\lpar B_{i\comma m}\comma V_{i\comma m}\rpar }\Bigg].}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn20.gif?pub-status=live)
We rewrite several of the terms appearing above as follows. The distribution function of V ires is given by
yielding
Similarly, we have that
which implies that
![\eqalignno{&{\open E}\left[e^{-s C_{/i}^{\rm res}}\right]={1-\widetilde{C}_{/i} \lpar s\rpar \over s {\open E}\lsqb C_{/i}\rsqb }\comma\;}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn22.gif?pub-status=live){kind=small}
where C˜/i denotes the Laplace–Stieltjes transform of the random variable C /i. Moreover,
![\eqalignno{{\open E}\left[e^{-s \sum_{m=1}^{N_i+1} {\bar C}_m}\right]&=\sum_{n=0}^\infty {\open E}\left[e^{-s \sum_{m=1}^{n+1} {\bar C}_m}\right]\lpar 1-p_i\rpar ^n p_i\cr & =\sum_{n=0}^\infty {\open E}\lsqb e^{-s {\bar C}}\rsqb ^{n+1} \lpar 1-p_i\rpar ^n p_i \cr & = {p_i {\open E}\lsqb e^{-s {\bar C}}\rsqb \over 1-\lpar 1-p_i\rpar {\open E}\lsqb e^{-s {\bar C}}\rsqb }\comma}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn23.gif?pub-status=live)
where C¯ = C /i + min(B i, V i). Likewise, we have that
![{\open E}\left[e^{-s \sum_{m=1}^{N_i} C_{/i\comma m}}\right]={p_i \over 1-\lpar 1-p_i\rpar {\open E}\lsqb e^{-s C_{/i}}\rsqb }](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn24.gif?pub-status=live){kind=small}
and
![{\open E}\left[e^{-s \sum_{m=1}^{N_i+1} \min\lpar B_{i\comma m}\comma V_{i\comma m}\rpar }\right]={p_i {\open E}\lsqb e^{-s \min\lpar B_{i}\comma V_{i}\rpar }\rsqb \over 1-\lpar 1-p_i\rpar {\open E}\lsqb e^{-s \min\lpar B_{i}\comma V_{i}\rpar }\rsqb}.](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn25.gif?pub-status=live){kind=small}
Substituting (4.7)–(4.11) into (4.6), we have that the Laplace–Stieltjes transform of the sojourn time of a customer of queue i is given by
![\eqalignno{{\open E}\lsqb e^{-s S_i}\rsqb &={1 \over {\open E}\lsqb C\rsqb } {\open E}\left[ e^{-s B_i}\, \vert\, B_{i} \le V_{i}^{\rm res}\right] \vint_0^\infty {\open P}\lsqb B_i \,{\le}\, x\rsqb {\open P}\lsqb V_i\gt x\rsqb\, { d} x \cr & \quad + {1 \over {\open E}\lsqb C\rsqb } {\open E}\left[e^{-s V_i^{\rm res}}\, \vert\, B_{i} \gt V_{i}^{\rm res}\right] {p_i {\open E}\big[ e^{-s {\bar C}}\big] \over 1-\lpar 1-p_i\rpar {\open E}\big[ e^{-s {\bar C}}\big] }\cr & \quad \times \vint_0^\infty {\open P}\lsqb B_i \gt x\rsqb {\open P}\lsqb V_i\gt x\rsqb \,dx \cr & \quad + {1-\widetilde{C}_{/i} \lpar s\rpar \over s {\open E}\lsqb C\rsqb } {p_i \over 1-\lpar 1-p_i\rpar \widetilde{C}_{/i} \lpar s\rpar } {p_i {\open E}\left[ e^{-s \min\lpar B_{i}\comma V_{i}\rpar }\right] \over 1-\lpar 1-p_i\rpar {\open E}\left[ e^{-s \min\lpar B_{i}\comma V_{i}\rpar }\right]}.}](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022131819267-0421:S0269964808000065_eqn26.gif?pub-status=live)
Clearly, from the above expression, one can retrieve (4.5) for the mean sojourn time of a customer of queue i.
The transforms appearing in (4.12) might be cumbersome to compute when the service times or the visit times are generally distributed. However, when both B i and V i follow a phase-type distribution, all transforms can be computed explicitly since the class of phase-type distributions is closed under finite minima. Phase-type distributions are widely used in computations. The class of phase-type distributions is dense (in the sense of weak convergence) in the class of all distributions on (0, ∞) (cf. [2, Props. 1 and 2]). As an example, we will derive the Laplace–Stieltjes transform of the sojourn time of a customer of queue i, as well as its mean, in the case that both the visit time and the service time at queue i are exponentially distributed.
4.3. A Special Case
Let the service time and the visit time at queue i be exponentially distributed with rates μi and γi, respectively. Then all terms appearing in (4.5) can be easily computed in terms of μi and γi. For example,
and ℙ[B i > V ires] = γi/(γi + μi). Thus, (4.5) becomes
or
Similarly, (4.12) reduces to
Since 
, we have that the previous expression reduces to
Similar expressions can be easily derived in the case that both the visit times and the service times follow some phase-type distribution, such as Gamma, hyperexponential, or Coxian distributions.
5. NUMERICAL RESULTS
This section is devoted to some numerical results. In particular, we want to examine numerically the effect of the first two moments of the visit and service times on the sojourn time of an arbitrary customer. In all examples, we make the following assumptions. We consider a polling system with two queues. The arrival rate at the first queue is λ1 = 0.8, and at the second queue, it is λ2 = 0.5. The service time and the visit time at the first queue are exponentially distributed with rates μ1 = 1 and γ1 = 1, respectively. Moreover, the total mean switch-over time is taken to be 𝔼[D] = 0.5, and its second moment is assumed to be zero. In all figures that follow, we plot the mean sojourn time of an arbitrary customer, which is estimated by (λ1 𝔼[S 1] + λ2 𝔼[S 2])/(λ1 + λ2).
In Figures 1 and 2 we investigate the effect of the first two moments of the service time at the second queue on the mean sojourn time of an arbitrary customer. For these plots, the visit time at the second queue is considered to be exponentially distributed with rate γ2 = 3/2. For various values of the squared coefficient of variation of the service time at the second queue, which is denoted by c 2B 2, we plot in Figure 1 the mean sojourn time of an arbitrary customer versus the mean service time 𝔼[B 2]. The squared coefficient of variation of the service time is chosen to be comparable to the squared coefficient of variation of the (exponentially distributed) visit time, which is equal to 1. In Figure 2, we plot the mean sojourn time of an arbitrary customer versus c 2B 2 for three values of 𝔼[B 2], which again are chosen to be comparable to 𝔼[V 2].
Mean sojourn time of an arbitrary customer against the mean service time 𝔼[B 2].
Mean sojourn time of an arbitrary customer against the squared coefficient of variation of the service time B 2.
For each case of c 2B 2, we fit a mixed Erlang or hyperexponential distribution to 𝔼[B 2] and c 2B 2, depending on whether the squared coefficient of variation is less or greater than 1; see, e.g., Tijms [Reference Tijms20]. So, if 1/n ⩽ c 2B 2 ⩽ 1/(n − 1) for some n = 2, 3, … , then the mean and squared coefficient of variation of the mixed-Erlang distribution
matches with 𝔼[B 2] and c B 22, provided the parameters p and ζ are chosen as
On the other hand, if c 2B 2 > 1, then the mean and squared coefficient of variation of the hyperexponential distribution
match with 𝔼[B 2] and c B 22, provided the parameters ζ1, ζ2, p, and q are chosen as
As is evident from the plot in Figure 1, the expected sojourn time of an arbitrary customer increases as the mean service time at the second queue increases. Moreover, the rate at which it increases is almost linear as c 2B 2 grows and the effect of the second moment is less pronounced than the effect of 𝔼[B 2].
In Figure 2, one observes that the mean sojourn time of an arbitrary customer decreases as the squared coefficient of variation of the service time increases, contrary to the case for the M/G/1 queue. This result is due to the fact that the service time of a customer that did not complete his service during one visit time is resampled for the following visit time. Therefore, the larger the variability in the service times, the larger is the probability that during the next visit time, this particular customer will complete his service. Recall that the mean visit time at the second queue is equal to 2/3 and observe that in the case that 𝔼[B 2] is less than 𝔼[V 2], the effect of the second moment of the service time on the mean sojourn time of an arbitrary customer is almost negligible.
In Figures 3 and 4 we now investigate the effects of the first two moments of the visit time at the second queue on the mean sojourn time of an arbitrary customer. For these plots, we now take the service time at the second queue to be exponentially distributed with rate μ2 = 3/2. For various values of the squared coefficient of variation of the visit time at the second queue, which is denoted by c 2V 2, we plot in Figure 3 the mean sojourn time of an arbitrary customer versus the mean visit time 𝔼[V 2]. As earlier, the squared coefficient of variation of the visit time is chosen to be comparable with the squared coefficient of variation of the (exponentially distributed) service time, which is equal to 1. In Figure 4, we plot the mean sojourn time of an arbitrary customer versus c 2V 2 for three values of 𝔼[V 2], which again are chosen to be comparable with 𝔼[B 2].
Mean sojourn time of an arbitrary customer against the mean visit time 𝔼[V 2].
Mean sojourn time of an arbitrary customer against the squared coefficient of variation of the visit time V 2.
The plot in Figure 3 is interesting. Evidently, when 𝔼[V 2] is significantly smaller than 𝔼[B 2], only a very small number of customers will be served during a visit. As the mean visit time increases, more customers are served during a visit and the mean sojourn time of an arbitrary customer is reduced. However, as the mean visit time continues to increase, this trend is reversed after the mean sojourn time of an arbitrary customer reaches a global minimum. In other words, there is an optimal value for the mean visit time to some queue that minimizes the mean sojourn time of an arbitrary customer; beyond that value, the mean sojourn time of an arbitrary customer increases at an almost linear rate. This indicates that the polling system under consideration can be optimized in expectation by controlling the visit time to each queue. In the following section, we will develop a policy that minimizes the mean sojourn time of an arbitrary customer in the system.
The plot in Figure 1 is also interesting. As is explained earlier, we fit either a mixture of Erlang distributions or a hyperexponential distribution to each pair of the first two moments of the visit time, depending on the value of the squared coefficient of variation. For every value of c 2V 2, we obtain a different visit time distribution. Note that the jump in Figure 1 occurs when the distribution we fit to the first two moments of the visit time shifts from a mixture of Erlang distributions to a hyperexponential distribution. This indicates that the shape of the visit time distribution is important; for example, hyperexponential distributions are always unimodal, which is not the case for mixed Erlang distributions. Consequently, the first two moments cannot capture sufficiently the effect of the visit time distribution on the mean sojourn time of an arbitrary customer; one needs to know the exact distribution.
6. DYNAMIC CONTROL OF SERVERS' VISITS
A basic question that arises when planning efficient polling systems concerns the order of visits performed by the servers. As it is suggested by Figure 3, the polling system we are considering can be optimized in some way so that the mean sojourn time of an arbitrary customer is minimized. Rather than identifying the value of the minimum mean sojourn time for the cyclic processing (visiting) order considered so far, we first investigate whether there exists a fixed static order that the servers visit the various queues so that the mean (weighted) sojourn time of an arbitrary customer is minimized. As is evident from (4.5), the mean sojourn time of a customer of queue i does not depend on the order the queues have been visited and, thus, neither does the weighted sum thereof. Since the mean sojourn time of an arbitrary customer remains unaffected when altering the processing order, it does not constitute a practical performance measure of our system.
An appealing approach that leads to a simple and tractable rule is to develop a semidynamic control scheme. The idea is to dispatch the group of servers to perform Hamiltonian tours, each tour being possibly different from the previous one, depending on the state of the system at the beginning of the tour, so as to optimize some performance measure. An adequate performance measure is the throughput of the system, namely the number of customers served per cycle, as the throughput can be measured per cycle, and the sojourn time of a customer spans over a random number of cycles. The goal is to maximize the throughput of the system for each cycle.
Specifically, suppose that at the beginning of a cycle n = (n 1, n 2, … , n N) is the state of the system, where n i is the number of jobs waiting in queue i. We will compute the expected value of the number of customers served per cycle under a specific processing order and, consequently, identify the optimal processing order per cycle. The following theorem summarizes the result.
Theorem 1
For the Hamiltonian-tour approach, the optimal visiting order is independent of the number of customers present at the various queues at the start of the cycle and is given by the index-type rule
in the sense that the throughput is maximized if and only if the visiting order is arranged according to an increasing sequence of this rule.
Before proceeding with the proof, we point out that having more information regarding the system, such as the number of customers present at all queues, has no effect on the optimal strategy; thus, it does not improve the performance of the system. This stands in contrast to many other polling systems where, typically, more information regarding a system leads to decisions that increase the efficiency of the system; see, for example, [Reference Browne and Yechiali7, Reference Browne, Yechiali and Bonatti8, Reference Yechiali, Donatiello and Nelson26]. This conclusion stems from the fact that no matter what cycle order is used, the number of customers served in a cycle among those initially present will have the same distribution and will have no effect on the number of others served (or the number receiving partial service) during the cycle. In other words, what happens to those initially present at the beginning of a tour is unaffected by what ordering is used.
Proof
The proof follows from an interchange argument. Consider the processing order π0 = (1, 2, … , N). Denote by θi the throughput of queue i under this processing order (i.e., the number of customers of queue i that are served during a cycle) and denote by θ the total throughput of the system (i.e., the sum of all θi). Given n (i.e., the state of the system at the beginning of a cycle), we will compute the expected value of θ.
The number of customers served after completing a visit at queue i is equal to the portion of customers that where present at polling instant i and successfully completed their service plus the number of customers that arrived during the visit time of queue i and completed their service within that visit. In other words,
As a result,
which yields
where
Observe that the constant c that appears in (6.1) does not depend on π0, whereas the second term at the right-hand side of (6.1) does.
Consider now the processing order π1 = (1, 2, … , j − 1, j + 1, j, j + 2, … , N), where the visit order of queues j and j + 1 is interchanged and denote by θ ′i and θ ′ the throughput of queue i and of the whole system under π1, respectively. We promptly have that 𝔼[θi] = 𝔼[θ ′i] for all i ≠ j, j + 1 and that
Thus,
Therefore, we have that 𝔼[θ]⩽𝔼[θ′] if and only if
or
In other words, we get that the optimal processing order is by visiting the queues according to an increasing order of λip i/(𝔼[V i] + 𝔼[D i]).■
Roughly stated, this rule arranges the visit order according to the ratio between new arrivals per unit time that will successfully complete their service (i.e., λip i) and the mean duration of a visit there (i.e., 𝔼[V i] + 𝔼[D i]). It is intuitively clear that if the mean visit and switch time for a queue are relatively long, then one should visit this queue early on. In this way, the number of customers at the other queues during this cycle will also be relatively high, and as a result, the throughput will be increased since all customers are served simultaneously by an infinite number of servers.
This is an extremely simple rule, which can be directly implemented. Moreover, suppose that, for one reason or another, the objective is to minimize the throughput of the system for each cycle. Then the index rule that determines the order of visits to the queues is simply reversed: The servers complete a Hamiltonian tour arranged in a decreasing order of λip i/(𝔼[V i] + 𝔼[D i]). Observe that, under this strategy, the servers also visit the queues that are empty at the beginning of the cycle.
One expects that the throughput of the system in the long run is improved when these queues are not visited within a cycle; namely it might be more efficient to avoid queues that are empty at the beginning of the cycle in order to allow them to build up.
According to the way the system is designed, even if the servers do not visit a queue that at the beginning of the cycle was empty, the switch time associated with this queue (i.e., the time to switch from this queue to the following one) is still incurred. Therefore, as the number of queues that will not be visited in a cycle grows, the servers spend an increasing amount of time being essentially idle (as they switch between queues).
A possibly more efficient system design is as follows. Rather than envision the group of servers moving from one queue to another, we can think of a central point to which the servers always return after each completion of a visit to a queue. The return time to the central point after visiting queue i is denoted by R i. The servers depart from that central point and move to the following queue that will be served. The total time from the moment the servers leave the central point until they enter queue i is denoted by E i. According to this design, the total time to go from queue i to queue j is given by R i + E j for any i ≠ j. The question that arises is whether there exists a semidynamic control of this system. As earlier, it emerges that a Hamiltonian-tour approach leads to a static processing order according to an index rule.
Theorem 2
For the polling system with a central point, the Hamiltonian-tour approach leads to a fixed optimal visiting order, which is independent of the number of customers present at the various queues at the start of the cycle. The throughput of the system for each cycle is maximized if and only if the visiting order is arranged according to an increasing sequence of the index-type rule
Proof
As earlier, let n = (n 1, n 2, … , n N) be the state of the system at the start of the tour and denote by L the number of nonempty queues, 0 < L ⩽ N, at the beginning of the cycle. The throughput of queue i during a Hamiltonian cycle that visits only the nonempty queues according to the order π0 = (1,2, … ,L) is given by
Consequently,
which yields
where
Applying an interchange argument, we have that the optimal processing order is constructed by an increasing sequence of the index rule given by (6.2).■
As earlier, the optimal tour does not depend on the number of customers present at the beginning of the cycle. This is a direct consequence of the fixed visit times and the underlying M/G/∞ process at each queue.
Index rules appear regularly when optimizing polling systems. Browne and Yechiali [Reference Browne and Yechiali7,Reference Browne, Yechiali and Bonatti8] were the first to obtain dynamic control policies for single-server systems under the exhaustive, gated, or mixed-service regimes. The mechanics of the system are as described here: At the beginning of each cycle, the server decides on a new Hamiltonian tour and visits the channels accordingly. The authors showed that if the objective is to optimize the cycle duration under these policies, then an index-type rule applies, which is similar to the one described here. The main difference is that the index rule that is optimal for these policies depends on the state of the system at the beginning of a cycle, contrary to the results obtained for the fixed-visit-time policy studied in this article. The result derived by Browne and Yechiali [Reference Browne and Yechiali7,Reference Browne, Yechiali and Bonatti8] is a surprising result, as the index rule does not include the service times at the various channels. It is also surprising that the same index rule holds for both the gated and the exhaustive disciplines although the duration of a cycle starting from the same state is different for the two regimes. For a further discussion on other types of index-rule policies, see Yechiali [Reference Yechiali, Donatiello and Nelson26], van der Wal and Yechiali [Reference van der Wal and Yechiali23], and references therein.
Acknowledgments
The authors thank Professor Onno Boxma for several insightful remarks. The authors also acknowledge the hospitality and support of EURANDOM while carrying out this research. The research of the first author was also supported by the Aristotle University of Thessaloniki (full scholarship from the legacy of L. Athanasoula). Part of the second author's work was carried out while visiting EURANDOM in his capacity as Beta Chair.
