Teori Antrian [PDF]

Citation preview

Teori Antrian Oleh : Niswatul Qona’ah, S.Si, M.Stat



Istilah dalam Sistem Antrian Sumber (Input) • Disebut juga populasi; pelanggan yang datang untuk minta jasa pelayanan. Perhitungan sumber lebih mudah untuk kasus infinite karena biasanya relatif besar. Asumsi umum dari sumber (input) mengikuti proses poisson, dan waktu antar kedatangan ke sistem antrian berdistribusi eksponensial dimana kedatangannya terjadi secara random. Antrian • Disebut juga garis tunggu ; jumlah pelanggan maksimum yang diijinkan untuk menunggu dilayani dalam sistem antrian. Antrian bisa finite atau infinite



Istilah dalam Sistem Antrian Disiplin Antrian • • • •



First Come-First Served (FCFS) / First In-First Out (FIFO) Prioritas Random Last In-First Out (LIFO)



Pelayanan • Single server, single phase -> hanya ada 1 server dan setiap pelanggan hanya dilayani 1 kali • Single server, multi phase -> hanya ada 1 server, setiap pelanggan dilayani lebih dari 1 kali proses pelayanan • Multi server, single phase -> ada lebih dari 1 server, setiap pelanggan hanya dilayani 1 kali proses pelayanan • Multi server, multi phase -> ada lebih dari 1 server, setiap pelanggan dilayani lebih dari 1 kali proses pelayanan



Terminologi dan Notasi ▪ Panjang antrian : jumlah pelanggan yang menunggu untuk dilayani ▪ N(t) : Jumlah pelanggan dalam sistem antrian pada waktu – t ▪ 𝑷𝒏 𝒕 : Probabilitas terdapat n pelanggan dalam sistem antrian pada waktu – t ▪ 𝒔 : Jumlah server (fasilitas pelayanan) parallel ▪ 𝝀𝒏 : Laju kedatangan rata-rata dalam sistem antrian, jika ada n pelanggan dalam sistem



(Ekspektasi jumlah kedatangan dalam sistem antrian persatuan waktu). Jika laju kedatangan konstan untuk setiap n, maka 𝝀𝒏 = 𝝀



Terminologi dan Notasi ▪



𝟏 𝝀



: Waktu antar kedatangan per satuan waktu yaitu selisih antara kedatangan dengan



kedatangan berikutnya ▪ 𝝁𝒏 : Laju pelayanan rata-rata pada sistem antrian, jika ada n pelanggan dalam sistem (Ekspektasi jumlah pelanggan yang dapat dilayani per satuan waktu). Jika laju pelayanan rata-rata setiap server konstan untuk setiap n, maka 𝝁𝒏 = 𝝁 ▪



𝟏 𝝁



: Waktu pelayanan per satuan waktu ; waktu yang digunakan server untuk melayani 1



pelanggan



Terminologi dan Notasi ▪ 𝝆 : Utilitas sistem (kegunaan sistem), besarnya 𝝆 = 𝝀/𝒔𝝁 ▪ 𝑳𝒒 : Panjang antrian; ekspektasi jumlah pelanggan dalam antrian (Rata-rata jumlah pelanggan yang sedang antri) ▪ 𝑳 : Ekspektasi jumlah pelanggan dalam sistem antrian (rata-rata jumlah pelanggan yang sedang antri dan dilayani) ▪ 𝑾 : Ekspektasi waktu menunggu dalam sistem antrian (Rata-rata waktu yang diperlukan dalam antrian dan pelayanan ▪ 𝑾𝒒 : Ekspektasi waktu menunggu dalam antrian (rata-rata waktu yang diperlukan untuk menunggu dalam antrian)



Proses Kelahiran dan Kematian ▪ Bentuk kelahiran adalah kedatangan pelanggan baru yang akan masuk sistem antrian. ▪ Bentuk kematian adalah kepergian pelanggan yang sudah dilayani Asumsi Proses Kelahiran dan Kematian a. Jika N(t)=n, maka waktu kelahiran dengan kelahiran berikutnya mengikuti distribusi



eksponensial dengan parameter 𝜆𝑛 , dimana n=0,1,2,… b. Jika N(t)=n, maka waktu kematian dengan kematian berikutnya mengikuti distribusi eksponensial dengan parameter 𝜇𝑛 , dimana n=1,2,3,… c. Pada suatu waktu hanya ada satu kelahiran dan satu kematian saja.



Terjadi secara random



Proses Kelahiran dan Kematian Diagram rate proses kelahiran dan kematian



Diasumsikan 𝜆0 = 𝜆1 = ⋯ = 𝜆𝑛−1 = 𝜆𝑛 khususnya untuk laju kedatangan infinite, sedangkan untuk single server diasumsikan 𝜇1 = 𝜇2 = ⋯ = 𝜇𝑛 = 𝜇𝑛+1



Proses Kelahiran dan Kematian Prinsip Rate In = Rate Out / Persamaan Balance



𝑃1 : Probabilitas state 1 pindah ke state 0 𝜇1 : laju rata-rata yang masuk ke state 0 𝜇1 𝑃1 : rata-rata kejadian yang masuk ke state 0 𝑃0 : Probabilitas state 0 pindah ke state 1 𝜆0 : laju rata-rata yang keluar dari state 0 𝜆0 𝑃0 : rata-rata kejadian yang keluar dari state 0



State



Rate In



Rate Out



0



𝜇1 𝑃1



𝜆0 𝑃0



1



𝜆0 𝑃0 + 𝜇2 𝑃2



𝜆1 𝑃1 + 𝜇1 𝑃1



⋯



⋯



⋯



𝑛−1



𝜆𝑛−2 𝑃𝑛−2 + 𝜇𝑛 𝑃𝑛



𝜆𝑛−1 𝑃𝑛−1 + 𝜇𝑛−1 𝑃𝑛−1



𝑛



𝜆𝑛−1 𝑃𝑛−1 + 𝜇𝑛+1 𝑃𝑛+1



𝜆𝑛 𝑃𝑛 + 𝜇𝑛 𝑃𝑛



Akibatnya 𝑃1 = 𝑃2 =



𝜆0 𝑃 𝜇1 0



𝜆0 𝜆1 𝑃 𝜇1 𝜇2 0 ⋯



𝑃𝑛 =



𝜆0 𝜆1 … 𝜆𝑛−1 𝑃 𝜇1 𝜇2 … 𝜇𝑛 0



𝑃𝑛 =



𝜆0 𝜆1 … 𝜆𝑛 𝑃 𝜇1 𝜇2 … 𝜇𝑛+1 0



State



Rate In



Rate Out



0



𝜇1 𝑃1



𝜆0 𝑃0



1



𝜆0 𝑃0 + 𝜇2 𝑃2



𝜆1 𝑃1 + 𝜇1 𝑃1



⋯



⋯



⋯



𝑛−1



𝜆𝑛−2 𝑃𝑛−2 + 𝜇𝑛 𝑃𝑛



𝜆𝑛−1 𝑃𝑛−1 + 𝜇𝑛−1 𝑃𝑛−1



𝑛



𝜆𝑛−1 𝑃𝑛−1 + 𝜇𝑛+1 𝑃𝑛+1



𝜆𝑛 𝑃𝑛 + 𝜇𝑛 𝑃𝑛



Akibatnya 𝑃1 = 𝑃2 =



𝜆0 𝑃 𝜇1 0



𝜆0 𝜆1 𝑃 𝜇1 𝜇2 0 ⋯



𝑃𝑛 =



𝜆0 𝜆1 … 𝜆𝑛−1 𝑃 𝜇1 𝜇2 … 𝜇𝑛 0



𝑃𝑛 =



𝜆0 𝜆1 … 𝜆𝑛 𝑃 𝜇1 𝜇2 … 𝜇𝑛+1 0



Secara umum, 𝑃𝑛 = 𝐶𝑛 𝑃0, untuk 𝑛 = 1,2, , … , 𝑛 ∞



Dimana, 𝐶𝑛 =



𝜆0 𝜆1 …𝜆𝑛 𝜇1 𝜇2 …𝜇𝑛+1



, ෍ 𝑃𝑛 = 1 , sehingga



(1 + σ∞ 𝑛=1 𝑃𝑛 )𝑃0 = 1



𝑛=0



Akibatnya 𝑃0 =



1 1 + σ∞ 𝑛=1 𝑃𝑛



∞



𝐿 = ෍ 𝑛𝑃𝑛 𝑛=0



∞



𝐿𝑞 = ෍ (𝑛 − 𝑠)𝑃𝑛 𝑛=0



𝐿 𝑊= 𝜆ҧ



𝐿𝑞 𝑊𝑞 = 𝜆ҧ



∞



𝜆ҧ = ෍ 𝜆𝑛 𝑃𝑛 𝑛=0



Model Sistem Antrian dengan Jumlah Server 1 (M/ M/ 1/ I/ I) M → Tingkat kedatangan berdistribusi poisson M → waktu antar kedatangan berdistribusi eksponensial 1 → jumlah server = 1 I → Populasi Infinite I → Panjang antrian Infinite 𝜌



(M/ M/ 1/ I/ I)



𝑃0



𝜆𝑛 = 𝜆 untuk 𝑛 = 0,1,2, …



𝜆



𝜆



𝑛



𝑃0 = 𝜌𝑛 𝑃0



𝜌



𝜇𝑛 = 𝜇 untuk 𝑛 = 0,1,2, … 𝜆



𝜌



𝜆 𝑃𝑛 = 𝜇



𝜌 𝜆



𝜆



𝜌



𝜆



𝜌 𝜇



𝜇



𝜇



𝜇



𝜇



𝜇



Contoh Soal Seorang tukang potong rambut, memerlukan rata-rata waktu untuk memotong rambut seorang pelanggan adalah 12 menit, dimana waktu yang diperlukan untuk memotong rambut berdistribusi eksponensial, sedangkan waktu antar kedatangan seorang pelanggan dengan pelanggan berikutnya berdistribusi eksponensial dengan rata-rata 15 menit. Tentukan : a. b. c. d. e. f. g.



Berapa probabilitas tukang potong tersebut menganggur ? Berapa probabilitas ada 2 pelanggan di tempat tukang potong rambut tersebut ? Berapa probabilitas ada 2 pelanggan menunggu di tukang potong rambut tersebut ? Berapa waktu yang diperlukan oleh seorang pelanggan harus menunggu untuk dilayani ? Berapa waktu yang diperlukan seorang pelanggan di tukang potong rambut tersebut ? Berapa rata-rata banyaknya pelanggan yang menunggu untuk dilayani ? Berapa rata-rata banyaknya pelanggan yang berada di tukang potong rambut tersebut ?



Penyelesaian Diketahui : 1 1 = 12𝑚𝑒𝑛𝑖𝑡/𝑝𝑙𝑔, 𝜇 = 5𝑝𝑙𝑔/𝑗𝑎𝑚, = 15𝑚𝑒𝑛𝑖𝑡/𝑝𝑙𝑔, 𝜆 = 4𝑝𝑙𝑔/𝑗𝑎𝑚 𝜇



𝜆



a. Berapa probabilitas tukang potong tersebut menganggur ? 𝜆 4 1 𝑃0 = 1 − 𝜌 = 1 − = 1 − = = 20% 𝜇 5 5 b. Berapa probabilitas ada 2 pelanggan di tempat tukang potong rambut tersebut ? 𝜆 𝑃2 = 𝜇



2



4 𝑃0 = 5



2



c, d, e, f, g silahkan dikerjakan sendiri untuk latihan



1 16 = = 0,128 5 125



Model Sistem Antrian dengan Jumlah Server >1 (M/ M/ s/ I/ I) M → Tingkat kedatangan berdistribusi poisson M → waktu antar kedatangan berdistribusi eksponensial 1 → jumlah server = s I → Populasi Infinite 𝜌 I → Panjang antrian Infinite



(M/ M/ s/ I/ I)



-1



𝜆𝑛 = 𝜆 untuk 𝑛 = 0,1,2, … 𝜇𝑛 = 𝑠𝜇 untuk 𝑛 = 0,1,2, …



𝜆



𝜆



𝜇



2𝜇



𝜆



3𝜇



𝜆



s𝜇



𝜆



s𝜇



𝜆



𝑠𝜇



𝜌 𝜌



Soal Latihan Suatu bank perkreditan melakukan penelitian untuk pelayanan nasabahnya, dimana waktu antar kedatangan berdistribusi eksponensial dengan rata-rata 4 menit pernasabah, waktu yang diperlukan oleh seorang teller untuk melayani nasabah berdistribusi eksponensial dengan rata-rata 6 menit pernasabah. Jika bank tersebut mempunyai 2 teller untuk melayani nasabah, maka tentukan : a. b. c. d. e. f.



Probabilitas kedua teller menganggur Probabilitas ada teller yang menganggur Rata-rata jumlah nasabah yang menunggu dilayani Rata-rata waktu yang diperlukan nasabah menunggu untuk dilayani Rata-rata waktu yang diperlukan nasabah di dalam bank tersebut Rata-rata jumlah nasabah di dalam bank tersebut



Model Sistem Antrian dengan Panjang Antrian Finite Model Sistem Antrian dengan Jumlah Server Satu (M/ M/ 1/ I/ F)



M → Tingkat kedatangan berdistribusi poisson M → waktu antar kedatangan berdistribusi eksponensial 1 → jumlah server = 1 𝜆 𝑛 I → Populasi Infinite 𝑃𝑛 = 𝜇 𝑃0 = 𝜌𝑛 𝑃0 ; untuk 𝑛 = 1,2, … , 𝐹 F → Panjang antrian finite



(M/ M/ 1/ I/ F)



𝑃𝑛 = 0; untuk 𝑛 ≥ 𝐹



𝜆𝑛 = 𝜆 untuk 𝑛 = 0,1,2, … , 𝐹 − 1



𝑃0 =



𝜆𝑛 = 0 untuk 𝑛 ≥ 𝐹 𝜆



𝜆



𝜆



F-2



𝜇



𝜇



𝐿𝑞 = 𝐿 − (1 − 𝑃0 )



𝜇



𝜆



𝜆



𝜆



𝜇



𝐿 𝑊= 𝜆ҧ



F



F-1



𝜇



σ𝐹𝑛=0



𝜆ൗ 𝜇



𝑛



=



1−𝜌 1 − 𝜌𝐹+1



1−𝜌 𝑛 𝜌 1 − 𝜌𝐹+1



𝜌 𝐹 + 1 𝜌𝐹+1 𝐿= − 1−𝜌 1 − 𝜌𝐹+1



𝜇 𝑊𝑞 =



𝑃𝑛 =



1



𝐿𝑞 𝜆ҧ



𝜆ҧ = 𝜆(1 − 𝑃F )



Latihan Soal Suatu bengkel mobil memiliki ruangan berukuran 10 x 30 meter yang terbagi menjadi 2, yaitu 10 x 8 meter untuk tempat teknisi memperbaiki mobil dan sisanya untuk tempat menunggu mobil-mobil yang akan diperbaiki. Setiap mobil memerlukan tempat 4 x 7 meter untuk tempat partir menunggu dilayani. Mobil yang akan diperbaiki di bengkel tsb dilarang parker di pinggir jalan. Waktu antar kedatangan mobil tersebut berdist eksponensial dengan rata-rata 12 menit per mobil, sedangkan rata-rata kemampuan teknisi memperbaiki mobil 4 mobil per jam. Jika bengkel tsb hanya punya 1 teknisi, berapa :



a. b. c. d.



Probabilitas teknisi menganggur Probabilitas mobil yang datang akan balking Rata-rata banyaknya mobil di bengkel tsb Rata-rata lamanya mobil di bengkel tsb



Model Sistem Antrian dengan Panjang Antrian Finite Model Sistem Antrian dengan Jumlah Server > 1 (M/ M/ s/ I/ F) M → Tingkat kedatangan berdistribusi poisson M → waktu antar kedatangan berdistribusi eksponensial s → jumlah server = s I → Populasi Infinite F → Panjang antrian finite 𝜆 𝑛 𝑃0 𝜇 𝑃𝑛 = 𝑛! ; untuk 𝑛 = 1,2, … , 𝑠



(M/ M/ s/ I/ F)



𝜆𝑛 = 𝜆 untuk 𝑛 = 0,1,2, … , 𝐹 − 1



𝑃𝑛 =



𝜆𝑛 = 0 untuk 𝑛 ≥ 𝐹 𝜆



𝜆



𝜆



F-2



𝜇



2𝜇



3𝜇



s𝜇



𝑠−1 𝐿 = σ𝑠−1 𝑛=0 𝑛𝑃𝑛 + 𝐿𝑞 + 𝑠 1 − σ𝑛=0 𝑃𝑛



σ𝑠𝑛=0 F



F-1



𝑠𝜇



s𝜇



𝐿 𝑊= 𝜆ҧ



; untuk 𝑛 = 𝑠, 𝑠 + 1, … , 𝐹 1



𝑃0 =



𝜆



𝜆



𝜆



𝜆 𝑛 𝜇 𝑠!𝑠 𝑛−𝑠



𝜆ൗ 𝜇 𝑛!



𝑛



+



𝜆ൗ 𝜇



𝑠



σ𝐹𝑛=𝑠+1



𝜆ൗ 𝑠𝜇



𝑛−𝑠



𝑠!



𝑃0 𝜆ൗ𝜇 𝑠𝜌 𝐿𝑞 = 1 − 𝜌𝐹−𝑠 − 𝐹 − 𝑠 𝜌𝐹−𝑠 (1 − 𝜌) 2 𝑠! 1 − 𝜌



𝑊𝑞 =



𝐿𝑞 𝜆ҧ



𝜆ҧ = 𝜆(1 − 𝑃F )



Contoh Soal Suatu bengkel mobil memiliki ruangan berukuran 10 x 30 meter yang terbagi menjadi 2; 10 x 8 meter untuk tempat teknisi memperbaiki mobil dan sisanya untuk tempat menunggu mobil-mobil yang akan diperbaiki. Setiap mobil memerlukan tempat 4 x 7 meter untuk tempat parker menunggu dilayani. Mobil yang akan diperbaiki di bengkel tsb dilarang parker di pinggir jalan. Waktu antar kedatangan mobil berdistribusi poisson dengan ratarata 10 menit per mobil, sedangkan rata-rata kemampuan teknisi memperbaiki mobil adalah 4 mobil per jam. Jika bengkel tsb memiliki 2 teknisi, berapa :



a. b. c. d. e.



Probabilitas semua teknisi menganggur Probabilitas ada teknisi yang menganggur Probabilitas mobil yang datang akan balking Rata-rata banyaknya mobil menunggu di bengkel tsb Rata-rata lamanya mobil di bengkel tsb