Martin I Reiman.

Heavy traffic analysis of polling systems in tandem online

. (page 1 of 3)
Online LibraryMartin I ReimanHeavy traffic analysis of polling systems in tandem → online text (page 1 of 3)
Font size
QR-code for this ebook

p;j.T.U3RARli:S- DEWEY



Heavy Traffic Analysis of Polling Systems in Tandem

Martin I. Reiman and Lawrence M. Wein
#3857-95-MSA September 1995

OCT 2 4 1995


Heavy Traffic Analysis of Polling Systems in Tandem

Martin I. Reinian

AT.L-T Bell Laboratories
Murray Hill, N.J 07974

Lawrence M. Wein

Sloan School of Management. M.I.T.
Cambridge, MA 02139


We analyze the performance of a tandem queueing network populated by two customer types.
The interarrival times of each type and the service times of each type at each station are
independent random variables with general distributions. A setup time is incurred when a
server switches from one customer type to the other, and each server employ's an exhausti\e
polling scheme. We assume that the load on each station is identical, and employ heavy traffic
approximations to compute the sojourn time distribution for a customer that arrives to find the
network in a particular state. When .setup times ai^e zero (except perhaps at the first station)
and additional "product-form" type assumptions are imposed, we find the steady state sojourn
time distribution for each customer type.

September 1995

We consider a tandem queueing system with /\ single-server stations. Customers of two
types, denoted by .4 and B, arrive to station 1 according to independent renewal processes.
Each customer is served once at each station, and customers exit after being served at station
A'. Although each customer type has its own general service time distribution at each station,
we require the load on each station to be identical. A setup (or switchover) time is incurred
at each station whenever a server switches from serving one customer type to the other. We
assume that each server employs an exhaustive polling scheme: Serve all customers of the type
that is currently set up; when there are no more of these customers in queue, switch to the
other customer type and serve all of its customers exhaustively.

Our goal is to derive the sojourn time distribution for each customer type in both the
transient and steady state cases. In the transient case, we attempt to find the sojourn time of a
customer who arrives to the network and finds it in a particular state (described, for example,
by the 2A'-dimensional queue length process and the location of each server). Hence, in contrast
to steady state performance analysis, where unconditioned or conditioned sojourn times can be
considered, the transient sojourn time distribution we compute is conditioned on the state, and
hence is state-dependent.

The motivation for studying this problem comes from manufacturing systems. Although
queueing network models for manufacturing typically do not include setup times, many factories
incur significant setup times and/or setup costs (the recent trend is to reduce setup times at
the expense of large material, equipment and/or labor costs) when a machine switches from
producing one type of product to another. To exploit these economies of scale, manufacturers
are forced to produce their products in large batches, and the exhaustive policy considered here
is the most natural way to reduce setups without incurring unnecessary idleness.

In manufacturing settings, sojourn time (also called manufacturing cycle time, lead time
or throughput time) distributions help managers to release and schedule work, quote delivery
dates for customers, coordinate with downstream operations (such as distribution), price their
products and set performance metrics. Steady state sojotun times are helpful for tactical and
strategic level decisions, and are the best available estimates for factories that cannot generate
real time queue length information. For systems with real time information capability, transient
sojourn times are preferable to steady state estimates for operational decisions, and can greatly
enhance performance (see Wein 1991 for a simple example in due-date cjuotation).

Our queueing network model is essentially a set of polling systems in tandem. Although


the performance analysis of polling systems has generated an enormous literature, there are no
studies that consider a network of interacting polling systems. Karmarkar et al. (1985) develop
a fixed batch size queueing network approximation that is useful for tactical level decisions,
but they do not capture the detailed system dynamics of the network. Since our queueing net-
work model appears to defy exact analysis, we employ heavy traffic approximations to address
the problem. Recently, Coffman, Puhalskii, and Reiman (1995a, 1995b) — henceforth referred
to as CPRI and CPRII, derived an averaging principle for single-server polling systems with
and without switchover times. This principle is due to a time scale decomposition that arises
under the traditional heavy traffic normalizations: On the time scale giving rise to a diffusion
process for the total workload, the individual workloads (for each class) move (asymptotically)
infinitely fast. When viewed on the time scale that makes the rate of movement of the indi-
vidual workloads positive and finite, the total workload remains constant, and the individual
workloads move deterniinistically. Consequently, the dynamics of thc^ individual workloads can
be analyzed deterministically. The primary contribution of this paper is the deterministic anal-
ysis of the individual workloads for a tandem queueing system. This deterministic analysis
yields a recursive procedure for the transient sojourn time distribution of each customer type
for the system described at the beginning of this paper. To perform a steady state sojourn time
analysis, the stationary tlistribution of the vector describing the total workload at each station
is required. We compute the steady state .sojourn time distribution by making the additional
assumptions that setup times are zero and that the total workload vector has a product-form
distribution (product-form conditions for an approximating Brownian network are slightly less
restrictive than the corresponding conditions for a traditional queueing network). In addition,
we derive a product-form solution in heavy traffic for the case where only the first station has
setup times.

The remainder of this paper is organized as follows. The model is formulated in Section
1 and the heavy traffic normalizations are introduced in Section 2. Section 3 contains the
deterministic analysis that forms the basis of this paper; to keep the analysis relatively easy
to follow, we restrict ourselves in this section to the case where all service time distributions
have the same mean. The deterministic results are used in Section 4 to obtain the transient
and steady state sojourn time distributions for the original queueing network. For several
simple examples, we also compare our steady state sojourn time estimates to those computed
via simulation. In Section 5, we investigate several generalizations of the model, including

service rates that differ by customer type at each station, closed networks, networks with three
customer types, the incorporation of FCFS nodes, and setup times at station 1. Conchiding
remarks are offered in Section 6.

1 The Model

The queueing network ha.s A' single-server stations and two customer types, A and B.
Customers of each type arrive to station 1 according to independent renewal processes with
rates A^ and A^, proceed through the tandem network from station 1 to station A', and exit
after service is completed at station A". Following traditional terminology, we define a different
class of customer for each stage of each type's route; these classes are denoted by Ai and Bi for
i = 1 . . . , K. Each class has a different general service time distribution, but all service rates
equal /.i. Let pj = \j/p for j = .4, B, and define the traffic intensity of tliis balanced system by
p = Pa + PB- Finally, let cJq denote the scjuared coefficient of variation of the interarrival times
for type j and let c~, represent the squared coefficient of \-ariation of the service times for class

We assume that a random setup time is incurred when a server switches from one class to
the other; however, due to the scaling of time and the rarity of switchovers in heavy traffic,
our transient sojourn time estimates are independent of the setup time. Consequently, we do
not introduce any setup time notation. Finally, the server at each station serves each class to
exhaustion, and then switches to the other class.

2 Heavy Traffic Preliminaries

In a typical heavy traffic analysis, one defines a sequence of queueing systems indexed by n
that approaches heavy traffic as n —> oc. Since a heavy traffic limit theorem will not be derived,
we avoid unnecessary notation by considering a single large integer n satisfying \/n{p — 1) = c,
where c is negative and of moderate size. This condition requires each server to be busy the
great majority of the t'nnc to satisfy demand. In Section 4, we see that our sojourn time
estimates are independent of the system parameter n.

For class ji,j = A,B:) = 1 A', let {Lj,{t),f > 0} denote the unfinished workload

process and {M'j,(f), t > 0} be the viytiiRl wniting time process. The quantity L_,j( 1 under exhaustive polling may not be the same as under FCFS. (With no setup
times, the total workload in station 1 is the same under both disciplines.) It .seems clear from
heavy-traffic scaling arguments that the heavy traffic limit of the vector total workload process
(with zero setup times) is the same under exhaustive polling as in FCFS a.s long as the mean
service time depends only on the station. Thus we use the results of Peterson even though
there is no rigorous proof that they apply (unless the service time distribution depends only on
the station). The heavy traffic scaling argument is roughly as follows. The drift of the limit
diffusion process depends only on arrival rates and mean service times, so it is the same in
both cases. The variance of the limit diffusion process depends on variation in the centered and
normahzed processes over 0{n) time; on this scale, based on results in CPRI and CPRII. the
fraction of each type served is the same as m FCFS, so the variances should match. Although
the stationary distribution of the limit diffusion process is not known in general, Peterson has
identified cases under which the stationary distribution is a product of exponential marginals.
When this condition is not met, the numerical procedure of Dai and Harrison (1992) can be

3 Deterministic Analysis

Throughout this section, we slow down time so that the total workload vector (\'i I'k)

is fixed, and {Vj,(/),f > 0},j = A,D:i = 1 K moves at a finite rate in a deterministic

fashion. If we denote the arrival time of a randomly arriving customer as time 0, then the initial

conditions are random, and consist of \'j,{0).j = A.B.i = 1 A' and .s,(0),( = 1 A'.

where Va,{0) + \'[u(0) — \', and .s,(/) is the customer type being served by .server i at time f.
Hence, the deterministic path of {\'j,{t).t > 0} is dictated by \',4/(0), ,s;(0),/ = 1 /; as we

will see shortly, it suffices to focus on VAi{t), i = 1, A', because V/t,(0 + ^Bi(0 is equal to

V; for all t.

The derivation of our main result consists of three main steps: First, we show that, inde-
pendent of initial conditions, the process {V4,( 0} enters a unique limit cycle within a
finite amount of time; that is. the trajectory of the process keeps repeating the same cycle.
Second, we identify the limit cycle for station ?. The cycle consists of the service of class Ai
customers for C4, time units followed by the service of class Di customers for C/j, time unitr.
and the cycle repeats itself every C, = CAi + Cbi time units; we refer to C, as the cycle length
for station i, and refer to Cj, as the cycle length for class ji. Finally, we derive the normalized
virtual waiting time from the limit cycle.

Before stating the main result, we illustrate our method on the single-server polling model in

CPRI and CPRII, and th(Mi informally describe 'he dynamics of VjAO^J = A. B\i = \ K

for a fixed total workload vector (I'l, . . . , \X-). Since arrivals to station 1 are exogenous, class

.41 work arrives to station 1 at rate p^. regardless of the system state. The server depletes

work at rate one, and hence V'4i(f) decreases at rate 1 — pa when class .41 is being served, and

increases at rate pA Because p = 1 in the heavy traffic limit, we assume that \'.\i(0

increases at rate 1 — pg, rather than pa, when class Bl is being served. Since setup times

do not appear at this time scale in the heavy traffic limit. {VAi{t),t > 0} follows the familiar

"saw-tooth" path that arises in the economic order quantity model with finite production rate:

see the top graph in Figure 1. Hence, regardless of the initial conditions (^41(0), .si(0)). the

process {VAi{t),t > 0} essentially enters a limit cycle at time zero. However, for convenience

and without loss of generality, we specify the start of a cycle as the moment that V^i (rver at station 2 will be serving
class 52 just after time to (and perhaps just before time ^2 also); hence, V'42(0 increases at
rate 1 starting at time f2-

Since V'l and V2 are fixed, the deterministic process {V/i2(0.^ > 0} is fully specified by the
initial conditions ( V'.\i(0), V'42(0), ,si (0), .§2(0)). We now compute ^2 foi" fhe four cases charac-
terized by the values of (.s-i(O), S2(0)). If .si(0) = .S2(0) = .4, then V;42(/) stays constant for the
first y^_ - time units. Thereafter, until V'42(0 reaches zero, it alternates between decreasing
at rate 1 for Cb\ time units and staying constant for C41 time units, and

f2 = Z +

1 - Pa



Cb\ +




1 c.



readers are referred to the bottom graph in Figure 1, where t^ = 44.

If 5i(0) = 52(0) = B. then after remaining constant for ^^'^ ' time units, V',42(0 rises and
stays constant during ^^^ periods of length C41 and ^^^ ' — 1 periods of length Cb] •
respectively. At this point V'42(0 = Vo, .si(0 = B, and .S2(0 = ■■^- then the process V'42(0
alternates between decreasing and constant phases until ^2^ where

r Vbi(0) ,

t2 = :; 1-

1 - PB




Cai +





\'> 1







1 c


If .si(0) = .4 and .^2(0) = B, then \'.42(0 grows initially. Before reaching t-i, it must rise by

Vb2{0) and then drop to zero. The length of the first growth period (which starts at time zero)

for V'42 is ^^'^ ' A V'/^2(0)^ and the length of any subsequent growth periods (there are none

if ^B2(0) < /' ■ ' ) is C'ai- Once \'.42(0 starts decreasing, it proceeds as in the previous case.
^ Pa



1 -Pa


Vb2(0) - t^

^'^{Vb.(0)>^} +




Cbi +




1 C.4, , (3.14)

where /|jj is the indicator function for the event .r. Sinularly, if .si(0) = B and •S2(0) = .4. then

12 = :; H

1 - PB






Mr I'bi(O)


1 3

Online LibraryMartin I ReimanHeavy traffic analysis of polling systems in tandem → online text (page 1 of 3)