Proses Stokastik

Semester Ganjil 2013

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

4

Ilustrasi penerapan Teori Antrian

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

17

Antrian M/M/1

m

m1

Wq

W

LLq

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”.

26

Solusi bagi W, Wq dan Lq

mm

11LW

)(111

mm

mmm WWq

)()(2

mm

mm qq WL

WL )(

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

30

nn n

m11

01 ,0 m n 0

2

012 !21

22 ,1

m

m

m

m

n

Dst secara rekursif:0!

1 m

n

n n

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.”

34

Solusi bagi W, Wq and Lq

mm

11 LW

0111 mmmWWq

00 qq WL

WL )(