SIMULASI SISTEM ANTRIAN SINGLE SERVER Sistem: himpunan entitas yang terdefinisi dengan jelas. Atribut: nilai data yang mengkarakterisasi entitas. List/file/set: entitas-entitas dengan properti yang sama. Record: dimiliki oleh setiap entitas yang berisi atribut-atribut entitas. Contoh: Sistem antrian single server Entitas: server → atribut:
status server (busy/idle) customer → atribut: waktu tiba
Simbol-simbol: ↑ Customer yang sudah selesai Server Customer yang sedang dilayani
Simulasi & Pemodelan
1
Customer yang sedang antri
Customer yang baru datang ↑ Definisi Masalah: Sistem antrian satu server dengan: A1, A2, ⋅⋅⋅ waktu antara kedatangan customer; merupakan variabel independen dan terdistribusi identik. Cara pelayanan:
FIFO (first in, first out); jika customer datang dan server sedang idle, langsung dilayani.
S1, S2, ⋅⋅⋅ waktu yang diperlukan server untuk melayani customer (tidak termasuk waktu tunggu customer di antrian). Variabel ini acak dan independen terhadap A. Simulasi dimulai dengan status: empty dan idle. Stopping time: setelah customer ke-n dilayani. Pengukuran kinerja: 1. Delay rata-rata ekspektasi di antrian yang dialami n customer → d(n).
Simulasi & Pemodelan
2
2.
3.
1.
Jumlah customer rata-rata ekspektasi pada antrian (tidak termasuk yang sedang dilayani) → q(n). Utilisasi server ekspektasi → u(n)
Delay rata-rata ekspektasi
Kata “ekspektasi” di atas berarti: pada waktu jalannya simulasi, delay rata-rata yang sebenarnya bergantung pada waktu antara datangnya customer (interarrival time) dan waktu pelayanan (service time) yang keduanya merupakan variabel acak. Dengan demkian, delay ratarata juga merupakan variabel acak. Yang ingin diestimasi adalah nilai ekspektasi dari variabel acak ini. Jika ada n customer dengan delay D1, D2, ⋅⋅⋅ , Dn, n
∑ Di i=1
d(n) = n Tidak tertutup kemungkinan adanya customer yang mengalami delay 0 karena langsung dilayani.
2.
Jumlah customer rata-rata ekspektasi
Pengukuran ini dilakukan dalam waktu kontinu dan bukan diskrit seperti delay di atas. Besaran-besaran yang dipakai: q(n) = jumlah rata-rata customer di antrian. Simulasi & Pemodelan
3
Q(t) =
T(n) = pi =
jumlah customer di antrian pada waktu t; t ≥ 0. (Tidak termasuk customer yang sedang dilayani). waktu untuk meneliti n delay. proporsi (antara 0 dan 1) Q(t) = i. ∞
q(n) =
∑ i pi i=0
pi
=
proporsi waktu yang terobservasi pada waktu simulasi di mana ada i customer di antrian.
q(n) dari simulasi: ∞
q(n) =
∑ i pi I=0
Ti
=
waktu total simulasi di mana panjang antrian adalah i. ∞
∑ i Ti i=0
q(n) = T(n) Gambar berikut ini mengilustrasikan jalur waktu, atau realisasi dari Q(t) untuk sistem ini dengan n = 6. Customer datang pada waktu 1.6, 2.1, 3.8, 4.0, 5.6, 5.8, dan 7.2. Waktu pergi customer (pelayanan selesai) adalah 2.4, 3.1, 3.3, 4.9, dan 8.6, dan simulasi berakhir pada waktu T(6) = 8.6.
Simulasi & Pemodelan
4
Q(t)
3
2
1
t 0 Datang
0.4 e1=0.4
Selesai
Simulasi & Pemodelan
1.6 e2=1.6
2.1 2.4 3.1 3.3 3.8 4.0 4.9 5.6 5.8 e3=2.1 e7=3.8 e10=5.6 e11=5.8 e8=4.0 e6=3.3 e4=2.4 e5=3.1
e9=4.9
5
7.2 e12=7.2
8.6
e13=8.6
Untuk menghitung q(n), harus dihitung dulu Ti yang dapat dibaca dari grafik pada interval di mana Q(t) ama dengan 0, 1, dst: T0 T1 T2 T3
∞
= (1.6-0.0) + (4.0-3.1) + (5.6-4.9) = 3.2 = (2.1-1.6) + (3.1-2.4) + (4.9-4.0) + (5.8-5.6) = 2.3 = (2.4-2.1) + (7.2-5.8) = 1.7 = (8.6-7.2) = 1.4
∑ i Ti = (0x3.2) + (1x2.3) + (2x1.7) + (3x1.4) = 9.9 i=0
dengan demikian estimasi dari jumlah di antrian rata-rata waktu pada simulasi ini adalah q(6) = 9.9/8.6 = 1.15 Penjumlahan Ti di atas adalah luas di bawah kurva Q(t) antara awal dan akhir simulasi, dan dapat dituliskan: ∞
T(n)
∑ i Ti = ∫ I=0
3.
Q(t) dt
0
Utilisasi server ekspektasi
Besaran ini merupakan pengukuran seberapa sibuknya server. Utilisasi ekspektai server adalah proporsi waktu simulasi (dari waktu 0 sampai T(n)) di mana server bekerja (tidak idle), sehingga merupakan angka antara 0 dan 1. Didefinisikan “busy function” (fungsi sibuk): B(t) = 1 jika server sibuk pada waktu t = 0 jika server idle (menganggur) pada saat t
Simulasi & Pemodelan
6
Dari contoh di atas: B(t)
1
t 0 Datang
0.4 e1=0.4
Selesai
Simulasi & Pemodelan
1.6 e2=1.6
2.1 2.4 3.1 3.3 3.8 4.0 4.9 5.6 5.8 e3=2.1 e7=3.8 e10=5.6 e11=5.8 e8=4.0 e6=3.3 e4=2.4 e5=3.1
e9=4.9
7
7.2 e12=7.2
8.6
e13=8.6
(3.3 - 0.4) + (8.6 - 3.8) u(n) =
7.7 =
8.6
= 0.90 8.6
Pembilang pada persamaan di atas dapat dianggap sebagai luas di bawah fungsi B(t) selama simulasi: T(n)
∫ 0
B(t) dt
u(n) = T(n)
KESIMPULAN: Delay rata-rata di antrian merupakan contoh dari statistik waktu diskrit. Jumlah rata-rata waktu di antrian dan proporsi waktu di mana server sibuk adalah contoh statistik waktu kontinu. Event untuk sistem ini adalah datangnya customer dan pergi (selesai) -nya customer. Variabel status yang diperlukan untuk mengestimasi d(n), q(n), dan u(n) adalah: 1. status server (0 untuk idle; 1 untuk sibuk) 2. jumlah customer di antrian 3. waktu datang setiap customer yang antri 4. waktu event yang paling akhir.
Simulasi & Pemodelan
8
Penggambaran sistem dan representasi komputer Waktu inisialisasi =0
0
A D
Clock 0 Status server
Sistem
0 Jumlah di antrian
0
Waktu datang
Waktu event terakhir
Pencacah Statistik
0
0
Jumlah ter-delay
Delay total
Representasi komputer
Simulasi & Pemodelan
0.4 ∞ Event list
9
0 Luas di bawah Q(t)
0 Luas di bawah B(t)
Waktu datang = 0.4
0.4
A D
Clock 1
0
0.4
1.6 2.4 Event list
0.4 Status server
Sistem
Jumlah di antrian
Waktu datang
Waktu event terakhir
Pencacah Statistik
1
0
Jumlah ter-delay
Delay total
Representasi komputer
Simulasi & Pemodelan
10
0 Luas di bawah Q(t)
0 Luas di bawah B(t)
Beberapa komentar khusus mengenai contoh di atas: Elemen kunci dari dinamika simulasi mungkin adalah interaksi antara clock simulasi dan event list. Event list dipertahankan, dan clock simulasi melompat ke event berikutnya, dengan cara menscan event list. Sementara memproses suatu event, tidak ada waktu “simulasi” yang berjalan. Kondisi seperti tidak adanya customer yangantri pada saat customer sebelumnya selesai harus diakomodasi. Pada simulasi tanpa FIFO, tetapi dengan waktu tersingkat didahulukan, mungkin ada 2 atau lebih customer dengan waktu proses yang sama. Harus dibuat aturan pemilihan pada kondisi semacam ini.
Organisasi dan Logika Program Alasan pemilihan bahasa pemrograman umum seperti Pascal, dan bukan bahasa simulasi yang lebih powerful adalah: Dengan belajar mensimulasi dengan bahasa pemrograman umum, programmer harus memperhatikan setiap detil, sehingga pemahaman simulasi akan lebih dalam. Walaupun banyak bahasa simulasi yang sangat baik, biasanya tetap dibutuhkan paling tidak sebagian dari simulasi yang kompleks dibuat dalam bahasa pemrograman umum. Bahasa pemrograman umum banyak tersedia, dan simulasi secara keseluruhan masih banyak yang ditulis dengan cara ini.
Simulasi & Pemodelan
11
Definisi masalah: Simulasi akan berakhir setelah n = 1000 delay telah terselesaikan. Waktu antara kedatangan dan waktu pelayanan (interarrival dan service) dimodelkan sebagai variabel acak dari distribusi eksponensial dengan mean 1 menit untuk waktu antara kedatangan dan 0.5 menit untuk waktu pelayanan Deskripsi event Tipe event Kedatangan customer pada sistem 1 Perginya customer dari sistem setelah pelayanan 2 selesai
Simulasi & Pemodelan
12
Flowchart untuk rutin kedatangan Event kedatangan
Jadwalkan event kedatangan berikutnya
Ya
Server sibuk?
Tambahkan 1 ke jumlah di antrian
Tulis pesan error; stop simulasi
Ya
Tidak
Set delay =0 untuk customer ini dan kumpulkan statistik
Antrian penuh? Tambahkan 1 ke jumlah cust. yg tertunda
Tidak Simpan waktu datang customer ini
Buat server sibuk
Jadwalkan event selesai untuk cust. ini
Return
Flowchart untuk rutin kepergian (selesai) Simulasi & Pemodelan
13
Event kepergian
Ya
Antrian kosong?
Jadikan server idle
Tidak
Kurangkan 1 dari jumlah di antrian
Hapus event kepergian dari perhitungan
Hitung delay cust. yg baru dilayani dan kumpulkan statistik
Tambahkan 1 ke jumlah customer yg tertunda Jadwalkan event selesai untuk cust. ini
Majukan cust. di antrian (jika ada) 1 posisi
Return
Output Simulasi: Simulasi & Pemodelan
14
Contoh laporan output, model antrian: Single-server queueing system Mean interarrival time 1.000 minutes Mean service time 0.500 minutes Number of customers 1000 Average delay in queue Average number in queue Server utilization Time simulation ended
0.430 minutes 0.418 0.460 1027.915 minutes
Kriteria Pemberhentian (Stopping) Alternatif Untuk banyak model dunia riil, simulasi berhenti setelah waktu tertentu. Graf event, model antrian
Kedatangan
Kepergian
Graf event, model antrian dengan event “mendapat pelayanan” yang terpisah
Kedatangan
Simulasi & Pemodelan
Mendapat pelayanan
Kepergian
15
