Resume : Computationally Efficient Simulation of Queues: The R Package queuecomputer
Kelompok 8 : Mutiara Putri S, Nur Aini Rahayu, Naura Aiswarya W, Jesica Permata P
2025-06-21
1. Pengantar
Antrian atau queueing systems merupakan fenomena umum yang kita temui dalam kehidupan sehari-hari, mulai dari antrean di kasir hingga sistem pelayanan digital seperti pemrosesan data dalam cloud computing. Dalam konteks teori antrian, istilah “customer” tidak selalu merujuk pada pelanggan literal, melainkan bisa berupa proses yang menunggu pelayanan, seperti: tugas komputasi (MapReduce jobs), pasien di rumah sakit, panggilan di call center, bahkan penumpang di bandara.
Demikian pula, istilah “server” mengacu pada entitas yang memberikan pelayanan kepada customer, yang bisa berupa manusia (seperti staf medis), perangkat (seperti mesin produksi), maupun sistem komputasi (seperti prosesor).
Model antrian digunakan secara luas untuk memodelkan sistem nyata seperti rumah sakit, call center, pelabuhan, dan bandara. Untuk memahami dan mengevaluasi performa dari sistem ini, pendekatan berbasis simulasi menjadi penting karena solusi analitik sering kali tidak tersedia—terutama dalam sistem antrian kompleks atau dinamis.
Simulasi antrian biasanya dilakukan dengan pendekatan Discrete Event Simulation (DES), yaitu metode simulasi di mana perubahan status sistem terjadi pada waktu diskrit yang ditentukan oleh suatu rangkaian kejadian (event list). Beberapa software yang populer dalam mendukung DES antara lain:
simmerdi R,simpydi Python, danJMTdi Java.
Namun, kelemahan dari pendekatan DES konvensional adalah keterbatasannya dalam hal efisiensi komputasi, khususnya saat berhadapan dengan data besar atau simulasi kompleks. Untuk mengatasi hal ini, Ebert et al. (2017) mengembangkan algoritma bernama Queue Departure Computation (QDC) dan mengimplementasikannya dalam bentuk paket R bernama queuecomputer.
Paket queuecomputer dirancang untuk secara efisien dan deterministik menghitung waktu keberangkatan (departure times) dari sebuah sistem antrian, berdasarkan input waktu kedatangan (arrival times) dan waktu pelayanan (service times). Algoritma QDC mampu memberikan peningkatan kecepatan simulasi hingga 1000x lebih cepat dibandingkan metode konvensional seperti simmer, tanpa kehilangan akurasi hasil.
Selain efisien, queuecomputer juga bersifat modular, terintegrasi dengan baik dalam ekosistem tidyverse (seperti dplyr), dan mendukung topologi antrian kompleks seperti tandem, paralel, dan fork/join. Keunggulan lainnya adalah pemisahan antara proses pengambilan sampel distribusi (sampling) dan proses komputasi antrian, memungkinkan fleksibilitas tinggi dalam jenis data dan distribusi.
Tujuan dari review ini adalah menjelaskan landasan teori dari sistem antrian yang digunakan dalam queuecomputer, sekaligus menelaah efisiensi algoritma QDC yang menjadi inti dari paket tersebut.
2. Teori Antrian
2.1. Definisi Sistem Antrian
Teori antrian adalah cabang dari riset operasi yang fokus pada analisis sistem di mana entitas (disebut customers) menunggu untuk dilayani oleh satu atau lebih servers. Studi awal dalam teori ini dimulai oleh Agner Krarup Erlang pada tahun 1909 dalam konteks sistem telepon Denmark.
Sistem antrian dapat direpresentasikan sebagai berikut:
Setiap pelanggan ke-i memiliki waktu kedatangan \(a_i\) dan waktu pelayanan \(s_i\).
Jika tidak ada server yang tersedia saat pelanggan datang, maka pelanggan harus menunggu dalam antrean.
Ketika server tersedia, pelanggan akan dilayani sesuai aturan disiplin layanan tertentu, seperti First Come First Serve (FCFS).
2.2. Notasi Kendall dan Karakteristik Antrian
Sistem antrian secara formal dijelaskan menggunakan notasi Kendall dalam bentuk:
\[ A/S/K/C/N/R \]
di mana:
A = Distribusi antar kedatangan (inter-arrival time)
S = Distribusi waktu pelayanan (service time)
K = Jumlah server
C = Kapasitas maksimum sistem
N = Ukuran populasi pelanggan
R = Disiplin layanan (misal FCFS)
Notasi distribusi:
M: Markovian (eksponensial)
G: General (umum)
GI: General Independent (umum dan independen)
Contoh:
M/M/1: sistem dengan kedatangan dan pelayanan eksponensial, serta satu server, kapasitas tak terbatas, dan FCFS.M/M/K: sistem dengan K server paralel.
2.3. Ukuran Kinerja Sistem Antrian
Beberapa metrik kinerja utama dalam sistem antrian:
\(N(t)\): Jumlah pelanggan dalam sistem pada waktu t
\(\bar{B}\): Rata-rata jumlah server yang sibuk
\(\rho\): Utilisasi (tingkat pemakaian server) = \(\lambda / (K \mu)\)
\(\bar{w}\): Rata-rata waktu tunggu pelanggan
Dalam sistem antrian M/M/K, metrik-metrik ini bisa dihitung secara analitik. Sebagai contoh:
\[ P(0) = \left[ \sum_{i=0}^{K-1} \frac{(K \rho)^i}{i!} + \frac{(K \rho)^K}{K!(1 - \rho)} \right]^{-1} \]
\[ E(w) = \frac{(K\rho)^K P(0)}{K! \cdot K\mu(1 - \rho)^2} \]
Namun, perhitungan ini hanya valid dalam kondisi steady state dan distribusi eksponensial. Ketika sistem bersifat kompleks atau dinamis (misalnya arrival rate berubah sepanjang hari), pendekatan ini menjadi tidak relevan.
2.4. Antrian Jaringan (Queueing Networks)
Dalam praktiknya, banyak sistem nyata berbentuk jaringan antrian (queueing networks), yang bisa diklasifikasikan sebagai:
Tandem: pelanggan melalui beberapa antrian secara berurutan.
Paralel: pelanggan dibagi ke beberapa antrian secara bersamaan.
Fork/Join: pelanggan dipecah menjadi sub-tugas yang ditangani paralel, kemudian digabung kembali.
Salah satu model awal untuk jaringan antrian adalah Jackson network, yang memodelkan aliran pelanggan antar antrian dengan probabilitas transisi tertentu.
2.5. Antrian Dinamis
Sebagian besar sistem antrian nyata tidak stasioner. Misalnya, antrean di rumah sakit, bandara, atau call center mengalami perubahan intensitas kedatangan sepanjang waktu. Sistem seperti ini disebut dynamic queueing systems, yang memerlukan pendekatan simulasi karena solusi analitiknya jarang tersedia.
Untuk menangani dinamika ini, queuecomputer memungkinkan kita menggunakan arrival time \(a_i\) dan service time \(s_i\) yang telah ditentukan, serta jumlah server yang berubah dari waktu ke waktu. Fitur ini sangat membantu dalam memodelkan skenario realistis seperti imigrasi bandara atau shift kerja di rumah sakit.
3. Perhitungan Keberangkatan Antrian
3.1 Jumlah Server Tetap
Algoritma Queue Departure Computation (QDC) merupakan perluasan multi-server dari algoritma Lindley (1952) untuk sistem antrian satu server. Dalam sistem satu server, waktu keberangkatan pelanggan ke-\(i\) adalah:
\[ d_i = \max(a_i, d_{i-1}) + s_i \]
Namun, algoritma ini tidak segera diperluas ke sistem multi-server hingga Krivulin (1994), dengan kompleksitas komputasi yang buruk yaitu \(\mathcal{O}(n^2)\). Kemudian, Kin dan Chan (2010) mengadaptasinya menjadi algoritma dengan kompleksitas \(\mathcal{O}(nK)\) untuk sistem tandem multi-server dengan blocking.
Dalam pendekatan QDC, pelanggan memilih server yang tersedia paling awal dari vektor waktu:
\[ b = (b_1, b_2, \ldots, b_K) \]
Pada setiap iterasi, hanya diperlukan pencarian elemen minimum dari \(b\), sehingga algoritma ini efisien dari sisi komputasi dan memori.
QDC dapat digunakan untuk mensimulasikan sistem antrian umum berbentuk:
\[ G(t)/G(t)/K/n/\text{FCFS} \]
di mana distribusi kedatangan dan pelayanan dapat bersifat umum, serta proses pengambilan sampel statistik dipisahkan dari perhitungan antrian.
3.2 Mengubah Jumlah Server
Dalam praktik, jumlah server sering kali berubah seiring waktu, misalnya penambahan server saat jam sibuk. Kondisi ini dimodelkan dalam bentuk:
\[ G(t)/G(t)/K(t)/n/\text{FCFS} \]
Vektor simpul waktu \(x = (x_1, x_2, \ldots, x_L)\) membagi waktu ke dalam beberapa epoch, dan jumlah server aktif di setiap epoch disimpan dalam vektor \(y = (y_1, y_2, \ldots, y_{L+1})\).
Diasumsikan bahwa waktu pelayanan \(s_i\) tidak melintasi dua epoch yang berbeda (dikenal sebagai ) agar perubahan status server hanya perlu ditinjau satu kali.
Status server (terbuka atau tertutup) dicatat dalam vektor \(b\). Walaupun pengguna tidak dapat menentukan server spesifik mana yang digunakan, algoritma ini tetap efisien untuk sistem nyata dengan sedikit perubahan jumlah server.
3.3 Diskusi
Jika tidak terpenuhi, atau jika pengguna ingin secara eksplisit menentukan kapan setiap server terbuka, maka digunakan algoritma .
Setiap server \(k\) memiliki simpul waktu \(x_k\) dan status buka/tutup \(y_k\) sendiri-sendiri. Algoritma ini memungkinkan kontrol penuh atas ketersediaan server, tetapi tidak seefisien algoritma sebelumnya secara komputasi.
Fungsi digunakan untuk menentukan kapan server akan tersedia kembali. Algoritma ini dapat diakses melalui fungsi dengan menyuplai objek ke argumen .
Algoritma QDC dapat mensimulasikan sistem antrian bentuk umum:
\[ G(t)/G(t)/K(t)/n/\text{FCFS} \]
dengan efisiensi tinggi. Tidak seperti pendekatan Kin dan Chan (2010), vektor status \(b\) dalam QDC ditulis ulang (overwrite) setiap iterasi, sehingga penggunaan memori hanya sebesar \(\mathcal{O}(n)\), bukan \(\mathcal{O}(nK)\).
4. Penggunaan
Tujuan dari paket queuecomputer adalah untuk menghitung secara deterministik output dari suatu sistem antrian, dengan asumsi bahwa waktu kedatangan (arrival times) dan waktu pelayanan (service times) untuk seluruh pelanggan sudah diketahui. Artinya, alih-alih melakukan simulasi acak (stochastic), paket ini fokus pada perhitungan langsung berdasarkan input yang diberikan oleh pengguna.
Fungsi utama dalam paket ini adalah queue_step, yang bertugas untuk menjalankan simulasi antrian. Fungsi ini menerima tiga argumen utama:
Vektor waktu kedatangan pelanggan,
Vektor waktu pelayanan masing-masing pelanggan,
Jumlah server yang tersedia untuk melayani pelanggan-pelanggan tersebut.
Dengan ketiga input tersebut, fungsi queue_step akan menghitung waktu keluar (departure times) setiap pelanggan sesuai dengan aturan first-come, first-served (FCFS), serta memperhatikan ketersediaan server secara real-time.
library("queuecomputer")## Warning: package 'queuecomputer' was built under R version 4.4.3arrivals <- cumsum(rexp(100))
head(arrivals)## [1] 0.508320 1.028699 1.275152 1.500999 2.134816 4.761809service <- rexp(100)
departures <- queue_step(arrivals, service = service, servers = 2)
departures## $departures
## [1] 3.215298 1.634655 2.840344 3.268269 7.225669 4.995408 5.689377
## [8] 9.744708 12.624795 14.793966 12.998907 14.828324 16.303043 18.183756
## [15] 17.414212 18.530365 19.835296 19.319043 19.468886 21.647311 21.637902
## [22] 23.709224 23.640934 26.710921 25.089209 26.581265 26.786016 27.468232
## [29] 27.586166 29.241105 30.451153 31.114295 31.741004 32.254172 32.512869
## [36] 34.484558 35.642170 35.389730 37.150633 36.303038 37.986076 38.858714
## [43] 39.189410 41.895333 41.934717 43.948474 42.493516 43.338589 47.839882
## [50] 44.046606 44.057287 44.681845 45.248152 47.674969 48.561405 48.124657
## [57] 48.161104 51.439183 50.802434 50.941001 51.956482 51.607438 52.888905
## [64] 52.079490 53.179801 53.282654 53.297835 56.858772 61.404284 61.527409
## [71] 61.475009 62.626837 62.232129 63.891541 64.912963 65.188994 66.981612
## [78] 66.244310 68.598757 69.509862 68.838371 69.528441 70.563091 70.601400
## [85] 72.689071 72.458805 73.608105 75.237850 74.740456 75.415550 78.447748
## [92] 76.726135 81.045745 79.548764 82.390070 82.906487 82.871335 84.529651
## [99] 83.416655 86.323294
##
## $server
## [1] 1 2 2 2 1 2 2 2 1 2 1 1 2 1 2 2 1 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 1 2 1 2 1
## [38] 2 2 1 1 2 1 2 1 2 1 1 1 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 2 1 2 1 2 1 2 2 1 1
## [75] 2 1 2 1 1 2 1 1 2 1 2 1 1 2 1 1 2 1 1 2 2 1 2 2 1 1
##
## $departures_df
## # A tibble: 100 × 6
## arrivals service departures waiting system_time server
## <dbl> <dbl> <dbl> <dbl> <dbl> <int>
## 1 0.508 2.71 3.22 0 2.71 1
## 2 1.03 0.606 1.63 0 0.606 2
## 3 1.28 1.21 2.84 3.60e- 1 1.57 2
## 4 1.50 0.428 3.27 1.34e+ 0 1.77 2
## 5 2.13 4.01 7.23 1.08e+ 0 5.09 1
## 6 4.76 0.234 5.00 1.67e-16 0.234 2
## 7 5.31 0.375 5.69 0 0.375 2
## 8 9.65 0.0936 9.74 0 0.0936 2
## 9 12.4 0.209 12.6 0 0.209 1
## 10 12.6 2.23 14.8 0 2.23 2
## # ℹ 90 more rows
##
## $queuelength_df
## times queuelength
## 1 0.000000 0
## 2 0.508320 1
## 3 0.508320 0
## 4 1.028699 1
## 5 1.028699 0
## 6 1.275152 1
## 7 1.500999 2
## 8 1.634655 1
## 9 2.134816 2
## 10 2.840344 1
## 11 3.215298 0
## 12 4.761809 1
## 13 4.761809 0
## 14 5.314012 1
## 15 5.314012 0
## 16 9.651152 1
## 17 9.651152 0
## 18 12.415939 1
## 19 12.415939 0
## 20 12.564623 1
## 21 12.564623 0
## 22 12.828297 1
## 23 12.828297 0
## 24 13.170721 1
## 25 13.170721 0
## 26 13.873791 1
## 27 14.430494 2
## 28 14.770960 3
## 29 14.793966 2
## 30 14.828324 1
## 31 15.392506 2
## 32 16.031301 3
## 33 16.303043 2
## 34 16.437284 3
## 35 17.414212 2
## 36 18.183756 1
## 37 18.328586 2
## 38 18.530365 1
## 39 19.319043 0
## 40 20.053393 1
## 41 20.053393 0
## 42 21.257547 1
## 43 21.257547 0
## 44 23.252926 1
## 45 23.252926 0
## 46 23.594709 1
## 47 23.594709 0
## 48 23.887457 1
## 49 23.887457 0
## 50 24.962555 1
## 51 24.962555 0
## 52 25.298890 1
## 53 25.298890 0
## 54 25.420873 1
## 55 25.786711 2
## 56 26.179528 3
## 57 26.581265 2
## 58 26.710921 1
## 59 26.786016 0
## 60 28.833912 1
## 61 28.833912 0
## 62 30.152088 1
## 63 30.152088 0
## 64 30.176810 1
## 65 30.176810 0
## 66 31.574127 1
## 67 31.574127 0
## 68 31.730210 1
## 69 31.730210 0
## 70 32.365202 1
## 71 32.365202 0
## 72 33.399059 1
## 73 33.399059 0
## 74 35.232821 1
## 75 35.232821 0
## 76 35.272546 1
## 77 35.272546 0
## 78 35.368937 1
## 79 35.389730 0
## 80 35.894359 1
## 81 35.894359 0
## 82 36.669593 1
## 83 36.669593 0
## 84 37.020995 1
## 85 37.150633 0
## 86 37.741270 1
## 87 37.986076 0
## 88 39.572684 1
## 89 39.572684 0
## 90 40.290713 1
## 91 40.290713 0
## 92 41.875550 1
## 93 41.895333 0
## 94 41.962486 1
## 95 41.962486 0
## 96 42.087431 1
## 97 42.493516 0
## 98 42.974044 1
## 99 43.241481 2
## 100 43.338589 1
## 101 43.346093 2
## 102 43.591377 3
## 103 43.905130 4
## 104 43.948474 3
## 105 44.046606 2
## 106 44.057287 1
## 107 44.681845 0
## 108 44.764261 1
## 109 44.845189 2
## 110 45.248152 1
## 111 46.151132 2
## 112 46.225821 3
## 113 47.053168 4
## 114 47.246503 5
## 115 47.406445 6
## 116 47.674969 5
## 117 47.703578 6
## 118 47.839882 5
## 119 48.030663 6
## 120 48.124657 5
## 121 48.161104 4
## 122 48.323031 5
## 123 48.561405 4
## 124 49.072251 5
## 125 49.197856 6
## 126 50.802434 5
## 127 50.941001 4
## 128 51.417330 5
## 129 51.439183 4
## 130 51.607438 3
## 131 51.956482 2
## 132 52.002562 3
## 133 52.079490 2
## 134 52.888905 1
## 135 53.179801 0
## 136 56.320890 1
## 137 56.320890 0
## 138 60.835243 1
## 139 60.835243 0
## 140 60.916518 1
## 141 60.916518 0
## 142 61.094357 1
## 143 61.404284 0
## 144 62.077373 1
## 145 62.077373 0
## 146 62.158325 1
## 147 62.158325 0
## 148 62.559190 1
## 149 62.559190 0
## 150 63.410389 1
## 151 63.410389 0
## 152 64.111533 1
## 153 64.111533 0
## 154 64.120559 1
## 155 64.912963 0
## 156 65.208160 1
## 157 65.208160 0
## 158 67.628620 1
## 159 67.628620 0
## 160 67.750231 1
## 161 67.750231 0
## 162 68.267198 1
## 163 68.331787 2
## 164 68.598757 1
## 165 68.838371 0
## 166 68.848565 1
## 167 69.509862 0
## 168 69.571145 1
## 169 69.571145 0
## 170 69.939336 1
## 171 70.563091 0
## 172 71.156066 1
## 173 71.156066 0
## 174 72.728251 1
## 175 72.728251 0
## 176 73.484999 1
## 177 73.484999 0
## 178 74.137959 1
## 179 74.137959 0
## 180 75.238176 1
## 181 75.238176 0
## 182 76.234651 1
## 183 76.234651 0
## 184 76.705303 1
## 185 76.705303 0
## 186 78.827537 1
## 187 78.827537 0
## 188 79.440422 1
## 189 79.440422 0
## 190 79.810943 1
## 191 79.810943 0
## 192 81.737956 1
## 193 81.737956 0
## 194 82.113487 1
## 195 82.390070 0
## 196 83.009882 1
## 197 83.009882 0
## 198 83.338894 1
## 199 83.338894 0
## 200 84.200652 1
## 201 84.200652 0
##
## $systemlength_df
## times queuelength
## 1 0.000000 0
## 2 0.508320 1
## 3 1.028699 2
## 4 1.275152 3
## 5 1.500999 4
## 6 1.634655 3
## 7 2.134816 4
## 8 2.840344 3
## 9 3.215298 2
## 10 3.268269 1
## 11 4.761809 2
## 12 4.995408 1
## 13 5.314012 2
## 14 5.689377 1
## 15 7.225669 0
## 16 9.651152 1
## 17 9.744708 0
## 18 12.415939 1
## 19 12.564623 2
## 20 12.624795 1
## 21 12.828297 2
## 22 12.998907 1
## 23 13.170721 2
## 24 13.873791 3
## 25 14.430494 4
## 26 14.770960 5
## 27 14.793966 4
## 28 14.828324 3
## 29 15.392506 4
## 30 16.031301 5
## 31 16.303043 4
## 32 16.437284 5
## 33 17.414212 4
## 34 18.183756 3
## 35 18.328586 4
## 36 18.530365 3
## 37 19.319043 2
## 38 19.468886 1
## 39 19.835296 0
## 40 20.053393 1
## 41 21.257547 2
## 42 21.637902 1
## 43 21.647311 0
## 44 23.252926 1
## 45 23.594709 2
## 46 23.640934 1
## 47 23.709224 0
## 48 23.887457 1
## 49 24.962555 2
## 50 25.089209 1
## 51 25.298890 2
## 52 25.420873 3
## 53 25.786711 4
## 54 26.179528 5
## 55 26.581265 4
## 56 26.710921 3
## 57 26.786016 2
## 58 27.468232 1
## 59 27.586166 0
## 60 28.833912 1
## 61 29.241105 0
## 62 30.152088 1
## 63 30.176810 2
## 64 30.451153 1
## 65 31.114295 0
## 66 31.574127 1
## 67 31.730210 2
## 68 31.741004 1
## 69 32.254172 0
## 70 32.365202 1
## 71 32.512869 0
## 72 33.399059 1
## 73 34.484558 0
## 74 35.232821 1
## 75 35.272546 2
## 76 35.368937 3
## 77 35.389730 2
## 78 35.642170 1
## 79 35.894359 2
## 80 36.303038 1
## 81 36.669593 2
## 82 37.020995 3
## 83 37.150633 2
## 84 37.741270 3
## 85 37.986076 2
## 86 38.858714 1
## 87 39.189410 0
## 88 39.572684 1
## 89 40.290713 2
## 90 41.875550 3
## 91 41.895333 2
## 92 41.934717 1
## 93 41.962486 2
## 94 42.087431 3
## 95 42.493516 2
## 96 42.974044 3
## 97 43.241481 4
## 98 43.338589 3
## 99 43.346093 4
## 100 43.591377 5
## 101 43.905130 6
## 102 43.948474 5
## 103 44.046606 4
## 104 44.057287 3
## 105 44.681845 2
## 106 44.764261 3
## 107 44.845189 4
## 108 45.248152 3
## 109 46.151132 4
## 110 46.225821 5
## 111 47.053168 6
## 112 47.246503 7
## 113 47.406445 8
## 114 47.674969 7
## 115 47.703578 8
## 116 47.839882 7
## 117 48.030663 8
## 118 48.124657 7
## 119 48.161104 6
## 120 48.323031 7
## 121 48.561405 6
## 122 49.072251 7
## 123 49.197856 8
## 124 50.802434 7
## 125 50.941001 6
## 126 51.417330 7
## 127 51.439183 6
## 128 51.607438 5
## 129 51.956482 4
## 130 52.002562 5
## 131 52.079490 4
## 132 52.888905 3
## 133 53.179801 2
## 134 53.282654 1
## 135 53.297835 0
## 136 56.320890 1
## 137 56.858772 0
## 138 60.835243 1
## 139 60.916518 2
## 140 61.094357 3
## 141 61.404284 2
## 142 61.475009 1
## 143 61.527409 0
## 144 62.077373 1
## 145 62.158325 2
## 146 62.232129 1
## 147 62.559190 2
## 148 62.626837 1
## 149 63.410389 2
## 150 63.891541 1
## 151 64.111533 2
## 152 64.120559 3
## 153 64.912963 2
## 154 65.188994 1
## 155 65.208160 2
## 156 66.244310 1
## 157 66.981612 0
## 158 67.628620 1
## 159 67.750231 2
## 160 68.267198 3
## 161 68.331787 4
## 162 68.598757 3
## 163 68.838371 2
## 164 68.848565 3
## 165 69.509862 2
## 166 69.528441 1
## 167 69.571145 2
## 168 69.939336 3
## 169 70.563091 2
## 170 70.601400 1
## 171 71.156066 2
## 172 72.458805 1
## 173 72.689071 0
## 174 72.728251 1
## 175 73.484999 2
## 176 73.608105 1
## 177 74.137959 2
## 178 74.740456 1
## 179 75.237850 0
## 180 75.238176 1
## 181 75.415550 0
## 182 76.234651 1
## 183 76.705303 2
## 184 76.726135 1
## 185 78.447748 0
## 186 78.827537 1
## 187 79.440422 2
## 188 79.548764 1
## 189 79.810943 2
## 190 81.045745 1
## 191 81.737956 2
## 192 82.113487 3
## 193 82.390070 2
## 194 82.871335 1
## 195 82.906487 0
## 196 83.009882 1
## 197 83.338894 2
## 198 83.416655 1
## 199 84.200652 2
## 200 84.529651 1
## 201 86.323294 0
##
## $servers_input
## [1] 2
##
## $state
## [1] 86.32329 84.52965
##
## attr(,"class")
## [1] "queue_list" "list"Keluaran dari fungsi adalah sebuah objek bertipe . Kami telah membuat metode khusus untuk objek bertipe , yang akan kami tunjukkan penggunaannya.
summary(departures)## Total customers:
## 100
## Missed customers:
## 0
## Mean waiting time:
## 0.54
## Mean response time:
## 1.58
## Utilization factor:
## 0.60113048197992
## Mean queue length:
## 0.641
## Mean number of customers in system:
## 1.83Jika elemen terakhir dari vektor bernilai nol, maka ada kemungkinan beberapa pelanggan tidak pernah terlayani. Hal ini ditandai sebagai (). Ukuran performa yang disediakan meliputi: waktu tunggu rata-rata (\(w\)), waktu respons rata-rata (\(r = d - a\)), faktor utilisasi server (\(B/K\)), panjang antrian rata-rata, dan jumlah rata-rata pelanggan dalam sistem. Faktor utilisasi ini mempertimbangkan perubahan jumlah server yang aktif sepanjang waktu \(K(t)\), terutama saat menggunakan Algoritma 2. Selanjutnya, penulis menjelaskan detail implementasi dari paket ini.
5. Implementasi
Fungsi utama yang digunakan adalah queue_step(). Fungsi ini menghitung waktu keluarnya pelanggan dari sistem berdasarkan data waktu kedatangan dan lama pelayanan. Tergantung tipe input servers, algoritma yang digunakan bisa:
Algoritma 1: jumlah server tetap (misal servers = 2),
Algoritma 2: jumlah server berubah sepanjang waktu (server.stepfun),
Algoritma 4: kendali penuh atas server mana yang aktif dan kapan (server.list).
Seluruh proses inti ditulis dalam bahasa C++ agar cepat dan efisien, lalu dibungkus oleh fungsi di R agar mudah digunakan.
6. Validasi
Paket queuecomputer telah diuji validitasnya dengan:
Membandingkan hasil simulasi dengan simmer (R) dan simpy (Python),
Mereplikasi hasil teori untuk sistem antrian M/M/K, seperti rata-rata waktu tunggu dan utilisasi server.
Hasilnya menunjukkan bahwa:
queuecomputer menghasilkan output yang sama akuratnya dengan kedua paket tersebut,
Proses simulasi jauh lebih cepat, bahkan untuk jutaan pelanggan sekalipun.
Tujuan: Membuktikan bahwa queuecomputer menghasilkan output yang sama dengan simmer (R) dan simpy (Python), serta mendekati hasil teoretis untuk M/M/K queue.
6.1 Bandingkan dengan simmer dan simpy
# Set seed dan buat data
set.seed(1)
n_customers <- 10000
lambda_a <- 1 # rata-rata 1 pelanggan per unit waktu
lambda_s <- 1 / 0.9 # rata-rata layanan 0.9 satuan waktu
# Generate data kedatangan dan layanan
interarrivals <- rexp(n_customers, lambda_a)
arrivals <- cumsum(interarrivals)
service <- rexp(n_customers, lambda_s)
# Jalankan simulasi dengan queuecomputer
library(queuecomputer)
departures <- queue_step(arrivals, service = service, servers = 2)
head(sort(depart(departures)))## [1] 1.340151 2.288112 2.639976 2.796572 3.249794 5.7149676.2 Replikasi Hasil Teori M/M/3
set.seed(1)
n_customers <- 5e6
lambda <- 2 # laju kedatangan
mu <- 1 # laju layanan
K <- 3 # jumlah server
interarrivals <- rexp(n_customers, lambda)
arrivals <- cumsum(interarrivals)
service <- rexp(n_customers, mu)
MM3 <- queue_step(arrivals = arrivals, service = service, servers = K)
summary(MM3)## Total customers:
## 5000000
## Missed customers:
## 0
## Mean waiting time:
## 0.445
## Mean response time:
## 1.44
## Utilization factor:
## 0.666140156160826
## Mean queue length:
## 0.889
## Mean number of customers in system:
## 2.897. Tolak Ukur
7.1 Metode
Efisiensi komputasi paket queuecomputer dan simmer dibandingkan melalui simulasi sistem antrian tipe \(M/M/2/\infty\) dengan disiplin layanan First Come First Serve (FCFS). Simulasi dilakukan untuk berbagai jumlah pelanggan, mulai dari \(n = 10^3\) hingga \(n = 10^7\), dengan laju kedatangan \(\lambda = 1\) dan laju pelayanan \(\mu = 1.1\). Tujuan dari perbandingan ini adalah untuk mengevaluasi kecepatan dan efisiensi masing-masing paket dalam menghitung waktu keberangkatan (departure times) pada sistem antrian berskala besar. Percobaan dilakukan 100 kali untuk n = \(10^3\), \(10^5\), dan \(10^6\), dengan \(n = 10^6\) diulang 10 kali untuk simmer dan hingga \(n = 10^7\) untuk queuecomputer. Nilai median dari waktu percobaan digunakan sebagai ukuran waktu. Pengukuran dilakukan dengan fungsi microbenchmark (Mersmann 2015, time = 100), dan rincian lengkap terdapat pada lampiran.
7.2 Hasil dan Pembahasan
Paket queuecomputer jauh lebih efisien dibandingkan simpy dan simmer untuk simulasi sistem antrian dengan jumlah pelanggan dari 100 hingga \(10^6\) (bahkan hingga \(10^7\)). Kecepatan queuecomputer dapat 5–600 kali lebih tinggi dari simpy, dan hingga 170 kali lebih tinggi dari simmer. Pada jumlah pelanggan kecil, kecepatan relatif memang lebih rendah, tetapi untuk jumlah pelanggan sangat besar (10 juta), queuecomputer dapat menyelesaikan simulasi dalam waktu kurang dari 1 detik. Pola kedatangan dan pelayanan tidak memengaruhi kecepatan relatif. Kesimpulannya, queuecomputer dan implementasi QDC-nya sangat efisien untuk simulasi sistem antrian dibandingkan dengan metode biasa dari simpy dan simmer.
8. Contoh
8.1 Pusat Panggilan
Queuecomputer digunakan untuk mensimulasikan pusat panggilan, di mana waktu kedatangan pelanggan adalah saat mereka menelepon, dan waktu pelayanan adalah durasi penyelesaian masalah oleh perwakilan layanan pelanggan. Mari kita asumsikan bahwa…
library("queuecomputer")
library("randomNames")## Warning: package 'randomNames' was built under R version 4.4.3 library("ggplot2")## Warning: package 'ggplot2' was built under R version 4.4.3 set.seed(1)
interarrivals <- rexp(20, 1)
arrivals <- cumsum(interarrivals)
customers <- randomNames(20, name.order = "first.last") service <- rexp(20, 0.5)
head(service)## [1] 0.8979956 0.7591994 2.4975352 5.3868231 0.3926436 4.5996743Waktu kedatangan dan pelayanan dimasukkan ke dalam fungsi queue_step untuk menghitung waktu keberangkatan, dengan jumlah pelayan (servers) ditetapkan sebagai dua.
queue_obj <- queue_step(arrivals, service, servers = 2, labels = customers)
head(queue_obj$departures_df)## # A tibble: 6 × 7
## labels arrivals service departures waiting system_time server
## <chr> <dbl> <dbl> <dbl> <dbl> <dbl> <int>
## 1 Saadiq, el-Molla 0.755 0.898 1.65 1.11e-16 0.898 1
## 2 Jelicha, Kim 1.94 0.759 2.70 0 0.759 2
## 3 Briana, Lesley 2.08 2.50 4.58 0 2.50 1
## 4 Daeun, Her 2.22 5.39 8.08 4.74e- 1 5.86 2
## 5 Ruwaida, al-Bahri 2.66 0.393 4.97 1.92e+ 0 2.31 1
## 6 Fawzi, al-Jamail 5.55 4.60 10.2 0 4.60 1Kwabena membutuhkan waktu layanan lebih lama, sehingga dua pelanggan berikutnya dilayani pelayan lain. Contoh ini menunjukkan bahwa waktu keberangkatan dapat dihitung dengan menjumlahkan waktu kedatangan dan waktu pelayanan masing‑masing pelanggan.
firstcustomers <- arrivals[1:2] + service[1:2]
firstcustomers## [1] 1.653177 2.696024Dashawn harus menunggu pelayan yang kosong sebelum dapat dilayani, sehingga waktu keberangkatannya ditentukan dari waktu selesai Beatriz ditambah waktu pelayanannya sendiri.
firstcustomers[2] + service[3]## [1] 5.193559Dua pelanggan pertama tidak menunggu, sedangkan Dashawn harus menunggu pelayan yang tersedia. Waktu tunggu masing‑masing dapat dihitung dengan metode ini.
depart(queue_obj)[1:3] - arrivals[1:3] - service[1:3]## [1] 1.110223e-16 -1.110223e-16 0.000000e+00Fungsi depart digunakan untuk mendapatkan waktu keberangkatan dari queue_list, sedangkan summary(departures) memberikan ringkasan dari objek tersebut.
summary(queue_obj)## Total customers:
## 20
## Missed customers:
## 0
## Mean waiting time:
## 0.893
## Mean response time:
## 2.52
## Utilization factor:
## 0.700476008415974
## Mean queue length:
## 0.82
## Mean number of customers in system:
## 2.17Fungsi plot pada queuecomputer menghasilkan empat jenis visualisasi dengan ggplot2: histogram waktu kedatangan/keberangkatan (gambar 3), jumlah pelanggan dari waktu ke waktu (gambar 4), waktu tunggu/pelayanan (gambar 5), dan distribusi kumulatif kedatangan/keberangkatan (gambar 6). Pemilihan plot dilakukan dengan argumen which.
plot(queue_obj, which = c(2, 4, 5, 6))## [[1]]
##
## [[2]]
##
## [[3]]
##
## [[4]]
Pada Gambar 5, sebuah pelayan tidak pernah melayani lebih dari satu pelanggan sekaligus, terlihat dari garis horizontal yang tidak pernah memotong lebih dari dua batang merah.
8.2 Terminal Bandara Internasional
# Membuat data contoh Passenger_df dari 10 data awal
Passenger_df <- data.frame(
ID = c("AB1481","AB1481","AB1481","AB1481","AB1481",
"AB1481","AB1481","AB1481","AB1481","AB1481"),
FlightNo = rep("564.85", 10),
arrival = rep(564.85, 10),
route_imm = c("manual","manual","manual","smart gate","smart gate",
"smart gate","manual","manual","manual","manual"),
arrive_imm = c(566.8549, 566.8532, 567.2014, 566.8377, 566.0994,
566.8928, 567.5558, 566.3114, 567.2563, 567.2167),
service_imm = c(0.29075606, 0.15927226, 0.22450319, 0.18222445, 0.09031344,
0.43900281, 0.12917143, 0.30556961, 0.31975687, 0.33944458),
bag_time = rep(NA, 10) # Nilai belum diketahui, diisi NA
)
# Cek data
print(Passenger_df)## ID FlightNo arrival route_imm arrive_imm service_imm bag_time
## 1 AB1481 564.85 564.85 manual 566.8549 0.29075606 NA
## 2 AB1481 564.85 564.85 manual 566.8532 0.15927226 NA
## 3 AB1481 564.85 564.85 manual 567.2014 0.22450319 NA
## 4 AB1481 564.85 564.85 smart gate 566.8377 0.18222445 NA
## 5 AB1481 564.85 564.85 smart gate 566.0994 0.09031344 NA
## 6 AB1481 564.85 564.85 smart gate 566.8928 0.43900281 NA
## 7 AB1481 564.85 564.85 manual 567.5558 0.12917143 NA
## 8 AB1481 564.85 564.85 manual 566.3114 0.30556961 NA
## 9 AB1481 564.85 564.85 manual 567.2563 0.31975687 NA
## 10 AB1481 564.85 564.85 manual 567.2167 0.33944458 NA# Sekarang Passenger_df siap digunakan!Ada dua jalur imigrasi (route_imm): smart gate dengan 5 pelayan, dan manual dengan jumlah pelayan yang berubah sesuai waktu (10, 12, dan 8 pelayan). Data ini disimpan dalam server_df.
server_df <- data.frame(immigration_route = c("smart gate", "manual"))
server_df$servers <-
list(5, as.server.stepfun(x = c(600,780), y = c(10,12,8)))Fungsi group_by dari dplyr digunakan untuk menghitung waktu keberangkatan dari pelayan paralel dengan memproses data seolah‑olah terdiri dari dua kelompok terpisah.
# Memuat library
library(dplyr)##
## Attaching package: 'dplyr'## The following objects are masked from 'package:stats':
##
## filter, lag## The following objects are masked from 'package:base':
##
## intersect, setdiff, setequal, union# Melakukan join berdasarkan kolom "immigration_route"
Passenger_df <- left_join(Passenger_df, server_df, by = c("route_imm" = "immigration_route"))
# Sekarang Passenger_df sudah memiliki data dari server_df berdasarkan route_imm
head(Passenger_df) # Cek data## ID FlightNo arrival route_imm arrive_imm service_imm bag_time
## 1 AB1481 564.85 564.85 manual 566.8549 0.29075606 NA
## 2 AB1481 564.85 564.85 manual 566.8532 0.15927226 NA
## 3 AB1481 564.85 564.85 manual 567.2014 0.22450319 NA
## 4 AB1481 564.85 564.85 smart gate 566.8377 0.18222445 NA
## 5 AB1481 564.85 564.85 smart gate 566.0994 0.09031344 NA
## 6 AB1481 564.85 564.85 smart gate 566.8928 0.43900281 NA
## servers
## 1 600, 780, 10, 12, 8
## 2 600, 780, 10, 12, 8
## 3 600, 780, 10, 12, 8
## 4 5
## 5 5
## 6 5Gambar 7 menunjukkan skenario bandara dengan 120 penerbangan dan dua sistem antrian paralel (manual dan gerbang otomatis). Penumpang dan bagasi “bercabang” saat pesawat tiba, kemudian “bergabung” kembali di area pengambilan bagasi.
library(dplyr)
# Contoh fungsi FIFO queue sederhana
queue <- function(arrival, service, servers = 1) {
n <- length(arrival)
departure <- numeric(n)
server_time <- rep(0, servers)
for (i in seq_len(n)) {
# Server pertama yang tersedia
next_free <- min(server_time)
start_time <- max(arrival[i], next_free)
departure[i] <- start_time + service[i]
server_time[which.min(server_time)] <- departure[i]
}
return(departure)
}
# Jumlah server untuk masing-masing rute
servers <- list("manual" = 3, "smart gate" = 5)
library(purrr)
# Simulasi untuk tiap jenis rute imigrasi
Passenger_df_split <- Passenger_df %>%
group_split(route_imm) %>%
map_dfr(~{
route <- unique(.x$route_imm)
server_n <- servers[[route]]
.x$departures_imm <- queue(.x$arrive_imm, .x$service_imm, servers = server_n)
.x$departures_bc <- pmax(.x$departures_imm, .x$bag_time, na.rm = TRUE)
return(.x)
})Kolom departures_imm dan departures_bc masing‑masing merepresentasikan waktu keluar dari area imigrasi dan area pengambilan bagasi. Dengan dplyr::summarise, waktu tunggu dapat diringkas berdasarkan FlightNo dan route_imm atau hanya berdasarkan route_imm.
Passenger_df_split %>%
group_by(FlightNo, route_imm) %>%
summarise(
waiting_imm = mean(departures_imm - service_imm - arrive_imm, na.rm = TRUE),
waiting_bc = mean(departures_bc - departures_imm, na.rm = TRUE)
)## `summarise()` has grouped output by 'FlightNo'. You can override using the
## `.groups` argument.## # A tibble: 2 × 4
## # Groups: FlightNo [1]
## FlightNo route_imm waiting_imm waiting_bc
## <chr> <chr> <dbl> <dbl>
## 1 564.85 manual 0.177 0
## 2 564.85 smart gate 0 0 Passenger_df_split %>%
group_by(route_imm) %>%
summarise(
waiting_imm = mean(departures_imm - service_imm - arrive_imm, na.rm = TRUE),
waiting_bc = mean(departures_bc - departures_imm, na.rm = TRUE)
)## # A tibble: 2 × 3
## route_imm waiting_imm waiting_bc
## <chr> <dbl> <dbl>
## 1 manual 0.177 0
## 2 smart gate 0 0Model antrian dinamis yang kompleks dapat dibangun dengan efisien dan mudah dikembangkan berkat kombinasi queuecomputer dan dplyr.
9. Kesimpulan
Paket queuecomputer menawarkan pendekatan yang sangat efisien untuk melakukan simulasi sistem antrian, terutama dalam konteks skenario besar dan dinamis yang umum dijumpai di dunia nyata, seperti bandara dan call center. Algoritma Queue Departure Computation (QDC) yang menjadi inti dari paket ini memisahkan proses pengambilan sampel statistik dari perhitungan keberangkatan antrian, sehingga memungkinkan pengguna untuk fokus pada fleksibilitas struktur sistem alih-alih beban komputasi.
Keunggulan utama queuecomputer dibandingkan pendekatan simulasi berbasis event tradisional seperti simmer (R) dan simpy (Python) adalah kecepatannya yang luar biasa, dengan peningkatan efisiensi hingga beberapa ratus kali lipat. Selain itu, implementasi berbasis C++ di balik fungsi utamanya menjadikan proses simulasi tidak hanya cepat, tetapi juga hemat memori.
Paket ini memungkinkan simulasi deterministik untuk jaringan antrian kompleks yang dapat berubah sepanjang waktu, seperti perubahan jumlah server sesuai shift kerja atau lonjakan permintaan. Dengan kompatibilitas terhadap ekosistem tidyverse (dplyr, ggplot2, dll.), queuecomputer juga sangat cocok digunakan dalam workflow analisis data modern di R.
Secara keseluruhan, queuecomputer adalah solusi simulasi antrian yang sangat relevan bagi para peneliti dan praktisi yang membutuhkan efisiensi komputasi tinggi tanpa mengorbankan fleksibilitas pemodelan.
Acknowledgements
Kami mengucapkan terima kasih kepada Tim queuecomputer, khususnya kepada Ebert, Pagendam, dan Ross, atas pengembangan paket ini dan publikasi artikel yang memberikan kontribusi signifikan terhadap dunia simulasi sistem antrian. Paket ini memberikan alat yang efisien dan intuitif bagi pengguna R untuk mengeksplorasi dan mensimulasikan sistem antrian kompleks yang sebelumnya sulit ditangani secara efisien.
Review ini juga disusun berdasarkan paper Computationally Efficient Simulation of Queues: The R Package queuecomputer