Skip to content
Kembali ke hasil pencarian

Simulasi Antrean — Pemodelan dan Analisis Sistem Antrean Tunggu

Diperkenalkan oleh
Agner Krarup Erlang
Tahun
1909
Jenis
Stochastic simulation / analytical modeling
Keluarga
Simulation / optimization

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Simulasi Antrean menggabungkan teori antrean klasik dengan simulasi kejadian diskret untuk memodelkan sistem di mana entitas tiba, menunggu layanan, dan pergi.

Simulasi ini memprediksi metrik kinerja seperti waktu tunggu rata-rata, panjang antrean, dan utilisasi server, yang memungkinkan perencanaan kapasitas dan identifikasi hambatan di seluruh sistem layanan, manufaktur, kesehatan, dan jaringan.

Intuisi di balik metode

Setiap kali pelanggan menunggu dalam antrean — di bank, di ruang gawat darurat rumah sakit, atau di jaringan komputer — terbentuklah antrean. Perilaku sistem bergantung pada seberapa cepat entitas tiba, berapa lama layanan berlangsung, dan berapa banyak server yang ada. Simulasi Antrean menangkap dinamika ini dengan memutar ulang proses kedatangan dan layanan acak berkali-kali, mengukur waktu tunggu rata-rata dan kemacetan. Berbeda dengan formula murni, simulasi menangani jadwal yang kompleks, berbagai jenis antrean, dan distribusi non-standar yang tidak dapat diselesaikan oleh persamaan bentuk tertutup.

Sejarah

Teori antrean didirikan oleh insinyur Denmark Agner Krarup Erlang pada tahun 1909 saat mempelajari kemacetan pertukaran telepon di Copenhagen Telephone Company. Formula Erlang-B dan Erlang-C-nya masih digunakan hingga kini. Bidang ini diformalkan oleh Kendall (1953) dengan notasi-notasinya, dan oleh Kleinrock (1975) untuk jaringan komputer. Analisis antrean berbasis simulasi muncul ketika komputer membuat pemodelan stokastik skala besar menjadi layak pada tahun 1960-an–1970-an.

Kapan digunakan

Gunakan Simulasi Antrean ketika sistem melibatkan entitas yang menunggu sumber daya bersama dan Anda memerlukan prediksi kinerja kuantitatif — pusat panggilan, departemen darurat, lini manufaktur, jaringan komputer, pusat logistik. Lebih pilih simulasi daripada model antrean analitis ketika distribusi non-Markovian, proses layanan bergantung pada keadaan, atau beberapa antrean yang berinteraksi membuat solusi bentuk tertutup tidak dapat dipecahkan. JANGAN gunakan ketika sistem tidak memiliki dinamika kemacetan, ketika penjadwalan deterministik sudah cukup, atau ketika data sampel waktu kedatangan dan layanan terlalu jarang untuk menyesuaikan distribusi masukan secara andal.

Batasan dan pertimbangan

  • Membutuhkan data empiris yang cukup untuk menyesuaikan distribusi kedatangan dan layanan; model masukan yang buruk menghasilkan keluaran yang menyesatkan.
  • Estimasi keadaan tunak menuntut penghapusan periode pemanasan (warm-up) yang cermat dan perencanaan replikasi, yang tidak sepele.
  • Waktu berjalan simulasi bisa lama untuk jaringan yang kompleks atau estimasi kejadian langka.
  • Hasilnya adalah estimasi stokastik dengan interval kepercayaan, bukan nilai eksak — memerlukan interpretasi statistik.
  • Validasi model sangat penting tetapi sulit; model yang masuk akal dapat memberikan hasil yang bias secara sistematis jika asumsi salah.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Menangani distribusi kedatangan dan layanan yang kompleks, non-Markovian yang tidak dapat diatasi oleh formula antrean bentuk tertutup.
  • Memodelkan jaringan multi-server, multi-antrean dengan perutean, prioritas, dan buffer terbatas dalam kerangka kerja terpadu.
  • Hukum Little memberikan pemeriksaan konsistensi internal yang independen dari asumsi distribusi.
  • Mendukung analisis 'bagaimana-jika' (what-if) dan perencanaan kapasitas dengan memvariasikan parameter sistem tanpa eksperimen fisik.
  • Interval kepercayaan keluaran memberikan kuantifikasi ketidakpastian yang ketat secara statistik untuk pengambilan keputusan.
  • Telah divalidasi secara luas di berbagai domain: telekomunikasi, kesehatan, manufaktur, dan transportasi.

Penerapan

  • Perencanaan kapasitas departemen darurat rumah sakit dan optimasi prioritas triase.
  • Analisis kepatuhan tingkat layanan dan penentuan staf pusat panggilan.
  • Penentuan ukuran buffer router jaringan dan estimasi penundaan paket dalam telekomunikasi.
  • Analisis throughput lini manufaktur dan identifikasi hambatan.
  • Konfigurasi jalur pemeriksaan dan keamanan bandara untuk manajemen aliran penumpang.
  • Alokasi sumber daya komputasi awan dan penjadwalan pekerjaan di bawah beban kerja yang bervariasi.

Cara kerjanya

Cara kerjanya

1

Definisikan batas sistem: identifikasi jenis entitas (pelanggan, pekerjaan, paket), server (sumber daya), disiplin antrean (FIFO, prioritas, putaran-giliran), dan batas kapasitas. Tentukan topologi jaringan — antrean tunggal, antrean tandem, atau jaringan antrean umum dengan probabilitas perutean antar simpul.

2

Sesuaikan distribusi waktu kedatangan dan layanan dengan data yang diamati. Pilihan umum adalah kedatangan Poisson (laju lambda) dan waktu layanan Eksponensial (laju mu), membentuk keluarga M/M/c. Untuk sistem nyata, gunakan distribusi Erlang, Gamma, atau empiris yang disesuaikan melalui uji kecocokan (goodness-of-fit). Validasi model masukan sebelum menjalankan simulasi.

Rumus
\lambda \sim \text{Poisson}(\lambda),\quad S \sim \text{Exp}(\mu)
3

Pilih model notasi Kendall (A/B/c/K/N/D): distribusi kedatangan / distribusi layanan / server / kapasitas / populasi / disiplin. Verifikasi kondisi stabilitas rho = lambda dibagi (c kali mu) kurang dari 1; jika tidak, antrean akan tumbuh tanpa batas. Untuk kasus yang dapat dipecahkan secara analitis, hitung metrik keadaan tunak bentuk tertutup sebagai tolok ukur.

Rumus
\rho = \lambda / (c \cdot \mu) < 1
4

Jalankan simulasi kejadian diskret: kalender kejadian bergerak melalui kejadian kedatangan, kejadian mulai layanan, dan kejadian keberangkatan. Untuk setiap replikasi, entitas dihasilkan dari distribusi yang disesuaikan, dirutekan melalui sistem, dan statistik dikumpulkan. Jalankan replikasi yang cukup (atau satu putaran panjang dengan penghapusan periode pemanasan) untuk mencapai estimasi keadaan tunak.

5

Estimasi ukuran kinerja utama: jumlah rata-rata dalam sistem L, jumlah rata-rata dalam antrean Lq, waktu rata-rata dalam sistem W, dan waktu tunggu rata-rata Wq. Hukum Little (L = lambda kali W) menghubungkan kuantitas-kuantitas ini dan berfungsi sebagai pemeriksaan konsistensi. Hitung utilisasi server rho dan probabilitas menunggu atau diblokir.

Rumus
L = \lambda W,\quad W_q = L_q / \lambda
6

Buat interval kepercayaan untuk setiap metrik kinerja menggunakan rata-rata batch atau replikasi independen. Lakukan analisis sensitivitas dengan memvariasikan laju kedatangan, laju layanan, atau jumlah server untuk mengidentifikasi hambatan. Bandingkan alternatif desain (misalnya, menambahkan server, mengubah disiplin) menggunakan peringkat-dan-pemilihan (ranking-and-selection) atau reduksi varians bilangan-acak-umum (common-random-numbers).

Kesalahan umum

  • Mengabaikan periode pemanasan (transien) menyebabkan estimasi keadaan tunak yang bias yang mencampur perilaku sistem kosong awal dengan kinerja sebenarnya.
  • Mengasumsikan kedatangan Poisson tanpa menguji data; kedatangan yang terlalu tersebar (overdispersed) atau bergelombang (bursty) (misalnya, dalam jaringan) memerlukan distribusi berekor lebih berat.
  • Melaporkan satu putaran simulasi seolah-olah itu adalah hasil deterministik, tanpa interval kepercayaan atau replikasi.
  • Memperlakukan antrean yang tidak stabil (rho >= 1) seolah-olah mencapai keadaan tunak — model hanya akan menunjukkan antrean yang terus bertambah.
  • Mencampuradukkan throughput dengan utilisasi: server bisa 90% terutilisasi sementara throughput masih dibatasi oleh hambatan di hulu.

Pertanyaan yang sering diajukan

Kapan saya harus menggunakan simulasi daripada formula M/M/c?

Gunakan simulasi ketika distribusi layanan atau kedatangan sangat menyimpang dari eksponensial (misalnya, layanan deterministik, varians tinggi), ketika beberapa antrean berinteraksi dengan perutean, ketika server mengalami kerusakan atau memiliki jadwal, atau ketika Anda memerlukan kinerja transien (bergantung waktu) daripada rata-rata keadaan tunak.

Berapa banyak replikasi yang saya butuhkan?

Tidak ada jawaban universal. Studi percontohan 5–10 replikasi memperkirakan varians; kemudian gunakan formula n = (z * s / epsilon)^2 untuk menemukan jumlah yang dibutuhkan untuk lebar setengah epsilon yang diinginkan pada tingkat kepercayaan z. Biasanya 20–50 replikasi cukup untuk presisi sedang, tetapi masalah kejadian langka mungkin memerlukan ribuan.

Apa itu Hukum Little dan mengapa itu penting?

Hukum Little menyatakan L = lambda * W: jumlah rata-rata jangka panjang dalam sistem sama dengan laju kedatangan dikalikan waktu rata-rata yang dihabiskan dalam sistem. Hukum ini berlaku untuk hampir semua antrean stabil terlepas dari distribusinya dan berguna sebagai pemeriksaan kewarasan (sanity check) pada keluaran simulasi.

Bagaimana saya tahu jika antrean saya stabil?

Untuk antrean server tunggal, intensitas lalu lintas rho = lambda / mu harus kurang dari 1. Untuk c server, rho = lambda / (c * mu) < 1. Jika rho >= 1, antrean tidak stabil dan tumbuh tanpa batas; tidak ada distribusi keadaan tunak yang ada dan hasil simulasi akan menunjukkan waktu tunggu yang terus meningkat.

Bisakah simulasi antrean menangani antrean prioritas dan preemptive?

Ya. Simulasi kejadian diskret secara alami mengakomodasi beberapa kelas prioritas, penjadwalan preemptive dan non-preemptive, serta aturan prioritas dinamis. Hasil analitis hanya ada untuk M/M/c/PR (prioritas resume preemptive) di bawah kedatangan Poisson; untuk struktur prioritas lainnya, simulasi adalah pendekatan standar.

Metode terkait

Sumber

  1. Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. Wiley-Interscience, New York.

    ISBN: 978-0471491101
    Disalin.
  2. Law, A. M. (2015). Simulation Modeling and Analysis (5th ed.). McGraw-Hill Education, New York.

    ISBN: 978-0073401324
    Disalin.