Math 18ma41 Ga

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 16

Dr.

AMBEDKAR INSTITUTE OF TECHNOLOGY


(An Autonomous Institute, Affiliated to Visvesvaraya Technological University,
Belagavi, Accredited by NAAC, with ‘A’ Grade)
Near Jnana Bharathi Campus, Mallathahalli, Bangalore – 560056

DEPARTMENT OF COMPUTER SCIENCE AND


ENGINEERING
Group Activity Report on
“ STEADY STATE PROBABILITY IN QUEUEING SYSTEM”
Submitted in partial fulfillment of
PROBABILITY,STATISTICS AND QUEUING THEORY
Submitted by :
NAMES USN
SWATHY K 1DA19CS175
SWETHA 1DA19CS176
T.MANJUNATH 1DA19CS177
TEJAS M.N 1DA19CS179
TEJAS PORWAL 1DA19CS180
TRISHUL VISHNU K.T 1DA19CS181
UDAYA M.S 1DA19CS182
UMERA .M 1DA19CS183
VAIBHAV RAJ 1DA19CS185
VARUN HEGDE 1DA19CS186
WHAT IS QUEUEING THEORY ???
Queuing theory (or queueing theory) refers to the mathematical study of
the formation, function, and congestion of waiting lines, or queues.
At its core, a queuing situation involves two parts.
* Someone or something that requests a service—usually referred to as
the customer, job, or request.
* Someone or something that completes or delivers the services—usually
referred to as the server.
Queuing theory scrutinizes the entire system of waiting in line, including
elements like the customer arrival rate, number of servers, number of customers,
capacity of the waiting area, average service completion time, and queuing
discipline. Queuing discipline refers to the rules of the queue, for example
whether it behaves based on a principle of first-in-first-out, last-in-first-out,
prioritized, or serve-in-random-order.
QUEUEING THEORY contd....
STATE OF QUEUEING SYSTEM
The transient state of a queuing system is the state where the probability of the number
of customers in the system depends upon time (t).

The steady state of a queuing system is the state where the probability of the number of
customers in the system is independent of time (t).
Let Pn(t) indicate the probability of having n customers in the system at time t. Then if
Pn(t) depends upon t, the queuing system is said to be in the transient state. After the
queuing system has become operative for a considerable period of time, the probability
Pn(t) may become independent of t. The probabilities are then known as steady state
probabilities.

Certain relationships exist among specific operating characteristics for any queuing
system in a steady state. A steady state condition exists when a queuing system is in its
normal stabilized operating condition, usually after an initial or transient state that may
occur (e.g., having customers waiting at the door when a business opens in the
morning). Both the arrival rate and the service rate should be stable in steady state.
Terminology and Notation
• State of the system : Number of customers in the queueing system
(includes customers in service)
• Queue length : Number of customers waiting for service
= State of the system - number of customers being served
• N(t) = State of the system at time t, t ≥ 0
• Pn(t) = Probability that exactly n customers are in the queuing system at
time t
• λn = Mean arrival rate (expected # arrivals per unit time)of new customers
when n customers are in the system
• µn = Mean service rate for overall system (expected # customers
completing
service per unit time) when n customers are in the system
1/λ = expected interarrival time
1/µ = expected service time
Terminology and Notation contd....
• State is number of customers in the system, may be infinite
• Transitions can happen at any time, so instead of transition probabilities, as
with Markov chains, we have transition rates also called as rate diagrams
• Queueing analysis is based on a special case of continuous time
Markov chains called birth-death processes
• Rate diagrams indicate the states in a birth-and-death process and the
arrows indicate the mean rates at which transitions occur
ρ = λ/sµ = utilization factor for the service facility= expected
fraction of time the system’s service capacity (sµ)is being utilized
by arriving customers (λ)
Utilization is ρ= λ/(sµ)
• If one server, s=1 , ρ= λ/µ --> if utilization > 1, so steady state
will never be
reached, queue length will increase to infinity in the long run
• If servers, s>1, ρ= λ/(sµ) = 1 --> if utilization = 1, queue is
unstable and may never reach steady state
• If servers keeps on increasing ,ρ= λ/(sµ)--> if utilization < 1, the
queue will reach steady state then number of customers are finite .
Stochastic Processes
A stochastic process is a sequence
X1,X2, . . . of random variables
indexed by the parameter t, such as
time.
For example, number of jobs at
CPU of computer system at time t is a
random variable X(t)
Time and state can be discrete or
continuous.
A queuing system is characterized by
three elements:
 A stochastic input process
 A stochastic service
mechanism or process 9
 A queuing discipline
Types of Stochastic Processes
Markov
Processes

Birth-death
Processes

Poisson
Processes
BIRTH AND DEATH PROCESS
The birth–death process (or birth-and-death process) is a special case of
continuous-time Markov process where the state transitions are of only two
types: "births", which increase the state variable by one and "deaths", which
decrease the state by one.
“BIRTH” = “ARRIVAL OF CUSTOMER”
“DEATH” = “DEPARTURE OF CUSTOMER”
When a birth occurs, the process goes from state n to i + 1.
When a death occurs, the process goes from state n to state i − 1.
The process is specified
by birth rates .
General assumptions of birth-and-death processes:
1. Given N(t) = n, the probability distribution of the time remaining until the
next birth is exponential with parameter λn
2. Given N(t) = n, the probability distribution of the time remaining until the
next death is exponential with parameter µn
3. Only one birth or death can occur at a time

The equilibrium probabilities of a BD process


We use the method of a cut = global balance condition applied on the set of
states 0,1, . . ., k.
In equilibrium the probability flows across the cut are balanced (net flow =0)
λkπk = µk+1πk+1 k = 0, 1, 2, . . .
We obtain the recursion
πk+1 =(λk /µk+1)πk
STEADY STATE PROBABILITIES FOR POISSON QUEUE SYSTEM
The steady state probabilities for poisson queue system are derived by assuming that
Pn(t) --> P(t) , independent of t , as
t --> infinity. The equations of steady state probabilities ,Pn , can be obtained by putting
dPn(t) = 0 and replacing Pn(t) by Pn
d(t)
Thus we obtain,
THANKYOU

You might also like