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] 0.8351502 1.6149204 2.4800390 3.5170734 6.2333778 8.6551312service <- rexp(100)
departures <- queue_step(arrivals, service = service, servers = 2)
departures## $departures
## [1] 2.312210 2.257978 7.452342 5.772324 7.060363 8.735302
## [7] 8.937176 9.430628 11.375743 15.570999 14.660065 14.867762
## [13] 15.345099 18.374075 18.294964 19.358463 20.284838 21.751119
## [19] 22.102153 24.050154 24.354716 25.230284 25.168747 25.544424
## [25] 25.882393 31.296033 29.524895 30.051970 34.374177 32.700275
## [31] 33.995620 35.308172 34.386340 37.948157 35.499039 35.824972
## [37] 36.174576 36.371254 37.154311 38.994809 39.510486 40.847047
## [43] 41.955054 43.038653 44.261456 44.142346 47.378360 45.538520
## [49] 46.897647 47.540868 47.661865 49.037081 51.317713 51.517929
## [55] 51.411882 54.326265 54.906637 56.708430 56.822447 57.949992
## [61] 62.312497 60.359725 60.622232 61.112999 65.726156 69.697432
## [67] 71.469793 74.807487 73.111291 73.199080 75.044081 75.521881
## [73] 77.061164 77.593303 77.231588 77.571281 78.906150 78.107302
## [79] 82.192385 82.429359 83.250440 83.265989 86.554440 89.225977
## [85] 92.515509 93.597313 95.353037 95.664357 101.124724 100.296023
## [91] 101.960899 103.820493 108.287662 110.271867 109.145936 110.068930
## [97] 110.845498 112.810585 111.233366 112.251625
##
## $server
## [1] 1 2 2 1 1 1 2 1 2 1 2 2 2 2 1 1 2 1 2 1 2 1 2 2 1 2 1 1 1 2 2 2 1 1 2 2 2
## [38] 2 2 2 1 2 1 2 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1 2 1 2 2 2 2 1 2 1 2 2 2 1 2 1
## [75] 2 2 2 1 1 2 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 2 2 1 2 2
##
## $departures_df
## # A tibble: 100 × 6
## arrivals service departures waiting system_time server
## <dbl> <dbl> <dbl> <dbl> <dbl> <int>
## 1 0.835 1.48 2.31 0 1.48 1
## 2 1.61 0.643 2.26 0 0.643 2
## 3 2.48 4.97 7.45 0 4.97 2
## 4 3.52 2.26 5.77 0 2.26 1
## 5 6.23 0.827 7.06 1.11e-16 0.827 1
## 6 8.66 0.0802 8.74 0 0.0802 1
## 7 8.70 0.240 8.94 0 0.240 2
## 8 8.94 0.494 9.43 0 0.494 1
## 9 9.26 2.12 11.4 4.44e-16 2.12 2
## 10 9.80 5.77 15.6 8.88e-16 5.77 1
## # ℹ 90 more rows
##
## $queuelength_df
## times queuelength
## 1 0.0000000 0
## 2 0.8351502 1
## 3 0.8351502 0
## 4 1.6149204 1
## 5 1.6149204 0
## 6 2.4800390 1
## 7 2.4800390 0
## 8 3.5170734 1
## 9 3.5170734 0
## 10 6.2333778 1
## 11 6.2333778 0
## 12 8.6551312 1
## 13 8.6551312 0
## 14 8.6970683 1
## 15 8.6970683 0
## 16 8.9361382 1
## 17 8.9361382 0
## 18 9.2569652 1
## 19 9.2569652 0
## 20 9.8039929 1
## 21 9.8039929 0
## 22 10.5281949 1
## 23 11.3757433 0
## 24 12.7849749 1
## 25 13.5776391 2
## 26 14.6600654 1
## 27 14.8677619 0
## 28 17.7291293 1
## 29 17.7291293 0
## 30 18.0394731 1
## 31 18.0394731 0
## 32 18.5703102 1
## 33 18.5703102 0
## 34 20.0315027 1
## 35 20.0315027 0
## 36 21.2641641 1
## 37 21.2641641 0
## 38 21.9580817 1
## 39 21.9580817 0
## 40 22.2718155 1
## 41 22.2718155 0
## 42 24.0613601 1
## 43 24.0613601 0
## 44 24.1019273 1
## 45 24.1019273 0
## 46 24.4571916 1
## 47 24.4571916 0
## 48 24.7378956 1
## 49 25.1687467 0
## 50 25.6578960 1
## 51 25.6578960 0
## 52 26.5665831 1
## 53 26.5665831 0
## 54 27.5197471 1
## 55 27.5197471 0
## 56 29.7912086 1
## 57 29.7912086 0
## 58 31.8875416 1
## 59 31.8875416 0
## 60 32.4316099 1
## 61 32.4316099 0
## 62 33.0654739 1
## 63 33.0654739 0
## 64 33.5930032 1
## 65 33.9956202 0
## 66 34.1811984 1
## 67 34.3741771 0
## 68 35.2595582 1
## 69 35.2595582 0
## 70 35.3676861 1
## 71 35.3676861 0
## 72 35.5195774 1
## 73 35.5195774 0
## 74 35.6078329 1
## 75 35.8249720 0
## 76 36.2064114 1
## 77 36.2064114 0
## 78 36.7120581 1
## 79 36.7120581 0
## 80 37.8985783 1
## 81 37.8985783 0
## 82 38.4050704 1
## 83 38.4050704 0
## 84 40.3573856 1
## 85 40.3573856 0
## 86 41.8984823 1
## 87 41.8984823 0
## 88 42.2987565 1
## 89 42.2987565 0
## 90 42.6653513 1
## 91 42.6653513 0
## 92 43.3006978 1
## 93 43.3006978 0
## 94 44.3396175 1
## 95 44.3396175 0
## 96 45.4360689 1
## 97 45.4360689 0
## 98 46.1840481 1
## 99 46.1840481 0
## 100 47.1447370 1
## 101 47.1447370 0
## 102 47.5787204 1
## 103 47.5787204 0
## 104 48.6175532 1
## 105 48.6175532 0
## 106 50.0958386 1
## 107 50.0958386 0
## 108 50.7575400 1
## 109 50.7575400 0
## 110 50.8442185 1
## 111 51.3177130 0
## 112 53.4925792 1
## 113 53.4925792 0
## 114 54.8062151 1
## 115 54.8062151 0
## 116 56.1007633 1
## 117 56.1007633 0
## 118 56.4052132 1
## 119 56.4052132 0
## 120 57.0916033 1
## 121 57.0916033 0
## 122 59.8700121 1
## 123 59.8700121 0
## 124 60.3329204 1
## 125 60.3329204 0
## 126 60.5059411 1
## 127 60.5059411 0
## 128 61.0331934 1
## 129 61.0331934 0
## 130 64.5537651 1
## 131 64.5537651 0
## 132 68.7619280 1
## 133 68.7619280 0
## 134 69.2773228 1
## 135 69.2773228 0
## 136 71.6560229 1
## 137 71.6560229 0
## 138 72.1730810 1
## 139 72.1730810 0
## 140 73.0621363 1
## 141 73.1112910 0
## 142 73.8423089 1
## 143 73.8423089 0
## 144 73.9279409 1
## 145 74.8074866 0
## 146 75.4177487 1
## 147 75.4177487 0
## 148 75.8431313 1
## 149 75.8431313 0
## 150 75.8468090 1
## 151 75.9502214 2
## 152 76.7531247 3
## 153 77.0089428 4
## 154 77.0611638 3
## 155 77.2315878 2
## 156 77.5712807 1
## 157 77.5933029 0
## 158 81.8036271 1
## 159 81.8036271 0
## 160 81.9758680 1
## 161 81.9758680 0
## 162 82.3581159 1
## 163 82.3581159 0
## 164 82.4197388 1
## 165 82.4293594 0
## 166 85.9623302 1
## 167 85.9623302 0
## 168 87.0739548 1
## 169 87.0739548 0
## 170 91.9623625 1
## 171 91.9623625 0
## 172 92.8927545 1
## 173 92.8927545 0
## 174 94.1233060 1
## 175 94.1233060 0
## 176 95.0531674 1
## 177 95.0531674 0
## 178 97.6570389 1
## 179 97.6570389 0
## 180 99.9225390 1
## 181 99.9225390 0
## 182 101.5938106 1
## 183 101.5938106 0
## 184 103.5432006 1
## 185 103.5432006 0
## 186 107.9073170 1
## 187 107.9073170 0
## 188 108.6406345 1
## 189 108.6406345 0
## 190 109.0216440 1
## 191 109.0216440 0
## 192 109.0461071 1
## 193 109.1459361 0
## 194 109.2105353 1
## 195 110.0223933 2
## 196 110.0689299 1
## 197 110.1883876 2
## 198 110.2718671 1
## 199 110.3913536 2
## 200 110.8454979 1
## 201 111.2333657 0
##
## $systemlength_df
## times queuelength
## 1 0.0000000 0
## 2 0.8351502 1
## 3 1.6149204 2
## 4 2.2579783 1
## 5 2.3122100 0
## 6 2.4800390 1
## 7 3.5170734 2
## 8 5.7723238 1
## 9 6.2333778 2
## 10 7.0603633 1
## 11 7.4523421 0
## 12 8.6551312 1
## 13 8.6970683 2
## 14 8.7353017 1
## 15 8.9361382 2
## 16 8.9371759 1
## 17 9.2569652 2
## 18 9.4306284 1
## 19 9.8039929 2
## 20 10.5281949 3
## 21 11.3757433 2
## 22 12.7849749 3
## 23 13.5776391 4
## 24 14.6600654 3
## 25 14.8677619 2
## 26 15.3450989 1
## 27 15.5709986 0
## 28 17.7291293 1
## 29 18.0394731 2
## 30 18.2949640 1
## 31 18.3740748 0
## 32 18.5703102 1
## 33 19.3584635 0
## 34 20.0315027 1
## 35 20.2848380 0
## 36 21.2641641 1
## 37 21.7511194 0
## 38 21.9580817 1
## 39 22.1021533 0
## 40 22.2718155 1
## 41 24.0501536 0
## 42 24.0613601 1
## 43 24.1019273 2
## 44 24.3547158 1
## 45 24.4571916 2
## 46 24.7378956 3
## 47 25.1687467 2
## 48 25.2302835 1
## 49 25.5444244 0
## 50 25.6578960 1
## 51 25.8823934 0
## 52 26.5665831 1
## 53 27.5197471 2
## 54 29.5248951 1
## 55 29.7912086 2
## 56 30.0519703 1
## 57 31.2960330 0
## 58 31.8875416 1
## 59 32.4316099 2
## 60 32.7002746 1
## 61 33.0654739 2
## 62 33.5930032 3
## 63 33.9956202 2
## 64 34.1811984 3
## 65 34.3741771 2
## 66 34.3863402 1
## 67 35.2595582 2
## 68 35.3081723 1
## 69 35.3676861 2
## 70 35.4990395 1
## 71 35.5195774 2
## 72 35.6078329 3
## 73 35.8249720 2
## 74 36.1745758 1
## 75 36.2064114 2
## 76 36.3712541 1
## 77 36.7120581 2
## 78 37.1543111 1
## 79 37.8985783 2
## 80 37.9481573 1
## 81 38.4050704 2
## 82 38.9948089 1
## 83 39.5104858 0
## 84 40.3573856 1
## 85 40.8470471 0
## 86 41.8984823 1
## 87 41.9550539 0
## 88 42.2987565 1
## 89 42.6653513 2
## 90 43.0386529 1
## 91 43.3006978 2
## 92 44.1423456 1
## 93 44.2614557 0
## 94 44.3396175 1
## 95 45.4360689 2
## 96 45.5385200 1
## 97 46.1840481 2
## 98 46.8976472 1
## 99 47.1447370 2
## 100 47.3783601 1
## 101 47.5408681 0
## 102 47.5787204 1
## 103 47.6618650 0
## 104 48.6175532 1
## 105 49.0370806 0
## 106 50.0958386 1
## 107 50.7575400 2
## 108 50.8442185 3
## 109 51.3177130 2
## 110 51.4118821 1
## 111 51.5179294 0
## 112 53.4925792 1
## 113 54.3262648 0
## 114 54.8062151 1
## 115 54.9066366 0
## 116 56.1007633 1
## 117 56.4052132 2
## 118 56.7084298 1
## 119 56.8224472 0
## 120 57.0916033 1
## 121 57.9499915 0
## 122 59.8700121 1
## 123 60.3329204 2
## 124 60.3597252 1
## 125 60.5059411 2
## 126 60.6222320 1
## 127 61.0331934 2
## 128 61.1129994 1
## 129 62.3124966 0
## 130 64.5537651 1
## 131 65.7261555 0
## 132 68.7619280 1
## 133 69.2773228 2
## 134 69.6974318 1
## 135 71.4697930 0
## 136 71.6560229 1
## 137 72.1730810 2
## 138 73.0621363 3
## 139 73.1112910 2
## 140 73.1990801 1
## 141 73.8423089 2
## 142 73.9279409 3
## 143 74.8074866 2
## 144 75.0440809 1
## 145 75.4177487 2
## 146 75.5218807 1
## 147 75.8431313 2
## 148 75.8468090 3
## 149 75.9502214 4
## 150 76.7531247 5
## 151 77.0089428 6
## 152 77.0611638 5
## 153 77.2315878 4
## 154 77.5712807 3
## 155 77.5933029 2
## 156 78.1073021 1
## 157 78.9061501 0
## 158 81.8036271 1
## 159 81.9758680 2
## 160 82.1923846 1
## 161 82.3581159 2
## 162 82.4197388 3
## 163 82.4293594 2
## 164 83.2504397 1
## 165 83.2659894 0
## 166 85.9623302 1
## 167 86.5544398 0
## 168 87.0739548 1
## 169 89.2259771 0
## 170 91.9623625 1
## 171 92.5155094 0
## 172 92.8927545 1
## 173 93.5973133 0
## 174 94.1233060 1
## 175 95.0531674 2
## 176 95.3530373 1
## 177 95.6643568 0
## 178 97.6570389 1
## 179 99.9225390 2
## 180 100.2960225 1
## 181 101.1247245 0
## 182 101.5938106 1
## 183 101.9608992 0
## 184 103.5432006 1
## 185 103.8204928 0
## 186 107.9073170 1
## 187 108.2876622 0
## 188 108.6406345 1
## 189 109.0216440 2
## 190 109.0461071 3
## 191 109.1459361 2
## 192 109.2105353 3
## 193 110.0223933 4
## 194 110.0689299 3
## 195 110.1883876 4
## 196 110.2718671 3
## 197 110.3913536 4
## 198 110.8454979 3
## 199 111.2333657 2
## 200 112.2516251 1
## 201 112.8105846 0
##
## $servers_input
## [1] 2
##
## $state
## [1] 112.8106 112.2516
##
## 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.133
## Mean response time:
## 1.14
## Utilization factor:
## 0.448014500398608
## Mean queue length:
## 0.119
## Mean number of customers in system:
## 1.01Jika 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