simulasi kejadian diskret discrete event...

Simulasi Kejadian Diskret(Discrete Event Simulation)

Kuliah Pemodelan Sistem Semester Genap 2015-2016

Fakultas InformatikaTelkom University

FIF Tel-U

Januari 2016

MZI (FIF Tel-U) Simulasi Kejadian Diskret Januari 2016 1 / 32

Acknowledgements

Slide ini disusun berdasarkan materi yang terdapat pada sumber-sumber berikut:

1 Simulation Modeling and Analysis, Edisi 3, 2000, oleh A. M. Law, W. D.Kelton (acuan utama).

2 Elements of Stochastic Process, oleh B. S. Gottfried.3 Discrete-Event Simulation, Edisi 4, oleh J. Banks, J. S. Carson II, B. L.Nelson, D. M. Nicol.

4 Slide kuliah Simulasi dan Pemodelan di Universitas Gunadarma oleh M. Iqbal.5 Slide kuliah Pemodelan Sistem di Telkom University oleh Tim DosenPemodelan dan Simulasi.

Beberapa gambar dapat diambil dari sumber-sumber di atas. Slide ini ditujukanuntuk keperluan akademis di lingkungan FIF Telkom University. Jika Andamemiliki saran/ pendapat/ pertanyaan terkait materi dalam slide ini, silakan kirimemail ke <pleasedontspam>@telkomuniversity.ac.id.

Bahasan

1 Definisi Terkait Simulasi Kejadian Diskret

2 Sifat-sifat Simulasi Kejadian Diskret

3 Contoh Kejadian Diskret

4 Mekanisme Memajukan Waktu

5 Komponen dan Organisasi Model pada Simulasi Kejadian Diskret

Definisi Terkait Simulasi Kejadian Diskret

Bahasan

Jenis-jenis simulasi

Simulasi statis vs simulasi dinamis.

Simulasi deterministik vs non-deterministik (stokastik).

Simulasi kejadian diskrit vs simulasi kejadian kontinu.

Simulasi Statis vs Simulasi Dinamis

Simulasi statis:

Simulasi yang tidak didasarkan pada waktu (peran variabel waktu tidakesensial pada simulasi statis).

Simulasi dapat mencakup sampel acak yang diambil untuk membangkitkansebuah hasil statistik (contohnya simulasi Monte Carlo).

Contoh: memilih portofolio saham, membuat desain jaringan BTS di JawaBarat.

Simulasi dinamis:

Simulasi yang meninjau lintasan waktu (timeline).

Simulasi memiliki mekanisme waktu (clock mechanism) yang digunakanuntuk menggerakkan waktu, sehingga status sistem berubah sesuaiperubahan waktu.

Contoh: simulasi proses manufaktur dan jasa.

Simulasi statis:

Simulasi dinamis:

Simulasi statis:

Simulasi dinamis:

Simulasi statis:

Simulasi dinamis:

Simulasi statis:

Simulasi dinamis:

Simulasi statis:

Simulasi dinamis:

Simulasi statis:

Simulasi dinamis:

Simulasi Deterministik vs Simulasi Probabilistik

Simulasi deterministik:

Simulasi tidak meninjau komponen masukan (input) yang bersifat acak(random).

Simulasi tidak memiliki keacakan (randomness) pada proses eksekusinya.Seluruh status sistem yang akan terjadi pada simulasi dapat ditentukansecara deterministik setelah data masukan (input) dan status awal (initialstate) ditentukan.

Simulasi probabilistik/ stokastik/ non-deterministik:

Setidaknya simulasi memiliki sebuah masukan (input) yang bersifat acak(random).

Simulasi memberikan keluaran (output) yang bersifat acak dengan sendirinya(self-random).

Setiap eksperimen simulasi dapat bervariasi secara statistik.

Simulasi tidak memiliki keacakan (randomness) pada proses eksekusinya.

Seluruh status sistem yang akan terjadi pada simulasi dapat ditentukansecara deterministik setelah data masukan (input) dan status awal (initialstate) ditentukan.

Kejadian Diskret

Kejadian diskret (discrete event) dari suatu sistem merupakan kejadian padasistem tersebut yang statusnya hanya berubah di titik-titik tertentu saja yangdapat dicacah (countable).

Status atau variabel status (state variable) merupakan kumpulan ataukombinasi dari satu atau lebih atribut yang menyatakan keterkaitan antarentitas pada sistem.Kejadian (event) pada sistem merupakan suatu kejadian dalam fungsi waktuyang dapat mengubah status suatu sistem.Suatu kejadian akan memulai/ memicu aktivitas yang terjadi atau dilakukanoleh sistem.

Contoh kejadian yang dapat terjadi pada suatu sistem:

kedatangan suatu entitas ke sebuah stasiun kerja (workstation), contoh:nasabah datang ke bank;kegagalan sumberdaya (resource), contoh: teller tidak dapat melayaninasabah;selesainya suatu aktivitas, contoh: nasabah selesai menyetor uang;akhir dari suatu shift, contoh: bank tutup pada pukul 15:00.

Kejadian Diskret

Kejadian diskret (discrete event) dari suatu sistem merupakan kejadian padasistem tersebut yang statusnya hanya berubah di titik-titik tertentu saja yangdapat dicacah (countable).Status atau variabel status (state variable) merupakan kumpulan ataukombinasi dari satu atau lebih atribut yang menyatakan keterkaitan antarentitas pada sistem.

Kejadian (event) pada sistem merupakan suatu kejadian dalam fungsi waktuyang dapat mengubah status suatu sistem.Suatu kejadian akan memulai/ memicu aktivitas yang terjadi atau dilakukanoleh sistem.

Kejadian Diskret

Kejadian diskret (discrete event) dari suatu sistem merupakan kejadian padasistem tersebut yang statusnya hanya berubah di titik-titik tertentu saja yangdapat dicacah (countable).Status atau variabel status (state variable) merupakan kumpulan ataukombinasi dari satu atau lebih atribut yang menyatakan keterkaitan antarentitas pada sistem.Kejadian (event) pada sistem merupakan suatu kejadian dalam fungsi waktuyang dapat mengubah status suatu sistem.

Suatu kejadian akan memulai/ memicu aktivitas yang terjadi atau dilakukanoleh sistem.

Kejadian Diskret

Kejadian diskret (discrete event) dari suatu sistem merupakan kejadian padasistem tersebut yang statusnya hanya berubah di titik-titik tertentu saja yangdapat dicacah (countable).Status atau variabel status (state variable) merupakan kumpulan ataukombinasi dari satu atau lebih atribut yang menyatakan keterkaitan antarentitas pada sistem.Kejadian (event) pada sistem merupakan suatu kejadian dalam fungsi waktuyang dapat mengubah status suatu sistem.Suatu kejadian akan memulai/ memicu aktivitas yang terjadi atau dilakukanoleh sistem.

Kejadian Diskret

kedatangan suatu entitas ke sebuah stasiun kerja (workstation), contoh:nasabah datang ke bank;

kegagalan sumberdaya (resource), contoh: teller tidak dapat melayaninasabah;selesainya suatu aktivitas, contoh: nasabah selesai menyetor uang;akhir dari suatu shift, contoh: bank tutup pada pukul 15:00.

Kejadian Diskret

kedatangan suatu entitas ke sebuah stasiun kerja (workstation), contoh:nasabah datang ke bank;kegagalan sumberdaya (resource), contoh: teller tidak dapat melayaninasabah;

selesainya suatu aktivitas, contoh: nasabah selesai menyetor uang;akhir dari suatu shift, contoh: bank tutup pada pukul 15:00.

Kejadian Diskret

kedatangan suatu entitas ke sebuah stasiun kerja (workstation), contoh:nasabah datang ke bank;kegagalan sumberdaya (resource), contoh: teller tidak dapat melayaninasabah;selesainya suatu aktivitas, contoh: nasabah selesai menyetor uang;

akhir dari suatu shift, contoh: bank tutup pada pukul 15:00.

Kejadian Diskret

Ilustrasi Grafis Kejadian Diskret

Pada grafik, status yang berubah adalah banyaknya pengunjung dalam restoran.

Ilustrasi Grafis Kejadian Diskret vs Kontinu

Sifat-sifat Simulasi Kejadian Diskret

Bahasan

Simulasi kejadian diskret biasanya bersifat stokastik, dinamis, dan diskret.

Stokastik/ non-deterministik/ probabilistik:

waktu antar kedatangan dan waktu layanan adalah variabel acak (randomvariable);waktu antar kedatangan dan waktu layanan memiliki suatu fungsi distribusikumulatif (cumulative distribution function, cdf ).

Diskret:status sistem hanya dapat berubah secara berhingga kali dalam satu selangwaktu yang terbatas;titik-titik waktu yang diamati direpresentasikan dalam bilangan naturaln = 0, 1, 2, . . ..

Dinamis:status simulasi berubah terhadap waktu;terdapat suatu mekanisme pada simulasi untuk memajukan waktu ke titiktertentu untuk mengetahui status yang mungkin terjadi berikutnya.

Stokastik/ non-deterministik/ probabilistik:waktu antar kedatangan dan waktu layanan adalah variabel acak (randomvariable);

waktu antar kedatangan dan waktu layanan memiliki suatu fungsi distribusikumulatif (cumulative distribution function, cdf ).

Stokastik/ non-deterministik/ probabilistik:waktu antar kedatangan dan waktu layanan adalah variabel acak (randomvariable);waktu antar kedatangan dan waktu layanan memiliki suatu fungsi distribusikumulatif (cumulative distribution function, cdf ).

Diskret:

status sistem hanya dapat berubah secara berhingga kali dalam satu selangwaktu yang terbatas;titik-titik waktu yang diamati direpresentasikan dalam bilangan naturaln = 0, 1, 2, . . ..

Diskret:status sistem hanya dapat berubah secara berhingga kali dalam satu selangwaktu yang terbatas;

titik-titik waktu yang diamati direpresentasikan dalam bilangan naturaln = 0, 1, 2, . . ..

Dinamis:

status simulasi berubah terhadap waktu;terdapat suatu mekanisme pada simulasi untuk memajukan waktu ke titiktertentu untuk mengetahui status yang mungkin terjadi berikutnya.

Dinamis:status simulasi berubah terhadap waktu;

terdapat suatu mekanisme pada simulasi untuk memajukan waktu ke titiktertentu untuk mengetahui status yang mungkin terjadi berikutnya.

Kejadian (Event)

Kumpulan kejadian (event) menggambarkan aliran proses pada sistem.

Aliran proses merupakan urutan kejadian yang diperlukan untuk menjalankansimulasi.

Suatu kejadian (event) dapat:

menciptakan suatu keterlambatan dalam simulasi untuk mereplikasi satulintasan waktu,memicu konsekuensi logis yang terkait dengan kejadian tersebut.

Suatu kejadian (event) dapat dibagi menjadi:

Kejadian terjadwal (scheduled event): kejadian yang dapat ditentukan dandijadwalkan sebelumnya.

Kejadian kondisional (conditional event): kejadian yang dipicu oleh kondisitertentu yang terjadi, bukan oleh lintasan waktu.

Kejadian (Event)

menciptakan suatu keterlambatan dalam simulasi untuk mereplikasi satulintasan waktu,

memicu konsekuensi logis yang terkait dengan kejadian tersebut.

Kejadian (Event)

Contoh Kejadian Diskret

Bahasan

Contoh: Single Server System

Entitas:

pelanggan (customer) dan pemberi layanan (server).

Atribut pelanggan: layanan yang diperlukan.

Atribut server : kemampuan server (service rate).

Kejadian: kedatangan pelanggan, selesainya pelanggan dilayani server,

Aktivitas: server melayani pelanggan, server menunggu pelanggan datang.

Kedatanganpelanggan

antrian serverPelangganSelesai

Entitas: pelanggan (customer) dan pemberi layanan (server).

Kedatanganpelanggan

Atribut pelanggan:

layanan yang diperlukan.

Kedatanganpelanggan

Atribut server :

kemampuan server (service rate).

Kedatanganpelanggan

Kejadian:

kedatangan pelanggan, selesainya pelanggan dilayani server,

Kedatanganpelanggan

Aktivitas:

server melayani pelanggan, server menunggu pelanggan datang.

Kedatanganpelanggan

Anjungan Tunai Mandiri (ATM)

Sistem ATM: Deskripsi

Entitas:

pelanggan (customer)/ nasabah dan ATM.

Atribut pelanggan/ nasabah: layanan yang diperlukan.

Atribut ATM: kemampuan layanan ATM (ATM service rate)

Kejadian: kedatangan pelanggan/ nasabah, selesainya pelanggan/ nasabahdilayani ATM,

Aktivitas: ATM melayani pelanggan/ nasabah, ATM menunggu pelanggan/nasabah datang.

Entitas: pelanggan (customer)/ nasabah dan ATM.

Atribut pelanggan/ nasabah:

layanan yang diperlukan.

Atribut ATM:

kemampuan layanan ATM (ATM service rate)

Kejadian:

kedatangan pelanggan/ nasabah, selesainya pelanggan/ nasabahdilayani ATM,

Aktivitas:

ATM melayani pelanggan/ nasabah, ATM menunggu pelanggan/nasabah datang.

Sistem ATM: Spesifikasi

Pelanggan tiba untuk memakai ATM dengan waktu antar kedatangan 3menit (yang terdistribusi eksponensial).

Antrian memiliki kapasitas tak terbatas untuk menampung sebanyak mungkinpelanggan yang datang.

ATM memiliki kapasitas satu pelanggan dalam satu waktu pelayanan.

Pelanggan rata-rata menghabiskan waktu 2.4 menit (yang terdistribusieksponensial).

Simulasi dijalankan ketika t = 0.

PermasalahanBagaimana cara mensimulasikan sistem ATM pada 22 menit pertama operasinyauntuk menentukan estimasi waktu tunggu (expected waiting time) seorangpelanggan dalam antrian?

Asumsi Sistem ATM

Tidak ada pelanggan di dalam ATM ketika sistem dijalankan untuk kalipertama, sehingga antrian kosong dan ATM tidak digunakan (idle).

Waktu bergerak dari antrian ke ATM sangat kecil sehingga dapat diabaikan.

Pelanggan diproses pada antrian dengan dasar first-in-first-out (FIFO) ataufirst-come-first-serve (FCFS).

ATM tidak pernah mengalami kerusakan, tidak pernah tidak dapat melayanipelanggan.

Asumsi Sistem ATM

Mekanisme Memajukan Waktu

Bahasan

Mekanisme memajukan waktu adalah dasar penting yang diperlukan untukmemodelkan sistem dinamis.

Setiap model mempunyai variabel yang dinamakan internal clock atausimulation clock.

Mekanisme memajukan waktu pada simulasi dinamis:

waktu dalam kaitan kejadian (next-event time advance, NETA): waktudimajukan berdasarkan kejadian berikutnya yang terjadi pada simulasi, dalamhal ini kejadian (event) pada sistem dijadikan sebagai patokan waktu;

waktu dibagi dalam selang yang sama (fixed-increment time advance, FITA):waktu dimajukan berdasarkan inkrementasi yang tetap, meskipun tidak adaperubahan kejadian pada sistem, dalam hal ini waktu pada sistem dapatdirepresentasikan dengan bilangan natural n = 0, 1, 2, . . ..

Waktu dalam Katian Kejadian (NETA) —ATM

Simulasi waktu dilakukan sebagai berikut.

Definisikan ti : waktu simulasi (clock simulation) pada langkah ke-i, dengan0 ≤ i ≤ N , dan N : banyaknya kejadian diskret yang ditinjau.

Pada saat simulasi dimulai t0 = 0.

t1 : nilai waktu simulasi ketika kejadian diskret pertama diproses.

t2 : nilai waktu simulasi ketika kejadian diskret ke dua diproses.

Secara umum ti : nilai waktu simulasi ketika kejadian diskret ke-i diproses,dengan 0 ≤ i ≤ N .

NETA —ATM

Pemodelan waktu (dengan NETA) dapat dilakukan sebagai berikut:

Misalkan ti : waktu kedatangan nasabah ke-i, dengan t0 = 0.

Misalkan Ai = ti − ti−1, nilai Ai merupakan interval (selisih) waktu antarakedatangan nasabah ke-(i− 1) dan nasabah ke-i.Dengan asumsi bahwa t0 < t1 < t2 < · · · , maka nilai dari Ai selalu positifuntuk semua i ≥ 0.Misalkan Si : lama ATM melayani nasabah ke-i (service time).

Misalkan Di : lama waktu tunda (delay) dalam antrian untuk pelanggan ke-i.

Misalkan ci = ti +Di + Si, nilai ci merupakan waktu pelanggan ke-i selesaidilayani dan keluar.

Misalkan ei : waktu terjadinya kejadian ke-i (dari semua jenis kejadian).

NETA —ATM

Misalkan Ai = ti − ti−1, nilai Ai merupakan interval (selisih) waktu antarakedatangan nasabah ke-(i− 1) dan nasabah ke-i.Dengan asumsi bahwa t0 < t1 < t2 < · · · , maka nilai dari Ai selalu positifuntuk semua i ≥ 0.

Misalkan Si : lama ATM melayani nasabah ke-i (service time).

NETA —ATM

Pemodelan ATM

Atribut entitas merupakan karakteristik entitas yang dipertahankan olehentitas tersebut sampai entitas keluar dari sistem.

Untuk simulasi ATM, salah satu atribut entitas adalah waktu kedatangannasabah (ti, i ≥ 1).

Variabel status:

Banyaknya entitas (nasabah) dalam antrian pada langkah ke-i, dinotasikandengan NQi.Status ATM pada langkah ke-i, dinotasikan dengan statusi, denganstatusi = idle bila ATM tidak dipakai dan statusi = busy bila ATM dipakai,dengan i ≥ 0.

Nilai dari ti, Si, dan Di bersifat probabilistik.Akibatnya nilai dari Ai dan ci juga bersifat probabilistik.Misalkan FA(x) : fungsi distribusi kumulatif dari probabilitas intervalkedatangan A1, A2, . . ., dan FS(x) : fungsi distribusi kumulatif dariprobabilitas lama waktu layanan S1, S2, . . ..

Pemodelan ATM

Atribut entitas merupakan karakteristik entitas yang dipertahankan olehentitas tersebut sampai entitas keluar dari sistem.Untuk simulasi ATM, salah satu atribut entitas adalah waktu kedatangannasabah (ti, i ≥ 1).

Variabel status:

Pemodelan ATM

Variabel status:

Banyaknya entitas (nasabah) dalam antrian pada langkah ke-i, dinotasikandengan NQi.

Status ATM pada langkah ke-i, dinotasikan dengan statusi, denganstatusi = idle bila ATM tidak dipakai dan statusi = busy bila ATM dipakai,dengan i ≥ 0.

Pemodelan ATM

Variabel status:

Pemodelan ATM

Variabel status:

Nilai dari ti, Si, dan Di bersifat probabilistik.

Akibatnya nilai dari Ai dan ci juga bersifat probabilistik.Misalkan FA(x) : fungsi distribusi kumulatif dari probabilitas intervalkedatangan A1, A2, . . ., dan FS(x) : fungsi distribusi kumulatif dariprobabilitas lama waktu layanan S1, S2, . . ..

Pemodelan ATM

Variabel status:

Nilai dari ti, Si, dan Di bersifat probabilistik.Akibatnya nilai dari Ai dan ci juga bersifat probabilistik.

Misalkan FA(x) : fungsi distribusi kumulatif dari probabilitas intervalkedatangan A1, A2, . . ., dan FS(x) : fungsi distribusi kumulatif dariprobabilitas lama waktu layanan S1, S2, . . ..

Pemodelan ATM

Variabel status:

Pemodelan Kejadian Diskret pada ATM

Pada waktu kejadian ke-0 terjadi (e0 terjadi), yaitu t0 = 0, ATM tidakdipakai (idle), sehingga status0 = idle. Kemudian t1 = t0 +A1, denganA1 = FA(t0).

Kita memiliki e0 = t0 = 0.

Selanjutnya waktu simulasi diubah menjadi waktu ketika kejadian e1 terjadi,yaitu t1.

Karena nasabah yang pertama datang langsung dilayani ATM (tidakmengantri), maka D1 = 0, kemudian status ATM diubah dari idle ke busy,yaitu status1 = busy.

Nilai c1 = t1 +D1 + S1 = t1 + 0 + S1 = t1 + S1, dengan S1 = t1 + FS(t0).

Selanjutnya:

Waktu kedatangan pelanggan ke dua diperoleh dari t2 = t1 +A2, denganA2 = FA(t1).

Kita dapat memperoleh e1 = t1.

Bila t2 < c1, atau artinya waktu kedatangan nasabah ke dua lebih cepat dariwaktu nasabah pertama selesai dilayani dan keluar, maka waktu simulasidimajukan dari t1 ke t2 (waktu kejadian ke dua).

Bila t2 < c1, maka status2 = busy, banyaknya pelanggan yang mengantripada langkah ke dua adalah 1 (pelanggan ke dua mengantri), yaituNQ2 = 1. Waktu kedatangan nasabah ke dua juga disimpan.

Lama waktu tunda untuk pelanggan ke dua adalah D2 = c1 − t2.Waktu pelanggan ke dua selesai dilayani dan keluar adalahc2 = t2 +D2 + S2 = t2 + c1 − t2 + S2 = c1 + S2. Nilai S2 diperoleh dariS2 = t2 + FS(t1).

Selanjutnya:

Lama waktu tunda untuk pelanggan ke dua adalah D2 = c1 − t2.

Waktu pelanggan ke dua selesai dilayani dan keluar adalahc2 = t2 +D2 + S2 = t2 + c1 − t2 + S2 = c1 + S2. Nilai S2 diperoleh dariS2 = t2 + FS(t1).

Selanjutnya:

Lama waktu tunda untuk pelanggan ke dua adalah D2 = c1 − t2.Waktu pelanggan ke dua selesai dilayani dan keluar adalahc2 = t2 +D2 + S2 =

t2 + c1 − t2 + S2 = c1 + S2. Nilai S2 diperoleh dariS2 = t2 + FS(t1).

Selanjutnya:

Waktu kedatangan pelanggan ke tiga diperoleh dari t3 = t2 +A3, denganA3 = FA(t2).

Bila t3 > c1, atau artinya waktu kedatangan nasabah ke tiga lebih lama dariwaktu nasabah pertama selesai dilayani dan keluar, maka waktu simulasidimajukan dari t2 ke t3 (waktu kejadian ke tiga).

Kita dapat memperoleh e3 = c1.

Ketika pelanggan ke tiga datang, maka pelanggan ke dua sedang berada didalam ATM. Akibatnya kita juga memiliki NQ3 = 1 (karena yang mengantrihanya pelanggan ke tiga).

Selanjutnya:

Komponen dan Organisasi Model pada Simulasi Kejadian Diskret

Bahasan

Komponen dan Organisasi Model pada SKD

Berikut beberapa komponen pada simulasi kejadian diskret.

Status sistem: kumpulan variabel status untuk menyatakan kondisi sistempada suatu waktu, pada model ATM contohnya statusi dan NQi.

Waktu simulasi (simulation clock): variabel yang memberikan nilai waktuketika suatu kejadian terjadi dalam suatu simulasi.

Daftar kejadian (event list): daftar kejadian apa saja yang akan terjadi.

Penghitung statistik (statistical counter): variabel-variabel yang dipakaiuntuk menghitung performansi sistem, pada model ATM contohnya:rata-rata waktu mengantri, rata-rata waktu layanan.

Komponen Program Simulasi

Initialization routine: bagian program simulasi untuk menginialisasi t0 = 0.

Timing routine: bagian program untuk menentukan kejadian berikutnya danmemajukan waktu ke saat kejadian tersebut terjadi.

Event routine: bagian program untuk memperbarui (meng-update) statussistem saat suatu kejadian berlangsung.

Library routine: sekumpulan sub program untuk membangkitkan nilai acakdari distribusi probabilitas yang ditentukan sebagai bagian dari simulasi.

Report generator : bagian program yang menghitung perkiraan danmengeluarkan laporan hasil simulasi dalam bentuk tabel, grafik, atau nilailainnya.

Main program: bagian program yang memanggil timing routine untukmenentukan kejadian berikutnya dan mengalihkan kontrol ke event routineyang sesuai untuk memperbarui status sistem; bagian ini juga berisi proseduruntuk menghentikan simulasi.

Struktur Data Kejadian

Kejadian disimpan secara terurut waktu.

Struktur data kejadian dapat berbentuk list/ array yang berisi data terurutwaktu.

List/ array tersebut berisi semua kejadian yang mungkin terjadi.

simulasi kejadian diskret discrete event...

Documents