ANALİTİK
KUYRUK
MODELLERİ
16-2


Geçiş durumu X Kararlı durum
 Geçiş durumunda, bir sistemin çalışma
özelliklerinin değerleri zamana bağlıdır.
 Kararlı durumda, sistem özellikleri zamandan
bağımsızdır ve sistemin istatistiksel bir denge
içinde olduğu düşünülmektedir.
Çoğu hizmet sistemi bazen her saat değişen
geliş hızıyla dinamik bir ortamda faaliyet
göstermektedir; bu nedenle, kararlı durum
nadiren gerçekleşir. Ancak, kararlı durum
modelleri uzun dönem kapasite planlama
kararları için yararlı sistem performans
tahminleri sağlayabilir.
16-3
ÖZEL POISSON KUYRUK MODELLERİ


c tane aynı şekilde paralel hizmet
verenin olduğu özel poisson kuyruk
durumu.
Boştaki ilk hizmet veren tarafından,
hizmet verilmek üzere kuyrukta
bekleyen bir müşteri seçilir.
16-4
ÖZEL POISSON KUYRUK MODELLERİ



Sistemdeki geliş hızı birim zamanda λ
müşteridir.
Tüm paralel hizmet verenler aynı hizmeti
sağlarlar, bunun anlamı herhangi bir
hizmet veren için hizmet hızının birim
zamanda μ müşteri olmasıdır.
Sistemdeki müşterilerin sayısı hizmet
gören ve kuyrukta bekleyenlerin toplamını
içermek üzere tanımlanır.
16-5
KENDALL NOTATION

(A / B / C ): (D / E / F)
 A: Geliş dağılımları
 B: Gidiş (hizmet süresi) dağılımı
 C: Paralel hizmet verenlerin sayısı(=1,2,...,∞)
 D: Kuyruk disiplini
 E: Sistemde (kuyruktaki + hizmet gören) izin
verilen maksimum sayı (sonlu veya sonsuz)
 F: İstek kaynağının (sonlu veya sonsuz)
büyüklüğü



(A/B/C) : D.G. Kendall (1953)
D, E
: M. Lee (1966)
F
: H. Taha (1968)
16-6
A: Geliş Dağılımı
B: Gidiş Dağılımı





M : Markov (veya Poisson) geliş ve gidiş
dağılımları (ya da eşdeğeri üstel gelişlerarası
veya hizmet süresi dağılımı)
D : Sabit (deterministik) süre
Ek : Sürenin Erlang veya Gamma dağılımı
(veya eşdeğeri bağımsız üstel dağılımların
toplamı)
GI : Gelişlerarası sürenin genel dağılımı (örn:
normal, düzgün, ya da herhangi bir deneysel
dağılım)
G : Hizmet süresinin genel dağılımı (örn:
normal, düzgün, ya da herhangi bir deneysel
dağılım)
16-7
D: Kuyruk Disiplini

FCFS: İlk Gelen İlk Hizmet Görür

LCFS: Son Gelen İlk Hizmet Görür

SIRO: Rastgele Sırada Hizmet Görme

GD: Genel Disiplin (başka bir deyişle,
başka herhangi bir disiplin)
16-8
Örnek

(M/D/10):(GD/20/∞)

M: Poisson gelişler (ya da üstel gelişlerarası
süre)

D: Sabit hizmet süresi

10: 10 paralel hizmet veren

GD: Genel kuyruk disiplini


20: Sistemin tamamında 20 müşteri sınırı
vardır
∞: Müşterilerin geldiği kaynak büyüklüğü
sonsuzdur
Kararlılık Durumu Performans
Ölçütleri

n
: Sistemdeki müşteri sayısı

λ
: Ortalama geliş hızı


μ
(örn: saatte gelen müşteri)
: Her bir dolu hizmet veren için ortalama servis hızı

(örn: saat başına müşteriler için hizmet kapasitesi)


: (λ/ μ) Hizmet gören müşterilerin ortalama sayısı

N
: Sistemde izin verilen maksimum müşteri sayısı

c
: Hizmet veren sayısı

/c : Kullanım oranı faktörü

Pn
: Sistemde izin verilen müşterilerin tam n olma olasılığı
16-9
Kararlılık Durumu Performans
Ölçütleri

Ls

16-10
: Sistemdeki ortalama müşteri sayısı
Sistemin kuyruk ve hizmet yerinin her ikisini de kapsadığını
hatırlayalım.

Lq
: Kuyruktaki ortalama müşteri sayısı

Lb
: Meşgul bir sistem için kuyruktaki ortalama müşteri sayısı

Ws : Sistemdeki müşterinin harcadığı ortalama süre

Wq : Kuyruktaki müşterinin harcadığı ortalama süre

Wb : Meşgul bir sistem için kuyruktaki müşterinin harcadığı
ortalama süre
16-11

Ls 
 nP
n
n 1

Lq 

n  c 1
( n  c )  Pn
16-12
Little’ın formülü
L s   ef f  W s
L q   ef f  W q

Bu ilişkiler böyle genel koşullar altında geçerlidir.

λeff : Sistemdeki etkin geliş hızı.


Tüm müşterilerin sisteme katılması durumunda geliş hızı
λeff = λ’dır.
Aksi halde, sistem dolu olduğu için (örneğin
otoparkta)bazı müşteriler sisteme katılmazlarsa λeff < λ
olur.
16-13
 Sistemdeki beklenen

bekleme süresi

Ws  Wq 
  Kuyruktaki beklenen
  
bekleme süresi
 
  Beklenen
  
  hizmet süresi



1

 ef f  W s   ef f  W q   ef f 
1

Sistemdeki ortalama sayı olan Ls
ile kuyruktaki ortalama sayı olan
Lq’nun farkı, meşgul hizmet
verenlerin ortalaması olan ’ye eşit
olmalıdır.
Ls  Lq 
 ef f

  Ls  Lq 
 eff
Tesis kullanım oranı (U) =


c
16-14
Example (Taha, 17.6-1)




Bir üniversitenin merkez binasında ziyaretçi otoparkı
5 otomobille sınırlıdır. Otomobiller bu alanı saatte 6
otomobil hızıyla Poisson dağılımına uygun olarak
kullanmaktadırlar.
Park süresi, ortalaması 30 dakika olan üstel dağılıma
uymaktadır.
Geldiklerinde boş yer bulamayan ziyaretçiler
parkeden otomobillerden biri gidene kadar geçici
olarak parkın içinde beklemektedir.
Bu geçici park alanı da ancak üç otomobil
almaktadır. Park yeri veya geçici bekleme yeri
bulamayan otomobiller ise başka bir otoparka
gitmek zorunda kalmaktadır.
16-15
n otomobilin sistemde bulunma olasılığı Pn




c=5 paralel hizmet verici
 Park alanları hizmet veren gibi davranır
Sistemin maksimum kapasitesi
 5+3=8 otomobil.
Olasılık genelleştirilmiş modelin özel bir hali
olarak belirlenebilir.
λ=6 oto/saat, n=0,1,2,...,8
  60
 n 
30
n   
60
 5 
  30

  2 n oto/saat,


  10 oto/saat,

n  1,2,3,4,5
n  6, 7, 8
16-16
Pn
  6 n
 

2

 
P0 ,

n!

 
n

6

 


  2 
P0 ,

n -5
 5! 5
n  1, 2, 3, 4, 5
n  6 , 7, 8
P 0  P1  P 2  P 3  P 4  P 5  P 6  P 7  1
P0  P0
2
 3
3


 1!
2!


3
3
3!

3
4
4!

3
5
5!

3
6
5! 5

3
7
5! 5
2

3
8
5! 5
3

  1


16-17
P0=0.04812
n
1
2
3
4
Pn
0.14436
0.21654
0.21654
0.16240
n
5
6
7
8
Pn
0.09744
0.05847
0.03508
0.02105
16-18
Otomobillerin otoparka etkin geliş hızı λeff



Müşteriler kaynaktan saatte λ otomobil hızıyla gelir.
Gelen bir otomobil λeff hızıyla otoparka girmekte veya
λlost hızıyla başka bir otoparka gitmektedir. (λ = λeff +
λlost)
Bir otomobil, otoparkta zaten 8 otomobil bulunuyorsa
otoparka giremez. (Otomobil oranı P8 olduğunda
girmek mümkün olmayacaktır)
λlost= λ x P8= 6 x 0.02105 = 0.1263 oto/saat
λeff= λ - λlost = 6 - 0.1263 = 5.8737 oto/saat
16-19
Otoparktaki ortalama otomobil sayısı, Ls

Otoparktaki ortalama araç sayısı (bekleyen veya
parketmiş olan) sistemdeki ortalama sayıya yani
Ls’ye eşit olur.

Ls 
 n P
n
n 1
L s  0  P0  1  P1  ...  8  P8  3 . 1286 oto
16-20
Otoparkın içinde boş park yeri için
bekleyen otomobilin ortalama süresi

Geçici park alanında bekleyen araç aslında
kuyrukta bekleyen araçtır. Böylece, bir yer
bulununcaya kadar aracın bekleme zamanı Wq
olarak bulunur.
Ws  Wq 
1

L s   ef f  W s
Wq  Ws 
Ws 
Ls
 ef f
1

16-21
Ws 
Ls
 eff

3 . 1286
 0 . 53265 saat
5 . 8737
W q  0 .53265 
1
2
 0.03265
saat
Dolu olan park yerlerinin
ortalama sayısı

Dolu park yerlerinin ortalama sayısı «meşgul
olan hizmet veren» sayısıyla aynıdır.
  Ls  Lq 
 
5 . 8737
2
 eff

 2 . 9368 spaces
16-22
Park alanının ortalama
kullanım oranı
Facility
utilizatio n 
parking lot utilizatio n 

c


c
2 . 9368
5
 0 . 58736
16-23
16-24
Queuing System Cost Tradeoff
Cw = Cost of one customer waiting in queue for an hour
Cs = Hourly cost per server
C = Number of servers
Total Cost = Service Cost + Customer Waiting Cost
Total Cost = Cs C + Cw Lq
Note: Only consider systems where
C   


16-25
Appendix D
Equations for selected queuing models
1.
Standard M/M/1 Model (0<ρ<1.0)
2.
Standard M/M/c Model (0<ρ<c)
3.
Standard M/G/1 Model (V(t)=service time
variance)
4.
Self-service M/G/∞ Model
5.
Finite-Queue M/M/1 Model
6.
Finite-Queue M/M/c Model
16-26
1. Standard M/M/1 Model (0<ρ<1.0)
1.
2.
3.
4.
5.
İstekli kişiler anakütlesi. İsteklilerin gelişi sonsuz ya
da çok büyük anakütleden. İstekliler birbirinden
bağımsızdır ve kuyruk sisteminden etkilenmezler.
Geliş süreci. Geliş hızı Poisson dağılımı.
Kuyruk yapısı. Uzunluğunda sınırlama olmayan tek
bekleme hattı, and no katılmama ya da kuyruğu
terk etme yok.
Kuyruk disiplini. FIFO
Hizmet süreci. Hizmet süresi üstel dağılımlı tek
hizmet veren.
16-27
Equations
1.
2.
3.
4.
5.
6.
Ortalama geliş hızı: 
Ortalama servis hızı: 

 
Hizmet gören müşterilerin ortalama sayısı:

n
Sistemdeki müşterilerin tam n olma olasılığı: Pn   (1   )
Sistemde “k” ya da daha fazla müşteri olma olasılığı: P ( n  k )   k

Sistemdeki ortalama müşteri sayısı:
Ls 

7. Kuyruktaki ortalama müşteri sayısı : Lq  

8. Sistemde geçen ortalama süre:
Ws 
9. Kuyrukta geçen ortalama süre:
Wq 
1



16-28
Example 14.2. (page 449)



λ=6 bot/saat (poisson)
μ=6 dakika/bot (10 bot/saat) (üstel)
M/M/1 model (sonsuz anakütle, kuyruk
uzunluğu kısıtlaması yok, kuyruğa katılmama ya
da kuyruğu terk etme yok, ve FCFS kuyruk
disiplini)
Ls
λ
Tek hizmet veren
Lq
μ
16-29




ρ=λ/μ=6/10= 0.60
Sistemin dolu olma ve gelen müşterinin
bekleme olasılığı :
k
1
1
P
(
n

k
)


P(n≥1)= ρ =0.60 =0.60
Rampayı boş bulma olasılığı:
P0=1- ρ=1-0.60=0.40
Sistemdeki ortalama bot sayısı:
Ls 



6
10  6
 1 . 5 boats
Ls 


16-30

Kuyruktaki ortalama bot sayısı:
Lq 



( 0 . 60 )( 6 )
10  6
1


1
10  6
Wq 


0 . 60
10  6
Ws 
1

 0 . 25 hour (15 min.)
Kuyrukta geçen ortalama süre:


 0 . 90 boat
Sistemde geçen ortalama süre:
Ws 


Lq 

Wq 
 0 . 15 hour (9 min.)


16-31

Bot rampası zamanın %60’ında dolu.


Bu nedenle gelişlerin zamanın %40’ında gecikmesiz
anında erişimi beklenebilir.
15 dakika olan sistemde geçen ortalama süre 9
dakikalık kuyrukta geçen ortalama süre ve 6
dakikalık ortalama hizmet süresinin toplamıdır.
16-32

Sistemdeki müşteri sayısı sistem durumunu
tespit etmek için kullanılabilir.
 Örneğin, n=0 olduğunda, sistem boştur.
 n=1 olduğunda, servis veren dolu fakat
kuyruk yoktur.
 n=2 olduğunda, hizmet veren dolu ve 1
kuyruk oluşmuştur.
 n için olasılık dağılımı, bekleme yerinin uygun
büyüklüğünü belirlemede çok yararlı olabilir
(örn: sandalye sayısı- belirli bir olasılıkla
gelen müşterilere uyum sağlamak için her
müşterinin boş sandalye bulacağını vaat
edecek)

Bot rampası örneği için, zamanın %90’ını
garanti etmek için ihtiyaç duyulan park
alanı sayısını belirleyin, bot rampasına
gelen bir kişi denize indirmeyi beklerken
park için boş yer bulacak.
n
Pn   (1   )
n
Pn
P (müşteri sayısı≤ n)
0
(0.6)0(0.4)=0.40
0.40
1
(0.6)1(0.4)=0.24
0.64
2
(0.6)2(0.4)=0.144
0.784
3
(0.6)3(0.4)=0.0864
0.8704
4
(0.6)4(0.4)=0.05184
0.92224
16-33
16-34



Artan n değeri için, sistem durumu için olasılık
dağılımını tekrar tekrar kullanarak, %90
garantisi aşılana kadar sistem durum
olasılıklarını topluyoruz.
n=4 ya da daha az bir sistem durumu zamanın
%92’sinde oluşacaktır.
4 bot römorku için yer önerisi sağlanmalıdır
çünkü zamanın %92’sinde gelenler denize
inmek için kuyrukta 3 ya da daha az insan
bulacaklar.
16-35
EXAMPLE



A Social Security Administration branch is considering the following two
options for processing applications for social security cards:

Option 1: Three clerks process applications in parallel from a single
queue. Each clerk fills out the form for the application in the presence of
the applicant. Processing time is exponential with a mean of 15 minutes.
Interarrival times are exponential.

Option 2: Each applicant first fills out an application without the clerk’s
help. The time to accomplish this is exponentially distributed, with a
mean of 65 minutes. When the applicant has filled out the form, he or
she joins a single line to wait for one of the three clerks to check the
form. It takes a clerk an average of 4 minutes (exponentially distributed)
to review an application.
The interarrival time of applicants is exponential, and an average of 4.8
applicants arrive each hour.
Which option will get applicants out of the more quickly?
16-36
For Option 1




Option 1 is an M/M/c system with λ = 4.8
applicants/hr. and µ = 4 applicants/hour.
c=3 and ρ = 4.8/4 = 1.2 , from table Lq =
0.094 applicants
Ls=Lq + ρ = 0.094 + 1.2 = 1.294 applicants
Ws = Ls/λ = 1.294/4.8 = 0 .27 hours
16-37
For Option 2

Option 2 is a 2-stage series queuing system

M/M/ + M/M/3


Stage 1 is an M/G/ system
 Ws1 = 1/µ = 1.08 hours.
Stage 2 is an M/M/c with ρ = 4.8/15=0.32
 c=3 and ρ = 0.32
 from table Lq = 0 applicants
 Ls = Lq +λ/µ = 0 + 0.32 = 0.32 customers
 Ws2 = Ls/λ =0.32/4.8 = 0.07 hours.

Ws= Ws1 + Ws2 = 1.08 + 0.07 = 1.15 hours.

Option 1 results in a much smaller customer waiting time than
Option 2.
16-38
EXAMPLE

Last National Bank is concerned about the level of
service at its single drive-in window. A study of
customer arrivals during the window’s busy period
revealed that, on average, 20 customers per hour
arrive, with a Poisson distribution, and they are given
FCFS service, requiring an average of 2 minutes, with
service times having an exponential distribution.
16-39
What is the expected number of customers waiting in queue?
  20 ,

  30
2
Lq 
( M / M / 1)
3


 
20
30  20

2
3
 1 13 customers
If Last National were using an automated teller machine with a
constant service time of 2 minutes, what would be the expected
number of drive-in customers in the system?
Ls  Lq  
   V (t)
2
Ls 
( M / G /1
2
2 (1   )

V (t)  0)
with
 
2
3
2
 20 ( 0 )
2 1 
2
2
3


2
3

2
3

2
3
 1 13 customers
16-40
There is space in the drive for 3 cars (including the one being
served). What is the probability of traffic on the street being
blocked by cars waiting to turn into the bank driveway?
Traffic will block the street when there are four or more cars
in the system.
n
Pn
Cumulative Probability
0
1/3
=
0.333
0.333
1
2/9
=
0.222
0.555
2
4/27 =
0.148
0.703
3
8/81 =
0.099
0.802
The probability of traffic being blocked is equal to
1 - 0.802 = 0.198.

μ  30
16-41
Last National is considering adding tellers at the current drivein facility. It has decided on $5 per hour as the imputed cost of
customer waiting time in the system. The hourly cost of a teller
is $10. The average arrival rate of customers has reached 30
per hour. On the basis of the total hourly cost of tellers and
customer waiting, how many tellers do you recommend?
Assume that with use of pneumatic tubes, tellers can serve
customers as though there were a single queue.
; λ  30 for system;
ρ

μ

30
30
1
This is a single queue, multiple server arrangement or M/M/c
system. Thus, Lq can be found using table.
Ls  Lq  
$10c
$5Ls
Total
0.333
1.333
$20.00
$6.67
$26.67
3
0.045
1.045
$30.00
$5.23
$35.23
4
0.007
1.007
$40.00
$5.04
$45.04
#Tellers, c
Lq
2
Recommend two tellers.
16-42
EXAMPLE (Winston, page 1106)
The last two things that are done to a car before its
manufacture is complete are installing the engine and
putting on the tires. An average of 54 cars per hour arrive
requiring these two tasks. One worker is available to install
the engine and can service an average of 60 cars per hour.
After the engine is installed, the car goes to the tire station
and waits for its tires to be attached. Three workers serve at
the tire station. Each works on one car at a time and can put
tires on a car in an average of 3 minutes. Both inter arrival
times and service times are exponential.

Determine the mean queue length at each work
station.

Determine the total expected time that a car spends
waiting for service.
16-43

This is a 2-stage series queuing system.
 λ = 54 cars per hour
 c=1 and μ1 =60 cars per hour
 c=3 and μ2=20 cars per hour.
 Since λ< μ1 and λ< 3μ2, neither queue will
blow up.
16-44
For stage 1 (engine):



ρ =54/60=0.90
Lq (for engine) =( ρ2/(1- ρ))
=[(0.90)2 / (1-0.90)]
=8.1 cars
Wq (for engine)=Lq / λ
= 8.1 / 54
= 0.15 hour
16-45
For stage 2 (tires):





ρ =54/(3.20)=0.90
P(j≥3)=0.83
Lq (for tires
=[(0.83)(0.90) / (1-0.90)]
=7.47 cars
Wq (for tires) =Lq / λ
= 7.47 / 54
= 0.138 hour
Thus the total expected time a car spends
waiting for engine installation and tires is
0.15 + 0.138 = 0.288 hour
16-46
EXAMPLE

A company has a central document –
copying service. Arrivals are assumed to
follow the Poisson probability distribution,
with a mean rate of 15 per hour. Service
times are assumed to follow the
exponential distribution. With the present
copying equipment, the average service
time is 3 minutes. A new machine is
available that will have a mean service
time of 2 minutes. The average wage of
the people who bring the documents to be
copied is $8 an hour.
16-47

If the new machine can be rented for $10 per hour more
than the old machine, should the company rent the new
machine? Consider lost productive time of employees as
time spent waiting in queue only because the copying
machine is a self-serve device.
  15 ,
 ( old )  20 ,
 ( new )  30
Savings
per hour in waiting

cost  $ 8 L q ( old )  L q ( new )

2
2




 8



(



)
 (   ) 

2
2


15
15
 8


20
(
20

15
)
30
(
30

15
)


 8 ( 2 . 25  0 . 5 )
 $ 14  $ 10 rental
Savings
therefore,
exceed rental cost;
rent new machine.
16-48

For the old copying machine, what is the probability
when a person arrives that he or she will encounter
people already waiting in line for service? (Be careful
to identify properly the number of customers who
might be present for this situation to arise.)
2
 15 
P (n  2)    
  0.5625
 20 
2
16-49

Suppose the new copying machine is rented. How many
chairs should be provided for those waiting in line if we
are satisfied when there will be enough chairs at least 90
percent of the time?
n
Pn
0
1 
1
 1
Cumulative Pn
15
.5
P0 
30
 (.5 )(.5 )
 0 .5
 0 .25
.75
2
P1 
 (.25 )(.5 )
 0 .125
.875
3
P2 
 (.125 )(.5 )  0 .0625
.9375
P rovide 2 chairs for w aiting custom ers.
(A ssum e cu stom er being served stands. )
Download

For Option 2