UvA-DARE (Digital Academic Repository)
A polling model with smart customers
Boon, M.A.A.; van Wijk, A.C.C.; Adan, I.J.B.F.; Boxma, O.J.
Published in:
Queueing Systems
DOI:
10.1007/s11134-010-9191-0
Link to publication
Citation for published version (APA):
Boon, M. A. A., van Wijk, A. C. C., Adan, I. J. B. F., & Boxma, O. J. (2010). A polling model with smart
customers. Queueing Systems, 66(3), 239-274. https://doi.org/10.1007/s11134-010-9191-0
General rights
It is not permitted to download or to forward/distribute the text or part of it without the consent of the author(s) and/or copyright holder(s),
other than for strictly personal, individual use, unless the work is under an open content license (like Creative Commons).
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating
your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask
the Library: https://uba.uva.nl/en/contact, or a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam,
The Netherlands. You will be contacted as soon as possible.
UvA-DARE is a service provided by the library of the University of Amsterdam (http://dare.uva.nl)
Download date: 05 Jun 2020
Queueing Syst (2010) 66: 239–274
DOI 10.1007/s11134-010-9191-0
A polling model with smart customers
M.A.A. Boon · A.C.C. van Wijk · I.J.B.F. Adan ·
O.J. Boxma
Received: 27 November 2009 / Revised: 7 June 2010 / Published online: 22 September 2010
© The Author(s) 2010. This article is published with open access at Springerlink.com
Abstract In this paper we consider a single-server, cyclic polling system with
switch-over times. A distinguishing feature of the model is that the rates of the
Poisson arrival processes at the various queues depend on the server location. For
this model we study the joint queue length distribution at polling epochs and at the
server’s departure epochs. We also study the marginal queue length distribution at
arrival epochs, as well as at arbitrary epochs (which is not the same in general, since
we cannot use the PASTA property). A generalised version of the distributional form
of Little’s law is applied to the joint queue length distribution at customer’s departure
epochs in order to find the waiting time distribution for each customer type. We also
provide an alternative, more efficient way to determine the mean queue lengths and
mean waiting times, using Mean Value Analysis. Furthermore, we show that under
certain conditions a Pseudo-Conservation Law for the total amount of work in the
system holds. Finally, typical features of the model under consideration are demonstrated in several numerical examples.
The research was done in the framework of the BSIK/BRICKS project, and of the European Network
of Excellence Euro-NF.
M.A.A. Boon () · I.J.B.F. Adan · O.J. Boxma
EURANDOM and Department of Mathematics and Computer Science, Eindhoven University
of Technology, P.O. Box 513, 5600MB Eindhoven, The Netherlands
e-mail: marko@win.tue.nl
I.J.B.F. Adan
e-mail: iadan@win.tue.nl
O.J. Boxma
e-mail: boxma@win.tue.nl
A.C.C. van Wijk
EURANDOM, Department of Industrial Engineering & Innovation Sciences and Department
of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513,
5600MB Eindhoven, The Netherlands
e-mail: a.c.c.v.wijk@tue.nl
240
Queueing Syst (2010) 66: 239–274
Keywords Polling · Smart customers · Varying arrival rates · Queue lengths ·
Waiting times · Pseudo-conservation law
Mathematics Subject Classification (2000) 60K25 · 90B22
1 Introduction
The classical polling system is a queueing system consisting of multiple queues, visited by a single server. Typically, queues are served in cyclic order, and switching
from one queue to the next queue requires a switch-over time, but these assumptions
are not essential to the analysis. The decision at what moment the server should start
switching to the next queue is important to the analysis, though. Polling systems satisfying a so-called branching property generally allow for an exact analysis, whereas
polling systems that do not satisfy this property rarely can be analysed in an exact
way. See Resing [24], or Fuhrmann [14], for more details on this branching property.
There is a huge literature on polling systems, mainly because of their practical
relevance. Applications are found, among others, in production environments, transportation, and data communication. The surveys of Takagi [27], Levy and Sidi [21],
and Vishnevskii and Semenova [29] provide a good overview of applications of
polling systems. These surveys, and [30], Chaps. 2.2 and 3, are also excellent references to find more information about various analysis techniques, such as the Buffer
Occupancy method, the Descendant Set approach, and Mean Value Analysis (MVA)
for polling systems. The vast majority of papers on polling models assumes that the
arrival rate stays constant throughout a cycle, although it may vary per queue. The
polling model considered in the present paper, allows the arrival rate in each queue to
vary depending on the server location. This model was first considered by Boxma [5],
who refers to this model as a polling model with smart customers, because one way
to look at this system is to regard it as a queueing system where customers choose
which queue to join, based on the current server position. Note that Boxma’s definition of smart customers is different from the definition used by Mandelbaum and
Yechiali [22], who study an M/G/1 queue where smart customers may decide upon
arrival to join the queue, not to enter the system at all, or to wait for a while and
postpone the decision.
A relevant application can be found in [16], where a polling model is used to
model a dynamic order picking system (DPS). In a DPS, a worker picks orders arriving in real time during the picking operations and the picking information can
dynamically change in a picking cycle. One of the challenging questions that online
retailers now face is how to organise the logistic fulfillment processes during and
after order receipt. In traditional stores, purchased products can be taken home immediately. However, in the case of online retailers, the customer must wait for the
shipment to arrive. In order to reduce throughput times, an efficient enhancement to
an ordinary DPS is to have products stored at multiple locations. The system can be
modelled as a polling system with queues corresponding to each of the locations, and
customers corresponding to orders. The location of the worker determines in which
of the queues an order is being placed. In this system arrival rates of the orders depend on the location of the server (i.e. the worker), which makes it a typical smart
Queueing Syst (2010) 66: 239–274
241
Fig. 1 A dynamic order picking
system. Orders are placed in
queues Q1 , . . . , QN
customers example. A graphical illustration is given in Fig. 1. We focus on one specific order type, which is placed in two locations, say Qi and Qj . While the picker is
on its way to Qi , say at location 1, all of these orders are routed to Qi and the arrival
rate at Qj is zero. If the picker is between Qi and Qj , say at location 2, the situation
is reversed and Qj receives all of these orders.
Besides practical relevance, the smart customers model also provides a powerful framework to analyse more complicated polling models. For example, a polling
model where the service discipline switches each cycle between gated and exhaustive, can be analysed constructing an alternative polling model with twice the number
of queues and arrival rates being zero during specific visit periods [9]. The idea of
temporarily setting an arrival rate to zero is also used in [2] for the analysis of a
polling model with multiple priority levels. Time varying arrival rates also play a role
in the analysis of a polling model with reneging at polling instants [1].
Concerning state dependent arrival rates, more literature is available for systems
consisting of only one queue, often assuming phase-type distributions for vacations
and/or service times. A system consisting of a single queue with server breakdowns
and arrival rates depending on the server status is studied in [26]. A difference with
the system studied in the present paper, besides the number of queues, is that the machine can break down at arbitrary moments during the service of customers. Polling
systems with breakdowns have been studied as well, cf. [8, 17, 20, 23]. However,
only Nakdimon and Yechiali [23] consider a model where the arrival process stops
temporarily during a breakdown. Shanthikumar [25] discusses a stochastic decomposition for the queue length in an M/G/1 queue with server vacations under less
restrictive assumptions than Fuhrmann and Cooper [15]. One of the relaxations is
that the arrival rate of customers may be different during visit periods and vacations.
Another system, with so-called working vacations and server breakdowns is studied
in [18]. During these working vacations, both the service and arrival rates are different. Mean waiting times are found using a matrix analytical approach. For polling
systems, a model with arrival rates that vary depending on the location of the server
has not been studied in detail yet. Boxma [5] studies the joint queue length distribution at the beginning of a cycle, but no waiting times or marginal queue lengths are
242
Queueing Syst (2010) 66: 239–274
discussed. In a recent paper [11], a polling system with Lévy-driven, possibly correlated input is considered. Just as in the present paper, the arrival process may depend
on the location of the server. In [11] typical performance measures for Lévy processes
are determined, such as the steady-state distribution of the joint amount of fluid at an
arbitrary epoch, and at polling and switching instants. The present paper studies a
similar setting, but assumes Poisson arrivals of individual customers. This enables us
to find the probability generating functions (PGFs) of the joint queue length distributions at polling instants and customer’s departure epochs, and the marginal queue
length distributions at customer’s arrival epochs and at arbitrary epochs (which are
not the same, because PASTA cannot be used). The introduction of customer subtypes, categorised by their moment of arrival, makes it possible to generalise the distributional form of Little’s law (see, e.g., [19]), and apply it to the joint queue length
distribution at departure epochs to find the Laplace–Stieltjes Transform (LST) of the
waiting time distribution.
The present paper is structured as follows: Sect. 2 gives a detailed model description and introduces the notation used in this paper. In Sect. 3 the PGFs of the joint
queue length distributions of all customer types at polling instants are derived. The
marginal queue length distribution is also studied in this section, but we show in
Sect. 4 that the derivation of the waiting time LST for each customer type requires a
more complicated analysis, based on customer subtypes. In Sects. 3 and 4 we need
information on the lengths of the cycle time and all visit times, which are studied
in Sect. 5. In Sect. 6 we adapt the MVA framework for polling systems, introduced
in [31], to our model. This results in a very efficient method to compute the mean
waiting time of each customer type. For polling systems with constant arrival rates, a
Pseudo-Conservation Law (PCL) is studied in [6]. In Sect. 7 we show that, under certain conditions, a PCL is satisfied by our model. Finally, we give numerical examples
that illustrate some typical features and advantages of the model under consideration.
2 Model description and notation
The polling model in the present paper contains N queues, Q1 , . . . , QN , visited in
cyclic order by one server. Switching from Qi to Qi+1 (i = 1, . . . , N , where QN +1
is understood to be Q1 , etc.) requires a switch-over time Si , with LST σi (·). We
assume that at least one switch-over time is strictly greater than zero, otherwise the
mean cycle length in steady-state becomes zero and the analysis changes slightly. See,
e.g., [4] for a relation between polling systems with and without switch-over times.
Switch-over times are assumed to be independent. The cycle time Ci is the time that
elapses between two successive visit beginnings to Qi , and Ci∗ is the time that elapses
between two successive visit endings to Qi . The mean cycle time does not depend
on the starting point of the cycle, so E[Ci ] = E[Ci∗ ] = E[C]. The visit time Vi of Qi
is the time between the visit beginning and visit ending of Qi . The intervisit time Ii
of Qi is the time between a visit ending to Qi and the next visit beginning at Qi .
We have Ci = Vi + Ii , and Ii = Si + Vi+1 + · · · + Si+N −1 , i = 1, . . . , N . Customers
arriving at Qi , i.e. type i customers, have a service requirement Bi , with LST βi (·).
We also assume independence of service times, and first-come-first-served (FCFS)
service order.
Queueing Syst (2010) 66: 239–274
243
The service discipline of each queue determines the moment at which the server
switches to the next queue. In the present paper we study the two most popular service disciplines in polling models, exhaustive service (the server switches to the next
queue directly after the last customer in the current queue has been served) and gated
service (only visitors present at the server’s arrival at the queue are served). The
reason why these two service disciplines have become the most popular in polling
literature, lies in the fact that they are from a practical point of view the most relevant
service disciplines that allow an exact analysis. In this respect the following property,
defined by Resing [24] and also Fuhrmann [14], is very important.
Property 2.1 (Branching Property) If the server arrives at Qi to find ki customers
there, then during the course of the server’s visit, each of these ki customers will
effectively be replaced in an i.i.d. manner by a random population having probability generating function hi (z1 , . . . , zN ), which can be any N -dimensional probability
generating function.
In most cases, a polling model can only be analysed exactly, if the service discipline at each queue satisfies Property 2.1, or some slightly weaker variant of this
property, because in this case the joint queue length process at visit beginnings to a
fixed queue constitutes a Multi-Type Branching Process, which is a nicely structured
and well-understood process. Gated and exhaustive service both satisfy this property,
whereas a service discipline like k-limited service (serve at most k customers during
each visit) does not.
The feature that distinguishes the model under consideration from commonly studied polling models, is the arrival process. This arrival process is a standard Poisson
process, but the rate depends on the location of the server. The arrival rate at Qi is
(P )
denoted by λi , where P denotes the position of the server, which is either serving a
queue, or switching from one queue to the next: P ∈ {V1 , S1 , . . . , VN , SN }. One of the
consequences is that the PASTA property does not hold for an arbitrary arrival, but
as we show in Sect. 3, a conditional version of PASTA does hold. Another difficulty
that arises is that the distributional form of Little’s law cannot be applied to the PGF
of the marginal queue length distribution to obtain the LST of the waiting time distribution anymore. We explain this in Sect. 4, where we also derive a generalisation of
the distributional form of Little’s law.
3 Queue length distributions
3.1 Joint queue length distribution at visit beginnings/endings
The two main performance measures of interest, are the steady-state queue length
distribution and the waiting time distribution of each customer type. In this section
we focus on queue lengths rather than waiting times, because the latter requires a
more complex approach that is discussed in the next section. We restrict ourselves
to branching-type service disciplines, i.e., service disciplines satisfying Property 2.1.
Boxma [5] follows the approach by Resing [24], defining offspring and immigration
244
Queueing Syst (2010) 66: 239–274
PGFs to determine the joint queue length distribution at the beginning of a cycle.
We take a slightly different approach that gives the same result, but has the advantage that it gives expressions for the joint queue length PGF at all visit beginnings
(P )
and endings as well. Denote by L
B (z1 , . . . , zN ) the PGF of the steady-state joint
queue length distribution at beginnings of period P ∈ {V1 , S1 , . . . , VN , SN }. The relation between these PGFs, also referred to as laws of motion in the polling literature, is
(V )
B i (z), where z is a shorthand notation
obtained by application of Property 2.1 to L
for the vector (z1 , . . . , zN ). This property states that each type i customer present at
the visit beginning to Qi will be replaced during this visit by a random population
having PGF hi (z), which depends on the service discipline. The only difference between conventional polling models and the model under consideration in the present
paper, is that the arrival rates depend on the server location. The relations between
(V )
(S )
(V )
B i (z), and L
B i+1 (z) are given by
L
B i (z), L
(S )
(V )
B i z1 , . . . , zi−1 , hi (z), zi+1 , . . . , zN ,
L
B i (z) = L
N
(S )
(V
)
(S
)
λj i (1 − zj ) ,
B i (z) σi
L
B i+1 (z) = L
(3.1)
(3.2)
j =1
where hi (z) is the PGF mentioned in Property 2.1. It is discussed in the context of a polling model with smart customers in [5]. For gated service, hi (z) =
(Vi )
(Vi )
βi ( N
j =1 λj (1 − zj )). For exhaustive service, hi (z) = πi ( j =i λj (1 − zj )),
where πi (·) is the LST of a busy period distribution in an M/G/1 system with only
(V )
type i customers, so it is the root in (0, 1] of the equation πi (ω) = βi (ω + λi i (1 −
(V )
(V )
πi (ω))), ω ≥ 0 (cf. [12], p. 250). Now that we can relate L
B i+1 (z) to L
B i (z), we
(V
)
can repeat this and finally obtain a recursion for L
B i (z). This recursive expression
is sufficient to compute all moments of the joint queue length distribution at a visit
beginning to Qi by differentiation, but iteration of the expression leads to the steadystate queue length distribution at polling epochs, written as an infinite product. We refer to [24] for more details regarding this approach, and for rigorous proofs of the laws
of motion. Stability conditions are studied in more detail in [11], where it is shown
that a necessary and sufficient condition for ergodicity is that the Perron–Frobenius
eigenvalue of the matrix R − IN should be less than 0, where IN is the N × N identity
(V )
matrix, and R is an N × N matrix containing elements ρij := λi j E[Bi ]. This holds
under the assumption that E[Vi ] > 0 for all i = 1, . . . , N .
3.2 Marginal queue length distribution
Common techniques in polling systems (see, e.g. [3, 13]) to determine the PGF of
the steady-state marginal queue length distribution of each customer type, are based
on deriving the queue length distribution at departure epochs. A level-crossing argument implies that the marginal queue length distribution at arrival epochs must be the
same as the one at departure epochs, and, finally, because of PASTA this distribution
is the same as the marginal queue length distribution at an arbitrary point in time.
In our model, the marginal queue length distributions at arrival and departure epochs
Queueing Syst (2010) 66: 239–274
245
are also the same, but the distribution at arbitrary moments is different because of the
varying arrival rates during a cycle. We can circumvent this problem by conditioning on the location P of the server (P ∈ {V1 , S1 , . . . , VN , SN }) and use conditional
PASTA to find the PGF of the marginal queue length distribution at an arbitrary point
in time. Let Li denote the steady-state queue length of type i customers at an arbitrary
(V )
(S )
moment, and let Li j and Li j denote the queue length of type i customers at an
arbitrary time point during Vj and Sj respectively (i, j = 1, . . . , N ). The following
relation holds:
E zLi =
N
(Vj )
(Sj )
E[Vj ]
E[Sj ]
+
E zLi
E zLi
E[C]
E[C]
i = 1, . . . , N.
,
(3.3)
j =1
Note that, at this moment, E[Vj ] and E[C] are still unknown. In Sects. 5 and 6 we
illustrate two different ways to compute them. Since Sj , for j = 1, . . . , N , and Vj ,
for j = i, are non-serving intervals for customers of type i, we use a standard result
(V )
(S )
(see, e.g., [3]) to find the PGFs of Li j and Li j respectively:
(Vj )
Ez
Li
(Sj )
Ez
Li
(Vj )
(Sj )
E[zLBi ] − E[zLBi ]
=
,
(S )
(V )
(1 − z) E[LBi j ] − E[LBi j ]
i = 1, . . . , N; j = i,
(3.4)
i, j = 1, . . . , N,
(3.5)
(Vj +1 )
(Sj )
]
E[zLBi ] − E[zLBi
=
,
(Vj +1 )
(S )
(1 − z) E[LBi
] − E[LBi j ]
)
where LB(P
i , for i = 1, . . . , N , are the number of type i customers at the beginning of period P ∈ {V1 , S1 , . . . , VN , SN }. Their PGFs can be expressed in terms of
(V )
L
B 1 (z) using the relations (3.2) and (3.1), and replacing argument z by the vector
(1, . . . , 1, z, 1, . . . , 1) where z is the element at position i. Using branching theory
(V )
B 1 (z) is given in [5]. The mean values,
from [24], an explicit expression for L
(Vj )
(Sj )
E[LBi ] and E[LBi ], can be obtained by differentiation of the corresponding
PGFs and substituting z = 1.
(Vi )
It remains to compute E[zLi ], i = 1, . . . , N , i.e., the PGF of the number of type i
customers at an arbitrary point within Vi . As far as the marginal queue length of type i
customers is concerned, the system can be viewed as a vacation queue with the intervisit time Ii corresponding to the server vacation. We can use the Fuhrmann–Cooper
decomposition [15], but we have to be careful here. In a polling system where type i
(V )
customers arrive with constant arrival rate λi i , the Fuhrmann–Cooper decomposition states that
(Vi )
E zLi =
(1 − λi
(Vi )
E[Bi ])(1 − z)βi (λi
(1 − z))
(V )
βi (λi i (1 − z)) − z
(Si )
(Vi )
E[zLBi ] − E[zLBi ]
.
×
(V )
(S )
(1 − z) E[LBi i ] − E[LBi i ]
(3.6)
246
Queueing Syst (2010) 66: 239–274
The two parts in this decomposition can be recognised as the PGFs of the number
of type i customers respectively at an arbitrary moment in an M/G/1 queue, and at
an arbitrary point during the intervisit time Ii . Of course, the following relation also
holds:
E zLi =
(Vi )
(Ii )
E[Ii ]
E[Vi ]
E zLi
E zLi .
+
E[C]
E[C]
(3.7)
Combining (3.6) with (3.7), results in:
(Vi )
E zLi
(Vi )
=
1 − λi
(Vi )
E[Bi ] z(1 − βi (λi
(V )
λi i E[Bi ]
(Si )
×
(1 − z)))
(V )
βi (λi i (1 − z)) − z
(Vi )
E[zLBi ] − E[zLBi ]
,
(V )
(S )
(1 − z) E[LBi i ] − E[LBi i ]
(3.8)
for i = 1, . . . , N . The second part of this decomposition is, again, the PGF of the
number of customers at an arbitrary point during the intervisit time Ii . The first part
can be recognised as the PGF of the queue length of an M/G/1 queue with type i
customers at an arbitrary point during a busy period.
Now we return to the model with varying arrival rates. The key observation is
that the behaviour of the number of type i customers during a visit period of Qi ,
is exactly the same in this system as in a polling system with constant arrival rates
(V )
λi i for type i customers. Equation (3.8) no longer depends on anything that happens
(V )
during the intervisit time, because this is all captured in LBi i , the number of type
i customers at the beginning of a visit to Qi . This implies that, for a polling model
with smart customers, the queue length PGF of Qi at a random point during Vi is
also given by (3.8). The only difference lies in the interpretation of (3.8). Obviously,
the first part in (3.8) is still the PGF of the queue length distribution of an M/G/1
queue at an arbitrary point during a busy period. However, the last term can no longer
be interpreted as the PGF of the distribution of the number of type i customers at an
arbitrary point during the intervisit time Ii .
Substitution of (3.4), (3.5), and (3.8) in (3.3) gives the desired expression for the
PGF of the marginal queue length in Qi .
Remark 3.1 The marginal queue length PGF (3.3) has been obtained by conditioning on the position of the server at an arbitrary epoch in a cycle, which explains the
E[Sj ]
E[V ]
probabilities E[C]j (server is serving Qj ) and E[C]
(server is switching to Qj +1 ). It
is easy now to obtain the marginal queue length PGF at an arrival epoch, simply by
conditioning on the position of the server at an arbitrary arrival epoch. The probability that the server is at position P ∈ {V1 , S1 , . . . , VN , SN } at the arrival of a type i
(P )
(Vj )
(S )
λ E[P ]
1 N
E[Vj ] + λi j E[Sj ]). This results
customer, is λi E[C] , with λi = E[C]
j =1 (λi
i
in the following expression for the PGF of the distribution of the number of type i
Queueing Syst (2010) 66: 239–274
247
customers at the arrival of a type i customer:
E zLi |arrival type i =
(V )
N
λi j E[Vj ]
λi E[C]
j =1
(Vj )
E zLi
(Sj )
+
λi
E[Sj ]
λi E[C]
(Sj )
E zLi
, (3.9)
for i = 1, . . . , N . A standard up-and-down crossing argument can be used to argue
that (3.9) is also the PGF of the distribution of the number of type i customers at
the departure of a type i customer. As stated before, it is different from the PGF
of the distribution of the number of type i customers at an arbitrary epoch, unless
(V )
(S )
λi j = λi j = λi for all i, j = 1, . . . , N (as is the case in polling models without
smart customers).
Remark 3.2 Equations (3.4) and (3.5) rely heavily on the PASTA property and are
only valid if type i arrivals take place during the non-serving interval. If no type i ar(P )
rivals take place (i.e. λi = 0 for the non-serving interval P ), both the numerator and
the denominator become 0. This situation has to be analysed differently. Now assume
(P )
that λi = 0 for a specific customer type i = 1, . . . , N , during a non-serving interval
P ∈ {V1 , S1 , . . . , VN , SN }\Vi . We now distinguish between visit periods and switchover periods. Let us first assume that P is a switch-over time, say Sj , j = 1, . . . , N .
The length of a switch-over time is independent from the number of customers in the
system, so the distribution of the number of type i customers at an arbitrary point in
time during Sj is the same as at the beginning of Sj :
(Sj )
E zLi
(Sj )
= E zLBi
,
i, j = 1, . . . , N.
The case where P is a visit time, say P = Vj for some j = i, requires more attention, because the length of Vj depends on the number of type j customers present
at the visit beginning. Since this number is positively correlated with the number of
customers in the other queues, we have to correct for the fact that it is more likely
that a random point during an arbitrary Vj , falls within a long visit period (with more
customers present at its beginning) than in a short visit period. The first step, is to
determine the probability that the number of type i customers at an arbitrary point
(V )
during Vj is k. Since we consider the case where λi j = 0, this implies that we need
the probability that the number of customers at the beginning of Vj is k. Standard
renewal arguments yield
(V )
(Vj )
P Li
(V )
P[LBi j = k]E[Vj |LBi j = k]
=k =
(Vj )
(V )
∞
= l]E[Vj |LBi j = l]
l=0 P[LBi
=
E[Vj 1[LBi(Vj ) = k] ]
E[Vj ]
,
(3.10)
where 1[A] is the indicator function for event A. The first line in (3.10) is based on
the fact that the probability is proportional to the length of visit periods Vj that start
with k type i customers, and to the number of such visit periods Vj . The denominator
is simply a normalisation factor.
248
Queueing Syst (2010) 66: 239–274
Now we can write down the expression for the number of type i customers at an
(V )
arbitrary point during Vj if λi j = 0:
(Vj )
E zLi
=
∞
(Vj )
z k P Li
=k
k=0
∞
1 k
z E[Vj 1[LBi(Vj ) = k] ]
E[Vj ]
k=0
∞
1
=
E Vj
zk 1[LBi(Vj ) = k]
E[Vj ]
=
k=0
=
(Vj )
1
E Vj zLBi
E[Vj ]
=−
for i = 1, . . . , N and j = i.
(Vj )
1
∂
E zLBi e−ωVj
,
E[Vj ] ∂ω
ω=0
(3.11)
(Vj )
Now we only need to determine E[zLBi e−ωVj ]. We use the joint queue length
distribution of all customers present at the beginning of Vj , which is given implicitly
by (3.2). Define Θj as the time that the server spends at Qj due to the presence of one
customer there, with LST θj (·). For gated service θj (·) = βj (·), and for exhaustive
service θj (·) = πj (·). The length of Vj , given that lj type j customers are present
at the visit beginning, is the sum of lj independent random variables with the same
distribution as Θj , denoted by Θj,1 , . . . , Θj,lj . The joint distribution of the number
of type i customers present at the beginning of Vj and the length of Vj is given by
(Vj )
E zLBi
e−ωVj =
∞
∞
E z li e
−ω(Θj,1 +···+Θj,lj )
(Vj )
P LBi
(Vj )
= li , LBj
= lj
li =0 lj =0
=
∞
∞
zli E e−ωΘj,1
li =0 lj =0
× ··· × E e
=
∞
∞
−ωΘj,lj
(Vj )
P LBi
(Vj )
zli θj (ω)lj P LBi
(Vj )
= li , LBj
(Vj )
= li , LBj
= lj
= lj
li =0 lj =0
(Vj )
=L
B
(1, . . . , 1, z, 1, . . . , 1, θj (ω), 1, . . . , 1),
(3.12)
where z corresponds to customers in Qi , and θj (ω) corresponds to customers in Qj .
Substitution of (3.12) in (3.11) gives the desired result.
Queueing Syst (2010) 66: 239–274
249
4 Waiting time distribution
In the previous section we gave an expression for the PGF of the distribution of
the steady-state queue length of a type i customer at an arbitrary epoch, Li . If the
(V )
(S )
arrival rates do not depend on the server position, i.e. λi j = λi j = λi for all i, j =
1, . . . , N , we can use the distributional form of Little’s law (see, e.g., [19]) to obtain
the LST of the distribution of the waiting time of a type i customer, Wi , i = 1, . . . , N .
Because of the varying arrival rates, there is no λi for which the relation E[zLi ] =
E[e−λi (1−z)(Wi +Bi ) ] holds (even if we choose λi = λi ). In the present section we
introduce subtypes of each customer type. Each subtype is identified by the position
of the server at its arrival in the system. We show that one can use a generalised
version of the distributional form of Little’s law that leads to the LST of the waiting
time distribution of a type i customer, when applied to the PGF of the joint queue
length distribution of all subtypes of a type i customer. Determining this PGF requires
a separate treatment of exhaustive and gated service, so results in this section do not
apply to any arbitrary branching-type service discipline.
4.1 Joint queue length distribution at visit beginnings/endings for all subtypes
In the present section we distinguish between subtypes of type i customers, arriving
during different visit/switch-over periods. We define a type i (P ) customer to be a
customer arriving at Qi during P ∈ {V1 , S1 , . . . , VN , SN }. Therefore, only in this
section, we define z in the following way:
(V )
(S )
(V )
(S )
z = z1 1 , . . . , z1 N , . . . , zN 1 , . . . , zN N .
Note that z has 2N 2 components: N customer types times 2N subperiods within
(P )
a cycle (N visit times plus N switch-over times). Let V
Bi (z) be the PGF of the
joint queue length distribution of all these customer types at the moment that the
server starts serving type i customers that have arrived when the server was located at
)
(P
position P . VC
i (z) is defined equivalently for the moment that the server completes
service of type i (P ) customers.
For exhaustive service, the visit period Vi can be divided into the following sub(V )
(S
)
periods: Vi = Vi(Si ) + Vi i+1 + · · · + Vi i+N−1 + Vi(Vi ) . First the type i (Si ) customers
that were present at the visit beginning are served, followed by the type i (Vi+1 ) customers, and so on. Note that during these services only type j (Vi ) customers arrive in
Qj , j = 1, . . . , N . Visit period Vi ends with Vi(Vi ) , i.e., the exhaustive service of all
type i (Vi ) customers that have arrived during Vi so far. The joint queue length process
at polling instants of each of the subperiods is still a Multi-Type Branching Process,
because the service discipline in each subperiod satisfies the Branching Property.
Hence, the laws of motion can be obtained by applying this property successively. As
an example, we show the relations for the PGFs of the joint queue length distributions
at beginnings and endings of the subperiods of V1 :
N
(V )
(S
)
(V
)
(S
)
(S
)
(V
)
(V
)
(V
)
1
2
1
N
2
1
1
1
1 (z) = V
,z ,...,z
1−z
,
λ
z , β1
B1
V
B1 (z) = VC
j
1
j =1
j
1
N
250
Queueing Syst (2010) 66: 239–274
(S )
2)
(V
V
B1 2 (z) = VC
1 (z)
..
.
(V )
=V
B1 2
(V )
z1 1 , 1, β1
N
j =1
(V )
1(SN ) (z)
V
B1 1 (z) = VC
(S )
=V
B1 N
(V )
(V )
λj 1 1 − zj 1
z1(V1 ) , 1, . . . , 1, β1
1)
(V
(V1 ) π1
VC
1 (z) = VB1
N
j =1
j =1
(V1 )
1)
1 − zj(V1 )
λ(V
j
(V1 )
1 − zj
λj
(S )
(S )
, z1 2 , . . . , zN N
(V1 )
, 1, . . . , 1, z2
,
(SN )
, z2(V1 ) , . . . , zN
(S )
, . . . , zN N
,
.
During a switch-over time Sj only type i (Sj ) customers arrive, i, j = 1, . . . , N . We
can relate the PGF of the joint queue length distribution at the beginning of a visit to
1)
(V
Q2 (starting with the service of type 2(S2 ) customers) to VC
1 (z):
(S )
1)
(V
V
B2 2 (z) = VC
1 (z)σ1
N
j =1
(S )
(S )
λj 1 1 − zj 1
.
(S )
(S )
The above expressions can be used to express V
B2 2 (·) in terms of V
B1 1 (·), and this
(S
)
can be repeated to obtain a recursion for V
B1 1 (·).
Remark 4.1 For gated service we take similar steps, but they are slightly different
because arriving customers will always be served in the next cycle. This means that
a visit to Qi starts with the service of all type i (Vi ) customers present at that polling
(V )
(S
)
(S )
(V )
instant: Vi = Vi i + Vi i + Vi i+1 + · · · + Vi i+N−1 . The relations for the PGF of
the joint queue length distribution at beginnings and endings of the subperiods of V1
are
(S )
1)
(V
(V1 )
V
B1 1 (z) = VC
1 (z) = VB1
(V )
1)
(S
(S1 )
V
B1 2 (z) = VC
1 (z) = VB1
N
(V )
(SN )
(S1 )
(V1 )
1
, z1 , . . . , zN
λj
1 − zj
,
β1
j =1
(V )
z1 1 , β1
N
j =1
..
.
(V )
(V )
λj 1 1 − zj 1
(V )
(S )
, z1 2 , . . . , zN N
N
(V )
(SN )
(S
)
(V
)
(S
)
(V
)
(V
)
N
N
1
1
1
1
, z2 , . . . , zN
λj
1 − zj
B1
.
z1 , 1, . . . , 1, β1
VC1 (z) = V
j =1
,
Queueing Syst (2010) 66: 239–274
251
The remainder of this section is valid for any branching-type service discipline treating customers in order of arrival in each queue, such as, for example, exhaustive,
gated, globally gated and multi-stage gated [28]. Having determined the joint queue
length distribution at beginnings and endings of all subperiods within each visit period, we are ready to determine the joint queue length distribution at departure epochs
of all customer subtypes. We follow the approach in [3, 4], which itself is based on
Eisenberg’s approach [13], developing a relation between joint queue lengths at service beginnings/completions and visit beginnings/endings. In [3], for conventional
polling systems, the joint distribution of queue length vector and server position at
service completions leads to the marginal queue length distribution. Developing an
equivalent for our model, requires distinguishing between customer subtypes. Firstly,
the queue length vector z contains all customer subtypes. Secondly, the type of service completion is not just defined by the location i of the server, but also by the
subtype P of the customer that has been served. Therefore, let Mi(P ) (z) denote the
PGF of the joint distribution of the subtypes of customers being served (combination
of i = 1, . . . , N and P ∈ {V1 , S1 , . . . , VN , SN }) and queue length vector of all customer subtypes at service completions. Equation (3.4) in [3], applied to our model,
gives:
(P )
Mi (z) =
1
λE[C]
(Vi )
(Vi )
j =1 λj (1 − zj )
N
(Vi )
(Vi )
(P )
zi − βi
j =1 λj (1 − zj )
βi
N
)
(P )
(P
V
Bi (z) − VC
i (z) , (4.1)
(P )
for i = 1, . . . , N; P ∈ {V1 , S1 , . . . , VN , SN }, and λ = N
i=1 λi . Thus, Mi (z) is the
generating function of the probabilities that, at an arbitrary departure epoch, the departing customer is a type i (P ) customer and the number of customers left behind
(V )
(S )
by this departing customer is l1 1 , . . . , lN N . We now focus on the queue length vector of subtypes of type i customers only, given that the departure takes place at Qi .
The probability that an arbitrary service completion (regardless of the subtype of
the customer) takes place at Qi , is λi /λ. It is convenient to introduce the notation
(V )
(S )
zi = (1, . . . , 1, zi 1 , . . . , zi N , 1, . . . , 1). The PGF of the joint queue length distribution of all subtypes of type i customers at an arbitrary departure from Qi is:
N
(V )
(Vj )
(SN ) D (SN ) λ
(S )
(V1 ) Di 1
i
Mi (zi ) + Mi j (zi ) ,
· · · zi
E zi
=
λi j =1
(4.2)
(P )
where Di is the number of type i (P ) customers left behind at a departure from
(P )
Qi (which should not be confused with Li , the number of type i customers at an
arbitrary moment while the server is at position P ).
(P )
Remark 4.2 Substitution of zi = z for all P ∈ {V1 , S1 , . . . , VN , SN } in (4.2) gives
the marginal queue length distribution of type i customers at departure epochs, which
is equal to (3.9), the marginal queue length distribution at arrival epochs of a type i
customer.
252
Queueing Syst (2010) 66: 239–274
Now we present a generalisation of the distributional form of Little’s law that can
be applied to the joint queue length distribution of all subtypes of a type i customer
at departure epochs from Qi , to obtain the waiting time LST of a type i customer.
Theorem 4.3 The LST of the distribution of the waiting time Wi of a type i customer,
i = 1, . . . , N , is given by
Ee
1
E
=
βi (ω)
−ωWi
1−
(V1 )
Di
ω
··· 1 −
(V1 )
λi
(SN )
Di
ω
(SN )
λi
(4.3)
.
Proof We focus on the departure of a type i customer that arrived during PA ∈
{V1 , S1 , . . . , VN , SN }. We make use of the fact that the sojourn time (i.e., waiting time
plus service time) of this tagged type i (PA ) customer can be determined by studying
the subtypes of all type i customers that he leaves behind on his departure. We need to
distinguish between two cases, which can be treated simultaneously, but require different notations. Firstly, the case where a customer arrives in the system and departs
during another period. In the second case, the customer departs during the same period in which he arrived. Considering the fact we study gated and exhaustive service
only, the second case can only occur in our model if a customer arrives at a queue
with exhaustive service while it is being visited by the server.
Case 1: departure in a different period. In this case we have that PA = Vi , or
PA = Vi but the cycle in which the arrival took place is not the same as the cycle in
which the departure takes place (this situation cannot occur with exhaustive service).
All type i customers that are left behind, have arrived during the residual period PA ,
all periods between PA and Vi (if any), and during the elapsed part of Vi . Denote
by PI the set of visit periods and switch-over periods that lie between PA and Vi .
Furthermore, let PA,res be the residual period PA . Finally denote by Vi,past the age of
Vi at the departure instant of the tagged type i customer.
Case 2: departure during the period of arrival. If the customer arrived during the
same visit period in which his departure takes place, take PA,res = 0, PI = ∅, and
Vi,past is the time that elapsed since the arrival of the tagged type i (Vi ) customer.
In both cases, the joint queue length distribution of all customer i subtypes at this
departure instant is given by (4.2). Since we assume FCFS service, at such a departure
instant no type i customers are present anymore that have arrived before the arrival
epoch of the tagged type i customer. This results in
(V )
(S ) D (SN )
(V ) D 1
E zi 1 i · · · zi N i
=E e
(PA )
−λi
(PA )
(1−zi
(V )
(V )
(p)
(p)
)PA,res − p∈P λi (1−zi )p−λi i (1−zi i )Vi,past
I
Equation (4.3) follows from the relation Wi + Bi = PA,res +
substitution of
(P )
zi
=1−
ω
(P )
λi
p∈PI
(4.4)
p + Vi,past and
for all P ∈ {V1 , S1 , . . . , VN , SN } in (4.4).
(P )
.
Remark 4.4 Theorem 4.3 only holds if λi > 0 for all i = 1, . . . , N , and P ∈
(P )
{V1 , S1 , . . . , VN , SN }. If λi = 0 for a certain i and P , we can still find an expression
Queueing Syst (2010) 66: 239–274
253
for E[e−ωWi ], but we might have to resort to some “tricks”. In Sect. 8, Example 2,
we show how the introduction of an extra (virtual) customer type can help to resolve
this problem.
5 Cycle time, intervisit time and visit times
In the previous sections we repeatedly needed the mean cycle time E[C] and the mean
visit times E[Vi ], i = 1, . . . , N . In this section we study the LSTs of the cycle time
distribution and visit time distributions, which can be used to obtain the mean and
higher moments. The LSTs of the distributions of the visit times Vi , i = 1, . . . , N ,
can easily be determined for any branching-type service discipline using the function
θi (·), introduced in Remark 3.2, and the joint queue length distribution at the visit
beginning of Qi (not taking subtypes into account):
(Vi )
1, . . . , 1, θi (ω), 1, . . . , 1 .
E e−ωVi = L
B
(5.1)
The cycle time Ci is defined as the time that elapses between two consecutive visit
beginnings to Qi . We consider branching-type service disciplines only, i.e., service
disciplines for which Property 2.1 holds. The cycle time LST for polling models with
branching-type service disciplines and arrival rates independent of the server position,
has been established in [10]. We adapt their approach to the model with arrival rates
depending on the server location. Using θi (·), i = 1, . . . , N , we define the following
functions in a recursive way:
ψ (VN ) (ω) = ω,
ψ (Vi ) (ω) = ω +
N
λk
N
λk
k=i+1
(Vi )
1 − θk ψ (Vk ) (ω) ,
i = N − 1, . . . , 1.
Similarly, define
ψ (SN ) (ω) = ω,
ψ (Si ) (ω) = ω +
k=i+1
1 − θk ψ (Vk ) (ω) ,
(Si )
i = N − 1, . . . , 1.
Theorem 5.1 The LST of the distribution of the cycle time C1 is:
N
θ1 ψ (V1 ) (ω) , . . . , θN ψ (VN ) (ω)
σi ψ (Si ) (ω) .
(V1 )
E e−ωC1 = L
B
(5.2)
i=1
Proof Similar to the proof of Theorem 3.1 in [10], by giving an expression for the cycle time LST conditioned on the numbers of customers in all queues at the beginning
of a cycle, and then by subsequently unconditioning one queue at a time.
254
Queueing Syst (2010) 66: 239–274
The LST of the distribution of the intervisit time I1 can be found in a similar way:
N
σi ψ (Si ) (ω) .
1, θ2 ψ (V2 ) (ω) , . . . , θN ψ (VN ) (ω)
(S1 )
E e−ωI1 = L
B
(5.3)
i=1
Equations (5.2) and (5.3) hold for general branching-type service disciplines. For
gated and exhaustive service we can give expressions that are more compact and
easier to interpret, using the joint queue length distribution of all customer subtypes
at visit beginnings, as given in Sect. 4.1.
Theorem 5.2 If Qi receives exhaustive service, the LST of the distribution of the
cycle time Ci∗ , starting at a visit ending to Qi , and the LST of the distribution of the
intervisit time Ii , are given by:
∗
(Si )
Bi
E e−ωCi = V
1, . . . , 1, πi (ω) −
(S )
Bi i 1, . . . , 1, 1 −
E e−ωIi = V
ω
(V )
λi 1
ω
(V )
λi 1
, . . . , πi (ω) −
,...,1 −
ω
(S )
λi N
ω
(S )
λi N
, 1, . . . , 1 , (5.4)
, 1, . . . , 1 ,
(5.5)
(P )
provided that λi = 0 for all P ∈ {V1 , S1 , . . . , VN , SN }. In the right hand sides
(P )
of (5.4) and (5.5), the components zj with j = i are 1.
If Qi receives gated service, the LST of the distribution of the cycle time Ci , and
the LST of the distribution of the intervisit time Ii , are given by
(Vi )
E e−ωCi = V
Bi
1, . . . , 1, 1 −
ω
(V )
λi 1
(V )
Bi i 1, . . . , 1, 1, 1 −
E e−ωIi = V
1−
ω
(S )
λi N
(P )
again provided that λi
in (5.6).
,...,1 −
ω
(V )
λi 1
ω
(S )
λi N
,...,1 −
, 1, . . . , 1 ,
ω
(S )
λi i−1
, 1, 1 −
ω
(S )
λi i
,...,
, 1, . . . , 1 ,
(5.6)
(Vi )
= 0 for all P ∈ {V1 , S1 , . . . , VN , SN }. Note that zi
=1
Proof We prove the exhaustive case only, the proof for gated service proceeds along
the same lines. Using Ii = Si + Vi+1 + Si+1 + · · · + Si+N −1 , and the fact that no type
i (Vi ) customers are present at the beginning of the intervisit period (and hence also at
the beginning of a cycle Ci∗ ), we obtain:
(S )
(V )
(S )
V
Bi i 1, . . . , 1, zi 1 , . . . , zi N , 1, . . . , 1
(S
)
(S
)
(S )
(Si )
(1−zi i )Si −···−λi i+N−1 (1−zi i+N−1 )Si+N−1
= E e−λi
.
(5.7)
Queueing Syst (2010) 66: 239–274
(P )
Substitution of zi
=1−
ω
(P )
λi
255
for all P ∈ {V1 , S1 , . . . , VN , SN } proves (5.5). Equa-
tion (5.4) follows by using the relation Ci∗ = Ii + Vi , and noting that Vi is the sum of
the busy periods initiated by all type i customers that have arrived during Ii . In terms
of LSTs:
(S
)
(Si )
(1−πi (ω)))Si −···−(ω+λi i+N−1 (1−πi (ω)))Si+N−1
∗
E e−ωCi = E e−(ω+λi
(Si )
−λi
(1−(πi (ω)−
=E e
which, by (5.7), reduces to (5.4).
(Si+N−1 )
ω
(1−(πi (ω)− (S ω ) ))Si+N−1
(S ) ))Si −···−λi
λi i
λi i+N−1
,
Differentiation of the LSTs of Ci and Ci∗ for i = 1, . . . , N , shows that, just like
in polling models with constant arrival rates, the mean cycle time does not depend
on the starting point of the cycle, i.e. E[Ci ] = E[Ci∗ ] = E[C]. The mean cycle time
E[C] and mean visit times E[Vi ] can be obtained by differentiating the corresponding
LSTs. In the next section a more efficient method is described to compute them.
6 Mean value analysis
In this section we extend the Mean Value Analysis (MVA) framework for polling
models, originally developed by Winands et al. [31], to suit the concept of smart customers. For this purpose, we first outline the main ideas of MVA for polling systems.
Subsequently, we determine the mean visit times and the mean cycle time in a numerically more efficient way than in the previous section, and, finally, we present the
MVA equations for a polling system with smart customers.
6.1 Main idea MVA
For “ordinary” polling models, where the arrival rates at a queue do not depend on
the position of the server, in [31] an approach is described for deriving the steadystate mean waiting times at each of the queues, E[Wi ] for i = 1, . . . , N , by setting
up a system of linear equations, where each equation has a probabilistic and intuitive
explanation. We sketch the main ideas of MVA for exhaustive service; the cases of
gated or mixed service disciplines require only minor changes.
The mean waiting time E[Wi ] of a type i customer, excluding his service time, can
be expressed in the following way: upon arrival of a (tagged) type i customer, he has
to wait for the (remaining) time it takes to serve all type i customers already present
in the system, plus possibly the time before the server arrives at Qi . By PASTA,
the arriving customer finds in expectation E[L̂i ] waiting type i customers in queue,
each having an expected service time E[Bi ]. Note that we use L̂i to denote the queue
lengths excluding customers in service. The expected time until the server returns
to Qi , is denoted by E[Ti ] (which depends on the service discipline of all queues).
A fraction ρi := λi E[Bi ] of the time, the server is serving Qi , and hence, with
probability ρi , an arriving customer has to wait for a mean residual service time,
256
Queueing Syst (2010) 66: 239–274
denoted by E[RBi ]; otherwise he has to wait until the server returns. This gives, for
i = 1, . . . , N :
E[Wi ] = E[L̂i ]E[Bi ] + ρi E[RBi ] + (1 − ρi )E[Ti ].
Little’s law gives E[L̂i ] = λi E[Wi ], for i = 1, . . . , N , and so it remains to derive
E[Ti ]. For this, first a system of equations is composed for the conditional mean
queue lengths, which can be expressed in mean residual durations of (sums of) visit
and switch-over times. The solution of this system of equations can be used to determine E[Ti ], and hence E[L̂i ] and E[Wi ] follow.
6.2 Mean visit times and mean cycle time
For the case of smart customers, the visit times to a queue depend on all arrival rates
(V )
(S )
λi j and λi j . In order to extend MVA to this case, we first derive the mean visit
times to each of the queues, E[Vi ], for i = 1, . . . , N . We set up a system of N linear
equations where the mean visit time of a queue is expressed in terms of the other
mean visit times. We again focus on the exhaustive service discipline.
At the moment the server finishes serving Qi , there are no type i customers present
in the system any more. From this point on, the number of type i customers builds up
at rates λ(Si ) , λ(Vi+1 ) , . . . , λ(Si+N−1 ) (depending on the position of the server), until the
server starts working on Qi again. Each of these customers initiates a busy period,
with mean E[BPi ] := E[Bi ]/(1 − λi(Vi ) E[Bi ]). This gives:
E[Vi ] = E[BPi ]
(S )
λi i E(Si ) +
(Vj )
(Sj )
λi E[Vj ] + λi E[Sj ] ,
i+N
−1
j =i+1
for i = 1, . . . , N . The E[Vi ] follow from solving this set of equations. This method
is computationally faster than determining (and differentiating) the LSTs of the visit
time distributions (5.1). Once
the mean visit times have been obtained, the mean cycle
time follows from E[C] = N
i=1 (E[Vi ] + E[Si ]).
6.3 MVA equations
We extend the MVA approach to polling systems with smart customers. First, we
briefly introduce some extra notation, then we give expressions for the mean waiting
times, and the mean conditional and unconditional queue lengths. After eliminating
variables, we end up with a system of linear equations. The system can (numerically) be solved in order to find the unknowns, in particular, the mean unconditional
queue lengths and the mean waiting times. Although all equations are discussed in
the present section, for the sake of brevity of this section, some of them are presented
in the Appendix.
The fraction of time the system is in a given period P ∈ {V1 , S1 , . . . , VN , SN } is
]
denoted by q (P ) := E[P
E[C] . The mean residual duration of a period P , at an arbitrarily
chosen point in this period, is denoted by E[RP ] =
E[P 2 ]
2E[P ] .
The mean conditional
Queueing Syst (2010) 66: 239–274
257
number of type j customers in the queue during a random point in P is denoted
)
by E[L̂(P
j ], and the mean (unconditional) number of type j customers in queue is
(P )
denoted by E[L̂j ]. Note that L̂j and L̂j
do not include a potential customer in
(P )
Lj ,
service, whereas Lj and
introduced in Sect. 3, denote queue lengths including
customers being served.
We define an interval, e.g. (Vi :Sj ), as the consecutive periods from the first mentioned period on, until and including the last mentioned period, here consisting of the
periods Vi , Si , Vi+1 , Si+1 , . . . , Vj , Sj . The mean residual duration of an interval, e.g.
(Vi : Sj ), is denoted by E[RVi :Sj ]. Analogously, we define E[RVi :Vj ], E[RSi :Vj ] and
E[RSi :Sj ].
An important concept in the remainder of the analysis is the concept of conditional
durations of a period. This is an extension of the well-known residual duration, or the
age of a period. It deals with the length of a period within the cycle (i.e., a visit
time or a switch-over time), given that the system is being observed from another
period. Before we proceed, we clarify this important concept by a simple example.
Consider a vacation system, i.e., a polling system with N = 1. A cycle consists of
a switch-over time (or: vacation) S1 , followed by a visit time V1 . We assume that
service is exhaustive. Now assume that the system is being observed at a random
−
→
epoch during the switch-over time S1 . We derive an expression for E[V1 (S1 ) ], which is
the conditional mean visit time following the switch-over time, given that the system
is being observed during S1 . Since service is exhaustive, the visit time consists of
the busy periods of the customers that arrived during the elapsed part of S1 , denoted
by S1,past , plus the busy periods of the customers that will arrive during the residual
switch-over time, denoted by S1,res . Hence, it can be seen that in this system
−
→
E V1 (S1 ) =
(S )
(S )
λ1 1 E[B1 ]
λ1 1 E[B1 ] E[S12 ]
.
E[S
]
+
E[S
]
=
1,past
1,res
(V )
(V )
1 − λ1 1 E[B1 ]
1 − λ1 1 E[B1 ] E[S1 ]
Instead of studying the mean visit time following the switch-over time during which
the system is observed, we can also study the mean visit time preceding this partic←
−
ular switch-over time, denoted by E[V1 (S1 ) ]. Now the expression is easier, because a
switch-over time is independent of the preceding visit time, so
←
−
E V1 (S1 ) = E[V1 ] =
(S )
λ1 1 E[B1 ]
(V1 )
1 − λ1
E[B1 ]
E[S1 ].
−
→
←
−
Similarly, we denote by E[ S1 (V1 ) ] and E[ S1 (V1 ) ] the mean switch-over times following, respectively preceding, the visit period V1 during which the system is observed.
Because of the independence between S1 and the preceding V1 , it is immediately
clear that
−
→
E S1 (V1 ) = E[S1 ].
←
−
Unfortunately, E[ S1 (V1 ) ] cannot be determined this easily, since V1 is positively
correlated with the preceding switch-over time. However, it plays a role in the set
258
Queueing Syst (2010) 66: 239–274
of MVA equations developed later in this section, relating the conditional mean
queue lengths, the conditional mean waiting times and the conditional durations of
the periods in a cycle. We leave it up to the reader to verify that (6.8) reduces to
←
−
E[ S1 (V1 ) ] = E[S12 ]/E[S1 ] in the exhaustive vacation model. This example simply
serves the purpose of illustrating the concept of these conditional durations. In a
polling system consisting of multiple queues, these expressions become more complicated and can only be found by solving sets of equations, as will be shown in
the remainder of this section. Note that, because of conditional PASTA, an arbitrary
customer arriving during S1 finds the system in the same state as an observer who
observes the system at an arbitrary epoch during S1 . Hence, the conditional durations
of periods play an important role in determining the mean waiting times.
←
−
For the mean conditional durations of a period, we have the following: E[ Vi (Vj ) ]
denotes the mean duration of the previous period Vi , seen from an arbitrary point in
−
→
Vj (i.e., Vi seen backwards in time from the viewpoint of Vj ), and E[ Vi (Vj ) ] denotes
the mean duration of the next period Vi (i.e., Vi seen forwards in time from the viewpoint of Vj ). For i = j they both coincide, and represent the mean age, resp. the mean
residual duration of Vi . Since the distribution of the age of a period is the same as the
←
−
−
→
distribution of the residual period, we have E[ Vi (Vi ) ] = E[ Vi (Vi ) ] = E[RVi ]. Gener←
−(Vj )
−
→(Vj )
ally, however, E[ Vi
]=
E[ Vi
] for i = j , because of the dependencies between
←
−
−
→
←
−
the durations of periods. Analogously, we define E[ Vi (Sj ) ], E[ Vi (Sj ) ], E[ Si (Vj ) ] and
−
→(Vj )
−
→(Vj )
←
−(Vj )
E[ Si
]. Note that, e.g., E[ Si
] = E[Si ], but E[ Si
]=
E[Si ]. As switch-over
times are independent, the following quantities directly simplify:
−
→(Sj )
←
−(Sj )
for i = j ,
E[Si ]
E S1
=
= E Si
E[RSi ] for i = j .
Having introduced the required notation, we now present the main theorem of this
section, which gives a set of equations that can be solved to find the mean waiting
times of customers in the system.
Theorem 6.1 The mean waiting times, E[Wi ], for i = 1, . . . , N , and the mean queue
lengths, E[L̂i ], satisfy the following equations:
(Vi )
E[Wi ] =
q (Vi ) λi
λi
+
(V )
L̂i j
(Sj )
(Sj )
q (Vj ) λi
i+N
−1
q (Sj ) λi
j =i
+
(Vj )
i+N
−1
j =i+1
+
(V )
E L̂i i E[Bi ] + E[RBi ]
λi
E
E[Bi ] +
k=j
E L̂i
−
→(Vj )
E[Sk ] + E Vk
E[Bi ] + E[RSj ]
−
→(Sj )
,
E[Sk ] + E Vk
i+N
−1
k=j +1
λi
i+N
−1
(6.1)
Queueing Syst (2010) 66: 239–274
259
E[L̂i ] = λi E[Wi ],
E[L̂i ] =
i+N
(6.2)
(V )
(V )
(S )
q j E L̂i j + q (Sj ) E L̂i j ,
(6.3)
j =i+1
(Vj )
where the conditional mean queue lengths E[L̂i
1, . . . , i + N − 1, are given by
(Vj )
E L̂i
=
(Sj )
=
λi
j
λi
k=i+1
], for j = i +
j −1
j
(Vk )
(S ) ←
−
←
−
λi k E Sk (Vj ) ,
E Vk (Vj ) +
(6.4)
k=i
k=i+1
E L̂i
(Sj )
] and E[L̂i
j
(Vk )
(S ) ←
−
←
−
λi k E Sk (Sj ) ,
E Vk (Sj ) +
(6.5)
k=i
←
−
−
→
and where all E[P1 (P2 ) ] and E[P1 (P2 ) ], for P1 , P2 ∈ {V1 , S1 , . . . , VN , SN }, satisfy the
set of equations (6.6)–(6.8) below, and (A.2)–(A.7) in the Appendix.
Proof In order to derive the mean waiting time E[Wi ], we condition on the period
(S )
(V )
in which a type i customer arrives. A fraction q (Vj ) λi j /λi , and q (Sj ) λi j /λi respectively, of the type i customers arrives during period Vj , and during period Sj respectively. If a tagged type i customer arrives during period Vi (i.e., while his queue
is being served), he has to wait for a residual service time, plus the service times of
all type i customers present in the system upon his arrival, which is (by conditional
(V )
(V )
PASTA), E[L̂i i ]. As a fraction q (Vi ) λi i /λi of the customers arrives during Vi ,
this explains the first line of (6.1). If the customer arrives in any other period, he has
to wait until the server returns to Qi again. For this, we condition on the period in
which he arrives. If the arrival period is a visit to Qj , say Vj for j = i, he has to wait
for the residual duration of Vj and the interval (Sj :Si−1 ), and for the service of the
type i customers present in the system upon his arrival. This gives the second line
of (6.1). The third line, the case where the customer arrives during the switch-over
time from Qj to Qj +1 (period Sj ), can be interpreted along the same lines as the
case Vj .
Equation (6.3) is obtained by unconditioning the conditional queue lengths
(P )
E[L̂i ]. The mean number of type i customers in the queue at an arbitrary point
during Vj , given by (6.4), is the mean number of customers built up from the last
visit to Qi (when Qi became empty) until and including a residual duration of Vj (as
the mean residual duration of Vj is equal to the mean age of that period), taking into
account the varying arrival rates. The mean number of type i customers queueing in
the system during period Sj , given by (6.5), can be found similarly. Equations (6.4)
and (6.5) show one of the difficulties in adapting the “ordinary” MVA approach to
that of smart customers. If the arrival rates remain constant during a cycle, these expressions would reduce to λi multiplied by the mean time passed since the server
left Qi . However, for the smart customers case, we have to keep track of the duration
of all the intermediate periods, from the viewpoint of period Vj respectively Sj .
260
Queueing Syst (2010) 66: 239–274
As indicated in Theorem 6.1, at this point the number of equations is insufficient
←
−
−
→
to find all the unknowns, E[P1 (P2 ) ] and E[P1 (P2 ) ], for P1 , P2 ∈ {V1 , S1 , . . . , VN , SN }.
In the remainder of the proof we develop additional relations for these quantities to
−
→
complete the set of equations. We start by considering E[ Vi (Vj ) ], which is the mean
duration of the next period Vi , when observed from an arbitrary point in Vj . For
i = j this is just the residual duration of Vi , consisting of a busy period induced by a
customer with a residual service time left, and the busy periods of all type i customers
in the queue. The cases i = j need some more attention. The duration of Vi now
consists of the busy period induced by the type i customers in the queue, which are in
(V )
expectation E[L̂i j ] customers. During the periods Vj , Sj , . . . , Si−1 , however, new
type i customers are arriving, each contributing a busy period to the duration of Vi .
Hence, summing over these periods and taking into account the varying arrival rates,
we get the mean total of newly arriving customers in this interval. This yields, for
i = 1, . . . , N and j = i + 1, . . . , i + N − 1:
−
→
(V )
(V )
E Vi (Vi ) = E[BPi ]E L̂i i + E[RBi ] 1 − λi i E[Bi ] ,
(6.6)
i+N
−1 (V ) −
−
→
→
(V )
(S )
λi k E Vk (Vj ) + λi k E[Sk ] . (6.7)
E Vi (Vj ) = E[BPi ] E L̂i j +
k=j
−
→
Analogously E[ Vi (Sj ) ] denotes the mean duration of the next period Vi , when observed from an arbitrary point in Sj . The explanation of its expression is along the
−
→
same lines as that of E[ Vi (Vj ) ], although it should be noted that i = j is not a special
case. See (A.1) in the Appendix.
The last step in the proof of Theorem 6.1, needs the following lemma to find the
←
−
−
→
final relations between E[P1 (P2 ) ] and E[P1 (P2 ) ]:
Lemma 6.2 For i = 1, . . . , N , and j = i + 1, . . . , i + N :
j −1
k
←
E[Sk ]
←
−
−
←
−
E Sl (Sk ) + E Vl (Sk )
E Si (Sk ) +
E[(Si :Vj )]
k=i
l=i+1
j −1
−
→(Sk )
−
→(Sk )
−
− E[RSk ] − E Vj
E[Sl ] + E Vl
l=k+1
=
j
k=i+1
j −1
E[Vk ]
−
→
−
→
E[Sl ] + E Vl (Vk )
E Vj (Vk ) +
E[(Si : Vj )]
←
−
←
−
− E Si (Vk ) − E Vk (Vk ) −
l=k
k−1
←
←
−(Vk )
−(Vk )
+ E Vl
.
E Sl
(6.8)
l=i+1
Proof Equation (6.8) can be proved by studying all mean residual interval lengths
E[RSi :Vj ], E[RSi :Sj ], E[RVi :Vj ] and E[RVi :Sj ]. Consider E[RSi :Vj ], the mean residual duration of the interval Si , Vi+1 , . . . , Vj . We condition on the period in which
Queueing Syst (2010) 66: 239–274
261
the interval is observed. As the mean duration of the interval is given by E[(Si :Vj )],
it follows that E[Sk ]/E[(Si : Vj )] is the probability that the interval is observed in
period Sk . The remaining duration of the interval consists of the remaining duration of Sk plus the mean durations of the (coming) periods Vk+1 , Sk+1 , . . . , Vj , when
observed from period Sk . When observing E[(Si : Vj )] from Vk , a similar way of
reasoning is used. This gives, for i = 1, . . . , N , and j = i + 1, . . . , i + N :
E[RSi :Vj ] =
j −1
k=i
+
j −1
E[Sk ]
−
→(Sk )
−
→(Sk )
+
E[Sl ] + E Vl
E[RSk ] + E Vj
E[(Si : Vj )]
l=k+1
j
k=i+1
E[Vk ]
−
→
E Vj (Vk ) +
E[(Si : Vj )]
−
→(Vk )
.
E[Sl ] + E Vl
j −1
l=k
(6.9)
We now use the fast that the distribution of the residual length of an interval is the
same as the distribution of the age of this interval. Again, focus on E[RSi :Vj ], conditioning on the period in which the interval is observed, but now looking forwards in
time. Consider all the periods in (Si : Vj ) that have already passed when observing
during Sk . The interval has lasted for the sum of these periods, plus the age of Sk .
The same can be done for an arbitrary point in Vk . This gives, for i = 1, . . . , N ,
j = i + 1, . . . , i + N :
E[RSi :Vj ] =
j −1
k
←
E[Sk ]
←
−(Sk )
−(Sk )
←
−(Sk )
+ E Vl
E Sl
+
E Si
E[(Si : Vj )]
+
j
k=i
l=i+1
k=i+1
E[Vk ]
←
−
←
−
E Si (Vk ) + E Vk (Vk )
E[(Si : Vj )]
k−1
←
←
−(Vk )
−(Vk )
.
+ E Vl
E Sl
+
(6.10)
l=i+1
The proof of Lemma 6.2 is completed by equating (6.9) and (6.10) and rearranging
the terms.
Similar to the proof of Lemma 6.2, we can develop two different expressions for
each of the terms E[RSi :Sj ], E[RVi :Vj ] and E[RVi :Sj ]. For the sake of brevity of this
section, they are presented in the Appendix, (A.2)–(A.7). Equating each pair of these
expressions, completes the set of (linear) equations for the mean waiting times and
mean queue lengths. This concludes the proof of Theorem 6.1.
7 Pseudo-conservation law
In this section we derive a so-called Pseudo-Conservation Law (PCL), which gives an
expression for the weighted sum of the mean waiting times at each of the queues. For
262
Queueing Syst (2010) 66: 239–274
“ordinary” cyclic polling systems, Boxma and Groenendijk [6] derive a PCL under
various servicedisciplines. This PCL, in commonly used notation ρi = λi E[Bi ], ρ =
N
N
i=1 ρi , S =
i=1 Si , states that:
N
ρi E[Wi ] = ρ
i=1
N
N
ρ
E[R
]
E[S]
i
B
i
i=1
+ ρE[RS ] +
E[Zii ],
ρi2 +
ρ2 −
1−ρ
2(1 − ρ)
i=1
i=1
(7.1)
N
with Zii denoting the amount of work left behind by the server at Qi at the ending
of a visit. For exhaustive service at Qi , we have E[Zii ] = 0, and for gated service
ρ 2 E[S]
E[Zii ] = i1−ρ .
We base our approach on [6], and adapt their ideas to derive a PCL for a polling
model with smart customers. The approach focusses on the mean amount of work in
the system at an arbitrary point in time. A required restriction for our approach in this
section, is that the Poisson process according to which work arrives in the system,
has a fixed arrival rate during all visit periods. We also require that the amounts of
work brought by an individual arrival are identically distributed for all visit periods.
We mention two typical cases where this requirement is satisfied. Firstly, the case
when the arrival rate at a given queue stays constant during different visit times,
and secondly when the total arrival rate remains constant during visit times and the
service times are identically distributed:
(V1 )
Case 1: λi
Case 2:
N
(V2 )
= λi
(Vj )
λi
(VN )
= · · · = λi
=: Λ(V ) ,
(V )
=: λi ,
d
i = 1, . . . , N,
d
and B1 = · · · = BN ,
(7.2)
j = 1, . . . , N. (7.3)
i=1
Note that Case 1 does allow for different arrival rates during switch-over times. During visit periods, let Λ(V ) be the total arrival rate of all customer types, and let B (V )
denote the generic service time of an arbitrary customer entering the system. In par
d
(V )
ticular, this means for Case 1 that Λ(V ) = N
and B (V ) = Bi with probability
i=1 λi
(V )
λi /Λ(V ) for i = 1, . . . , N . We introduce ρ (V ) to denote the mean amount of work
entering the system per time unit during a visit period, so ρ (V ) = Λ(V ) E[B (V ) ].
Denote by Y the amount of work in the polling system at an arbitrary point in time,
and by Y (V ) and Y (S) the amount of work at an arbitrary point during respectively a
visit period, and a switch-over period. Then
d
Y=
where ρ :=
unit. Hence,
N
i=1 ρ i
=
N
(V )
Y
Y (S)
i=1 λi E[Bi ]
w.p. ρ,
w.p. 1 − ρ,
(7.4)
is the mean offered amount of work per time
E[Y ] = ρE Y (V ) + (1 − ρ)E Y (S) .
(7.5)
Queueing Syst (2010) 66: 239–274
263
Another way to obtain the mean total amount of work in the system is by taking the
sum of the mean workloads. The mean workload in Qi is the mean amount of work of
all customers in the queue plus, with probability ρ i = λi E[Bi ], the mean remaining
amount of work of a customer in service at Qi :
E[Y ] =
N
E[L̂i ]E[Bi ] + ρ i E[RBi ] .
(7.6)
i=1
In the next subsections we show that equating (7.5) and (7.6), and applying Little’s
law, E[L̂i ] = λi E[Wi ], gives a PCL for the mean waiting times in the system. But
first we have to find E[Y (V ) ] and E[Y (S) ]. We start with the latter.
7.1 Work during switch-over periods
The term E[Y (S) ] denotes the mean amount of work in the system when observed
at a random point in a switch-over interval. Denoting by E[Y (Si ) ] the mean amount
of work in the system at an arbitrary moment during Si , we can condition on the
switch-over interval in which the system is observed:
E Y (S) =
N
E[Si ]
i=1
E[S]
E Y (Si ) .
(7.7)
We can split E[Y (Si ) ] into two parts: the mean amount of work present at the start
of Si plus the mean amount of work built up since the start of the switch-over time.
In expectation, a duration E[RSi ] has passed since the beginning of the switch-over
(S )
time, in which work arrived at rate λj i E[Bj ] at Qj . Hence, this gives a contribution
(Si )
to E[Y (Si ) ] of N
j =1 λj E[Bj ]E[RSi ]. For the work present at the start of the switchover period, we start looking at the moment that the server left Qj , leaving a mean
amount of work E[Zjj ] behind in this queue. For exhaustive service, E[Zjj ] = 0,
(V )
for gated service E[Zjj ] = λj j E[Bj ]E[Vj ]. Since then, the interval (Sj :Vi+N ) has
passed, for j = i + 1, . . . , i + N − 1. In this interval the amount of type j work
(V
)
(S )
(S )
(V )
increased at rates λj j E[Bj ], λj j +1 E[Bj ], . . . , λj i−1 E[Bj ], λj i E[Bj ] during the
various periods. This leads to the following expression for E[Y (Si ) ]:
E Y (Si ) =
N
(Si )
λj E[Bj ]E[RSi ] + E[Zjj ]
j =1
+
i+N
−1
−1 i+N
j =i+1
k=j
(Sk )
(V )
λj E[Bj ]E[Sk ] + λj k+1 E[Bj ]E[Vk+1 ] . (7.8)
7.2 Work during visit periods
The key observation in the proof of [6] is the work decomposition property in a polling
system. This property states that the amount of work at an arbitrary epoch in a visit
264
Queueing Syst (2010) 66: 239–274
period is distributed as the sum of two independent random variables: the amount of
work in the “corresponding” M/G/1 queue at an arbitrary epoch during a busy pe(V )
riod, denoted by YM/G/1 , and the amount of work in the polling system at an arbitrary
epoch during a switch-over time, Y (S) . In a polling model with smart customers, this
decomposition does not typically hold, but only a minor adaptation is required. We
follow the proof in [6] as closely as possible, meaning that we use the concepts of
ancestral line and offspring of a customer, as introduced in [15]. We also copy the
idea of comparing the polling system to an M/G/1 queue with vacations and LastCome-First-Served (LCFS) service. The traffic process offered to this M/G/1 queue
is identical to the traffic process of the polling system. The server of the M/G/1
queue takes vacations exactly during the switching periods of the polling system.
These vacations might interrupt the service of a customer in the M/G/1 queue. This
service is not resumed until all customers that have arrived during the vacation and
their offspring have been served (in LCFS order).
We now focus on the amount of work in this M/G/1 system at an arbitrary moment during a visit (busy) period. Let K be the customer being served at this observation moment, and let KA be his ancestor. By definition, KA has arrived during a
vacation period (or: switch-over period in the corresponding polling system). Denote
by YKA the amount of work present in the system at the moment that KA enters the
system. An important difference with the situation studied in [6] is that we cannot use
the PASTA property, so in general YKA = Y (S) . We now condition on the customer
type of KA . The mean duration of the service of a type i ancestor and his entire ancestral line is E[Bi ]/(1 − ρ (V ) ). This can be regarded as the mean busy period commencing with the service of an exceptional first customer (namely a type i customer).
(S )
Each type i customer arriving during Sj , with arrival rate λi j , i, j = 1, . . . , N , starts
such a busy period, so the probability that KA is a type i customer is
pi =
N
(Sj )
E[Sj ]E[Bi ]/(1 − ρ (V ) )
j =1 λi
N N
(Sj )
(V ) )
k=1
j =1 λk E[Sj ]E[Bk ]/(1 − ρ
=
N
(Sj )
E[Sj ]E[Bi ]
j =1 λi
.
N N
(Sj )
k=1
j =1 λk E[Sj ]E[Bk ]
(7.9)
Given that KA is a type i customer, we again pick up the proof of the work decomposition in [6]. Denote by BKA the service requirement of KA . Then, because of the
LCFS service discipline of the M/G/1 queue, the amount of work when KA goes
into service is exactly YKA + BKA , and the amount of work when the last descendant
of KA has been served equals YKA again (for the first time, since the arrival of KA ).
Ignoring the amount of work present at KA ’s arrival, the residual amount of work
evolves just as during a busy period in an M/G/1 queue with an exceptional first
customer (having generic service requirement Bi ). The only exception is caused by
the vacations (or switch-over times in the polling model), during which the work remains constant or may increase because of new arrivals. However, just as in [6], if we
ignore these vacations and the (LCFS) service of the ancestral lines of the customers
that arrive during these vacations, what remains is the workload process during a
Queueing Syst (2010) 66: 239–274
265
(V )
busy period initiated by a type i customer. Denote by YM/G/1|i the amount of work
(S)
at an arbitrary moment during this busy period, and denote by YAi the amount of
work present in the polling system at an arbitrary arrival epoch of a type i customer
(S)
during a switch-over time. Note that YKA is distributed like YAi . Then we have the
following decomposition:
d
(V )
(S)
Y (V ) = YM/G/1|i + YAi
w.p. pi , i = 1, . . . , N,
(V )
(7.10)
(S)
with pi as given in (7.9), and YM/G/1|i and YAi being independent. This leads to
E Y (V ) =
N
i=1
(V )
(S)
pi E YM/G/1|i + E YAi ,
(7.11)
with
(V )
E YM/G/1|i = E[RBi ] +
(S)
E YAi
=
N
j =1
ρ (V )
E[RB (V ) ],
1 − ρ (V )
(7.12)
(Sj )
E[Sj ]
E
(Sk )
E[Sk ]
k=1 λi
λi
N
Y (Sj ) .
(7.13)
For (7.12) we use standard theory on an M/G/1 queue with an exceptional first customer (cf. [32]), and (7.13) is established by conditioning on the switch-over period
in which a type i customer arrives.
7.3 PCL for smart customers
We are now ready to state the PCL.
Theorem 7.1 Provided that (7.2) or (7.3) is valid, the following Pseudo-Conservation
Law holds:
N
ρ i E[Wi ] = (1 − ρ)
i=1
N
E[Si ]
i=1
+ρ
N
i=1
pi
E[S]
E Y (Si ) −
N
ρ i E[RBi ]
i=1
(S )
λi j E[Sj ]
E
N
(Sk )
E[Sk ]
k=1 λi
j =1
N
ρ (V )
E[RB (V ) ] ,
+ E[RBi ] +
1 − ρ (V )
where E[Y (Si ) ] are as in (7.8), and pi as in (7.9).
Y (Sj )
(7.14)
266
Queueing Syst (2010) 66: 239–274
Proof We have two equations, (7.5) and (7.6), for the mean total amount of work in
the system. Combining these two equations, and plugging in (7.7) and (7.11), we find
N
N
E[Sj ]
E Y (Sj )
E[L̂i ]E[Bi ] + ρ i E[RBi ] = (1 − ρ)
E[S]
j =1
i=1
+ρ
N
i=1
(V )
(S)
pi E YM/G/1|i + E YAi .
By application of Little’s law, E[L̂i ] = λi E[Wi ], using that ρ i = λi E[Bi ], plugging
in (7.12) and (7.13), after some rewriting we obtain (7.14), which is a PCL for a
polling model with smart customers.
(S )
(S )
(S )
(V )
(V )
Remark 7.2 When λi 1 = λi 2 = · · · = λi N = λi 1 = · · · = λi N = λi , for all
(S)
i = 1, . . . , N , (7.14) reduces to (7.1). E.g., because of PASTA, E[YAi ] = E[Y (S) ],
and pi = λi /Λ for all i.
Case 2, where assumptions (7.3) hold, has a nice practical interpretation if we add
(Sj )
(Vj )
the additional requirement that N
= N
=: Λ for all j = 1, . . . , N .
i=1 λi
i=1 λi
Now, the model can be interpreted as a polling system with customers arriving in one
Poisson stream with constant arrival rate Λ, and generic service requirement B, but
joining a certain queue with a fixed probability that may depend on the location of
the server at the arrival epoch. In Sect. 8 we discuss an example on how these probabilities may be chosen to minimise the mean waiting time of an arbitrary customer.
The PCL (7.14) can be simplified considerably in this situation.
Corollary 7.3 If (7.3) is valid, the PCL (7.14) reduces to
N
ρ i E[Wi ] =
N
E[Si ]
i=1
i=1
E[S]
E Y (Si ) +
ρ2
E[RB ].
1−ρ
(7.15)
Proof This is a direct consequence of assumptions (7.3). That is, in the computation
of (7.12) there is no need to condition on a special first customer, and hence the term
E[YM/G/1|i ] does not depend on i anymore:
E[YM/G/1|i ] =
where ρ = ΛE[B]. Additionally, the term
ably:
N
i=1
pi E
(S)
YAi
=
E[RB ]
,
1−ρ
N
(S)
i=1 pi E[YAi ]
N
E[Si ]
i=1
E[S]
also simplifies consider-
E Y (Si ) .
Queueing Syst (2010) 66: 239–274
267
Combining this, multiple terms cancel out and (7.15) follows. It is easily seen
that (7.15) is in line with (7.1), when the arrival rates do not change during various
visit and switch-over times.
8 Numerical examples
8.1 Example 1: smart customers
In the first numerical example we study a polling system where arriving customers
choose which queue they join, based on the current position of the server. In [5, 7]
a fully symmetric case is studied with gated service, and it is proved that the mean
sojourn time of customers is minimised if customers join the queue that is being
served directly after the queue that is currently being served. Although the exhaustive
case is not studied, it is intuitively clear that in this situation smart customers join the
queue that is currently being served, or, in the case that an arrival takes place during
a switch-over time, join the next queue that is visited. In this example we study this
situation in more detail by adding an extra parameter that can be varied. The polling
model is fully symmetric, except for the service time of customers in Q1 , which is
varied. The practical interpretation is the following: as in the previously described
examples, customers arrive with a fixed arrival intensity, say Λ, and choose which
queue they join. This does not affect their service time, except when they choose Q1 .
In this case the service time has a different distribution. To illustrate the dynamics
of this system, we choose the following setting. The system consists of three queues
with exhaustive service. The switch-over times are all exponentially distributed with
mean 1. The service times are also exponentially distributed with E[B2 ] = E[B3 ] = 1,
and E[B1 ] is varied between 0 and 2. Arriving customers choose one queue which
they want to join. This queue is the same for all customers, so there is no randomness
involved in the selection, which is only based on the location of the server at their
arrival epochs. We intend to find the optimal queue for customers to join. In terms of
(V )
(S )
the model parameters: we seek to find values for λi j and λi j , i, j = 1, 2, 3, that
minimise the mean sojourn time of an arbitrary customer, under the restriction that
(V )
(S )
for each value of j , exactly one λi j and exactly one λi j is equal to Λ, and all the
other values are 0. A valid combination of these arrival intensities is called a strategy,
and we introduce the short notation for a strategy by the indices of the queues that are
joined in respectively (V1 , S1 , V2 , S2 , V3 , S3 ). For example, for the fully symmetric
case, with E[B1 ] = 1, it is intuitively clear that the optimal strategy is to join Qi , if the
arrival takes place during Vi , and to join Qi+1 if the arrival takes place during Si . This
(V )
(V )
(V )
strategy is denoted by (1, 2, 2, 3, 3, 1), and corresponds to λ1 1 = λ2 2 = λ3 3 = Λ,
(S )
(S )
(S )
and λ2 1 = λ3 2 = λ1 3 = Λ. The other arrival intensities are 0. As stated before,
we vary E[B1 ] between 0 and 2, and focus on the overall mean sojourn time. It is
clear that making E[B1 ] smaller makes it more attractive to join Q1 (even if another
queue is served), whereas making E[B1 ] larger, makes it less attractive to join Q1 .
In order to obtain numerical results, we choose (arbitrary) value Λ = 35 . It turns out
that as much as seven different strategies can be optimal, depending on the value of
E[B1 ]. We refer to these strategies as I through VII, listed in Table 1, along with
268
Table 1 The seven smartest
strategies in Example 1 that
minimise the mean waiting time
of an arbitrary customer who
can choose the queue in which
he wants to be served. An ‘X’
means that the length of the
corresponding visit time equals
0 because customers never join
this queue
Queueing Syst (2010) 66: 239–274
Strategy
Queue to join during
Region of optimality
V1
S1
V2
S2
V3
S3
I
1
1
X
1
X
1
0.00 ≤ E[B1 ] ≤ 0.41
II
1
2
1
1
X
1
0.41 ≤ E[B1 ] ≤ 0.66
0.66 ≤ E[B1 ] ≤ 0.73
III
1
2
2
1
X
1
IV
1
2
2
3
1
1
0.73 ≤ E[B1 ] ≤ 0.84
V
1
2
2
3
3
1
0.84 ≤ E[B1 ] ≤ 1.10
VI
2
2
2
3
3
1
1.10 ≤ E[B1 ] ≤ 1.16
VII
X
2
2
3
3
2
1.16 ≤ E[B1 ]
Fig. 2 The mean sojourn time of an arbitrary customer for the seven smartest strategies in Example 1,
against the mean service time in Q1
their region of optimality. For each of these strategies, the mean sojourn time of an
arbitrary customer is plotted versus E[B1 ] in Fig. 2.
As expected, Q1 is most popular if E[B1 ] is very small. In particular, for very
small values of E[B1 ], customers always join this queue (Strategy I). As E[B1 ] becomes larger, Q2 and later also Q3 are chosen in more and more situations (Strategies II–V). Strategy V, which is optimal if the system is (nearly) symmetric, is the
one where customers join the queue that is being served, or is going to be served next
if the arrival takes place during a switch-over time. Strategy VI, which is optimal in
only a very small range of values of E[B1 ], states that customers only join Q1 during
the switch-over time S3 . Strategy VII, in which customers never join Q1 , is optimal for large values of E[B1 ]. The ergodicity constraint, considering all parameters
are fixed except for E[B1 ], for the different strategies is also interesting to mention.
For strategies I–V, the necessary and sufficient condition for stability is E[B1 ] < 35 .
Strategies VI and VII always result in a stable system, regardless of E[B1 ]. For illustration purposes, we show how to compute the ergodicity constraint for Strategy V.
Queueing Syst (2010) 66: 239–274
269
As indicated in Sect. 3, the ergodicity constraint requires computation of the eigenvalues of the matrix R − IN , where IN is the N × N identity matrix, and R is an
(V )
N × N matrix containing elements ρij := λi j E[Bi ]. For Strategy V, we find
⎛
ΛE[B1 ] − 1
0
0
Λ−1
R − I3 = ⎝
0
0
⎞
0
0 ⎠.
Λ−1
The eigenvalues of this matrix are ΛE[B1 ]−1, Λ−1, and again Λ−1. The ergodicity
constraint in this situation states that the largest (and, hence, all) of these eigenvalues
should be negative. This means that E[B1 ] < Λ1 is a sufficient and necessary condition
for stability of this system, given that Λ < 1. The ergodicity constraints of the other
strategies are computed similarly, but all rows and columns corresponding to visit
times that are zero should be deleted from the matrix R − I3 (cf. [11]). For Strategies
VI and VII this implies that the first row and the first column should be deleted. Since
the first row is the only row which contains E[B1 ], these strategies always result in a
stable system. Note that the arrival rates during switch-over times do not play a role
in the ergodicity constraint.
It is also interesting to discuss what stupid customers would do in this system.
Stupid customers choose the worst possible strategy, in order to maximise the mean
sojourn time of an arbitrary customer. We do not go into details and do not mention
exactly which strategy is worst for each value of E[B1 ], but we pick out some interesting cases. Obviously, when E[B1 ] = 0, the worst possible thing to do is never to
join Q1 . The worst strategy in this case is (X, 3, 3, 2, 2, 3), where X means that any
queue can be chosen (because the length of the corresponding visit time equals 0,
since customers never join this queue). This strategy leads to an overall mean sojourn
time of 7.48. As E[B1 ] grows larger, Q1 gradually will be chosen more frequently.
In the symmetric case, E[B1 ] = 1, customers arriving during Vi choose Qi−1 , and
customers arriving during Si choose Qi , resulting in a mean sojourn time of 8.5. For
large E[B1 ], the worst possible strategy might be a bit surprising. It is not simply to
always join Q1 , but it is (1, 1, 1, 2, 1, 3). During visit periods, customers always join
Q1 , but during Si customers join Qi . For E[B1 ] ↑ 35 , this strategy results in the highest mean sojourn time of an arbitrary customer. For the situation E[B1 ] ≥ 53 , there are
many strategies for which the system becomes unstable and sojourn times become
infinite. The worst possible strategy for E[B1 ] ≥ 35 that still results in a stable system,
is (3, 1, X, 1, 1, 1).
8.2 Example 2: no arrivals during a specific period
In this example we illustrate how to deal with polling models with arrival rates being
zero during certain periods. For MVA, this is no problem. The equations presented
in Sect. 6 still give the correct solution if some of the arrival rates during periods
are zero. The problem arises when determining the LST of the waiting time distribution (4.3) and can only be circumvented by a work-around, which is explained
using a simple example. The polling model in this example contains two queues, Q1
and Q2 , which are served exhaustively. All switch-over times and all service times
270
Queueing Syst (2010) 66: 239–274
are exponentially distributed with parameter 1. All arrival rates are 12 , except for
the arrival rate of type 1 customers arriving during the service of type 2 customers:
(V )
λ1 2 = 0. This brings along some complications. First of all, (5.4) cannot be used
to determine the cycle time LST. This is no real problem, because (5.2) can be used
(V )
instead. Because of λ1 2 being zero, we should use (3.11) instead of (3.4) for type
(V
)
1 2 customers to determine the PGF of the steady-state queue length of Q1 . Again,
no real problem but just something to be careful about. Determining the waiting time
LST for type 1 customers does raise some issues, though. The (generalisation of the)
distributional form of Little’s law, given by (4.3), uses the joint distribution of customers left behind by a departing type i customer to determine his time spent in the
system. As can be seen in the proof of Theorem 4.3, this technique requires that type i
customers may arrive during each period within a cycle. In our model this is not the
case, because no type 1 customers arrive during V2 . This implies that the number of
customers left behind by a departing type 1 customer, does not give any information
about the waiting time of type 1 customers (more specifically, of those that arrived
during S1 ), because a departing type 1 customer does not leave behind any customers
(of any type) that have arrived during V2 .
A work-around for this problem, is to introduce an extra queue, QX , with type
(V )
X customers that have no service requirement (BX = 0), and λX 2 > 0. Customers
in this queue are served exhaustively somewhere between the end of V1 and the beginning of V2 , because type X (V2 ) customers have to be present at departure epochs
of type 1 customers. In our approach, we choose to treat QX as a regular queue
between Q1 and Q2 with no switch-over time from QX to Q2 because this gives
us a “normal”, three-queue polling system. Determining the waiting time LST of
type 1 customers, requires a careful application of the distributional form of Little’s law to the various customer subtypes in (4.2). For convenience, we introduce
the following two vectors, where the elements correspond to customer subtypes
(1(V1 ) , . . . , 1(S2 ) , X (V1 ) , . . . , X (S2 ) , 2(V1 ) , . . . , 2(S2 ) ):
ω1 = 1 −
ω∗1 = 1 −
ω
(V )
λ1 1
ω
(V )
λ1 1
,1 −
,1 −
ω
(S )
λ1 1
ω
(S )
λ1 1
, 1, 1 −
, 1, 1 −
ω
(S )
λ1 2
ω
(S )
λ1 2
, 1, 1, 1, 1, 1, 1, 1, 1 ,
, 1, 1, 1 −
ω
(V )
λX 2
, 1, 1, 1, 1, 1 ,
the difference being in the element corresponding to the type X customers that arrive during V2 . Note that we do not introduce customer subtypes that arrive during
VX or SX , because the lengths of these periods are 0. The LST of the waiting time
distribution of type 1 customers is given by:
E e−ωW1 =
1 λ (V1 )
(V )
(S )
(S )
M1 (ω1 ) + M1 1 (ω∗1 ) + M1 2 (ω1 ) + M1 2 (ω1 ) .
β1 (ω) λ1
The interpretation is that we use the type X (V2 ) customers left behind by a departing
1(S1 ) customer to determine the length of V2 , which is part of the total waiting time
of a type 1(S1 ) customer. The other type 1 customers arrive after the visit to Q2 and
Queueing Syst (2010) 66: 239–274
271
Table 2 Numerical results for
the polling model discussed in
Example 2
Q1
Q2
Mean queue length at arrival epochs
1.750
3.375
Mean queue length at departure epochs
1.750
3.375
Mean queue length at arbitrary epochs
1.188
3.375
Mean waiting time
3.750
5.750
Standard deviation waiting time
5.093
6.280
can be handled in the regular way. The numerical results of this example are shown
in Table 2.
We can modify (5.4) and (5.5) accordingly to obtain the LSTs of the cycle time
distribution C1∗ , starting at a visit ending to Q1 , and the intervisit time distribution I1 :
∗
(S1 )
B1
E e−ωC1 = V
1−
π1 (ω) −
ω
(V )
λX 2
ω
(V )
λ1 1
, π1 (ω) −
ω
(S )
λ1 1
, 1, π1 (ω) −
ω
(S )
λ1 2
, 1, 1,
, 1, 1, 1, 1, 1 ,
(S )
E e−ωI1 = V
B1 1 (ω∗1 ).
Open Access This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium,
provided the original author(s) and source are credited.
Appendix: MVA equations
In this appendix we present all MVA equations that have been omitted in Sect. 6.
−
→
The mean duration of the next period Vi , when in Sj is denoted by E[ Vi (Sj ) ].
−
→
−
→
−
→
A difference with E[ Vi (Vj ) ] is that E[ Vi (Si ) ] is not different from E[ Vi (Sj ) ] for j = i.
Similar to (6.7), we have for i = 1, . . . , N , j = i, . . . , i + N − 1:
−
→
E Vi (Sj )
= E[BPi ] E
(S )
L̂i j
(S )
+ λi j E[RSj ] +
i+N
−1
k=j +1
(Vk ) −
→(Sj )
(Sk )
+ λi E[Sk ] .
λi E Vk
(A.1)
Equation (6.9) for E[RSi :Vj ], the mean residual duration of the interval Si ,
Vi+1 , . . . , Vj , is obtained by conditioning on the period in which the interval is
observed, looking forwards in time. Similarly, we find expressions for E[RSi :Sj ],
E[RVi :Vj ], and E[RVi :Sj ]. For i = 1, . . . , N , j = i + 1, . . . , i + N − 1:
E[RSi :Sj ] =
j
k=i
j
E[Sk ]
−
→(Sk )
E[Sl ] + E Vl
E[RSk ] +
E[(Si :Sj )]
l=k+1
272
Queueing Syst (2010) 66: 239–274
j
+
k=i+1
j
E[Vk ]
−
→(Vk )
.
E[Sl ] + E Vl
E[(Si : Sj )]
(A.2)
l=k
For i = 1, . . . , N , j = i + 1, . . . , i + N − 1:
E[RVi :Vj ] =
j −1
k=i
+
j −1
E[Sk ]
−
→(Sk )
−
→(Sk )
+
E[Sl ] + E Vl
E[RSk ] + E Vj
E[(Vi : Vj )]
l=k+1
j
k=i
j −1
E[Vk ]
−
→(Vk )
−
→(Vk )
.
+
E[Sl ] + E Vl
E Vj
E[(Vi : Vj )]
(A.3)
l=k
For i = 1, . . . , N , j = i + 1, . . . , i + N − 1:
j
E[RVi :Sj ] =
k=i
+
j
E[Sk ]
−
→(Sk )
E[Sl ] + E Vl
E[RSk ] +
E[(Vi : Sj )]
l=k+1
j
k=i
E[Vk ]
E[(Vi : Sj )]
j
−
→(Vk )
.
E[Sl ] + E Vl
(A.4)
l=k
In Sect. 6 a second set of equations is discussed for E[RSi :Vj ], E[RSi :Sj ], E[RVi :Vj ],
and E[RVi :Sj ]. This set is obtained by conditioning on the period in which the interval
is observed, but now looking backwards in time. We use that the residual length of an
interval has the same distribution as the elapsed time of this interval. The equation for
E[RSi :Vj ] is given by (6.10). The other equations are given below. For i = 1, . . . , N ,
j = i + 1, . . . , i + N − 1:
E[RSi :Sj ] =
j
k
←
E[Sk ]
←
−(Sk )
−(Sk )
←
−(Sk )
+
+ E Vl
E Sl
E Si
E[(Si : Sj )]
+
j
k=i
l=i+1
k=i+1
E[Vk ]
←
−
←
−
E Si (Vk ) + E Vk (Vk )
E[(Si : Sj )]
k−1
←
←
−(Vk )
−(Vk )
.
+ E Vl
E Sl
+
(A.5)
l=i+1
For i = 1, . . . , N , j = i + 1, . . . , i + N − 1:
E[RVi :Vj ] =
j −1
k=i
+
k
←
E[Sk ]
←
−(Sk )
−(Sk )
+ E Vl
E Sl
E[(Vi : Vj )]
j
k=i
l=i
k−1
←
E[Vk ]
−(Vk )
←
−(Vk )
←
−(Vk )
+
. (A.6)
E Sl
+ E Vl
E Vk
E[(Vi : Vj )]
l=i
Queueing Syst (2010) 66: 239–274
273
For i = 1, . . . , N , j = i, . . . , i + N − 1:
E[RVi :Sj ] =
j
k=i
+
k
←
E[Sk ]
←
−(Sk )
−(Sk )
+ E Vl
E Sl
E[(Vi : Sj )]
j
k=i
l=i
k−1
←
E[Vk ]
−(Vk )
←
−(Vk )
←
−(Vk )
. (A.7)
E Sl
+ E Vl
+
E Vk
E[(Vi : Sj )]
l=i
References
1. Boon, M.A.A.: A polling model with reneging at polling instants. Ann. Oper. Res. (2010, to appear).
doi:10.1007/s10479-010-0758-2
2. Boon, M.A.A., Adan, I.J.B.F.: Mixed gated/exhaustive service in a polling model with priorities.
Queueing Syst. 63, 383–399 (2009)
3. Borst, S.C.: Polling Systems. CWI Tracts, vol. 115 (1996)
4. Borst, S.C., Boxma, O.J.: Polling models with and without switchover times. Oper. Res. 45(4), 536–
543 (1997)
5. Boxma, O.J.: Polling systems. In: From Universal Morphisms to Megabytes: A Baayen Space
Odyssey. Liber Amicorum for P.C. Baayen, pp. 215–230. CWI, Amsterdam (1994)
6. Boxma, O.J., Groenendijk, W.P.: Pseudo-conservation laws in cyclic-service systems. J. Appl. Probab.
24(4), 949–964 (1987)
7. Boxma, O.J., Kelbert, M.: Stochastic bounds for a polling system. Ann. Oper. Res. 48, 295–310
(1994)
8. Boxma, O.J., Weststrate, J.A., Yechiali, U.: A globally gated polling system with server interruptions,
and applications to the repairman problem. Probab. Eng. Inf. Sci. 7, 187–208 (1993)
9. Boxma, O.J., van Wijk, A.C.C., Adan, I.J.B.F.: Polling systems with a gated-exhaustive discipline.
In: ValueTools 2008 (Third International Conference on Performance Evaluation Methodologies and
Tools, Athens, Greece, October 20–24, 2008)
10. Boxma, O.J., Bruin, J., Fralix, B.H.: Waiting times in polling systems with various service disciplines.
Perform. Eval. 66, 621–639 (2009)
11. Boxma, O.J., Ivanovs, J., Kosiński, K., Mandjes, M.: Lévy-driven polling systems and continuousstate branching processes. E URANDOM report 2009-026, E URANDOM (2009)
12. Cohen, J.W.: The Single Server Queue, revised edn. North-Holland, Amsterdam (1982)
13. Eisenberg, M.: Queues with periodic service and changeover time. Oper. Res. 20(2), 440–451 (1972)
14. Fuhrmann, S.W.: Performance analysis of a class of cyclic schedules. Technical memorandum 8159531-1, Bell Laboratories (March 1981)
15. Fuhrmann, S.W., Cooper, R.B.: Stochastic decompositions in the M/G/1 queue with generalized
vacations. Oper. Res. 33(5), 1117–1129 (1985)
16. Gong, Y., de Koster, R.: A polling-based dynamic order picking system for online retailers. IIE Trans.
40, 1070–1082 (2008)
17. Ibe, O.C., Trivedi, K.S.: Two queues with alternating service and server breakdown. Queueing Syst.
7, 253–268 (1990)
18. Jain, M., Jain, A.: Working vacations queueing model with multiple types of server breakdowns. Appl.
Math. Model. 34(1), 1–13 (2010)
19. Keilson, J., Servi, L.D.: The distributional form of Little’s Law and the Fuhrmann–Cooper decomposition. Oper. Res. Lett. 9(4), 239–247 (1990)
20. Kofman, D., Yechiali, U.: Polling systems with station breakdowns. Perform. Eval. 27–28, 647–672
(1996)
21. Levy, H., Sidi, M.: Polling systems: applications, modeling, and optimization. IEEE Trans. Commun.
38, 1750–1760 (1990)
22. Mandelbaum, A., Yechiali, U.: Optimal entering rules for a customer with wait option at an M/G/1
queue. Manag. Sci. 29(2), 174–187 (1983)
23. Nakdimon, O., Yechiali, U.: Polling systems with breakdowns and repairs. Eur. J. Oper. Res. 149,
588–613 (2003)
274
Queueing Syst (2010) 66: 239–274
24. Resing, J.A.C.: Polling systems and multitype branching processes. Queueing Syst. 13, 409–426
(1993)
25. Shanthikumar, J.G.: On stochastic decomposition in M/G/1 type queues with generalized server
vacations. Oper. Res. 36(4), 566–569 (1988)
26. Shogan, A.W.: A single server queue with arrival rate dependent on server breakdowns. Nav. Res.
Logist. Q. 26(3), 487–497 (1979)
27. Takagi, H.: Queuing analysis of polling models. ACM Comput. Surv. (CSUR) 20, 5–28 (1988)
28. van der Mei, R.D., Resing, J.A.C.: Analysis of polling systems with two-stage gated service: fairness
versus efficiency. In: Mason, L., Drwiega, T., Yan, J. (eds.) Proc. ICT-20—Managing Traffic Performance in Converged Networks: The Interplay Between Convergent and Divergent Forces, pp. 544–
555. Springer, Berlin (2007)
29. Vishnevskii, V.M., Semenova, O.V.: Mathematical methods to study the polling systems. Autom.
Remote Control 67(2), 173–220 (2006)
30. Winands, E.M.M.: Polling, Production & Priorities. PhD thesis, Eindhoven University of Technology
(2007)
31. Winands, E.M.M., Adan, I.J.B.F., van Houtum, G.-J.: Mean value analysis for polling systems. Queueing Syst. 54, 35–44 (2006)
32. Wolff, R.: Stochastic Modeling and the Theory of Queues. Prentice-Hall, Englewood Cliffs (1989)