Online Library → Martin I Reiman → Heavy traffic analysis of polling systems in tandem → online text (page 1 of 3)

Font size

p;j.T.U3RARli:S- DEWEY

Oewey

HD28

Heavy Traffic Analysis of Polling Systems in Tandem

Martin I. Reiman and Lawrence M. Wein

#3857-95-MSA September 1995

M/^SÂ£gHasc-rrs,,vsT,rL.)E

OCT 2 4 1995

L!3aAR;es

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

ABSTRACT

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

1

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

used.

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 otherwi.se. 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

V42(Q)

Cbi

Cb\ +

v;42(o)

c

B\

1 c.

.41-

(3.12

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

Vb2{0)

c

A\

Cai +

VbtW

C

.41

l|Cs,+

\.

\'> 1

C

Bl

c

B\

^2

C7i

1 c

(3.13)

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

Hence,

^;

V:4i(0)

1 -Pa

+

Vb2(0) - t^

Cm

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

V?

C

fli

Cbi +

Vi

C

B\

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

Va2{0)

Vbi(0)

1-PB

Cbi

CJ.v

Mr I'bi(O)

,^

Oewey

HD28

Heavy Traffic Analysis of Polling Systems in Tandem

Martin I. Reiman and Lawrence M. Wein

#3857-95-MSA September 1995

M/^SÂ£gHasc-rrs,,vsT,rL.)E

OCT 2 4 1995

L!3aAR;es

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

ABSTRACT

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

1

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

used.

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 otherwi.se. 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

V42(Q)

Cbi

Cb\ +

v;42(o)

c

B\

1 c.

.41-

(3.12

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

Vb2{0)

c

A\

Cai +

VbtW

C

.41

l|Cs,+

\.

\'> 1

C

Bl

c

B\

^2

C7i

1 c

(3.13)

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

Hence,

^;

V:4i(0)

1 -Pa

+

Vb2(0) - t^

Cm

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

V?

C

fli

Cbi +

Vi

C

B\

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

Va2{0)

Vbi(0)

1-PB

Cbi

CJ.v

Mr I'bi(O)

,^

Online Library → Martin I Reiman → Heavy traffic analysis of polling systems in tandem → online text (page 1 of 3)