Queing

Queuing Systems

Topic 2:

1

Queuing Systems

M/M/1 Queuing System

M/M/1/K Queuing System

2

QUEUEING SYSTEMS : Kendall Notation

A/ B / X /Y/ Z

A : Inter-Arrival time distribution M  Exponential

B : Service time M  Exp. Em  kth Erlang

D  Deterministic G  General

X : # of Servers

Y : System Capacity

Z : Q Discipline ; e.g. FIFO , LIFO , SIRO ( Service in Random Order ), PRI

M/D/1

,

M/M/1

∆

,

M/G/1

3

M / M / 1 @ M / M / 1 /  / FIFO

M/M/1

QUEUING SYSTEM

Infinite Buffer l

Server

m

l

= # of Arriving customers / sec. (Arrival Rate)

m = # of customers being served / sec. ( Service Rate , Departure Rate ) a(t) = l e-lt u(t) b(t) = m e-µt u(t) Let N(t) = # of msg’s in system at time “t” Pn(t) = Prob. { N(t) = n }

4

FIG.

State Transition Diagram

n+1 B

( M / M / 1)

A

n

C n-1

n

. . . .

1

D

. . . . . .

1 E 0 time t +∆t 5

0 t

Pn(t + t)

=

A Pn + 1(t) + B Pn(t) + C Pn - 1(t) - - - - - - - - - -(1)

A

= Prob.[ NO customer arrives & ONE customer is served 

= ( 1 - l t ) m t B

@

m t

= Prob.[ NO arrival & NO departure OR ONE arrival & ONE departure ] = ( 1 - m t ) ( 1 - l t ) + m t . l t @ 1 - m t - l t

C

= Prob.[ 1 arrival & NO departure] = l t [1 - m t ] @

lt

Pn(t + t) d Pn (t) dt

=

m t Pn + 1(t) + (1 - m t - l t) Pn(t) + l t Pn - 1(t)

Pn ( t + t ) - Pn (t) t

= Lim t  0 

= m Pn + 1(t) - ( m  l ) Pn(t) + l Pn - 1(t) - - - - - - - - - (2)

6

ALWAYS CHECK THE BOUNDARI ES ; P0 (t + t) = D P1(t) + E P0(t) D = Prob.[ NO a rri va l& ONE de pa rture ] = (1 - l t) m t E = 1 - l t P0 (t + t) = m t P1(t) + (1 - lt) P0(t) d P0 (t) = m P1(t) - l P0(t) - - - - - - - - - -(3) dt For Sta ti ona rySta ti s ti ca Proce s s l Li mt   Pn(t) = Pn   d Pn(t) = 0 dt @ m t

I n(2) & (3) Pn + 1 & P1  (m + l ) l Pn - Pn - 1 - - - - - - - - - - - - - (4) m m l  P0 - - - - - - - - - - - - -...