2_Simulasi_Antrian

Sistem Antrian dengan Server Tunggal (M/M/1)

Notasi M/M/1 (notasi Kendall) berarti: waktu antar kedatangan berdistribusi eksponensial/Markovian (M pertama), waktu layanan juga berdistribusi eksponensial/Markovian (M kedua), dan jumlah server = 1.

Waktu antar kedatangan nasabah $A_{1}, A_{2}, A_{3}, ...$ adalah variabel random IID (independent identically distributed — mempunyai distribusi yang sama). Nasabah yang datang segera dilayani bila server kosong, dengan waktu layanan $S_{1}, S_{2}, S_{3}, ...$ (juga IID). Bila server busy, nasabah masuk ke antrian. Sistem antrian bersifat FIFO (first-in first-out) — yang paling depan dilayani terlebih dahulu.

Performansi yang Dihitung

Rata-rata delay nasabah $\hat{d} (n) = \frac{\sum _{i = 1}^{n} D _{i}}{n}$ , dimana $D_{i}$ adalah delay nasabah ke- $i$ .
Rata-rata panjang antrian $\overset{q}{^} (n) = \frac{\sum _{i = 0}^{\infty} i T _{i}}{T ( n )}$ , dimana $T_{i}$ adalah selang waktu di mana panjang antrian sama dengan $i$ , dan $T (n)$ adalah lamanya waktu simulasi sampai nasabah ke- $n$ . (Catatan: $\sum_{i = 0}^{\infty} i T_{i} = \int_{0}^{T (n)} Q (t) d t$ )
Utilisasi server $\overset{u}{^} (n) = \frac{\int _{0}^{T (n)} B ( t ) d t}{T ( n )}$ , dimana $B (t) = 1$ jika server busy pada saat $t$ , dan $0$ jika idle.

Ilustrasi Perhitungan

Misalkan jumlah nasabah $n = 6$ :

Inter-arrival time: $A_{1} = 0.4; A_{2} = 1.2; A_{3} = 0.5; A_{4} = 1.7; A_{5} = 0.2; A_{6} = 1.6; ...$
Service time: $S_{1} = 2.0; S_{2} = 0.7; S_{3} = 0.2; S_{4} = 1.1; S_{5} = 3.7; S_{6} = 0.6; ...$

Dari sini bisa dihitung waktu kedatangan kumulatif tiap nasabah, delay masing-masing (dimulai dari $D_{1} = 0$ karena nasabah pertama langsung dilayani), rata-rata panjang antrian (dengan menghitung $T_{i}$ = total waktu antrian berisi tepat $i$ nasabah, lalu $\overset{q}{^} (6) = \sum i T_{i} / T (6)$ ), serta utilisasi server dari grafik $B (t)$ (total waktu server busy dibagi total waktu simulasi). Pada contoh ini didapat $\overset{q}{^} (6) = 9.9/8.6 = 0.9$ dan $\overset{u}{^} (6) = 7.7/8.6 = 0.90$ .

Diagram Alir Event Kedatangan dan Keberangkatan

Simulasi M/M/1 berbasis event-driven, dieksekusi lewat dua rutin event: Arrival dan Departure.

Alur event kedatangan: jadwalkan kedatangan berikutnya → cek apakah server sedang busy → jika busy: tambah antrian (cek dulu apakah antrian penuh, jika penuh hentikan simulasi dengan pesan error) dan simpan waktu kedatangan nasabah tersebut → jika idle: delay = 0, catat statistik, tambah jumlah nasabah yang sudah dilayani, set server jadi busy, dan jadwalkan event keberangkatan untuk nasabah ini.

Alur event keberangkatan: cek apakah antrian kosong → jika kosong: set server jadi idle → jika tidak kosong: kurangi jumlah antrian, hitung delay nasabah yang mulai dilayani beserta statistiknya, jadwalkan event keberangkatan berikutnya, dan geser posisi tiap nasabah dalam antrian maju satu tempat.

Implementasi Program dalam C

Waktu antar kedatangan dan waktu layanan terdistribusi eksponensial. Untuk membangkitkan bilangan random dengan distribusi ini digunakan inverse transform:

$F (x) = 1 - e^{- x / β} = U ⟹ X = - β ln (1 - U)$

Struktur program C terdiri atas fungsi-fungsi utama:

initialize() — inisialisasi simclock, status server (IDLE), jumlah antrian (0), variabel statistik (semua 0), serta jadwal event kedatangan pertama.
timing() — menentukan tipe event berikutnya (kedatangan atau keberangkatan) dengan mencari time_next_event[i] yang paling kecil, lalu memajukan simclock.
arrive() — memproses event kedatangan: jadwalkan kedatangan berikutnya; jika server busy, tambah antrian (num_in_q) dan cek overflow terhadap Q_LIMIT; jika idle, delay = 0, tambah num_custs_delayed, set server busy, jadwalkan keberangkatan.
depart() — memproses event keberangkatan: jika antrian kosong, server jadi idle; jika tidak, kurangi antrian, hitung delay nasabah yang mulai dilayani (simclock - time_arrival[1]), jadwalkan keberangkatan berikutnya, dan geser array time_arrival.
update_time_avg_stats() — mengakumulasi area dari num_in_q dan server_status terhadap waktu (untuk menghitung rata-rata panjang antrian & utilisasi di akhir).
report() — mencetak rata-rata delay antrian, rata-rata jumlah dalam antrian, utilisasi server, dan waktu akhir simulasi.
expon(mean) — membangkitkan variate eksponensial: -mean * log(1 - u) dimana u adalah bilangan random [0,1].

float expon(float mean)
{
  float u;
  u = (float) random()/ (float) INT_MAX;
  return (-mean * log(1-u));
}

Sumber

Materi kuliah IF4021 Model dan Simulasi, minggu 3, “Contoh M/M/1” — berbasis Law & Kelton, Simulation Modeling and Analysis.

Flashcard

flashcards Apa yang dimaksud sistem antrian M/M/1, dan apa arti FIFO di dalamnya? :: Sistem antrian server tunggal dengan waktu antar kedatangan dan waktu layanan yang IID; FIFO berarti nasabah yang datang paling awal dilayani terlebih dahulu (first-in first-out). Bagaimana rumus rata-rata panjang antrian q̂(n), dan apa arti T_i di dalamnya? :: q̂(n) = (Σ i·T_i) / T(n), dimana T_i adalah total selang waktu di mana panjang antrian tepat berisi i nasabah, dan T(n) adalah lamanya waktu simulasi sampai nasabah ke-n. Distribusi apa yang dipakai untuk waktu antar kedatangan dan waktu layanan pada implementasi M/M/1 di materi ini, dan bagaimana rumus pembangkitannya? :: Distribusi eksponensial, dibangkitkan dengan inverse transform: X = -mean * ln(1 - U), dimana U adalah bilangan random uniform [0,1]. Pada event kedatangan (arrive), apa yang terjadi jika server dalam keadaan busy vs idle? :: Jika busy: nasabah ditambahkan ke antrian (num_in_q bertambah, dicek terhadap Q_LIMIT untuk overflow) dan waktu kedatangannya disimpan. Jika idle: delay = 0, nasabah langsung dilayani (server jadi busy), dan event keberangkatannya langsung dijadwalkan. Pada event keberangkatan (depart), apa yang dilakukan jika antrian tidak kosong? :: Jumlah antrian dikurangi 1, delay nasabah yang mulai dilayani dihitung (simclock dikurangi waktu kedatangannya), event keberangkatan berikutnya dijadwalkan, dan seluruh nasabah dalam antrian digeser maju satu posisi. Apa fungsi dari update_time_avg_stats() dalam program simulasi M/M/1? :: Mengakumulasi luas area (integral) dari jumlah dalam antrian dan status server terhadap waktu sejak event terakhir, sebagai dasar penghitungan rata-rata panjang antrian dan utilisasi server di akhir simulasi.

Catatan Kuliah

Penjelajah

2_Simulasi_Antrian_MM1