Transcript ST3030(2)

Introduction to Queueing and
Simulation
Kingshuk Roy Choudhury
Statistics Department
UCC
Examples of queues
`That's the way the whole thing started,
Silly but it's true,
Thinking of a sweet romance
Beginning in a queue."
--G. Gouldman, ``Bus Stop," The Hollies
Introductory Examples
•
people waiting
–
–
–
–
–
for tickets at a box office each gets his own ticket one person gets tickets for a group
in a bank for a teller with one line and several tellers
at a grocery store in several check out lines, and jockeying
for Star Tours at Disneyland, then reneging
for medical treatment in a hospital emergency room
machines waiting for repair
•
–
–
office copiers under maintenance contract
factory equipment
telephone calls waiting for
•
–
–
switching and available lines
service at the other end hanging up if busy waiting on hold
•
factory jobs waiting at several stages of production
•
cars waiting to get on the freeway
•
cases working their way through the court system
Local Area Networks
or Media Access Systems
Subdividing an Ethernet with switches
Frequency Division Multiple
Access (FDMA)
Time Division Multiplex Access
(TDMA)
Basic queueing system components
Performance evaluation
Arrival processes
Memoryless
Deterministic
General
Poisson Process
The random process used most frequently to model the arrival pattern.
Characteristics of the Poisson process :
1. P[instant occurrence in (t, t+Dt)] = lDt+o(Dt);
l is mean arrival rate; o(Dt) approaches 0 faster than Dt.
2. P[no instance occurrence in (t, t+Dt)] = 1- lDt+o(Dt);
3. Arrivals are memoryless. Arrival in one time interval
is independent of arrivals in previous or future intervals.
4. P[2 or more arrivals in (t, t+Dt)] = o(Dt).
Note that the probability is independent of t.
Queueing disciplines
•FIFO
•LIFO
•Round Robin
•SJF
•SRPT
•FBn
•Priority
Number of servers
Birth and death processes
Steady-state probabilities (p10)
pnl = pn+1
…………………………..

pn+1 = n+1 p0
…………………………..

pn = n ( 1 -  )
…………………………..

N=/(1-)
(1)
(2)
(3)
(4)
Administrivia
• Lectures : Mon. 10-11, Boole LL3, Tue 5-6
CE110
• Contacting Kingshuk:
• ph. 4902546
• e-mail: [email protected]
• Office: Room 258 Aras Na Laoi
• Hours: 3-4 pm Tue. and Thu.
• Notes/practicals later
• 20% of grade final will be exercises.