Gambar 2.1. Struktur sistem antrian

Riset Operasi Probabilistik Teori Permainan (Game Theory)

Nughthoh Arfawi Kurdhi, M.Sc Departement of Mathematics FMIPA UNS

Lecture 9: Pure Birth Model and Pure Death Model A. Notasi dan Struktur dalam Sistem Antrian Notasi dalam system antrian n : jumlah pelanggan dalam sistem Po : probabilitas tidak ada pelanggan dalam sistem Pn : probabilitas kepastian n pelanggan dalam sistem λ : jumlah rata-rata pelanggan yang datang per satuan waktu µ : jumlah rata-rata pelanggan yang dilayani per satuan waktu 1/µ : rata-rata waktu pelayanan 1/λ : rata-rata waktu antar kedatangan p : tingkat intensitas fasilitas pelayanan (λ/µ) L : jumlah rata-rata pelanggan yang diharapkan dalam sistem Lq : jumlah pelanggan yang diharapkan menunggu dalam antrian W : waktu yang diharapkan oleh pelanggan selama dalam sistem Wq : waktu yang diharapkan oleh pelanggan selama menunggu dalam antrian c : jumlah fasilitas pelayanan Struktur sistem antrian

Gambar 2.1. Struktur sistem antrian

B.

Pure Birth Model Pola kedatangan yang sifatnya acak dapat digambarkan dengan distribusi statistik dan dapat ditentukan dua cara yaitu - kedatangan per satuan waktu (rata-rata kedatangan) dan - distribusi waktu antar kedatangan (rata-rata waktu kedatangan). Kedatangan per satuan waktu (number of arrivals)  Jika kedatangan terjadi secara acak dan diasumsikan terjadi dengan kecepatan rata-rata yang konstan dan bebas satu sama lain, ahli matematika dan fisika, Simeon Poisson (1781 – 1840) menemukan suatu distribusi yang disebut distribusi probabilitas Poisson.





Jika ( ) adalah probabilitas terjadi n ( > 0) kedatangan selama interval waktu t, maka ( )=

(

) !

; = 0,1,2, …

dengan λ adalah rata-rata kedatangan per satuan waktu. Distribusi dari banyaknya kedatangan selama interval waktu t yaitu Poisson dengan Mean = ( | ) = . 

“Jumlah yang dilayani (jumlah kepergian) juga mengikuti distribusi Poisson”.

Waktu antar kedatangan (interarrival time)  Jika pada kedatangan per satuan waktu mengikuti distribusi Poisson, pada waktu antar kedatangan terdistribusi sesuai dengan distribusi eksponensial. Distribusi eksponensial menyatakan apabila t = waktu diantara dua kedatangan yang berurutan (interarrival time) maka sebaran eksponensial dengan parameter yang sama (seperti pada Poisson) adalah: ( )= dengan ( ) =

; > 0 adalah rata-rata waktu antar kedatangan.



Jadi dapat disimpulkan, jika banyaknya kedatangan per satuan waktu memiliki sebaran Poisson dengan rata-rata 10, maka waktu diantara dua kedatangan memiliki sebaran eksponensial dengan rata-rata 1/10. Sistem antrian seperti ini dikatakan memiliki input Poisson, dan pelanggan dikatakan datang mengikuti Proses Poisson.



“Waktu pelayanan (service time) juga mengikuti distribusi eksponensial”.

Kesimpulan Tabel 9.1. Pola kedatangan dan waktu antar kedatangan



Role of Exponential Distribution Waktu antar kedatangan (interarrival time) dan waktu pelayanan (service time) dalam model antrian diasumsikan mengikuti distribusi eksponensial, yang didefinisikan oleh ( )= ; > 0 dengan ( )= ( ≤ )=∫ =1− . Karakteristik penting dalam distribusi eksponensial adalah forgetfulness atau lack of memory, yaitu probabilitas kedatangan pada waktu yang akan datang tidak dipengaruhi oleh sudah berapa lama sejak kedatangan terakhir. Sebagai contoh “Jika waktu sekarang 08.20 dan kedatangan terakhir terjadi pada pukul 08.02, maka probabilitas kedatangan pada pukul 08.29 hanya dipengaruhi oleh interval 08.20 – 08.20 dan tidak dipengaruhi oleh interval 08.02 – 08.29” Jadi, dalam distribusi eksponensial diperoleh ( > + | > )= ( > ) Bukti: Perhatikan bahwa ( > )=1− ( ≤ ) =1− 1− = . Sehingga diperoleh ( ) ∩ ( > + | > )= = (

=

(

)

)

=

(

) (

)

= ( > ).

Terbukti.

1.

2.

3.

Soal – Soal 1 In each of the following cases, determine the average arrival rate per hour and the average interarrival time in hours. a. One arrival occurs every 10 minutes. b. Two arrivals occur every 6 minutes. c. Number of arrivals in a 30-minute period is 10. d. The average interval between successive arrivals is 0.5 hour In each of the following cases, determine the average service rate per hour and the average service time in hours. a. One service in completed every 12 minutes. b. Two departures occur every 15 minutes. c. Number of customers served in a 30-minute period is 5. d. The average service time is 0.3 hour. The time between arrivals at the State Revenue Office is exponential with mean value 0.05 hour. The office opens at 08.00. a. Write the exponential distribution that describes the interarrival time. b. Find the probability that no customers will arrive at the office by 08.15.


4.

5.


c. It is now 08.35. The last customer entered the office at 08.26. What is the probability that the next customer will arrive before 08.38? That the next customer will not arrive by 08.40? d. What is the average number of arriving customers between 08.10 and 08.45? Ann and Jim, two employees in a fast-food restaurant, play the following game while waiting for customers to arrive: Jim pays Ann 2 cents if the next customer does not arrive within 1 minute; otherwise, Ann pays Jim 2 cents. Detemine Jim’s average payoff in an 8-hour period. The interarrival time is exponential with mean 1.5 minute. A customer arriving at a McBurger fast-food restaurant within 4 minutes of the immediately preceding custemer will receive a 10% discount. If the interarrival time is between 4 and 5 minutes, the discount is 6%. If the interarrival time is longer than 5 minutes, the customer gets 2% discount. The interarrival time is exponential with mean 6 minutes. a. Determine the probability that an arriving customer will receive the 10% discount. b. Determine the average discount per arriving customer. Contoh Soal Pure Birth Model Diketahui rata-rata 1 kelahiran setiap 12 menit. Diasumsikan waktu antar kelahiran mengikuti distibusi eksponensial. Tentukan a. Rata-rata jumlah kelahiran per tahun b. Probabilitas tidak ada kelahiran dalam satu hari c. Probabilitas menerbitkan 50 sertifikat kelahiran dalam 3 jam dengan 40 sertifikat sudah diterbitkan dalam 2 jam pertama. Penyelesaian: a. Rata-rata kelahiran dalam satu hari: =

× 24 = 120 kelahiran/hari

Rata-rata kelahiran dalam satu tahun: = 120 × 365 = 43.800 kelahiran/tahun. b. Cara 1: Kelahiran berdistribusi Poisson, sehingga probabilitas tidak ada kelahiran dalam satu hari ( )=

(

(1) =

(

) ! . )

.

!

=

=0

Cara 2: Probabilitas tidak ada kelahiran dalam satu hari ekuivalen dengan probabilitas waktu antar kelahiran lebih dari satu hari, sehingga ( > 1) = = = 0. c. Karena jumlah kelahiran berdistribusi Poisson, maka probabilitas menerbitkan 50 sertifikat kelahiran dalam 3 jam dengan 40 sertifikat sudah diterbitkan dalam 2 jam pertama ekuivalen dengan probabilitas menerbitkan 10 sertifikat kelahiran dalam 1 jam. Diberikan =

= 4 kelahiran/jam

Diperoleh (1) =

.

( . ) !

= 0.01813.


1.

2.

3.


Soal – Soal 2 Babies are born in a sparsely populated state at the rate of one birth every 12 minutes. The time between births follows an exponential distribution. Suppose that the clerk who enters the information from birth certificates into the computer normally waits until at least 5 certificates have accumulated. Find the probability that the clerk will be enterig a new batch every hour. The time between arrivals at L&J restaurant is exponential with mean 5 minutes. The restaurant opens for business at 11.00. Determine the following: a. The probability of having 10 arrivals in the restaurant by 11.12 given that 8 customers arrived by 11.05. b. The probability that a new customer will arrive between 11.28 and 11.33 given that the last customer arrived at 11.25. The U of A runs two bus lines on campus: red and green. The red line serves north campus and the green line serves south campus with a transfer station linking the two lines. Green buses arrive randomly (according to a Poisson distribution) at the transfer station every 10 minutes. Red buses also arrive randomly every 7 minutes. What is the probability that two buses will sto at the station during a 5-minute interval?

C. Pure Death Model Pada pure death model, semula terdapat N pelanggan (customers) dan tidak ada kedatangan. Kepergian (departures) atau jumlah pelanggan yang dilayani terjadi dengan rata-rata pelanggan per satuan waktu. Jumlah pelanggan yang masih tersisa dalam system setelah t satuan waktu dirumuskan dengan ( )=

(

) (

( )=1−∑

)!

, = 1,2, … , ( ).

Contoh Soal Pure Death Model Dalam proses pengiriman barang, dimana terdapat 15 barang dikirim untuk keperluan selama 1 minggu. Lebih jelasnya, bahwa persediaan barang hanya digunakan selama 6 hari pertama (karena hari minggu libur) dan diikuti dengan distribusi Poisson dengan mean 3 unit per hari. Ketika persediaan barangnya masih 5 unit, dia akan memesan 15 unit barang untuk dikirim ke tempatnya pada minggu berikutnya. a. Berapa probabilitas pemesanan ulang terhadap barang pada hari ke t , ketika masih tersedia 5 unit barang? b. Berapa probabilitas pemesanan ulang terhadap barang pada hari ke t , ketika barang yang tersedia kurang dari atau sama dengan 5 unit? c. Berapa rata-rata banyaknya barang yang akan dibuang pada minggu akhir atau ekspektasi dari banyaknya unit yang tersedia pada hari ke-6? Penyelesaian: a. Perhitungan probabilitas pemesanan ulang terhadap barang pada hari ke t , ketika masih tersedia 5 unit barang, yaitu 5

( )=

(3 ) 15−5 −3 (15−5)!


Hari ke-t ( )


1 3

2 6

3 9

0.0008

0.0413

0.1186

4 12

5 15

6 18

0.1048

0.0486

0.015

Terlihat bahwa probabilitas tertinggi untuk pemesanan ulang terhadap barang yaitu pada hari ke-3. b. Perhitungan probabilitas pemesanan ulang terhadap barang pada hari ke t , ketika barang yang tersedia kurang dari atau sama dengan 5 unit, yaitu ( ) = 0 ( ) + 1 ( ) + 2 ( ) + 3( ) + 4( ) + 5 ( ) ≤5 Hari ke-t ( )

1 3 0.0012

2 6

3 9

4 12

5 15

6 18

0.0839

0.4126

0.7576

0.9303

0.9847

probabilitas monoton naik seiring dengan pemesanan pada hari ke-t. c. Menentukan rata-rata banyaknya barang yang akan dibuang pada minggu akhir atau ekspektasi dari banyaknya unit yang tersedia pada hari ke-6, yaitu [ | = 6] = ∑ (6) n (6)

0

1

2

3

4

5

6

7

0.792

0.0655

0.0509

0.0368

0.0245

0.015

0.0083

0.0042

8

9

10

11

0.0018

0.0007

0.0002

0.0001

(6) ≅ 0, untuk n = 12, 13, 14, 15. [ | = 6] = 0.5537 ≈ 1. Rata-rata banyaknya barang yang akan dibuang pada minggu akhir adalah 1 unit barang.

1.

Soal – Soal 3 The florist section in a grocery store stocks 18 dozen roses at the beginning of each week. On the average, the florist sells 3 dozens a day (one dozen at a time), but the actual demand follows a Poisson distribution. Whenever the stock level reaches 5 dozens, a new order of 18 new dozens is placed for delivery at the beginning of the following week. Because of the nature of the item, all roses left at the end of the week are disposed of. a. The probability that the stock out is depleted after 3 days. b. The average number of dozen roses left at the end of the second day. c. The probability that at least one dosen is purchased by the end of the fourth day, given that the last dozen was bought at the end of the third day. d. The probability that no purchases will occur during the first day.


2.

3.


e. The probability that no order will placed by the end of the week. A freshman student receives a bank deposit of $100 a month from home to cover incidentals. Withdrawal checks of $20 each occur randomly during the month and are spaced according to an exponential distribution with a mean value of 1 week. Determine the probability that the student will run out of incidental money before the end of the fourth week. Demand for an item occurs according to a Poisson distribution with mean 3 per day. The maximum stock level is 25 items, which occur on each Monday immediately after a new order is received. The order size depends on the number of units left at the end of the week on Saturday (business is closed on Sundays). Determine the following: a. The average weekly size of the order. b. The probability of incurring shortage when the business opens on Friday morning. c. The probability that the weekly order size exceeds 10 units.

D. Notasi Kendal (Kendal notation) Suatu sistem antrian didefinisikan dalam sebuah notasi yang kerap dikenal dengan sebutan notasi Kendal, sesuai dengan nama penemunya. Notasi Kendal dituliskan sebagai berikut: a/b/c/d/e/f dengan - a : distribusi waktu antar kedatangan - b : distribusi waktu layanan - c : jumlah server - d : disiplin antrian - e : kapasitas maksimum antrian - f : jumlah source Untuk notasi Kendal a dan b, yaitu distribusi waktu kedatangan dan distribusi waktu layanan dapat digunakan beberapa jenis distribusi peluang antara lain distribusi hyperexponential, erlang-k dan exponential. Namun selain itu juga dengan menggunakan distribusi umum waktu antar kedatangan (general independent interarrival time) dan distribusi umum waktu layanan (general service time distribution). Berikut adalah carian untuk notasi Kendal a dan b. - GI : general independent interarrival time - G : general service time distribution - Hk : k-stage hyperexponential - Ek : erlang-k - M : exponential - D : deterministik Disiplin antrian notasi d dapat berupa - FCFS : First come first served - LCFS : Last come first served - SIRO : Service in random order - GD : General disiplice

Gambar 2.1. Struktur sistem antrian

Recommend Documents