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.3.3arrivals <- cumsum(rexp(100))
head(arrivals)## [1] 1.208176 1.694646 2.530735 3.026869 3.178799 3.472499service <- rexp(100)
departures <- queue_step(arrivals, service = service, servers = 2)
departures## $departures
## [1] 1.378424 4.397573 5.210008 5.126900 5.290041 5.270927 5.273496
## [8] 5.289124 9.680537 8.940558 11.854593 9.873306 11.873385 12.086845
## [15] 12.342527 12.677330 13.933122 15.217991 16.097139 15.730683 17.385636
## [22] 19.191738 19.633659 20.675037 21.435593 27.993281 26.415607 26.759407
## [29] 27.442207 29.454979 29.828787 31.939016 32.475670 33.005699 43.345918
## [36] 44.086672 43.698532 43.826988 45.705856 44.898658 45.234621 45.729058
## [43] 45.976460 46.590258 48.303038 47.118679 48.607180 48.417770 48.700348
## [50] 50.453951 53.110838 51.074094 51.652909 52.366757 56.936753 55.641462
## [57] 58.177985 57.543404 57.915338 58.564082 60.132732 60.894665 60.845301
## [64] 61.634169 62.373122 65.988465 64.289960 64.476238 69.704369 66.971468
## [71] 67.767248 70.321839 69.847993 75.015130 75.856136 76.225585 76.873320
## [78] 77.422081 78.429205 78.903679 79.423483 80.609068 82.101772 82.742247
## [85] 82.495009 83.898365 86.612526 85.644013 87.051544 87.628018 88.281159
## [92] 88.056687 88.299859 90.124690 90.714168 90.174114 95.834278 91.357245
## [99] 92.199001 92.228194
##
## $server
## [1] 1 2 1 2 2 1 1 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 2 2 2 1 2 1 2 1 2 1
## [38] 1 1 2 2 2 1 2 1 2 2 1 1 2 1 2 2 2 2 1 1 2 2 2 1 2 1 1 2 1 2 2 2 1 1 1 2 2
## [75] 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 2 1 2 2 1 2 1 1 2 2 2
##
## $departures_df
## # A tibble: 100 × 6
## arrivals service departures waiting system_time server
## <dbl> <dbl> <dbl> <dbl> <dbl> <int>
## 1 1.21 0.170 1.38 1.11e-16 0.170 1
## 2 1.69 2.70 4.40 4.44e-16 2.70 2
## 3 2.53 2.68 5.21 4.44e-16 2.68 1
## 4 3.03 0.729 5.13 1.37e+ 0 2.10 2
## 5 3.18 0.163 5.29 1.95e+ 0 2.11 2
## 6 3.47 0.0609 5.27 1.74e+ 0 1.80 1
## 7 3.98 0.00257 5.27 1.29e+ 0 1.29 1
## 8 4.29 0.0156 5.29 9.79e- 1 0.994 1
## 9 6.24 3.45 9.68 4.44e-16 3.45 1
## 10 8.12 0.822 8.94 5.55e-16 0.822 2
## # ℹ 90 more rows
##
## $queuelength_df
## times queuelength
## 1 0.000000 0
## 2 1.208176 1
## 3 1.208176 0
## 4 1.694646 1
## 5 1.694646 0
## 6 2.530735 1
## 7 2.530735 0
## 8 3.026869 1
## 9 3.178799 2
## 10 3.472499 3
## 11 3.979700 4
## 12 4.294814 5
## 13 4.397573 4
## 14 5.126900 3
## 15 5.210008 2
## 16 5.270927 1
## 17 5.273496 0
## 18 6.235207 1
## 19 6.235207 0
## 20 8.118882 1
## 21 8.118882 0
## 22 8.214736 1
## 23 8.272457 2
## 24 8.940558 1
## 25 9.452958 2
## 26 9.680537 1
## 27 9.873306 0
## 28 9.967149 1
## 29 10.017254 2
## 30 10.209891 3
## 31 10.812024 4
## 32 11.001736 5
## 33 11.854593 4
## 34 11.873385 3
## 35 12.086845 2
## 36 12.342527 1
## 37 12.677330 0
## 38 15.326366 1
## 39 15.326366 0
## 40 15.708443 1
## 41 15.708443 0
## 42 16.595886 1
## 43 16.595886 0
## 44 17.045264 1
## 45 17.045264 0
## 46 19.147155 1
## 47 19.147155 0
## 48 19.455114 1
## 49 19.455114 0
## 50 21.360237 1
## 51 21.360237 0
## 52 24.474164 1
## 53 24.474164 0
## 54 25.862512 1
## 55 25.862512 0
## 56 26.055250 1
## 57 26.415607 0
## 58 26.931976 1
## 59 26.931976 0
## 60 28.739586 1
## 61 28.739586 0
## 62 29.710259 1
## 63 29.710259 0
## 64 30.840844 1
## 65 30.840844 0
## 66 31.192016 1
## 67 31.192016 0
## 68 32.190370 1
## 69 32.190370 0
## 70 39.646066 1
## 71 39.646066 0
## 72 43.069489 1
## 73 43.069489 0
## 74 43.282215 1
## 75 43.345918 0
## 76 43.568824 1
## 77 43.628872 2
## 78 43.698532 1
## 79 43.826988 0
## 80 44.573094 1
## 81 44.573094 0
## 82 44.763396 1
## 83 44.898658 0
## 84 44.963142 1
## 85 45.017808 2
## 86 45.186744 3
## 87 45.234621 2
## 88 45.535377 3
## 89 45.705856 2
## 90 45.729058 1
## 91 45.966802 2
## 92 45.976460 1
## 93 46.590258 0
## 94 47.133455 1
## 95 47.133455 0
## 96 47.189746 1
## 97 47.628167 2
## 98 47.749690 3
## 99 48.303038 2
## 100 48.417770 1
## 101 48.607180 0
## 102 49.334084 1
## 103 49.334084 0
## 104 49.464754 1
## 105 50.453951 0
## 106 51.281419 1
## 107 51.281419 0
## 108 51.749493 1
## 109 51.749493 0
## 110 52.679057 1
## 111 52.679057 0
## 112 52.918923 1
## 113 53.110838 0
## 114 54.807049 1
## 115 55.408440 2
## 116 55.641462 1
## 117 56.936753 0
## 118 57.571759 1
## 119 57.571759 0
## 120 58.312208 1
## 121 58.312208 0
## 122 59.044103 1
## 123 59.044103 0
## 124 59.615700 1
## 125 59.615700 0
## 126 60.614638 1
## 127 60.614638 0
## 128 60.766467 1
## 129 60.845301 0
## 130 61.437611 1
## 131 61.437611 0
## 132 63.331286 1
## 133 63.331286 0
## 134 63.431822 1
## 135 63.431822 0
## 136 63.859926 1
## 137 64.289960 0
## 138 65.825931 1
## 139 65.825931 0
## 140 65.932683 1
## 141 65.988465 0
## 142 67.172620 1
## 143 67.172620 0
## 144 69.198531 1
## 145 69.198531 0
## 146 69.691732 1
## 147 69.704369 0
## 148 72.466249 1
## 149 72.466249 0
## 150 73.244030 1
## 151 73.244030 0
## 152 76.216832 1
## 153 76.216832 0
## 154 76.859047 1
## 155 76.859047 0
## 156 77.024485 1
## 157 77.024485 0
## 158 77.487446 1
## 159 77.487446 0
## 160 78.379173 1
## 161 78.379173 0
## 162 79.259060 1
## 163 79.259060 0
## 164 79.784398 1
## 165 79.784398 0
## 166 81.613109 1
## 167 81.613109 0
## 168 82.239788 1
## 169 82.239788 0
## 170 82.267025 1
## 171 82.267025 0
## 172 83.524366 1
## 173 83.524366 0
## 174 84.633900 1
## 175 84.633900 0
## 176 85.182301 1
## 177 85.182301 0
## 178 86.353613 1
## 179 86.353613 0
## 180 87.450554 1
## 181 87.450554 0
## 182 87.588254 1
## 183 87.588254 0
## 184 87.840561 1
## 185 87.840561 0
## 186 87.931228 1
## 187 88.056687 0
## 188 89.027778 1
## 189 89.027778 0
## 190 89.495550 1
## 191 89.495550 0
## 192 89.935132 1
## 193 89.997999 2
## 194 90.124690 1
## 195 90.174114 0
## 196 90.623697 1
## 197 90.703504 2
## 198 90.714168 1
## 199 91.335184 2
## 200 91.357245 1
## 201 92.199001 0
##
## $systemlength_df
## times queuelength
## 1 0.000000 0
## 2 1.208176 1
## 3 1.378424 0
## 4 1.694646 1
## 5 2.530735 2
## 6 3.026869 3
## 7 3.178799 4
## 8 3.472499 5
## 9 3.979700 6
## 10 4.294814 7
## 11 4.397573 6
## 12 5.126900 5
## 13 5.210008 4
## 14 5.270927 3
## 15 5.273496 2
## 16 5.289124 1
## 17 5.290041 0
## 18 6.235207 1
## 19 8.118882 2
## 20 8.214736 3
## 21 8.272457 4
## 22 8.940558 3
## 23 9.452958 4
## 24 9.680537 3
## 25 9.873306 2
## 26 9.967149 3
## 27 10.017254 4
## 28 10.209891 5
## 29 10.812024 6
## 30 11.001736 7
## 31 11.854593 6
## 32 11.873385 5
## 33 12.086845 4
## 34 12.342527 3
## 35 12.677330 2
## 36 13.933122 1
## 37 15.217991 0
## 38 15.326366 1
## 39 15.708443 2
## 40 15.730683 1
## 41 16.097139 0
## 42 16.595886 1
## 43 17.045264 2
## 44 17.385636 1
## 45 19.147155 2
## 46 19.191738 1
## 47 19.455114 2
## 48 19.633659 1
## 49 20.675037 0
## 50 21.360237 1
## 51 21.435593 0
## 52 24.474164 1
## 53 25.862512 2
## 54 26.055250 3
## 55 26.415607 2
## 56 26.759407 1
## 57 26.931976 2
## 58 27.442207 1
## 59 27.993281 0
## 60 28.739586 1
## 61 29.454979 0
## 62 29.710259 1
## 63 29.828787 0
## 64 30.840844 1
## 65 31.192016 2
## 66 31.939016 1
## 67 32.190370 2
## 68 32.475670 1
## 69 33.005699 0
## 70 39.646066 1
## 71 43.069489 2
## 72 43.282215 3
## 73 43.345918 2
## 74 43.568824 3
## 75 43.628872 4
## 76 43.698532 3
## 77 43.826988 2
## 78 44.086672 1
## 79 44.573094 2
## 80 44.763396 3
## 81 44.898658 2
## 82 44.963142 3
## 83 45.017808 4
## 84 45.186744 5
## 85 45.234621 4
## 86 45.535377 5
## 87 45.705856 4
## 88 45.729058 3
## 89 45.966802 4
## 90 45.976460 3
## 91 46.590258 2
## 92 47.118679 1
## 93 47.133455 2
## 94 47.189746 3
## 95 47.628167 4
## 96 47.749690 5
## 97 48.303038 4
## 98 48.417770 3
## 99 48.607180 2
## 100 48.700348 1
## 101 49.334084 2
## 102 49.464754 3
## 103 50.453951 2
## 104 51.074094 1
## 105 51.281419 2
## 106 51.652909 1
## 107 51.749493 2
## 108 52.366757 1
## 109 52.679057 2
## 110 52.918923 3
## 111 53.110838 2
## 112 54.807049 3
## 113 55.408440 4
## 114 55.641462 3
## 115 56.936753 2
## 116 57.543404 1
## 117 57.571759 2
## 118 57.915338 1
## 119 58.177985 0
## 120 58.312208 1
## 121 58.564082 0
## 122 59.044103 1
## 123 59.615700 2
## 124 60.132732 1
## 125 60.614638 2
## 126 60.766467 3
## 127 60.845301 2
## 128 60.894665 1
## 129 61.437611 2
## 130 61.634169 1
## 131 62.373122 0
## 132 63.331286 1
## 133 63.431822 2
## 134 63.859926 3
## 135 64.289960 2
## 136 64.476238 1
## 137 65.825931 2
## 138 65.932683 3
## 139 65.988465 2
## 140 66.971468 1
## 141 67.172620 2
## 142 67.767248 1
## 143 69.198531 2
## 144 69.691732 3
## 145 69.704369 2
## 146 69.847993 1
## 147 70.321839 0
## 148 72.466249 1
## 149 73.244030 2
## 150 75.015130 1
## 151 75.856136 0
## 152 76.216832 1
## 153 76.225585 0
## 154 76.859047 1
## 155 76.873320 0
## 156 77.024485 1
## 157 77.422081 0
## 158 77.487446 1
## 159 78.379173 2
## 160 78.429205 1
## 161 78.903679 0
## 162 79.259060 1
## 163 79.423483 0
## 164 79.784398 1
## 165 80.609068 0
## 166 81.613109 1
## 167 82.101772 0
## 168 82.239788 1
## 169 82.267025 2
## 170 82.495009 1
## 171 82.742247 0
## 172 83.524366 1
## 173 83.898365 0
## 174 84.633900 1
## 175 85.182301 2
## 176 85.644013 1
## 177 86.353613 2
## 178 86.612526 1
## 179 87.051544 0
## 180 87.450554 1
## 181 87.588254 2
## 182 87.628018 1
## 183 87.840561 2
## 184 87.931228 3
## 185 88.056687 2
## 186 88.281159 1
## 187 88.299859 0
## 188 89.027778 1
## 189 89.495550 2
## 190 89.935132 3
## 191 89.997999 4
## 192 90.124690 3
## 193 90.174114 2
## 194 90.623697 3
## 195 90.703504 4
## 196 90.714168 3
## 197 91.335184 4
## 198 91.357245 3
## 199 92.199001 2
## 200 92.228194 1
## 201 95.834278 0
##
## $servers_input
## [1] 2
##
## $state
## [1] 95.83428 92.22819
##
## 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.311
## Mean response time:
## 1.37
## Utilization factor:
## 0.553162850119532
## Mean queue length:
## 0.338
## Mean number of customers in system:
## 1.43Jika 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.3.3 library("ggplot2")
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)## Warning: package 'dplyr' was built under R version 4.3.3##
## 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)## Warning: package 'purrr' was built under R version 4.3.3# 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