Download - Proses Stokastik
2
Penerapan Teori Antrian Telekomunikasi Traffic control Menentukan urutan operasional komputer Memprediksi performance dari komputer Pelayanan kesehatan atau pelayanan umum
lainnya Airport traffic, airline ticket sales
3
Contoh Pada supermarket atau bank
Beberapa counter atau checkout system sistem antrian di mana pelanggan menunggu kasir yang kosong berikutnya
5
Hukum Little (Little’s Law)
Little’s Law: Rata-rata jumlah pekerjaan di dalam sistem (L)=
rata-rata laju kedatangan (λ) x rata-rata waktu respons layanan (W)
Dapat diterapkan untuk sembarang sistem dalam kondisi kesetimbangan (equilibrium)
Arrivals Departures
System
WL )(
6
Proving Little’s Law
J = daerah yg diarsir = 9
Sama di semua kasus!
1 2 3 4 5 6 7 8
Job #
Time
123
1 2 3 4 5 6 7 8
# of Jobs in theSystem
123
Time
1 2 3
Time inSystem
Job #
123
Arrivals
Departures
7
Definisi-definisi J: “Luas” pada slide sebelumnya N: Jumlah pekerjaan T: Total waktu : Rata-rata laju kedatangan
N/T W: Rata-rata waktu pekerjaan di dalam sistem
= J/N L: Rata-rata jumlah pekerjaan di dalam sistem
= J/T
8
Proof: By Definition
1 2 3 4 5 6 7 8
# in System(L) 1
23
Time (T) 1 2 3
Time inSystem(W)
Job # (N)
123=
WL TN )(
NWTLJ
WL )(
9
Model Queuing System
Model antrian (Queuing models) digunakan untuk: Menggambarkan perilaku sistem antrian Mengevaluasi kinerja sistem
Server System Queuing System Queue Server
Queuing System
10
Karakteristik dari sistem antrian Proses kedatangan (Arrival Process)
Sebaran yang menentukan bagaimana pekerjaan datang ke sistem
Proses pelayanan Sebaran yang menentukan waktu memproses
pekerjaan Jumlah server/meja layan
Jumlah server/meja layan yang tersedia untuk memproses pekerjaan
11
Notasi Kendall 1/2/3(/4/5/6) Enam Paremeter
Tiga pertama yang paling sering digunakan1. Sebaran kedatangan (Arrival Distribution)2. Sebaran pelayanan (Service Distribution)3. Jumlah server4. Total kapasitas (diasumsikan tak terbatas jika
tidak didefinisikan)5. Ukuran populasi (diasumsikan tak terbatas jika
tidak didefinisikan) 6. Disiplin antrian (FCFS-First Come First
Served/FIFO-First in First Out)
12
Sebaran-sebaran M: berasal dari istilah "Markovian", yang
berarti sebaran eksponensial untuk waktu antar kedatangan atau waktu layanan.
D: deterministik (konstan) Ek: Erlang dengan parameter k Hk: Hyperexponential dengan parameter k G: General (umum/apapun)
13
Contoh Notasi Kendall M/M/1:
Kedatangan sebagai proses Poisson dan waktu layanan menyebar eksponensial, 1 server, kapasitas tak terbatas, populasi tak terbatas dan FCFS (FIFO)
Antrian paling sederhana yang realistis M/M/m
Kedatangan sebagai proses Poisson dan waktu layanan menyebar eksponensial, m server, kapasitas tak terbatas, populasi tak terbatas dan FCFS (FIFO)
G/G/3/20/1500/SPF Jumlah kedatangan dan waktu layanan mempunyai
sebaran umum, 3 server, kapasitas antrian sejumlah 17 slot (20 – 3), 1500 total pekerjaan (populasi) dan Shortest Packet First (pekerjaan yang tersedikit yang didahulukan)
14
Proses Poisson
Untuk proses Poisson dengan rata – rata kedatangan λ, peluang bahwa akan ada n kedatangan pada selang waktu ∆t
0...1)(Pr
1)(Pr)(...]!2)(1[1)(Pr
10)(Pr)(1...!2)(10)(Pr
)(!
)(Pr
2
2
tX
ttXtotttttetX
ttXtotttetX
ttXEntentX
t
t
nt
15
Proses Poisson dan Sebaran eksponensial
Waktu antar kedatangan (interarrival time) t di dalam proses Poisson mengikuti sebaran eksponensial dengan parameter λ
1)(
0,)(
TE
tetf tT
16
Antrian M/M/1 Diberikan : Laju kedatangan pekerjaan m: Laju selesainya layanan dari server
Ingin ditentukan L: rata-rata jumlah pekerjaan di dalam sistem Lq : rata-rata jumlah pekerjaan yang
menunggu di antrian W: rata-rata waktu tunggu di dalam sistem
Wq : rata-rata waktu tunggu di antrian
18
Menyelesaikan sistem antrian 4 variabel yang ingin dicari solusinya: L, Lq W, Wq
Hubungan yang berlaku: L=W Lq=Wq (steady-state argument) W = Wq + (1/m)
Penentuan L adalah langkah awal. Yang tergantung dari tipe sistem antrian.
0
n
nnL n Peluang equilibrium bahwa sistem mempunyai n pekerjaan di dalam antrian
Nilai harapan
19
Analisis dari antrian M/M/1 Tujuan: Mendapatkan bentuk langsung dari peluang jumlah
pekerjaan pada sistem (πi) sebagai fungsi dari dan m
20
Syarat/kondisi Equilibrium
n+1nn-1
m mm m
Adalah proses kelahiran dan kematian dengan parameter kelahiran dan parameter kematian yang sama di setiap state yang mungkin πi , i=1, 2, … peluang equilibrium dari proses
kelahiran dan kematian
21
Berdasarkan hubungan net flow balance:
,2,1,0 ,11 nnnnn m
nn m 1
01 ,0 m n
0
2
012 ,1 m
m
m
m
n
Dst secara rekursif0
m
n
n
n+1nn-1
m mm m
1 nn m
Dengan batasan sedemikian sehingga fungsi peluang terdefinisi dengan baik
1k
k
1
0 1k
k
π0 ditentukan dari syarat di atas
101k
k
m
11
00
k
k
m 1
00
k
k
m
0
01
k
k
m
23
Penyebut akan menjadi berhingga (deret geometri) jika λ <µ, or ρ<1
00
011
k
k
k
k
m
11
0k
k
Sedemikian:m
111
0
0
k
k
m
m
m 10
nn
n
24
Perhatikan: ,2,1,0,1
n
n
n m
m
Adalah fungsi dari sebaran geometrik dengan peluang sukses:
m1p
Sehingga rata-rata jumlah pekerjaan di dalam sistem L:
0
n
nnL
adalah nilai harapan dari sebaran geometrik.
25
Solusi bagi L
Hasil tsb diterapkan untuk L:
m1:~ ppGeometricX
mm
m
mm
1
111ppXE
m
XE
m-
0
nnnL
m
Intensitas traffic: ukuran performance sistem
L akan berhingga jika λ <µ, or ρ<1, sebaliknya sistem akan “exploded”.
27
Analis model antrian M/M/∞ Jumlah server yang tak hingga Semua pelanggan dalam sistem akan segera
dilayani seketika : Laju kedatangan pekerjaan m: Laju pelayanan setiap server Jika terdapat k kedatangan ke dalam server maka
laju pelayanan akan menjadi km.
mm kkk ,
28
Analis model antrian M/M/∞
Tujuan: Bentuk langsung dari peluang jumlah pekerjaan di dalam sistem (πi) sebagai fungsi dari dan m
29
Syarat Equilibrium
n+1nn-1
nm (n+1)m(n-1)m (n+2)mAdalah proses kelahiran dan kematian πi , i=1, 2, … adalah peluang ekuilbrium Menggunakan hubungan net flow balance:
,2,1,0 ,11 nnnnn m 1)1( nn n m
Dengan batasan:
1k
k
1
0 1k
k
π0 sesuai syarat di atas menjadi:
10 !
11k
k
k m
1!
11
00
k
k
k m 1
!1
00
k
k
k m
0
0
!1
1
k
k
k m
32
Penyebut adalah deret Taylor:
0
0
!1
1
k
k
k m
m
m e
kk
k
0 !1
Sedemikian mm e
e1
0
m
m
m
e
nn
nn
n !1
!1
0
33
Solusi bagi L
Penerapan hasil tsb untuk L:
mPoissonX ~
m
XE
m
0n
nnL
m
Intensitas Traffic:
L akan berhingga jika λ <µ, or ρ<1, sebaliknya sistem akan “exploded.”