Samsico, Andreas Reynard (2026) Analisis Perbandingan Metode Klasik dan Variance Reduction Technique (VRT) pada Permasalahan Simulasi Antrian: SPOJ 34983 - Cairo Tower. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5025221020-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5025221020-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (4MB) | Request a copy |
Abstract
Studi kasus SPOJ 34983 – Cairo Tower merupakan representasi permasalahan simulasi antrean M/M/1 yang menuntut efisiensi komputasi tingkat tinggi. Tantangan komputasional utama dalam penyelesaian kasus ini adalah mengestimasi nilai ekspektasi waktu tunggu pengunjung—berdasarkan parameter jumlah replikasi (n), interval kedatangan (a), dan waktu pelayanan (s)—tanpa melampaui batasan ketat sumber daya memori dan batas waktu eksekusi yang ditetapkan oleh platform Sphere Online Judge (SPOJ). Penelitian ini mengusulkan optimalisasi algoritma simulasi melalui penerapan Variance Reduction Technique (VRT), secara spesifik menggunakan metode Control Variates (CV), yang kinerjanya dikomparasikan terhadap simulasi Monte Carlo klasik. Pendekatan CV diimplementasikan sebagai teknik analisis luaran (output analysis) untuk mereduksi varians statistik, sehingga konvergensi estimasi dapat dicapai secara lebih efisien. Evaluasi kinerja dari kedua metode tersebut diuji secara komprehensif melalui 11 (sebelas) skenario rancangan algoritma komparatif. Hasil pengujian empiris pada peladen (server) daring SPOJ menunjukkan bahwa keseluruhan variasi algoritma yang diusulkan berhasil memecahkan permasalahan dengan capaian skor akurasi sempurna (100). Secara performa, sistem menunjukkan efisiensi yang sangat tinggi dengan mencatatkan rata-rata waktu eksekusi 0,075 detik dan konsumsi memori 5,19 MB. Temuan paling signifikan dari penelitian ini adalah bahwa metode Control Variates terbukti mampu mempertahankan tingkat presisi estimasi yang ekuivalen dengan metode Monte Carlo klasik, namun dengan kebutuhan jumlah replikasi simulasi yang lebih minim. Walaupun infrastruktur peladen daring meredam signifikansi perbedaan waktu eksekusi antar-algoritma, pembuktian empiris ini memvalidasi ketahanan (robustness) metode VRT dalam mengoptimalkan simulasi antrean pada lingkungan komputasi dengan batasan sumber daya yang ekstrem.
=======================================================================================================================================
The SPOJ 34983 – Cairo Tower case study represents an M/M/1 queueing simulation problem that demands high-level computational efficiency. The primary computational challenge in solving this case is estimating the expected visitor waiting time—given the parameters of replication count (n), inter-arrival time (a), and service time (s)—without exceeding the strict memory constraints and execution time limits imposed by the Sphere Online Judge (SPOJ) platform. This research proposes the optimization of the simulation algorithm through the application of Variance Reduction Techniques (VRT), specifically utilizing the Control Variates (CV) method, whose performance is compared against the classic Monte Carlo simulation. The CV approach is implemented as an output analysis technique to reduce statistical variance, thereby achieving estimation convergence more efficiently. The performance evaluation of both methods was comprehensively tested through 11 (eleven) comparative algorithm design scenarios. Empirical testing results on the SPOJ online server demonstrate that all proposed algorithm variations successfully solved the problem, achieving a perfect accuracy score of 100. In terms of performance, the system exhibited exceptionally high efficiency, recording an average execution time of 0.075 seconds and a memory consumption of 5.19 MB. The most significant finding of this study is that the Control Variates method proved capable of maintaining a level of estimation precision equivalent to the classic Monte Carlo method, but with a substantially lower number of required simulation replications. Although the online server infrastructure dampened the significance of execution time differences among the algorithms, this empirical evidence validates the robustness of the VRT method in optimizing queueing simulations within computational environments subjected to extreme resource constraints.
Actions (login required)
 |
View Item |