MODEL SISTEM ANTRIAN

BAB V

MODEL SISTEM ANTRIAN Pada teori antrian, suatu model antrian digunakan untuk memperkirakan suatu situasi antrian sesungguhnya , sehingga kelakuan antrian dapat dianalisa secara matematik. Dengan model sistem antrian maka akan dimungkinkan untuk menentukan ukuran performansi pada kondisi steady, antara lain termasuk:     

Jumlah rata-rata pelanggan yang berada dalam antrian atau sistem, Waktu rata-rata dalam antrian atau sistem, Distribusi statistik dari jumlah pelanggan dan waktu dalam antrian, Probabilitas antrian penuh atau kosong, dan Probabilitas mendapatkan sistem dalam suatu kondisi tertentu.

Ukuran-ukuran performansi tersebut sangat penting sebagai isu atau problem yang disebabkan oleh situasi antrian yang biasanya terkait dengan masalah kepuasan pelanggan terhadap layanan. Analisa terhadap model antrian yang tepat akan memungkinkan penyebab antrian dapat diidentifikasi dan akibat-akibatnya dapat diminimisasi. Secara umum, model-model antrian sendiri dapat direpresentasikan dengan menggunakan notasi Kendall sebagai berikut : A/B/S/K/N/Dis Dimana :      

A adalah distribusi waktu antar kedatangan B adalah distribusi waktu layanan S adalah jumlah dari sever K adalah kapasitas sistem N adalah populasi pendudukan ( yang sedang melakukan pendudukan ) Dis adalah asumsi dari disiplin layanan

Umumnya, 3 parameter terakhir diabaikan, sehingga notasi hanya terdiri dari A/B/S dan diasumsikan bahwa K = infinitely (= ∾), N = infinitely, dan Dis = FIFO. Notasi standar yang sering digunakan untuk distribusi (A atau B) adalah: UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 1



M untuk suatu distribusi Markovian (exponential)



Eκ untuk suatu distribusi Erlang dengan fase κ D untuk distribusi (konstan) Degenerate (atau Deterministic) G untuk distribusi General (arbitrary) PH untuk suatu distribusi Phase-type

  

Sebagai contoh, "G/D/1" akan mengindikasikan suatu proses kedatangan General (bisa apa pun), suatu proses layanan Deterministic (constant time) dan suatu server tunggal (single). Pada sistem switching, implementasi sistem antrian memungkinkan pelanggan-pelanggan yang belum terlayani untuk antri sampai tersedianya sarana (resources) untuk proses pelayanan. Ini berarti bahwa jika level intensitas trafik melebihi kapasitas yang tersedia, maka panggilan dari pelanggan yang tidak dapat dilayani tidak harus langsung hilang; tapi dibuat menunggu sampai dapat dilayani. Model sistem antrian dapat diilustrasikan secara sederhana pada gambar 5.1. Disiplin suatu antrian ditentukan oleh cara sistem switching menangani panggilan. Secara umum ada empat disiplin antrian yang dikenal, yaitu: First in first out Prinsip disiplin ini, hanya satu pelanggan yang dapat dilayani pada suatu waktu tertentu dan pelanggan yang sudah menunggu paling lama yang akan dilayani lebih dulu. Last in first out Pada disiplin ini hanya satu pelanggan juga yang dapat dilayani pada suatu waktu tertentu, tapi pelanggan dengan waktu menunggu paling pendek yang akan dilayani lebih dulu.

A Erlang

antrian N server

(trafik yang ditawarkan)

Gambar 5.1 Model sistem antrian. UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 2

Processor sharing Pelanggan-pelanggan akan dilayani secara sama. Kapasitas jaringan dibagi (shared) diantara para pelanggan dan para pelanggan secara efektif akan mengalami delay yang sama. Priority Pelanggan dengan prioritas tinggi akan dilayani lebih dulu. Proses antrian ditangani oleh sistem prosesor perangkat switching dan dapat dimodelkan dengan menggunakan persamaan kondisi. Sistem antrian biasanya menggunakan suatu bentuk persamaan kondisi tertentu yang dikenal sebagai Markov chain yang menjadi model sistem pada setiap kondisi. Trafik yang datang ke sistem di-model-kan dengan suatu distribusi Poisson dan menjadi subyek dari asumsi sistem antrian Erlang, yaitu : 1. 2. 3. 4.

Pure-chance traffic – Kelahiran dan kematian panggilan bersifat random dan kejadian-kejadiannya bersifat independent. Statistical equilibrium – Probabilitas dalam sistem tidak berubah. Full availability – Semua trafik yang datang dapat di-routing-kan ke semua pelanggan lainnya dalam jaringan. Congestion di clear kan segera setelah server-server bebas.

Asumsi (1) sampai (3) merupakan faktor umum pada sistem rugi. Dalam hal ini, asumsi (2) mengimplikasikan bahwa A ≤ N ( A, trafik yang ditawarkan, dan N, kapasitas server sistem switching). Jika A ≥ N, maka panggilanpanggilan akan masuk ke sistem dengan rate yang jauh lebih besar dibanding keluarnya. Sebagai hasilnya, panjang antrian secara kontinyu akan bertambah ke arah tidak terhingga (infinity). Ini berarti tidak terjadi keseimbangan statistik (statistical equilibrium). Jika k merupakan jumlah total panggilan dalam sistem, maka jika k < N panggilan-panggilan akan dapat dilayani semuanya dan tidak terjadi delay. Apabila k > N, jika semua server sibuk maka panggilan-panggilan yang datang pada saat itu akan mengalami delay. Jadi akan ada N panggilan yang dilayani dan k – N panggilan dalam antrian. Jika k ≤ N Tidak ada antrian dan perilaku sistem sama dengan sistem rugi tanpa congestion. Dimana UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 3

P(k) =

Ak P(0) k!

untuk 0 ≤ k ≤ N

............... (5-1)

Jika k ≥ N Probabilitas dari suatu panggilan datang pada suatu periode waktu yang sangat pendek, δt, dari persamaan terdahulu di bab 2, yaitu probabilitas suatu panggilan datang yang dinyatakan dengan P(a) = A δt / h dimana h adalah waktu pendudukan rata-rata. Maka, probabilitas suatu transisi dari panggilan k – 1 ke k pada sistem selama δt, dapat dinyatakan dengan P(k-1 → k) = P(k-1) A δt / h Karena semua server sibuk, hanya N panggilan yang sedang dilayani yang akan diterminasi, sehingga probabilitas panggilan berakhir (ending) dapat dinyatakan dengan P(e) = N δt / h dan probabilitas suatu transisi dari k ke k-1 adalah P(k → k-1) = P(k) P(e) = P(k) N δt / h Untuk keseimbangan statistik, P(k-1 → k) = P(k → k-1) , jadi P(k) N δt / h = P(k-1) A δt / h dan P(k) =

A P(k  1) N

.............. (5-2)

Tetapi karena P(N) =

AN P (0) N!

(persamaan (5-1))

maka

UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 4

P(N+1) =

A A N 1 P( N )  P(0) N N .N !

P(N+2) =

A A N 2 P ( N )  2 P (0 ) N N .N !

dan seterusnya ...... Maka, secara umum untuk k ≥ N : k

Ak

NN  A P(k )  k  N P ( 0)    P ( 0) N .N ! N!  N 

............... (5-3)

Jika tidak ada batasan untuk panjang antrian, maka k dapat mempunyai nilai antara 0 sampai ∾ (infinity). Jadi 

 P(k )  1 k 0

Selanjutnya, dari persamaan (5-1) dan (5-3) : N 1 1 Ak N N  A      P (0 ) k  0 k ! N!  N 

N 

 A    m0  N 

m

................ (5-4)

dimana m = k-N . Karena A/N ≤ 1, maka 

m

 A  A    1     N m0  N  N 1 1 Ak A N   P (0) k 0 k! N !

1

 A 1  N   

1

Sehingga didapat N 1  N .A N Ak  P(0)      N !( N  A) k 0 k! 

1

............... (5-5)

Dalam hal ini, persamaan (5-1) dan (5-3) tergantung pada apakah k ≤ N atau k ≥ N, dimana P(0) adalah berdasarkan persamaan (5-5). Ini dikenal sebagai Distribusi Erlang Kedua (Second Erlang Distribution).

UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 5

Probabilitas Delay Delay terjadi jika semua server sibuk, misal k > N. Berdasarkan pesamaan (5-3), probabilitas bahwa setidaknya ada x panggilan dalam sistem (dimana x > N) dinyatakan dengan : 

P (k  x )   P ( k ) k x

 NN  A  P (0)    N! k x  N 



NN  A P (0)  N! N

k

x 

 A    kx  N 

k

dimana x = k – N. Sehingga : x

NN  A  A P(k  x)    P (0) 1   N!  N   N



NN N!

1

x

N  A P (0)   N NA

............... (5-6)

Probabilitas delay adalah PD = P(k > N). Jadi PD 

AN N P (0 ) N! N  A

.............. (5-7)

 E 2, N ( A)

Yang menyatakan probabilitas delay untuk sistem dengan kapasitas N server dan penawaran trafik A Erlang, dimana P(0) berasal dari persamaan (5-5). Formula ini, untuk E2,N (A), dikenal sebagai Rumus Tunggu Erlang (Erlang Delay Formula). Jika diperhatikan kembali persamaan (4-16) untuk n = N, dapat ditulis

EN (A) = E1,N

AN (A) = NN ! i A  i  0 i!

UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

............... (5-8)

Halaman 6

Dari persamaan (5-5), (5-7) dan (5-8), dengan beberapa langkah matematis akan didapatkan hubungan antara E1,N (A) dan E2,N (A) sebagai berikut : E1, N ( A)

E2, N ( A)  1

............... (5-9)

A (1  E1, N ( A)) N

Dengan memperhatikan persamaan (4-22), dimana E1,N (A) = A-Y/A atau E1,N (A) =

R A

.............. (5-10)

Dimana R merupakan selisih antara trafik yang ditawarkan dengan trafik yang dapat diolah oleh sistem = merupakan trafik yang hilang atau tidak dapat dimuat/diolah oleh sistem. Substitusi persamaan (5-10) ke persamaan (5-9) akan menghasilkan persamaan praktis : PD  E2, N ( A) 

R.N A( N  A  R)

.............. (5-11)

Kapasitas Antrian Terbatas Secara praktis, sistem tidak dapat diimplementasikan dengan jumlah antrian tak terbatas (infinity). Karenanya, bila antrian sudah penuh , panggilan yang datang berikutnya akan dihilangkan. Jika antrian dibatasi hanya sampai Q panggilan, maka k < Q + N , sehingga dari penurunan persamaan (5-4) didapat N 1 1 Ak N N  A      P (0 ) k  0 k ! N!  N 

N Q

 A    m 0  N 

m

, jadi :

 

Q 1

A N 1 1 Ak A N 1  N   P (0) k 0 k! N ! 1  A N

............... (5-12)

Dalam hal ini, jika probabilitas ruginya kecil, maka kesalahan pada penggunaan persamaan (5-5) dapat diabaikan. Probabilitas ruginya sendiri dapat diestimasi

UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 7

dengan terlebih dahulu mengasumsikan bahwa kapasitas antrian adalah tak terbatas dan dilakukan perhitungan P(k > Q+N), hasilnya : P(k  Q  N ) 

NN N!

 A   N

Q N

N P (0) NA

Q

 A    PD N

............... (5-13)

Beberapa Persamaan Praktis Lain : Persamaan (5-3) sampai dengan (5-7) akan menjadi dasar pada persamaan-persamaan berikut : 1. Jumlah panggilan rata-rata dalam sistem : (i) Ketika terjadi delay (harus menunggu), jumlah panggilan rata-rata adalah k' 

(ii)

A N NA

.............. (5-14)

Rata-rata terhadap seluruh waktu, jumlah panggilan rata-rata adalah A E 2, N ( A)  N NA A k PD  N NA k

atau .............. (5-15)

2. Panjang antrian rata-rata: (i) Ketika terjadi delay, panjang antrian rata-rata adalah q'  k '  N 

(ii)

A NA

.............. (5-16)

Panjang antrian rata-rata terhadap seluruh waktu q  q'.PD  q

A E 2, N ( A) NA

atau

A PD NA

.............. (5-17)

3. Waktu tunggu rata-rata (mean delay time) ketika disiplin antriannya “first in first out” (FIFO) : UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 8

(i)

Ketika terjadi delay, waktu tunggu rata-ratanya adalah T' 

(ii)

h NA

.............. (5-18)

dimana h adalah waktu pendudukan rata-rata. Waktu tunggu rata-rata terhadap seluruh waktu T  E 2, N ( A).T '  PD .T ' atau T  PD .

h NA

.............. (5-19)

4. Probabilitas menunggu pada antrian dengan disiplin FIFO : Karena waktu pendudukan mempunyai suatu distribusi probabilitas dengan eksponensial negatif, maka untuk waktu tunggu TD : (i) Ketika terjadi delay, probabilitas menunggu lebih lama dari waktu t adalah : .............. (5-20) P (TD  t )  e t / T ' (ii) Probabilitas terhadap seluruh waktu P(TD  t )  E2, N ( A).e  t / T ' atau  PD .e t / T '

.............. (5-21)

Formula untuk k ', q ', dan T ' diperlukan karena ketika E2,N(A) kecil, delay (waktu tunggu) yang terjadi biasanya jauh lebih besar dari T ' . Formula-formula ini juga digunakan sebagai dasar untuk situasi antrian yang lebih komplek, misal, untuk waktu pendudukan yang konstan (bukan merupakan distribusi eksponensial negatif), layanan random (tidak termasuk disiplin antrian FIFO) dan antrian dengan prioritas. Antrian Dengan Prioritas : Sejauh ini telah dibahas model antrian pada sistem klasik, dimana semua proses trafik mengikuti proses kelahiran dan kematian (birth and death process). Pada sistem-sistem dengan tipe trafik yang berbeda, maka perlu diaplikasikan prioritas diantara kelas-kelas yang berbeda. Sebagai contoh kasus, dapat diamati antrian M/G/1 (notasi Kendall) dengan tipe trafik r ( contoh, tipe-tipe pelanggan). Tipe pelanggan i datang dengan model kedatangan (stream) Poisson dengan rate kedatangan λi , i = 1,2, UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 9

..., r. Waktu layanan rata-rata dinyatakan dengan Si . Trafik yang ditawarkan dari stream i adalah Ai = λi Si . Pelanggan tipe 1 mempunyai prioritas paling tinggi, pelanggan tipe 2 mempunyai prioritas kedua, dan seterusnya. Dalam hal ini, secara basis ada 2 tipe prioritas : 1. Prioritas Nonpreemptive : layanan yang sedang berjalan untuk pelanggan yang prioritasnya lebih rendah tidak diinterupsi oleh pelangganpelanggan yang prioritasnya lebih tinggi, tetapi mereka harus menunggu sampai layanan untuk pelanggan-pelanggan dengan prioritas lebih rendah tersebut selesai diproses. 2. Prioritas Preemtive-resume : layanan yang sedang berjalan akan diinterupsi oleh kedatangan pelanggan dengan prioritas lebih tinggi. Kemudian baru layanan dari pelanggan dengan prioritas lebih rendah dilanjutkan mulai dari titik saat dimana terjadinya interupsi.

(i). Prioritas Nonpreemtive Jika dinotasikan Wi dan Li masing-masing sebagai waktu rata-rata dalam antrian pelanggan tipe i dan jumlah pelanggan tipe i yang menunggu dalam antrian, dimana i = 1,2, ...., r. Semua pelanggan dibagi dalam kelas-kelas prioritas r. Waktu layanan dan waktu residual (sisa) untuk pelanggan tipe i masing-masing dinyatakan dengan Si dan Ri . Maka waktu tunggu untuk pelanggan-pelanggan (misal tipe 1) dengan prioritas paling tinggi dapat dinyatakan dengan r

Wi = L 1q S1 +

A R j

j

............ (5-22)

j 1

Suatu relasi yang sangat penting antara jumlah rata-rata pelanggan dalam sistem L, waktu tunda (tinggal) rata-rata T, dan jumlah rata-rata pelanggan memasuki (datang) ke sistem λ, dapat dinyatakan dengan hukum Little sebagai L = λ T. Dengan mengaplikasikan hukum Little ke suatu antrian (tanpa server) akan memberikan hubungan sebagai berikut L 1q = λ Wi

UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

............ (5-23)

Halaman 10

Dengan mengkombinasikan kedua persamaan terakhir, akan didapat waktu tunggu rata-rata untuk kelas prioritas paling tinggi : r

A R j

Wi =

j

j 1

............ (5-24)

1  A1

Penentuan dari waktu tunggu minimum dari pelanggan-pelanggan dengan prioritas lebih rendah lebih sulit. Biasanya dilakukan dengan cara membagi waktu tunggu ini dalam porsi-porsi seperti diperlihatkan pada gambar 5.2. Porsi pertama s1 adalah jumlah “work” yang terkait dengan pelanggan yang dalam layanan dan semua pelanggan-pelanggan lain baik dengan prioritas sama atau lebih tinggi yang datang pada antrian. Porsi kedua s2 adalah jumlah dari work dengan prioritas yang lebih tinggi yang datang selama s1. Porsi ketiga s3 adalah jumlah dari work dengan prioritas yang lebih tinggi yang datang selama s2, dan seterusnya, sehingga waktu tunggunya adalah 

Wi = E(s1 + s2 + s3 + ......) =

s

............ (5-25)

k

k 1

Karena setiap kelas j mempunyai trafik yang ditawarkan sebesar Aj, akan lebih mudah ditunjukkan bahwa untuk pelanggan-pelanggan tipe i, hubungan antar porsi waktu yang berurutannya dapat dinyatakan sebagai : Work (waktu)

S1

S2

S3 waktu

Kedatangan dari pelanggan-pelanggan tipe 1

Gambar 5.2. Waktu tunggu dari pelanggan tipe 2. UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

Halaman 11

E(sk+1 ) = (A1 + A2 + ......+ Ai-1 ) E(sk )

........... (5-26)

Menggunakan persamaan (5-26) untuk setiap trafik tipe i, akan didapat progresi geometrik dari porsi-porsi waktu sebagai berikut : E(sk+1 ) = (A1 + A2 + ......+ Ai-1 )k E(s1 ) , k=0,1,2, .....

........... (5-27)

Dari persamaan (5-25) dan (5-27), maka dapat diperoleh waktu tunggu rata-rata dari tipe trafik i : i

r q j

L S  A R j

j

j

E ( s1 ) j 1 j 1 Wi =  1  ( A1  A2  .....  Ai 1 1  ( A1  A2  ....  Ai 1 )

........... (5-28)

Menggunakan persamaan (5-24) dan (5-28) di atas, secara langsung dapat ditunjukkan bahwa r

A R j

Wi =

j

j 1

1  ( A1  A2  ....  Ai 1  ( A1  A2  .....  Ai 1 )

dengan i = 1,2,..., r ............ (5-29)

Sehinggga didapat waktu tunda untuk tipe trafik i adalah Ti = Wi + S1

........... (5-30)

(ii). Prioritas Preemtive Delay layanan untuk prioritas preemtive mengikuti analisa untuk prioritas non-preemtive. Waktu tunggu Wi dari tipe trafik i dikalkulasi menggunakan persamaan (5-29) seperti untuk non-preemtive , dimana untuk hal ini jumlah total work pada sistem tidak tergantung kepada permintaan dimana pelanggan-pelanggan dilayani, tetapi yang berbeda adalah waktu tundanya (sojourn time), sehingga dengan bereferensi persamaan (5-28) akan didapat Ti = Wi +

Si 1  ( A1  A2  ......  Ai 1 )

, i = 1,2,...., r

UNJANI/REKAYASA TRAFIK TELEKOMUNIKASI/BAB V

............. (5-31)

Halaman 12