Saat kita mengantri di kasir supermarket, call center menahan panggilan, atau server web menangani request bersamaan, sistem di belakang layar adalah queue. Untuk memprediksi waktu tunggu rata-rata, panjang antrean puncak, dan utilisasi server, kita tidak bisa mengandalkan estimasi intuitif — kita perlu simulasi. Discrete event simulation adalah paradigma di mana kita melompat dari satu event ke event berikutnya (bukan increment waktu kecil-kecil), membuatnya sangat efisien. Pada Chapter ini kita akan menyimulasikan M/M/1 queue — model matematika klasik dengan kedatangan Poisson dan layanan eksponensial. Implementasinya memperlihatkan bagaimana priority queue (event queue) dan queue biasa (FIFO customer) saling melengkapi.

Discrete Event Simulation: Konsep #

Pada simulasi waktu diskrit, sistem berevolusi melalui event — titik waktu ketika sesuatu terjadi (kedatangan customer, selesainya layanan). Karena tidak ada perubahan antar event, kita melompat langsung dari satu event ke event berikutnya. Priority queue berisi event diurutkan berdasarkan waktu — event paling awal diproses lebih dulu.

KomponenStruktur DataPeran
Event queuepriority_queue<Event, vector<Event>, greater<Event>>Min-heap berdasarkan waktu
Customer queuequeue<int> FIFOCustomer menunggu giliran
RNG arrivalexponential_distribution<double>(1/lambda)Poisson process
RNG serviceexponential_distribution<double>(1/mu)Service eksponensial
StatisticsCounter skalarTotal arrival, completed, dll

M/M/1 Queue: Aturan dan Mekanisme #

Aturan #

Notasi M/M/1 (Kendall notation):

  • M pertama: Markovian (Poisson/exponential) arrival process dengan rate λ.
  • M kedua: Markovian service time dengan rate μ.
  • 1: satu server.

Utilisasi sistem: ρ = λ / μ. Bila ρ ≥ 1, sistem tidak stabil — antrian tumbuh tanpa batas. Bila ρ < 1, sistem stabil dengan metrik teoretis:

  • E[N] (panjang antrean rata-rata) = ρ / (1 - ρ)
  • E[T] (waktu di sistem rata-rata) = 1 / (μ - λ)
  • E[W] (waktu tunggu rata-rata) = ρ / (μ - λ)

Mekanisme di Balik Layar #

Saat arrival terjadi:

  1. Bila server idle → customer langsung dilayani, jadwalkan departure setelah service time.
  2. Bila server sibuk → customer masuk FIFO queue, menunggu giliran.

Saat departure terjadi:

  1. Hapus customer dari sistem.
  2. Bila queue tidak kosong → pop customer berikutnya, jadwalkan departure setelah service time.
  3. Bila queue kosong → set server menjadi idle.

Priority queue memastikan event diproses dalam urutan kronologis. Setiap event dapat menjadwalkan event baru (arrival berikutnya, departure) — paradigma event-driven.

Kompleksitas #

OperasiTimeSpace
Event pushO(log E)O(1) per event
Event popO(log E)O(1)
Customer queue push/popO(1)O(1)
Total simulationO(E log E), E = jumlah eventO(E) untuk event queue + O(N) untuk customer queue

Kode: Simulasi M/M/1 #

cpp 
#include <iostream>
#include <queue>
#include <vector>
#include <random>
#include <iomanip>
using namespace std;

struct Event {
    double time;
    int type;       // 0 = arrival, 1 = departure
    int customer_id;

    bool operator>(const Event& o) const { return time > o.time; }
};

class MM1Simulation {
public:
    MM1Simulation(double lambda, double mu, double sim_time)
        : lambda_(lambda), mu_(mu), sim_time_(sim_time),
          rng_(42), arrival_dist_(1.0/lambda), service_dist_(1.0/mu) {}

    void run() {
        // Event pertama: arrival customer 1
        double t = arrival_dist_(rng_);
        event_queue_.push({t, 0, 1});
        next_customer_ = 2;

        cout << "=== Simulasi M/M/1 Queue ===\n";
        cout << "lambda (arrival rate) = " << lambda_ << " cust/min\n";
        cout << "mu     (service rate) = " << mu_ << " cust/min\n";
        cout << "rho    (utilization)  = " << lambda_/mu_ << "\n";
        cout << "Sim time = " << sim_time_ << " min\n\n";

        cout << left << setw(8) << "Time"
             << setw(12) << "Event"
             << setw(12) << "Customer"
             << setw(15) << "Queue Size" << "\n";
        cout << "-------|------------|-----------|---------------\n";

        while (!event_queue_.empty()) {
            Event e = event_queue_.top(); event_queue_.pop();
            if (e.time > sim_time_) break;

            if (e.type == 0) {       // arrival
                total_customers_++;
                cout << left << setw(8) << fixed << setprecision(2) << e.time
                     << setw(12) << "arrival"
                     << setw(12) << e.customer_id
                     << setw(15) << queue_.size() << "\n";

                if (server_busy_) {
                    queue_.push(e.customer_id);
                } else {
                    // Langsung dilayani
                    server_busy_ = true;
                    double service_t = service_dist_(rng_);
                    event_queue_.push({e.time + service_t, 1, e.customer_id});
                    current_service_start_ = e.time;
                }

                // Jadwalkan arrival berikutnya
                double next_arr = e.time + arrival_dist_(rng_);
                event_queue_.push({next_arr, 0, next_customer_++});

            } else {                   // departure
                completed_customers_++;
                total_service_time_ += (e.time - current_service_start_);

                cout << left << setw(8) << fixed << setprecision(2) << e.time
                     << setw(12) << "departure"
                     << setw(12) << e.customer_id
                     << setw(15) << queue_.size() << "\n";

                if (!queue_.empty()) {
                    int next_cust = queue_.front(); queue_.pop();
                    double service_t = service_dist_(rng_);
                    event_queue_.push({e.time + service_t, 1, next_cust});
                    current_service_start_ = e.time;
                } else {
                    server_busy_ = false;
                }
            }
        }

        report();
    }

private:
    double lambda_, mu_, sim_time_;
    mt19937 rng_;
    exponential_distribution<double> arrival_dist_, service_dist_;
    priority_queue<Event, vector<Event>, greater<Event>> event_queue_;
    queue<int> queue_;       // FIFO: customer menunggu di antrian
    bool server_busy_ = false;
    int next_customer_ = 1;
    int total_customers_ = 0;
    int completed_customers_ = 0;
    double total_service_time_ = 0;
    double current_service_start_ = 0;

    void report() {
        cout << "\n=== Laporan Simulasi ===\n";
        cout << "Total arrival   : " << total_customers_ << " customer\n";
        cout << "Total completed : " << completed_customers_ << " customer\n";
        cout << "Sisa antrian    : " << queue_.size() << " customer\n";
        cout << "Total service   : " << fixed << setprecision(2)
             << total_service_time_ << " min\n";
        cout << "Avg service time: " << fixed << setprecision(2)
             << (completed_customers_ ? total_service_time_/completed_customers_ : 0)
             << " min\n";
    }
};

int main() {
    // lambda=0.8, mu=1.0 (rho=0.8), sim 20 min
    MM1Simulation sim(0.8, 1.0, 20.0);
    sim.run();
    return 0;
}

Output yang Dihasilkan:

text 
=== Simulasi M/M/1 Queue ===
lambda (arrival rate) = 0.8 cust/min
mu     (service rate) = 1 cust/min
rho    (utilization)  = 0.8
Sim time = 20 min

Time    Event       Customer    Queue Size
-------|------------|-----------|---------------
1.27    arrival     1           0
1.48    departure   1           0
2.48    arrival     2           0
2.96    arrival     3           0
3.04    arrival     4           1
3.39    departure   2           2
3.53    arrival     5           1
3.66    arrival     6           2
3.80    departure   3           3
3.86    departure   4           2
4.50    arrival     7           1
5.14    departure   5           2
5.14    departure   6           1
6.73    arrival     8           0
7.50    arrival     9           1
8.25    arrival     10          2
8.26    arrival     11          3
8.28    arrival     12          4
8.87    arrival     13          5
9.28    arrival     14          6
9.32    arrival     15          7
9.99    departure   7           8
10.26   departure   8           7
10.35   departure   9           6
11.32   departure   10          5
11.80   departure   11          4
12.23   arrival     16          3
12.74   arrival     17          4
14.31   arrival     18          5
15.22   arrival     19          6
15.70   arrival     20          7
15.71   arrival     21          8
15.89   departure   12          9
16.71   departure   13          8
17.20   departure   14          7
17.22   departure   15          6
17.48   departure   16          5
17.76   departure   17          4
17.99   arrival     22          3
18.74   arrival     23          4
18.91   departure   18          5
19.10   departure   19          4
19.59   departure   20          3
19.79   departure   21          2

=== Laporan Simulasi ===
Total arrival   : 23 customer
Total completed : 21 customer
Sisa antrian    : 1 customer
Total service   : 17.51 min
Avg service time: 0.83 min

Bedah Kode Baris-per-Baris #

  1. struct Event { double time; int type; int customer_id; bool operator>(const Event& o) const { return time > o.time; } };: tiap event memiliki waktu terjadinya, tipe (arrival/departure), dan customer yang terlibat. Operator > mengubah max-heap default menjadi min-heap — event dengan waktu terkecil keluar lebih dulu.
  2. priority_queue<Event, vector<Event>, greater<Event>> event_queue_;: event queue berbasis min-heap. greater<Event> memilih comparator yang mengembalikan true saat a > b, sehingga top() adalah event dengan time minimum.
  3. exponential_distribution<double> arrival_dist_(1.0/lambda);: distribusi eksponensial untuk arrival. Parameter rate λ diterjemahkan ke mean 1/λ. Saat dipanggil arrival_dist_(rng_), menghasilkan random variate dengan distribusi Poisson process inter-arrival.
  4. mt19937 rng_(42);: Mersenne Twister dengan seed deterministik (42) — menghasilkan output reproducible. Penting untuk debugging simulasi.
  5. if (server_busy_) queue_.push(e.customer_id);: bila server sibuk, customer masuk FIFO queue. Operasi O(1).
  6. double service_t = service_dist_(rng_); event_queue_.push({e.time + service_t, 1, e.customer_id});: jadwalkan departure untuk customer yang dilayani. Service time acak dari distribusi eksponensial; event departure ditempatkan di masa depan.
  7. double next_arr = e.time + arrival_dist_(rng_); event_queue_.push({next_arr, 0, next_customer_++});: jadwalkan arrival berikutnya. Poisson process: inter-arrival time eksponensial, sehingga setiap arrival men-trigger penjadwalan arrival berikutnya.
  8. if (!queue_.empty()) { int next_cust = queue_.front(); queue_.pop(); ... }: setelah departure, ambil customer berikutnya dari FIFO. Bila queue kosong, server idle.
  9. if (e.time > sim_time_) break;: stop simulasi pada batas waktu. Event yang tersisa di queue diabaikan.

Validasi terhadap Teori #

Untuk λ=0.8, μ=1.0 (ρ=0.8):

  • E[N] teoretis = ρ/(1-ρ) = 0.8/0.2 = 4 customer
  • E[T] teoretis = 1/(μ-λ) = 1/0.2 = 5 min
  • E[W] teoretis = ρ/(μ-λ) = 0.8/0.2 = 4 min

Pada simulasi kami, total service time 17.51 min untuk 21 customer → avg service ~0.83 min (mendekati 1/μ=1.0 dengan toleransi statistik). Untuk mendapatkan konvergensi yang lebih dekat ke teori, jalankan simulasi lebih lama (mis. 1000 min) dan rata-ratakan beberapa run dengan seed berbeda.

Varian Sistem Antrean #

NotasiArrivalServiceServerContoh
M/M/1PoissonExponential1Single teller bank
M/M/cPoissonExponentialcCall center
M/D/1PoissonDeterministic1Conveyor belt
M/G/1PoissonGeneral1Web server (mixed loads)
G/G/1GeneralGeneral1Worst-case bound
M/M/∞PoissonExponential∞Self-service

Aplikasi Simulasi Antrean #

DomainApa yang DisimulasikanManfaat
Call centerJumlah agen optimalMengurangi waktu tunggu
Server webKapasitas untuk peak loadCapacity planning
ManufakturThroughput lini produksiIdentifikasi bottleneck
TransportasiAntrian di traffic lightOptimasi timing sinyal
HealthcareAntrian pasien IGDAlokasi staf
Theme parkAntrean wahanaDesign fast-pass system

Ringkasan #

  • Discrete event simulation melompat antar event, bukan increment waktu kecil — sangat efisien.
  • M/M/1 queue: arrival Poisson, service exponential, satu server.
  • Priority queue berisi event (min-heap by time); FIFO queue berisi customer.
  • ρ = λ/μ harus < 1 untuk sistem stabil.
  • Random number generator dengan seed deterministik → output reproducible.
  • Varian M/M/c, M/G/1, dan lain-lain dapat disimulasikan dengan struktur yang sama.