Sistem Antrian Umum
Karakteristik Proses Antrian ªPola kedatangan ªPola layanan ªDisiplin antrian ªKapasitas sistem ªJumlah kanal layanan ªJumlah tingkat/stages layanan
Pola Kedatangan •
•
Stochastic – Distribusi probabilitas – Kedatangan tunggal/single atau batch Kelakuan pelanggan – Pelanggan sabar • Menunggu selamanya – Pelanggan tidak sabar • Menunggu utk suatu perioda waktu dan memutuskan utk pergi • Melihat antrian panjang dan memutuskan tdk bergabung • Mengubah barisan utk menunggu
• Apakah time dependent? – Pola kedatangan Stationary (time independent – probability distribution) – Pola kedatangan Nonstationary
Pola Layanan • • • •
Distribusi utk waktu layanan Layanan tunggal/single atau batch (mesin paralel) Proses layanan tergantung jumlah pelanggan menunggu (state dependent) Layanan sangat cepat Æ masih memerlukan antrian? – Tergantung juga pada kedatangan – Mengasumsikan mutually independent
Disiplin Antrian • Cara pelanggan-pelanggan mendapatkan layanan – First come, first serve – Last come, first serve – Random serve – Priority serve • Preemptive • Nonpreemptive
Kapasitas Sistem • •
Kapasitas terbatas – Ukuran sistem maksimum Kapasitas tdk terbatas
Jumlah Kanal Layanan • Sistem antrian multiserver – Single line service – Multiple line service
Tingkat/Stages Layanan • Single stage • Multiple stages – Tanpa feedback (Entrance Exam) – Dg feedback (Manufacturing)
Notasi Antrian •
Notasi Kendall (1953) A/B/X/Y/Z A : Distribusi waktu antar kedatangan B : Distribusi waktu layanan X : # kanal layanan paralel Y : Kapasitas sistem Z : Disiplin antrian
Notasi Antrian A/B/X/Y/Z • M/M/3/∞/FCFS – Waktu antar kedatangan exponential – Waktu layanan exponential – 3 server paralel – Ruang tunggu tdk terbatas – Disiplin antrian First-Come First-Serve • M/D/1 – Waktu antar kedatangan exponential – Waktu layanan Deterministic – 1 server – Ruang tunggu tdk terbatas (default) – Disiplin antrian FCFS (default)
• • • • • • •
M/M/1 M/M/c/k M/M/∞ Ek/M/1 M/G/1 G/M/m G/G/1
Sistem Antrian - Dasar • G/G/m – Waktu antar kedatangan dg distribusi A(t) – Waktu layanan dg distribusi B(x) – m servers • Cn: pelanggan ke-n memasuki sistem
• τn: waktu kedatangan utk Cn • tn: Waktu antar kedatangan (τn – τn-1) • xn: service time utk Cn
• • • •
wn: waktu tunggu dlm antrian utk Cn sn: waktu dlm sistem utk Cn Æ (wn + xn) λ : laju kedatangan rata-rata µ : laju layanan rata-rata
Notasi Diagram Waktu
Sistem Antrian - Dasar • •
• • • • • •
N(t): # pelanggan dlm sistem @waktu t U(t): pekerjaan belum selesai/ unfinished @waktu t – U(t) = 0 Æ Sistem idle – U(t) > 0 Æ Sistem busy α(t): # kedatangan pada (0,t) δ(t): # keberangkatan pada (0,t) λt : laju kedatangan λ t = α(t)/t = # kedatangan/waktu γ(t) : waktu total semua pelanggan dlm sistem (pelanggan-detik) Tt = γ(t)/αt = waktu sistem/pelanggan
Rata-rata # pelanggan dlm sistem
Hasil Little Jumlah rata-rata pelanggan dlm sistem antrian sama dg laju kedatangan pelanggan ke sistem tsb, dikalikan ratarata waktu yg dihabiskan dlm sistem”
• Nq = rata-rata # pelanggan dlm antrian • λ = laju kedatangan • W = rata-rata waktu dihabiskan dlm antrian
• • •
Ns = rata-rata # pelanggan dlm fasilitas layanan λ = laju kedatangan x = rata-rata waktu dihabiskan dlm fasilitas layanan
Sistem Antrian - Dasar
•
ρ = faktor utilisasi – = laju kerja/ laju kapasitas max Utk single server Utk m server
•
Utk G/G/1 stabil : 0 ≤ ρ < 1
Teknik-Teknik Performansi • Tiga teknik dasar utk analisa performansi – Pengukuran/Measurements • Mengumpulkan data eksperimental dari prototype atau sistem eksisting – Simulasi • Eksperimen dg model komputer dari sistem – Analisis Æ Teori Antrian/Queueing Theory • Model analitis dari sistem
Teori Antrian • •
•
Model analitis dari sistem Kelebihan – Cepat – Aplikasi utk semua tingkatan dari sistem – Memungkinkan tradeoffs dan sensitivitas utk dipelajari Kelemahan – Mungkin mencakup aproksimasi – Abstraksi detail – Perlu waktu untuk mengembangkan model
Memilih Teknik Performansi • Tiap metoda punya rentang aplikabilitas • Sebaiknya cross check hasil
Model Network • Bagaimana kita memodelkan? • Jaringan (network) secara umum dimodelkan dlm tiga kategori: – Resource sharing networks – Process networks – Switching networks
Resource Sharing Network (1)
• • • • • •
Time-shared computer (Programs : CPU/Disk/IO) Statistical multiplexer/concentrator Packet-based (Packets : Links) Channel-based (Calls : Channels) Multiple-Access and random access networks (Packets : Shared Medium)
Resource Sharing Network (2) • Ukuran performansi – Waktu tunggu (waiting time) – Probabilitas blocking • Pertanyaan – Bagaimana relasi antara jumlah user, pola penggunaan, jumlah sumberdaya (resources), dan performansi? – Apakah resources diduduki secara adil (atau tepat) oleh user?
Proces Network (1)
• Multi-stage switch • Distributed simulation system • Manufacturing process
Proces Network (2) • Ukuran performansi – Waktu penyelesaian (delay) – Throughput (penyelesaain per unit waktu) • Pertanyaan – Bagaimana performansi dipengaruhi oleh pola penggunaan yg berbeda? – Proses mana yang “bottlenecks” yang membatasi performansi? – Apakah input-input berbeda diperlakukan secara adil dlm kaitannya dg performansi?
