Queuing Models • Deskripsi matematis dari sistem antrian: – The arrival process of customers – The behaviour of customers – The service times – The service discipline – The service capacity – The waiting room
Sistem Antrian
Kuliah Analisis Jaringan Komputer KOM511 Julio Adisantoso, ILKOM-IPB
Slide 3
Sumber
Deskripsi
• Ghanbari, et.al. Principles of Performance Engineering
Arrival process
for Telecommunication and Information Systems. Ch. 4.
• Model queue digunakan untuk menduga perilaku sistem
• Adan & Resing. Queueing Theory.
di waktu berikutnya, 0 ≤ t ≤ ∞
• Antar waktu kedatangan (interarrival times)
diasumsikan sebagai sembarang p.a yang saling bebas. Apa artinya?
• Pada beberapa situasi, kedatangan mengikuti sebaran Poisson (exponential interarrival times).
• Customers bisa datang satu per satu, atau dalam bentuk batch.
Slide 1
Service Systems
Slide 4
Deskripsi
• Konsep antrian sudah sangat umum. Contoh: antrian
Behaviour of customers
layanan di bank, kantor pos, stasiun kereta api, dsb.
• Customer bersedia menunggu untuk jangka waktu lama
• Contoh lain: pengiriman paket data pada jaringan
atau tidak sabar dan meninggalkan antrian jika menunggu terlalu lama.
komputer, dimana paket masuk ke switch dan antri menunggu di dalam buffer sampai tersedia jalur kosong untuk dihantarkan.
Service times
• Struktur queue:
• Biasanya diasumsikan bahwa waktu layanan mengikuti sebaran saling bebas dan identik.
potential customers queue server
Slide 2
Slide 5
1
Deskripsi
Single channel, multiserver
Service discipline
• first come first served (FCFS) or first in first out (FIFO) • last come first served (LCFS) or last in first out (LIFO) • random order; •p priorities • processor sharing. Service capasity
• Single server or multiple servers Waiting room
• Ada batasan banyaknya customers dalam sistem Slide 6
Kendall’s notation
Slide 9
Multichannel, single server
• Bentuk notasi: A/B/C/m1/m2/Z A: arrival process, B: service process, C: number of servers, m1: maximum capasity of queue(s), m2: populations of users, Z: service dicipline.
• Catatan: – Notasi sebaran, G: general, GI: general independent, M: exponential, D: deterministic (constant). – Jika tiga notasi terakhir tidak dicantumkan, berarti m1=m2=∞ dan disiplin antrian adalah FIFO.
Slide 7
Single channel, single server
Slide 10
Multichannel, multiserver
Slide 8
Slide 11
2
Occupation rate
Little's law
• Pada G/G/1 dengan laju kedatangan λ dan rata2 waktu
• Ada hubungan antara E(L), E(S), dan λ
layanan sebesar E(B), maka banyaknya pekerjaan per satuan waktu adalah λE(B).
E(L) = λ E(S) Artinya, kapasitas sistem mencukupi, atau banyaknya costumers dalam sistem tidak tumbuh tak terbatas.
• Laju kedatangan = rata2 antar waktu kedatangan
λ= 1
T
dimana Tj = (tj – tj-1)
• Server menangani satu pekerjaan per unit waktu. • Occupation rate atau server utilization adalah: ρ = λE(B) < 1 Slide 12
Performance measures
Slide 15
M/M/1 Queue
Relevant performance measures in the analysis of queueing models are:
• Antar waktu kedatangan : eksponensial Æ rata2 = 1/λ • Waktu layanan : eksponensial Æ rata2 = 1/µ
• The distribution of the waiting time and the sojourn time
• Single server
(waktu singgah) of a customer. The sojourn time is the waiting time plus the service time.
• Flow diagram:
• The distribution of the number of customers in the system (including or excluding the one or those in service).
• The distribution of the amount of work in the system.
That is the sum of service times of the waiting customers and the residual service time of the customer in service.
• The distribution of the busy period of the server. This is a period of time during which the server is working continuously.
Slide 13
Performance measures
Slide 16
Limiting or equilibrium behavior
• Misal : sistem G/G/c
• Limiting or equilibrium probabilities pn:
• L(t) adalah banyaknya customers dalam sistem pada
0 = -λp0 + µp1
waktu t.
0 = λpn-1 – (λ+µ)pn + µpn+1, n=1,2,3, …
• Sn adalah waktu singgah customer ke-n di dalam sistem.
• Diperoleh:
• Occupation p rate p per server < 1,, t → ∞,, n → ∞
pn = (1-ρ)ρ (1 ) n, dimana di ρ=λ/µ λ/
• Beberapa ukuran:
pn = ρnp0
Slide 14
Slide 17
3
Mean performance measures
Busy period
• Rata2 banyaknya costumers dalam sistem:
• Siklus dari server : periode sibuk (busy period=BP) pada saat server melayani, diikuti dengan periode menganggur (idle period = IP) pada saat server tidak melayani.
• Rata2 waktu yang dibutuhkan oleh costumer dalam sistem:
• Maka: • Banyaknya costumers dalam antrian (queue):
• Fungsi peluang BP: • Rata2 waktu tunggu
Slide 18
Distribution of the sojourn time • Diketahui
Slide 21
M/M/1 on the www
La
adalah banyaknya costumers dalam sistem sebelum costumer a datang.
http://www.win.tue.nl/cow/Q2
• Diketahui Bk adalah waktu layanan untuk costumer ke-k • Maka:
Slide 19
Distribution of the the waiting time
Slide 22
Exersice
Slide 20
Slide 23
4
Exercise
Slide 24
5
