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")
arrivals <- cumsum(rexp(100))
head(arrivals)## [1] 0.1791802 1.3994321 1.8245555 1.8785778 2.6542950 2.7607712service <- rexp(100)
departures <- queue_step(arrivals, service = service, servers = 2)
departures## $departures
## [1] 0.493986 1.415403 3.011788 2.432606 4.619476 4.912031 5.102461
## [8] 5.010263 6.032202 6.264437 6.983208 8.622357 8.980979 12.075098
## [15] 11.414591 11.802086 11.862263 11.919448 13.433755 13.088280 14.509986
## [22] 13.510724 15.350269 19.533395 19.553113 19.741754 22.303309 22.934273
## [29] 25.562688 27.339255 28.112736 28.380375 28.826869 30.072324 32.255789
## [36] 34.684126 32.750171 36.689800 35.369322 37.670067 37.198399 37.920418
## [43] 37.860092 40.918222 40.454347 42.077314 43.098234 42.705061 43.320025
## [50] 44.324627 46.607316 48.660626 48.033764 48.809336 48.975401 49.921260
## [57] 49.803907 53.103909 49.991351 51.914479 53.113932 53.626677 54.686174
## [64] 55.102785 56.090519 57.010354 58.122173 61.062620 61.788229 65.066158
## [71] 63.658972 64.132565 64.439220 64.768646 66.693056 66.110262 66.159484
## [78] 66.911262 66.960837 67.411837 70.432105 70.262011 70.877435 72.368898
## [85] 75.078575 75.896603 76.512643 76.516723 77.201539 77.986701 78.595315
## [92] 79.920882 80.566898 81.724692 86.746503 84.914344 85.994885 86.738286
## [99] 86.753745 87.782807
##
## $server
## [1] 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 1 1 1 1 2 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
## [38] 1 2 2 1 1 2 2 1 1 2 1 1 2 1 2 1 1 2 1 2 2 1 1 1 2 1 2 1 2 1 2 1 2 1 1 1 1
## [75] 1 2 2 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 1 1 2
##
## $departures_df
## # A tibble: 100 × 6
## arrivals service departures waiting system_time server
## <dbl> <dbl> <dbl> <dbl> <dbl> <int>
## 1 0.179 0.315 0.494 0 0.315 1
## 2 1.40 0.0160 1.42 0 0.0160 2
## 3 1.82 1.19 3.01 0 1.19 1
## 4 1.88 0.554 2.43 0 0.554 2
## 5 2.65 1.97 4.62 2.22e-16 1.97 2
## 6 2.76 1.90 4.91 2.51e- 1 2.15 1
## 7 3.06 0.483 5.10 1.56e+ 0 2.05 2
## 8 3.53 0.0982 5.01 1.38e+ 0 1.48 1
## 9 3.65 1.02 6.03 1.36e+ 0 2.39 1
## 10 6.15 0.113 6.26 0 0.113 2
## # ℹ 90 more rows
##
## $queuelength_df
## times queuelength
## 1 0.0000000 0
## 2 0.1791802 1
## 3 0.1791802 0
## 4 1.3994321 1
## 5 1.3994321 0
## 6 1.8245555 1
## 7 1.8245555 0
## 8 1.8785778 1
## 9 1.8785778 0
## 10 2.6542950 1
## 11 2.6542950 0
## 12 2.7607712 1
## 13 3.0117884 0
## 14 3.0558095 1
## 15 3.5343999 2
## 16 3.6469047 3
## 17 4.6194755 2
## 18 4.9120305 1
## 19 5.0102631 0
## 20 6.1517960 1
## 21 6.1517960 0
## 22 6.3507917 1
## 23 6.3507917 0
## 24 7.3875563 1
## 25 7.3875563 0
## 26 8.4663863 1
## 27 8.4663863 0
## 28 9.2641767 1
## 29 9.2641767 0
## 30 9.4285498 1
## 31 9.4285498 0
## 32 9.7599505 1
## 33 11.1144014 2
## 34 11.3861124 3
## 35 11.4145909 2
## 36 11.6465049 3
## 37 11.6887883 4
## 38 11.8020859 3
## 39 11.8326509 4
## 40 11.8622632 3
## 41 11.9194483 2
## 42 12.0750983 1
## 43 12.8864343 2
## 44 13.0882804 1
## 45 13.4337549 0
## 46 14.3762860 1
## 47 14.3762860 0
## 48 16.2986983 1
## 49 16.2986983 0
## 50 19.2854078 1
## 51 19.2854078 0
## 52 19.4754201 1
## 53 19.5333954 0
## 54 20.9177942 1
## 55 20.9177942 0
## 56 21.5595643 1
## 57 21.5595643 0
## 58 23.9401191 1
## 59 23.9401191 0
## 60 26.5275557 1
## 61 26.5275557 0
## 62 27.2487350 1
## 63 27.2487350 0
## 64 27.2912481 1
## 65 27.3392549 0
## 66 27.6632839 1
## 67 27.7223351 2
## 68 28.1127356 1
## 69 28.3803747 0
## 70 30.8709383 1
## 71 30.8709383 0
## 72 32.3165296 1
## 73 32.3165296 0
## 74 32.4385756 1
## 75 32.4385756 0
## 76 34.9586904 1
## 77 34.9586904 0
## 78 35.0393674 1
## 79 35.0393674 0
## 80 35.8871957 1
## 81 35.8871957 0
## 82 35.9686490 1
## 83 36.6897995 0
## 84 37.4751457 1
## 85 37.4751457 0
## 86 37.5554396 1
## 87 37.6700671 0
## 88 39.2805364 1
## 89 39.2805364 0
## 90 39.7920208 1
## 91 39.7920208 0
## 92 41.2010177 1
## 93 41.2010177 0
## 94 41.5026530 1
## 95 41.5026530 0
## 96 41.6856156 1
## 97 42.0773145 0
## 98 42.2997974 1
## 99 42.5214019 2
## 100 42.7050608 1
## 101 43.0982341 0
## 102 46.5564623 1
## 103 46.5564623 0
## 104 47.5797217 1
## 105 47.5797217 0
## 106 47.7533513 1
## 107 47.7533513 0
## 108 48.4032125 1
## 109 48.4032125 0
## 110 48.8740578 1
## 111 48.8740578 0
## 112 48.8952460 1
## 113 48.8952460 0
## 114 49.1914515 1
## 115 49.1914515 0
## 116 49.4075645 1
## 117 49.5647365 2
## 118 49.8039071 1
## 119 49.9212596 0
## 120 50.8909939 1
## 121 50.8909939 0
## 122 51.1384768 1
## 123 51.2526391 2
## 124 51.9144789 1
## 125 53.0785923 2
## 126 53.1039086 1
## 127 53.1139323 0
## 128 54.9453470 1
## 129 54.9453470 0
## 130 55.0961081 1
## 131 55.0961081 0
## 132 56.3331959 1
## 133 56.3331959 0
## 134 57.4581147 1
## 135 57.4581147 0
## 136 57.5952121 1
## 137 57.5952121 0
## 138 58.5378143 1
## 139 58.5378143 0
## 140 59.5190841 1
## 141 59.5806473 2
## 142 60.0847378 3
## 143 60.2136756 4
## 144 60.4530168 5
## 145 60.9532438 6
## 146 61.0626202 5
## 147 61.7882285 4
## 148 62.9448802 5
## 149 63.2497802 6
## 150 63.6589718 5
## 151 64.1325652 4
## 152 64.2091754 5
## 153 64.4392197 4
## 154 64.7686459 3
## 155 65.0661580 2
## 156 65.8281977 3
## 157 66.1102620 2
## 158 66.1594841 1
## 159 66.6930558 0
## 160 67.3707839 1
## 161 67.3707839 0
## 162 69.0390443 1
## 163 69.0390443 0
## 164 69.4345243 1
## 165 69.4345243 0
## 166 70.1634050 1
## 167 70.2620107 0
## 168 71.2977679 1
## 169 71.2977679 0
## 170 74.4133486 1
## 171 74.4133486 0
## 172 75.2277685 1
## 173 75.2277685 0
## 174 75.9682016 1
## 175 75.9682016 0
## 176 76.4711891 1
## 177 76.4711891 0
## 178 76.9731419 1
## 179 76.9731419 0
## 180 77.0446421 1
## 181 77.0446421 0
## 182 77.2395833 1
## 183 77.2395833 0
## 184 77.4417940 1
## 185 77.9867005 0
## 186 79.0524734 1
## 187 79.0524734 0
## 188 79.9295565 1
## 189 79.9295565 0
## 190 83.9591190 1
## 191 83.9591190 0
## 192 84.3122136 1
## 193 84.3122136 0
## 194 84.4952531 1
## 195 84.9143436 0
## 196 85.1609379 1
## 197 85.7594477 2
## 198 85.9948854 1
## 199 86.7382861 0
## 200 86.8160792 1
## 201 86.8160792 0
##
## $systemlength_df
## times queuelength
## 1 0.0000000 0
## 2 0.1791802 1
## 3 0.4939860 0
## 4 1.3994321 1
## 5 1.4154033 0
## 6 1.8245555 1
## 7 1.8785778 2
## 8 2.4326057 1
## 9 2.6542950 2
## 10 2.7607712 3
## 11 3.0117884 2
## 12 3.0558095 3
## 13 3.5343999 4
## 14 3.6469047 5
## 15 4.6194755 4
## 16 4.9120305 3
## 17 5.0102631 2
## 18 5.1024611 1
## 19 6.0322022 0
## 20 6.1517960 1
## 21 6.2644370 0
## 22 6.3507917 1
## 23 6.9832079 0
## 24 7.3875563 1
## 25 8.4663863 2
## 26 8.6223571 1
## 27 8.9809786 0
## 28 9.2641767 1
## 29 9.4285498 2
## 30 9.7599505 3
## 31 11.1144014 4
## 32 11.3861124 5
## 33 11.4145909 4
## 34 11.6465049 5
## 35 11.6887883 6
## 36 11.8020859 5
## 37 11.8326509 6
## 38 11.8622632 5
## 39 11.9194483 4
## 40 12.0750983 3
## 41 12.8864343 4
## 42 13.0882804 3
## 43 13.4337549 2
## 44 13.5107240 1
## 45 14.3762860 2
## 46 14.5099864 1
## 47 15.3502691 0
## 48 16.2986983 1
## 49 19.2854078 2
## 50 19.4754201 3
## 51 19.5333954 2
## 52 19.5531125 1
## 53 19.7417539 0
## 54 20.9177942 1
## 55 21.5595643 2
## 56 22.3033093 1
## 57 22.9342735 0
## 58 23.9401191 1
## 59 25.5626876 0
## 60 26.5275557 1
## 61 27.2487350 2
## 62 27.2912481 3
## 63 27.3392549 2
## 64 27.6632839 3
## 65 27.7223351 4
## 66 28.1127356 3
## 67 28.3803747 2
## 68 28.8268688 1
## 69 30.0723235 0
## 70 30.8709383 1
## 71 32.2557891 0
## 72 32.3165296 1
## 73 32.4385756 2
## 74 32.7501711 1
## 75 34.6841264 0
## 76 34.9586904 1
## 77 35.0393674 2
## 78 35.3693224 1
## 79 35.8871957 2
## 80 35.9686490 3
## 81 36.6897995 2
## 82 37.1983986 1
## 83 37.4751457 2
## 84 37.5554396 3
## 85 37.6700671 2
## 86 37.8600921 1
## 87 37.9204185 0
## 88 39.2805364 1
## 89 39.7920208 2
## 90 40.4543473 1
## 91 40.9182221 0
## 92 41.2010177 1
## 93 41.5026530 2
## 94 41.6856156 3
## 95 42.0773145 2
## 96 42.2997974 3
## 97 42.5214019 4
## 98 42.7050608 3
## 99 43.0982341 2
## 100 43.3200250 1
## 101 44.3246267 0
## 102 46.5564623 1
## 103 46.6073164 0
## 104 47.5797217 1
## 105 47.7533513 2
## 106 48.0337644 1
## 107 48.4032125 2
## 108 48.6606260 1
## 109 48.8093356 0
## 110 48.8740578 1
## 111 48.8952460 2
## 112 48.9754006 1
## 113 49.1914515 2
## 114 49.4075645 3
## 115 49.5647365 4
## 116 49.8039071 3
## 117 49.9212596 2
## 118 49.9913506 1
## 119 50.8909939 2
## 120 51.1384768 3
## 121 51.2526391 4
## 122 51.9144789 3
## 123 53.0785923 4
## 124 53.1039086 3
## 125 53.1139323 2
## 126 53.6266772 1
## 127 54.6861745 0
## 128 54.9453470 1
## 129 55.0961081 2
## 130 55.1027848 1
## 131 56.0905189 0
## 132 56.3331959 1
## 133 57.0103540 0
## 134 57.4581147 1
## 135 57.5952121 2
## 136 58.1221730 1
## 137 58.5378143 2
## 138 59.5190841 3
## 139 59.5806473 4
## 140 60.0847378 5
## 141 60.2136756 6
## 142 60.4530168 7
## 143 60.9532438 8
## 144 61.0626202 7
## 145 61.7882285 6
## 146 62.9448802 7
## 147 63.2497802 8
## 148 63.6589718 7
## 149 64.1325652 6
## 150 64.2091754 7
## 151 64.4392197 6
## 152 64.7686459 5
## 153 65.0661580 4
## 154 65.8281977 5
## 155 66.1102620 4
## 156 66.1594841 3
## 157 66.6930558 2
## 158 66.9112619 1
## 159 66.9608373 0
## 160 67.3707839 1
## 161 67.4118370 0
## 162 69.0390443 1
## 163 69.4345243 2
## 164 70.1634050 3
## 165 70.2620107 2
## 166 70.4321047 1
## 167 70.8774347 0
## 168 71.2977679 1
## 169 72.3688977 0
## 170 74.4133486 1
## 171 75.0785751 0
## 172 75.2277685 1
## 173 75.8966028 0
## 174 75.9682016 1
## 175 76.4711891 2
## 176 76.5126430 1
## 177 76.5167226 0
## 178 76.9731419 1
## 179 77.0446421 2
## 180 77.2015388 1
## 181 77.2395833 2
## 182 77.4417940 3
## 183 77.9867005 2
## 184 78.5953151 1
## 185 79.0524734 2
## 186 79.9208825 1
## 187 79.9295565 2
## 188 80.5668980 1
## 189 81.7246916 0
## 190 83.9591190 1
## 191 84.3122136 2
## 192 84.4952531 3
## 193 84.9143436 2
## 194 85.1609379 3
## 195 85.7594477 4
## 196 85.9948854 3
## 197 86.7382861 2
## 198 86.7465027 1
## 199 86.7537447 0
## 200 86.8160792 1
## 201 87.7828071 0
##
## $servers_input
## [1] 2
##
## $state
## [1] 86.75374 87.78281
##
## 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.464
## Mean response time:
## 1.48
## Utilization factor:
## 0.576208536775958
## Mean queue length:
## 0.534
## Mean number of customers in system:
## 1.68Jika 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")
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)##
## 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