03/12/2012
Delay System II
Sistem Antrian M/M/m
Kedatangan panggilan : Poisson arrival Service time : exponentially distributed Jumlah server : m Panjang antrian : tak terhingga Diagram transisi kondisi l l
0
l
1 m
l
2 2m
m
m-1 3m
l
l
(m-1)m
mm
l m+1
mm
mm
= system state • kKetika jumlah panggilan,k, kurang dari jumlah server,m, (k<m), maka service rate adalah km • • Ketika k m, maka service rate adalah mm Anhar - TES 3114 UR
2
1
03/12/2012
Sistem Antrian M/M/m (2)
Bila Pk adalah peluang kondisi k, maka global balance equation : m P1 = l P0 untuk k=0 (l + km)Pk = l Pk-1 + (k+1)m Pk+1 (l + mm)Pk = l Pk-1 + mm Pk+1 <
untuk 0 < k < m untuk m k
Untuk mencari Pk, kita gunakan local balance equation : Pk Pk -1 Pk - 2 ...
k k ( k - 1) – Untuk k m, kita peroleh l P0= m P1, l P1= 2m P2 , …, l Pk-1 = km Pk (m ) k ... P0 P0 – Maka kita peroleh k (k - 1) 2 k!
*
Catatan, r = l/(mm)
Anhar - TES 3114 UR
3
Sistem Antrian M/M/m (3) • Dengan cara serupa, untuk k > m, diperoleh : mm k Pk P0 , dimana ρ 1 m!
**
• P0 dicari menggunakan dua persamaan (*) dan (**) serta hukum peluang seperti yang sudah kita lakukan sebelumnya ketika menurunkan P0 untuk M/M/1
P0
1 (m ) k (m ) m k ! (1 - ) m! k 0 m -1
Anhar - TES 3114 UR
4
2
03/12/2012
Sistem Antrian M/M/m (4) Peluang kondisi k adalah sbb :
Pk
1 (m ) k (m ) m k! (1 - )m! k 0 m -1
mm k m!
Peluang bahwa suatu kedatangan akan menemukan seluruh server sibuk sehingga harus menunggu adalah :
P0 m m k P{Queueing} PQ Pk m! k m k m m P0 (m ) P 0 ( m ) m k -m (1 - )m! m! k m
Ini adalah rumus Erlang-C atau disebut juga Erlang’s Delay Formula Anhar - TES 3114 UR
5
Sistem Antrian M/M/m (5)
Utilisasi
– Untuk k < m, utilisasi server rata-rata adalah k/m – Untuk k m, utilisasi adalah satu – Maka utilisasi total adalah sbb: m -1
k Pk Pk m k 1 m k m
Anhar - TES 3114 UR
6
3
03/12/2012
Sistem Antrian M/M/m (6) Mari kita sesuaikan notasinya dengan notasi sebrlumnya : – N adalah sama dengan m – Sedangkan r =l/(mm)
– Bila kita menggunakan notasi tsb, maka r adalah A/N (ingat A=l/m) – Jadi:
AN 1 PQ DN ( A) N! 1 - A N
DN(A) dapat dihitung menggunakan rumus rugi Erlang :
1 1 1 DN ( A) E N ( A) E N -1 ( A) Anhar - TES 3114 UR
7
Hasil-hasil lain – Jumlah pelanggan rata-rata yang antri • nq=DN(A)[A/(N-A)]
– Waktu rata-rata pelanggan dalam antrian (senelum dilayani) untuk semua panggilan termasuk yang tak menunggu • tq= DN(A)[h/(N-A)]
– Waktu rata-rata pelanggan dalam antrian dihitung untuk pelanggan yang menunggu saja • tqm=h/(N-A)
– Waktu rata-rata lamanya pelanggan di dalam sistem • ts= h + tq – h=waktu rata-rata lamanya pelanggan di dalam pelayanan – tq=waktu rata-rata lamanya pelanggan di dalam antrian Anhar - TES 3114 UR
8
4
03/12/2012
Hasil-hasil lain (2) – Jumlah rata-rata pelanggan dalam sistem • N=A + [DN(A).A/(N-A)]
– Peluang panggilan menunggu selama T yang melebihi harga t tertentu (ini merupakan bagian panggilan yang memiliki waktu tunggu melebihi t) • Prob (T>t) = DN(A).e-(N-A)t/h • Prob (T>0) = DN(A)
Anhar - TES 3114 UR
9
Probabilitas waktu tunggu melebihi harga tertentu P(t>to)=P(t>0).e-(N-A)to/h = DN(A). e-(N-A)to/h
Anhar - TES 3114 UR
10
5
03/12/2012
Probabilitas jumlah yang antri melebihi harga tertentu Kita tinjau sistem M/M/1 dengan : – Laju kedatangan panggilan rata-rata:l – Waktu l pelayanan l rata-rata:lh=1/m l – Diagram transisi kondisi 0
1 m
2 m
l k+1
k m
m
l
m
m
– Dengan langkah solusi yang sudah sering kita lakukan, akan diperoleh hasil seperti pada slide no 20 Anhar - TES 3114 UR
11
Probabilitas jumlah yang antri melebihi harga tertentu (2) Probabilitas yang antri melebihi harga tertentu (N) Probabilitas (n N)=
(1-r)rn = rN n=N
Hati-hati, di sini r=l/m Anhar - TES 3114 UR
12
6
03/12/2012
Sistem Antrian M/M/m/N
Poisson Arrival Exponential Distribution Service Time Jumlah server = m Jumlah panggilan dalam sistem = N
– Jadi bila panggilan datang pada saat tempat menunggu penuh (yaitu kondisi terdapat N panggilan di dalam sistem), maka panggilan tersebut akan ditolak (loss) l
0
l
1
l
2
3m
(m-1)m
l
m
m-1
2m
m
l
l
mm
l
l
m+1
mm
N
mm
Anhar - TES 3114 UR
mm
13
Sistem Antrian M/M/m/N (2)
( m ) k P0 k! Pk mm k P0 m!
Untuk 0 k < m
Untuk m k N
Bila kita menghitung P0 menggunakan kondisi k=0Pk=1, maka kita peroleh : P0
1 (m ) m m m - N 1 k! m! 1 - k 0 m -1
k
Anhar - TES 3114 UR
Dimana r = l/(mm)
14
7
03/12/2012
Sistem Antrian M/M/m/N (3) Jumlah rata-rata panggilan yang menunggu di dalam antrian (belum dilayani)
(m ) m [1 - N - m - ( N - m) N - m (1 - )] m!
E[kq ] P0
Karena beberapa panggilan dapat diblok (loss) maka kita dapat menghitung effective (equivalent) arrival rate,le,sebagai berikut (ingat l adalah actual arival rate ):
mm N e (1 - PN ) (1 - P0 ) m!
Jumlah panggilan rata-rata di dalam sistem,E(k), adalah sama dengan jumlah panggilan yang menunggu di dalam antrian,E[kq], ditambah panggilan yang sedang dilayani :
E[k ] E[k q ] m (1 - P0
mm N ) m! Anhar - TES 3114 UR
15
Sistem Antrian M/M/m/N (4) • Waktu rata-rata di dalam antrian, E[w] :
E[ w]
E[k q ]
e
E[ k q ]
(1 - PN )
E[ k q ]
(1 - Po
mm N ) m!
• Delay yang dialami oleh panggilan :
E[d] = E[w] + (1/m) • Utilisasi untuk sistem antrian ini adalah sbb :
P 0 m
(m ) k m m m - N 1 P0 m! 1 - k 1 ( k - 1)! m -1
Anhar - TES 3114 UR
16
8
03/12/2012
Sistem Antrian M/M/m/N (5) Jika kita sumsikan N=m, maka setiap panggilan yang datang pada saat seluruh server sibuk akan diblok (loss) – Pada kondisi ini, sistem menjadi blocking system (sama dengan sistem M/M/m/m) – Rumus Erlang B merupakan peluang suatu panggilan yang datang menemui seluruh server sibuk
Pada kondisi ini : – E[kq] = E[w] = 0 – E[k] = (l/m)(1-B) • B : blocking Anhar - TES 3114 UR
17
Contoh : Misalkan pada suatu transmisi paket. Diketahui panjang paket terdistribusi eksponensial dengan panjang rata-rata 1200 bit. Paket ditransmisikan pada kecepatan 4800 bps. Paket datang dengan rate 6 paket per detik dan jumlah saluran yang digunakan adalah 4. tentukan : • Jumlah paket yang mengantri. • Waktu rata-rata paket dalam antrian. • Jumlah rata-rata paket dalam sistem. Anhar - TES 3114 UR
18
9
03/12/2012
Penyelesaian Diketahui :
L=1200 bit C=2400 bps λ= 6 paket/detik m=4 buah • Jumlah Paket yg mengantri :
C / L 4800bps / 1200bit 4 paket / det ik A / 6 paket / det ik / 4 paket / det ik 1,5erl / m 6 paket / det ik / 2.4 paket / det ik 6 / 8 Gunakan erlang tabel, cari nilai B utk A=1,3 ; N=4 dan A=1,5;N=3
Anhar - TES 3114 UR
Utk N=4, interpolasi : Utk N=3, interpolasi :
19
1,52 - 1,26 1,52 - 1,5 x 0,051 0,05 - 0,03 0,05 - x 1,93 - 1,27 1,93 - 1,5 x 0,265 0,2 - 0,1 0,2 - x
1 1 1 1 1 15,83 DN ( A) E N ( A) E N -1 ( A) 0,051 0,265 DN ( A) 0,063
1,5 A nq DN ( A). 0,063. 0,0378 N A 4 - 1,5
Anhar - TES 3114 UR
20
10
