ANALISIS KINERJA SISTEM ANTRIAN M/M/1/N Florensa Br Ginting Dosen Pembimbing : Ir. M. Zulfin, MT Konsentrasi Teknik Telekomunikasi, Departemen Teknik Elektro Fakultas Teknik Universitas Sumatera Utara (USU) Jl. Almamater, Kampus USU Medan 20155 INDONESIA e-mail:
[email protected] or
[email protected]
Abstrak Sistem antrian sangat banyak terdapat dalam dunia nyata, diantaranya pada loket penjualan karcis, transaksi di bank, aliran paket pada jaringan data dan yang lainnya. Sistem antrian M/M/1/N adalah sistem antrian dengan satu pelayan (server) dengan tempat tunggu yang terbatas. Sistem antrian seperti ini banyak sekali penerapannya. Salah satu permasalahan pada sistem antrian adalah apabila laju kedatangan melebihi laju pelayanan yang menyebabkan sebagian paket akan diblok apabila tempat antri sudah penuh. Kondisi seperti ini apabila berlanjut dapat menyebabkan keluhan pelanggan terhadap kinerja sistem tersebut yang pada akhirnya pelanggan akan mencari sistem yang lebih baik. Tulisan ini mengenai analisis kinerja sistem antrian M/M/1/N yang terdapat pada sebuah jaringan paket data. Perolehan kinerja dilakukan secara simulasi dan secara teoritis. Selanjutnya kedua hasil analisis tersebut dibandingkan.Dari analisis yang dilakukan diperoleh bahwa untuk utilisasi sistem (ρ) = 5 diperoleh bahwa hasil simulasi hampir mendekati hasil teori. Pada pelanggan yang dibatasi (N) = 10 diperoleh ratarata waktu antri yaitu 0,0177 dengan 0,0175. Untuk rata-rata waktu transaksi diperoleh yaitu 0,007 dengan 0,01. Untuk rata-rata waktu dalam sistem yaitu 0,0248 dengan 0,0195. Untuk rata-rata jumlah paket dalam antri yaitu 9 dengan 8,75, rata-rata jumlah paket dalam fasilitas pelayanan yaitu 0,9833 dengan 1. Untuk rata-rata jumlah paket dalam sistem yaitu 10 dengan 9,75. Kata kunci: Sistem Antrian M/M/1/N, Kinerja Antrian M/M/1/N
melihat masalah antrian merupakan topik yang sangat menarik untuk dibahas lebih dalam. Dengan demikian, maka pada tulisan ini mengangkat masalah sistem antrian, karena sistem antrian ini paling banyak dijumpai dalam kehidupan sehari-hari. Sistem antrian M/M/1/N merupakan sistem antrian satu server yang membatasi pelanggan sebanyak N. Jika sudah ada N pelanggan dalam sistem, maka pelanggan yang tiba berikutnya ditolak. Sistem antrian M/M/1/N dibahas didalam tulisan ini adalah sistem M/M/1/N yang terdapat pada simpul switching dalam jaringan data. Antrian disebabkan oleh kebutuhan akan layanan melebihi kemampuan (kapasitas) pelayanan atau fasilitas layanan, sehingga pengguna fasilitas yang tiba tidak bisa segera mendapat layanan disebabkan kesibukan layanan. Pada banyak hal, tambahan fasilitas pelayanan dapat diberikan untuk mengurangi antrian atau untuk mencegah timbulnya antrian. Akan tetapi biaya karena memberikan pelayanan tambahan, akan menimbulkan pengurangan keuntungan mungkin sampai di bawah tingkat
1. Pendahuluan Pada kehidupan seperti sekarang ini, semua masyarakat ingin serba cepat dalam segala kegiatan. Kecepatan dan penghematan waktu sangat menunjang untuk menjalani segala kegiatan kehidupan. Salah satu kegiatan yang memerlukan kecepatan dan penghematan waktu adalah antrian. Dalam kehidupan sehari-hari seseorang sering mengalami hal untuk menunggu antrian dengan waktu yang lama dan ini merupakan suatu hal yang sangat membosankan. Menunggu antrian yang panjang ini dapat disebabkan oleh kurangnya fasilitas untuk melayani masyarakat atau jumlah loket pelayanan yang ada belum memadai untuk melayani masyarakat, serta kurang sigapnya para pelayanan untuk melayani masyarakat atau konsumen. Contoh-contoh kasus antrian dalam kehidupan sehari-hari misalnya antrian pembelian tiket bioskop, antrian pembelian BBM, antrian mahasiswa membayar uang kuliah, antrian pada nasabah BANK, antrian pada simpul switching di jaringan data dan masih banyak lagi. Oleh sebab itu, penulis -98-
copyright @ DTE FT USU
SINGUDA ENSIKOM
VOL. 8 NO. 2/Agustus 2014 maka antrian akan semakin panjang sehingga tidak ada solusi keseimbangan. Pada sistem antrian M/M/1/N dengan buffer berhingga, λ dapat lebih besar dari N, karena kelebihan pelanggan akan ditolak.
yang dapat diterima. Sebaliknya, sering timbulnya antrian yang panjang akan mengakibatkan hilangnya pelanggan / nasabah[1]. 2. Antrian M/M/1/N
2.3 Rumus Teori Antrian M/M/1/N
Sistem antrian M/M/1/N merupakan variasi dari sistem antrian pelayanan saluran tunggal M/M/1, dimana panjang antrian atau kapasitas tunggu dibatasi maksimum N individu. Jumlah maksimum ini meliputi individu yang menunggu dan yang sedang dilayani. Bila individu mencapai N atau lebih, individu yang datang berikutnya akan ditolak atau meninggalkan antrian[2].
Untuk menghitung kinerja sistem antrian pada tulisan ini dilakukan juga secara teori. Adapun rumus teorinya terdapat pada persamaan 1,2,4, dan 5, yaitu[5] : 1. Rata – rata jumlah paket di dalam sistem L = N =
2.1 Sifat Antrian M/M/1/N Adapun sifat dari sistem antrian M/M/1/N adalah sebagai berikut; a. Sumber kedatangan terdistribusi Poisson ( Markov) b. Distribusi service time; eksponensial negative (Markov) c. Hanya ada satu server d. Disiplin antrian : FIFO (First In First Out) e. Kapasitas terbatas hanya untuk N pelanggan dalam sistem[3]
−
(
).
(1)
2. Rata-rata jumlah pelanggan di tempat antri L = N – (1 − P ) (2) jika nilai ρ ≠ 0 terlebih dahulu dicari Dimana dengan Persamaan 3 : P = (3) 3. Rata- rata waktu tunggu didalam sistem (4) W = 4. Rata – rata waktu tunggu pada antrian W =
2.2 Pemodelan Sistem Antrian Pelayanan Tunggal
(5)
3. Metodologi Penelitian Adapun metodologi penelitian dalam tulisan ini adalah sebagai berikut :
Adapun model dari sistem antrian dengan server tunggal yakni seperti yang ditunjukkan pada Gambar 1.
3.1 Menetapkan Model Antrian Model antrian M/M/1/N yang digunakan dalam tulisan ini adalah seperti Gambar 2.
Gambar 1. Model Antrian Pelayanan Tunggal Dapat dilihat sebuah model antrian pelayanan tunggal (single server). Paket – paket tiba secara acak, kemudian paket antri di dalam buffer sebelum dilayani oleh server. Setelah selesai dilayani, maka paket meninggalkan sistem antrian[4]. Pada umumnya untuk memecahkan masalah antrian yang sederhana formula-formula yang digunakan berdasarkan pada asumsi λ < µ, yaitu tingkat pelayanan harus lebih besar daripada kedatangan paket/pelanggan, dengan demikian semua pengantri akan dapat dilayani jika tidak
Gambar 2. Model Antrian M/M/1/N Untuk model antrian M/M/1/N ini diambil asumsi-asumsi sebagai berikut : a. Jumlah server : 1 b. Jumlah paket didalam sistem N: 10,15,20,25 c. Pola kedatangan paket:Eksponensial Negatif d. Pola pelayanan paket :Eksponensial Negatif e. Waktu antar kedatangan : 0,002 f. Waktu transaksi : 0,01 -99-
copyright @ DTE FT USU
SINGUDA ENSIKOM
VOL. 8 NO. 2/Agustus 2014 Setelah waktu antar kedatangan tiap paket diperoleh, maka diperoleh juga waktu transaksi tiap- tiap paket yang diperlihatkan pada Tabel 3. Waktu transaksi paket merupakan lamanya waktu setiap paket yang datang dilayani oleh server. Untuk memperoleh waktu transaksi paket digunakan hasil pembangkitan acak U(i) yang sama dengan waktu antar kedatangan dengan asumsi waktu transaksi = 0,01.
3.2 Membangkitkan Bilangan Acak Adapun pembangkitan bilangan acak dilakukan dengan menggunakan metode LCG. Asumsi yang diambil untuk membangkitkan bilangan acak yaitu : a = 21, c = 3, m = λ (500), dan Z[0] = 13. Hasil dari pembangkitan bilangan acak tersebut dapat dilihat pada Tabel 1. Tabel 1. Nilai Bilangan Acak Metode LCG i Z[i] U[i] 0 1 2 3 4 5 6 7 8 9 10
13 276 299 282 425 428 491 314 97 40 343
Tabel 3. Waktu Transaksi Paket ke i Waktu Transaksi (tt)
-0,55200 0,59800 0,56400 0,85000 0,85600 0,98200 0,62800 0,19400 0,08000 0,68600
1 2 3 4 5 6 7 8 9 10 4.
Setelah bilangan acak diperoleh, maka didapatkan hasil untuk waktu antar kedatangan setiap paket yang diperlihatkan pada Tabel 2. Waktu antar kedatangan ini merupakan variabel acak yang artinya waktu antar kedatangan tiap paket ke dalam server tidak terikat satu sama lainnya, dan waktunya berbeda – beda untuk setiap paket yang datang. Adapun waktu antar kedatangan diperoleh dari hasil pembangkitan bilangan acak U(i) dan dengan asumsi waktu antar kedatangan yaitu 0,002.
0.00594 0.00514 0.00573 0.00165 0.00155 0.00018 0.00465 0.01640 0.02526 0.00377
Hasil dan Pembahasan
Hasil hasil yang diperoleh dari simulasi yang dilakukan akan ditampilkan. Adapun hasilhasil yang diperoleh akan dibuat ke dalam tabel dan dilakukan perhitungan secara teoritis juga. Selanjutnya akan dibandingkan hasil-hasil dari simulasi dan perhitungan secara teoritis tersebut. 4.1 Hasil – hasil dari Simulasi Adapun hasil yang diperoleh terlebih dahulu adalah waktu kedatangan paket (tk) yang merupakan waktu paket tiba didalam sistem. Waktu kedatangan paket tersebut diperoleh dengan menambahkan waktu antar kedatangan sebelumnya dengan waktu antar kedatangan berikutnya. Waktu kedatangan paket hasil simulasi tampak pada Tabel 4.
Tabel 2. Waktu Antar Kedatangan Paket Paket ke i Waktu Antar Kedatangan 1 0.00119 2 0.00103 3 0.00115 4 0.00033 5 0.00031 6 0.00004 7 0.00093 8 0.00328 9 0.00505 10 0.00075
Tabel 4. Waktu Kedatangan Paket Paket ke i Waktu Kedatangan (tk) 1 0.00119 2 0.00222 3 0.00336 4 0.00369 5 0.00400 6 0.00403
-100-
copyright @ DTE FT USU
SINGUDA ENSIKOM 7 8 9 10
VOL. 8 NO. 2/Agustus 2014 Kemudian diperoleh waktu antri paket yang diperlihatkan pada Tabel 7. Waktu antri paket merupakan waktu setiap paket yang telah tiba didalam sistem mulai menunggu karena belum dapat dilayani oleh server sebab pada server masih terdapat paket yang sedang dalam proses pelayanan.
0.00496 0.00824 0.01330 0.01405
Waktu mulai transaksi paket adalah waktu ketika paket yang telah tiba didalam sistem saat mulai dilayani oleh server. Paket yang pertama langsung mulai dilayani karena tidak ada antrian dari paket sebelumnya, paket berikutnya dimulai jika paket sebelumnya telah selesai dilayani atau pada saat server sudah tidak ada lagi antrian. Waktu mulai transaksi hasil simulasi diperlihatkan pada Tabel 5.
Tabel 7. Waktu Antri(tan) Paket Waktu Antri (tan) ke i 1 0.00000 2 0.00491 3 0.00891 4 0.01431 5 0.01563 6 0.01714 7 0.01640 9 0.02912 10 0.05362
Tabel 5. Waktu Mulai Transaksi Paket ke i Waktu Mulai Transaksi (tm) 1 0.00119 2 0.00713 3 0.01227 4 0.01800 5 0.01962 6 0.02118 7 0.02136 8 0.02601 9 0.04241 10 0.06767
Lama waktu paket didalam sistem merupakan lamanya setiap paket tersebut berada didalam sistem yaitu lamanya paket tersebut mengantri dan paket tersebut dilayani oleh server.Waktu dalam sistem hasil simulasi diperlihatkan pada Tabel 8. Tabel 8. Waktu Dalam Sistem Paket Waktu Dalam Sistem (tds) ke i 1 0.00594 2 0.01006 3 0.01464 4 0.01594 5 0.01718 6 0.01733 7 0.02105 8 0.03417 9 0.05437 10 0.05739
Setelah diperoleh hasil waktu mulai transaksi, maka dapat diperoleh hasil untuk waktu selesai transaksi paket yang diperlihatkan pada Tabel 6. Waktu selesai transaksi paket merupakan waktu setiap paket keluar dari sistem antrian karena telah selesai dilayani oleh server. Waktu paket selesai dilayani dapat diperoleh dengan menambahkan waktu kedatangan paket dengan waktu lamanya transaksi paket tersebut dalam sistem. Tabel 6. Waktu Selesai Transaksi Paket ke i Waktu Selesai (ts) 1 2 3 4 5 6 7 8 9 10
Adapun tampilan simulasi hasil kinerja sistem antrian yang menggunakan pemograman bahasa C, untuk pelanggan yang dibatasi N=10 dapat dilihat pada Gambar 3. Pada gambar dapat dilihat hasil kinerja dari sistem antrian untuk pelanggan yang dibatasi (N)= 10. Terlebih dahulu dimasukkan nilai-nilai untuk a, c, m, Z[0], setelah itu dimasukkan nilai tar ( rata-rata waktu antar kedatangan) dan nilai ttr ( rata-rata waktu transaksi). Kemudian dimasukkan nilai N (batas pelanggan yang dapat masuk kedalam sistem). Setelah itu maka akan keluar hasil dari
0.00713 0.01227 0.01800 0.01962 0.02118 0.02136 0.02601 0.04241 0.06767 0.07144 -101-
copyright @ DTE FT USU
SINGUDA ENSIKOM
VOL. 8 NO. 2/Agustus 2014
kinerja sistem antrian. Untuk jumlah paket didalam sistem di simulasi disingkat menjadi ‘jpksrt’. Untuk jumlah paket rata-rata dalam antrian disingkat menjadi ‘jpkanrt’. Untuk jumlah paket rata-rata dalam pelayanan disingkat menjadi ‘jpkfprt’.
ρ= =
=5
Untuk memperoleh P dilakukan perhitungan dengan menggunakan Persamaan 3 sehingga dihasilkan : = P = =
.
= 8,19 . 10
.
Untuk memperoleh rata –rata jumlah pelanggan di dalam sistem digunakan Persamaan (1) yang menghasilkan : L = N =
−
(
= −1,25 − = −1,25 − Gambar 3. Tampilan Hasil Simulasi untuk pelanggan dibatasi (N)=10
).
.
.
.
.
=
. .
−
.
. .
= 9,75
Untuk memperoleh rata-rata jumlah pelanggan ditempat antri digunakan Persamaan (2), yang menghasilkan : L = L − (1 − P ) = 9,75 − (1 − 8,19 . 10 ) = 9,75 − 0.99999992 = 8,75
Dengan cara yang sama dapat diperoleh hasil untuk N=15, 20,25. Hasil selengkapnya diperlihatkan pada Tabel 9. Tabel 9. Hasil Perhitungan Kinerja Sistem Antrian M/M/1/N dengan Simulasi Kinerja Simulasi N=10 N=15 N=20 N=25 0,0177 0,0339 0,0477 0,0630 0,0070 0,0069 0,0068 0,0078 τ 0,0248 0,0408 0,0544 0,0708 τ 9 14 19 24 L L 0,9833 0,9886 0,9919 0,9939 10 15 20 25 L
Untuk memperoleh rata- rata waktu tunggu didalam sistem digunakan Persamaan (4), yang menghasilkan : W= =
,
= 0,0195
Untuk memperoleh rata – rata waktu tunggu pada antrian digunakan Persamaan (5), yang menghasilkan :
4.2 Hasil Perhitungan Kinerja Sistem Antrian M/M/1/N secara Teoritis
W =
Untuk mendapatkan kinerja sistem antrian M/M/1/N selain dengan menggunakan simulasi, dilakukan juga perhitungan secara teori. Perhitungan secara teori juga dihitung menggunakan N=10,15,20 dan 25. Perhitungan secara teori terlebih dahulu dilakukan dengan menggunakan N=10 yaitu pelanggan yang masuk kedalam sistem dibatasi hingga 10 paket saja. Telah diasumsikan saat simulasi bahwa rata-rata waktu antar kedatangan (tar)= 0.002 yang berarti bahwa λ = 1/0.002 = 500 paket/detik. Demikian juga rata-rata waktu transaksi (ttr) = 0.01 yang berarti bahwa µ = 100 paket/detik. Sehingga diperoleh :
Hasil perhitungan secara teori selengkapnya diperlihatkan pada Tabel 10.
=
,
= 0,0175
Tabel 10. Hasil Perhitungan Kinerja Sistem Antrian M/M/1/N secara teori Kinerja Teori N=10 N=15 N=20 N=25 0,0175 0,0275 0,0375 0,0495 0,01 0,01 0,01 0,01 τ 0,0195 0,0295 0,0395 0,0475 τ 8,75 13,75 18,75 23,75 L L 1 1 1 1 9,75 14,75 19,75 24,75 L -102-
copyright @ DTE FT USU
SINGUDA ENSIKOM
VOL. 8 NO. 2/Agustus 2014 Pinem ST.MT yang sudah membimbing penulis dalam menyelesaikan jurnal ini dan semua pihak yang tidak sempat penulis sebutkan satu persatu.
4.3 Perbandingan Hasil Simulasi dengan Hasil Perhitungan Teori Setelah dilakukan perhitungan secara simulasi dan dengan perhitungan secara teori, maka keduanya memperoleh hasil masing-masing. Hasil dari perhitungan secara simulasi dan teori tersebut kemudian dibandingkan agar dapat diketahui apakah hasil simulasi mendekati hasil teori atau tidak mendekati. Perbandingan hasil simulasi dengan hasil perhitungan secara teori dapat dilihat seperti pada Tabel 11.
7. Daftar Pustaka [1] http://armandjexo.blogspot.com/2012/04/te ori-antrian.html?m=1/diakses pada tanggal 21 Juli 2013. [2] Zulfin, M., 2008, “Diktat Kuliah : Teori Antrian”. Departemen Teknik Elekro Universitas Sumatera Utara, Medan. [3] Hendrawan , “Teori Antrian , Antrian Antrian Lain “.Institut Teknologi Bandung. [4] Nauvalisya, Viona. 2009, “Analisa Kinerja Jaringan Packet Switching Tipe Virtual Circuit dengan Menggunakan Algoritma Routing Bellman-Ford ”. Departemen Teknik Elektro Universitas Sumatera Utara, Medan [5] http://iitd.vlab.co.in/?sub=65&brch=182&s im=415&cnt=626/diakses pada tanggal 3Desember 2013.
Tabel 11. Perbandingan Hasil Simulasi dengan Hasil Teori
5.
Kesimpulan
Adapun kesimpulan yang dapat diambil dari tulisan ini untuk asumsi rata - rata waktu antar kedatangan = 0,002 dan rata – rata waktu transaksi = 0,01, diperoleh bahwa hasil simulasi hampir mendekati hasil teori. Pada pelanggan yang dibatasi (N) = 10 diperoleh rata-rata waktu antri yaitu 0,0177 dengan 0,0175. Untuk ratarata waktu transaksi yaitu 0,007 dengan 0,01. Untuk rata-rata waktu dalam sistem yaitu 0,0248 dengan 0,0195. Untuk rata-rata jumlah paket dalam antri yaitu 9 dengan 8,75. Untuk rata-rata jumlah paket dalam fasilitas pelayanan yaitu 0,9833 dengan 1. Untuk rata-rata jumlah paket dalam sistem yaitu 10 dengan 9,75.
6. Ucapan Terima Kasih Penulis mengucapkan terima kasih kepada M. Ginting dan S. br Tarigan selaku orang tua penulis, Ir. M. Zulfin, MT selaku dosen pembimbing, Rahmad Fauzi ST.MT, Maksum -103-
copyright @ DTE FT USU
