BAB IV PROSES BIRTH-DEATH DAN APLIKASINYA DALAM SISTEM ANTRIAN. Kebanyakan sistem antrian dimodelkan menggunakan interarrival times dan

BAB IV PROSES BIRTH-DEATH DAN APLIKASINYA DALAM SISTEM ANTRIAN

4.1 Distribusi Eksponensial Dalam Proses Birth-Death Kebanyakan sistem antrian dimodelkan menggunakan interarrival times dan service times berdistribusi eksponensial. Berdasarkan The no-memory property dari distribusi exponensial maka probabilitas suatu kelahiran dalam selang waktu (t , t  t ) tidak tergantung pada berapa lama sistem berada dalam state j. Probabilitas sebuah kelahiran dalam selang waktu (t , t  t ) adalah : t

 e

 t

dt  1  e t

0

Dari ekspansi deret Taylor t

 e

 t

 t

e

 1  t  o(t ) maka :

dt  t  o(t )

0

Dari sini dapat disimpulkan bahwa laju kelahiran dalam state j hanya berupa arrival rate  . Untuk menentukan laju kematian pada saat t, dengan catatan jika state = 0 pada saat t berarti tidak ada service dalam selang waktu (t , t  t ) berarti  0  0 . Jika state pada waktu t adalah j  1 dan diketahui hanya ada satu server, jadi hanya tepat satu customer yang sedang dilayani. Berdasarkan The no-memory property dari distribusi

exponesial diperoleh probabilitas satu customer selesai dilayani dalam selang waktu (t , t  t ) adalah : t

 e

 t

dt  1  e t  t  o(t )

0

Jadi untuk j  1 ,  j   . Misal kita asumsikan service times dan interarrival times saling independen, maka M / M /1/ FCFS / /  merupakan sebuah proses birth-death. Untuk sistem antrian yang lebih kompleks dengan interarrival times dan service times berdistribusi exponensial, dapat dimodelkan sebagai proses birth-death dengan menambah jumlah server. Berikut ini adalah contoh sebuah sistem antrian yang dapat dimodelkan sebagai proses birth-rate. Sistem antrian M / M / 2 / FCFS /  / 

dengan   3 ,   6 . Sistem ini dapat

dimodelkan sebagai proses birth-death dengan :

 j  3 , untuk j = 0, 1, 2,…

0  0 , 1  6 , 2  6  6  12 ,  j  12 untuk j = 3, 4, 5,…. Jika salah satu dari interarrival times atau service times tidak berdistribusi exponensial, maka sistem tersebut tidak dapat digambarkan sebagai proses birth-death.

4.1.1 Penurunan Steady State Untuk proses Birth-Death Terdapat empat jalan yang mungkin agar pada saat t  t , sistem berada pada state j. Untuk j  1 keempat jalan itu adalah sebagai berikut :

Kejadian

State pada

State pada

Probabilitas kejadian

Saat t

Saat t  t

I

j–1

j

Pi. j 1 (t )( j 1t  o(t ))

II

j+1

j

Pi. j 1 (t )( j 1t  o(t ))

III

j

j

Pi. j (t )(1   j t   j t  2o(t ))

IV

State lain

j

o(t )

Jika pada saat t sistem berada pada state j, j – 1, atau j + 1 maka supaya sistem berada pada state j pada saat t  t akan terdapat lebih dari satu kejadian (birth atau death) dalam selang waktu (t , t  t ) . Berdasarkan Hk. 3. kejadian ini akan memiliki probabilitas o(t ) . Diasumsikan untuk t kecil maka o(t )  0 . Selanjutnya Pij (t  t ) dapat kita tulis sebagai berikut : Pij (t  t )  ( I )  ( II )  ( III )  ( IV )

Pij (t  t )  Pij (t )  t ( j 1Pi. j 1 (t )   j 1Pi. j 1 (t )  Pij (t )  j  Pij (t ) j )

…………(4.1.1.1)

 o(t )( Pi. j 1 (t )  Pi. j 1 (t )  1  2Pij (t )).

Untuk yang digaris bawah dapat ditulis sebagai o(t ) sehingga diperoleh

Pij (t  t )  Pij (t )  t ( j 1Pi. j 1 (t )   j 1Pi. j 1 (t )  Pij (t )  j  Pij (t ) j )  o(t )

kedua ruas dibagi dengan (t ) untuk (t ) mendekati nol, maka diperoleh untuk semua

i dan j  1 ,

Pij' (t )   j i Pi. j 1 (t )   j 1Pj 1 (t )  Pij (t ) j  Pij (t ) j ……………….……(4.1.1.2)

ambil j = 0, maka Pi. j 1 (t )  0, dan  j  0 sehingga diperoleh : Pi.'0 (t )  1Pi.1 (t )  0 Pi.0 (t )

Dalam kenyataan persamaan deferensial ini sangat sulit untuk diselesaikan, maka didefinisikan probabilitas steady-state  j , (j=0, 1, 2,…) sebagai suatu rantai Markov,

 j  lim Pij (t ) t 

Untuk t besar dan sebarang inisial state, Pij (t ) tidak akan berubah banyak, bahkan mungkin akan berupa konstan. Berarti dalam keadaan steady-state Pij' (t )  0 , kemudian juga diperoleh Pi. j 1 (t )   j 1 , Pi. j 1 (t )   j 1 , dan Pij (t )   j . Substitusikan ke persamaan (4.1.1.2) maka untuk j  1 , didapat :

 j 1 j i   j 1 j 1   j  j   j  j  0

………………………...………(4.1.1.3)

 j 1 j 1   j 1 j 1   j ( j   j ) ambil j = 0, didapat :

11   00 Persamaan terakhir dapat pula diperoleh dari kenyataan hasil pengamatan yaitu : Untuk setiap t di dalam proses birth-death, pastilah benar bahwa untuk setiap state j, jumlah dari berapa kali kita masuk state j dan jumlah berapa kali kita keluar dari state j, akan paling banyak berbeda satu.

Misal setelah observasi selama t waktu, diperoleh hasil bahwa kita telah masuk state 4 sebanyak tiga kali. Maka kejadian-kejadian berikut pastilah benar.

Kejadian

Inisial State

State Pada

Banyaknya berapa kali keluar dari

Saat t

state 4 setelah t waktu

1

State 4

State 4

3

2

State 4

Selain state 4

4

3

Selain state 4

State 4

2

4

Selain state 4

Selain state 4

3

Terlihat pada kolom 4, bahwa setelah t waktu bila kita telah masuk state 4 sebanyak tiga kali maka banyaknya berapa kali keluar dari state 4 adalah 2, 3, atau 4 kali. Jadi paling banyak hanya berbeda satu. Jadi untuk t besar pastilah benar bahwa : nilai 

nilai

harapan berapa kali keluar dari state satuan waktu

j

harapan berapa kali masuk ke state satuan waktu

j

…..……..(4.1.1.4)

Diasumsikan bahwa sistem telah masuk steady-sate. Maka untuk setiap state j, j = 0, 1, 2,… terdapat probabilitas  j yaitu peluang terdapat j orang dalam sistem setelah tercapai steady-state. Untuk j  1 , kita hanya dapat meninggalkan state j menuju state j – 1 atau state j + 1, sehingga :

Nilai

harapan keluar dari state satuan waktu

j

  j ( j   j )

…...…...….(4.1.1.5)

Juga untuk j  1 kita hanya dapat masuk state j dari state j – 1 atau state j + 1, sehingga :

Nilai

harapan masuk ke state satuan waktu

j

  j 1 j 1   j 1  j 1

….……(4.1.1.6)

Dari persamaan (4.1.1.5) dan (4.1.1.6) diperoleh :

 j 1 j 1   j 1 j 1   j ( j   j )

(j = 0, 1, 2, 3, ….)

………….(4.1.1.7)

diambil j = 0 , maka 0   1  0 sehingga diperoleh :

11   00

…...…………..(4.1.1.8)

Persamaan (4.1.1.7) dan (4.1.1.8) disebut sebagai flow balance equations atau conservation of flow equation untuk proses birth-death. Perhatikan persamaan (4.1.1.7), maka kita peroleh flow balance equation : (j=0)

 00  11

(j=1)

(1  1 )1  0 0  2 2

(j=2)

(2  2 ) 2  11  3 3

: : (j=j)

( j   j ) j   j 1 j 1   j 1 j 1

4.1.2 Penyelesaian Dari Flow Balance Equation Dari j = 0 telah kita telah kita peroleh  1 

substitusikan ke (j = 1) :

 00 . 1

0 0  2 2 

(1  1 ) 00

1

 2 2 

 0 (01 ) 1

2 

 0 (01 ) 1 2

bila substitusi diteruskan untuk (j = 2), (j = 3), ….. maka akan diperoleh :

 j   0c j , dengan c j 

01... j 1 1 2 ... j

……………………….....(4.1.2.1)

Untuk sebarang waktu t kita harus berada dalam suatu state, jadi jumlah probabilitas steady-state harus sama dengan satu. j 

 c j 0

0 j

1

…………………….………....(4.1.2.2)

untuk j = 0, maka persamaan (4.1.2.1) menjadi  0   0c0 c0  1

jadi j 

 0 (1   c j )  1

…………………………....(4.1.2.3)

j 1

dari (4.1.2.3) dapat dihitung  0 asalkan

0 

j 

c j 1

j

1

terbatas, yaitu :

……………….…………...(4.1.2.4)

j 

1 cj j 1

selanjutnya substitusikan persamaan (4.1.2.4) ke (4.1.2.1) maka akan didapat nilai  j , j 

j = 1, 2, … Jika

c j 1

j

tak terbatas, tidak ada steady-state pada sistem, hal ini disebabkan

arrival rate sama atau melebihi jumlah maksimum yang bisa dilayani server, sehingga state akan terus naik dan tak ada equilibrium.

4.2 Sistem Antrian M/M/1/GD/  /  Dan Formula Antrian L  W Sistem antrian M/M/1/GD/  /  mempunyai interarrival times dan service times yang berdistribusi eksponensial dan hanya memiliki satu server, sedangkan jumlah arrival tidak dibatasi. Kita asumsikan arrival rate =  dan service rate =  . Sistem antrian ini dapat kita modelkan sebagai proses birth-death dengan parameter sebagai berikut :

j  

(j = 0, 1, 2,…), 0  0 ,  j  

(j = 1, 2, 3, …) ………...…….…(4.2)

4.2.1 Penurunan Dari Probabilitas Steady-State Untuk memperoleh nilai  j , kita substitusikan persamaan (4.2) ke (4.1.2.1) :

1 

2  j 0  0 ,  2  2 0 , …,  j   j 

didefinisikan  

………………...…(4.2.1.1)

 kita sebut  sebagai intensitas traffic dari sistem antrian. Jika 

terjadi   1 berarti    ( arrival rate paling sedikit sebesar service rate). Untuk

  1 maka arrival rate sama dengan service rate jadi server akan terus sibuk dan tidak akan tercapai steady-state. Demikian pula jika   1 maka jumlah customer dalam sistem akan terus meningkat sehingga tidak akan tercapai steady-state. Substitusi persamaan (4.2.1.1) ke (4.1.2.2) diperoleh :

 0 (1     2  ...)  1 karena 0    1 , maka

0 

…………..….…(4.2.1.2)

1 1 1 

0  1 

(0    1)

…….(4.2.1.3)

substitusi persamaan (4.2.1.3) ke (4.2.1.1) diperoleh :

 j   j (1   )

(0    1)

…………...…(4.2.1.4)

4.2.2 Penurunan Dari L Didefinisikan L adalah jumlah rata-rata customer yang ada dalam sistem. Diberikan L 

j 

 j j  j 0

j 

j 

j 0

j 0

 j j (1   )  (1   )  j j

j 

didefinisikan S   j j    2  2  3 3  ...  j 0

jadi

L  (1   ) S  (1   )

 (1   ) 2

  /     2 1  1  /     (1   )

……………...(4.2.2)

4.2.3 Penurunan dari Lq Didefinisikan Lq adalah nilai harapan dari jumlah jumlah customer yang sedang menunggu di garis antrian. Jadi jika ada 0 atau 1 customer dalam sistem, maka tidak ada customer yang menunggu di antrian. Jika terdapat j orang di dalam sistem ( j  1) maka akan terdapat j – 1 orang di garis antrian. 

Lq   ( j  1) j  j 1

j 

j 

j 1

j 1

 j j   j

 L  (1   0 ) substitusi dari persamaan (4.1.1.8) diperoleh : Lq  L  

substitusi dari persamaan (4.2.2) diperoleh :

Lq 

 1 

 

2 2  1    (   )

…………..……………...(4.2.3)

4.2.4 Penurunan dari Ls Ls merupakan nilai harapan dari jumlah cutomer yang sedang dilayani. Ls  0 0  1(1   2  ...)  1   0  1  (1   )  

Kita dapat juga mencari Lq menggunakan persamaan L  Ls  Lq ,



2 Lq  L  Ls    1  1 

4.2.5 Formula Antrian L  W Kita definisikan W adalah nilai berapa lama seorang customer berada di dalam sistem, yaitu waktu yang dibutuhkan untuk antri ditambah waktu pelayanan server. Didefinisikan besaran-besaran sebagai berikut :

  Jumlah rata-rata arrival masuk ke sistem per unit waktu L  Jumlah rata-rata customer yang ada di dalam sistem

Lq  Jumlah rata-rata customer yang sedang antri

Ls  Jumlah rata-rata customer yang sedang dilayani server W  Waktu rata-rata seorang customer berada di dalam sistem

Wq  Waktu rata-rata seorang customer harus antri

Ws  Waktu rata-rata yang dibutuhkan server untuk melayani satu

customer. Diasumsikan sistem telah mencapai steady-state, semua rata-rata di atas adalah rata-rata steady-state. Besaran-besaran di atas dapat diselesaikan menggunakan Little’s Queuing formula. Formula ini bisa dilihat pada teorema berikut :

Teorema Untuk sebarang sistem antrian yang terdapat distribusi steady-state, berlaku relasi-relasi berikut : L  W

…………...………..(4.2.5.1)

Lq  Wq

………………….....(4.2.5.2)

Ls  Ws

……………….….…(4.2.5.3)

Untuk membuktikan teorema tersebut dapat dilihat dari satuannya. Misal untuk persamaan (4.2.5.1), L adalah jumlah customer dalam sistem, jadi mempunyai satuan “orang”, kemudian  mempunyai satuan “orang / jam” dan W mempunyai satuan “jam”. Jadi LW mempunyai satuan “orang”. Untuk bukti lain, perhatikan kejadian saat seorang customer datang, kita namai customer-A. Diasumsikan customer-A datang setelah steady-state tercapai.

Saat

customer-A berada dalam sistem maka akan terdapat (nilai rata-rata) L customer dalam sistem. Customer-A akan berada dalam sistem selama W waktu. Setelah customer-A meninggalkan sistem, maka yang tinggal di dalam sistem adalah customer-customer di belakangnya yang datang dalam W waktu tersebut, dan ini berjumlah W . Dari sini terlihat bahwa L  W Dengan menggunakan teorema di atas, kita bisa mendapatkan nilai W dan Wq . Substitusi dari persamaan (4.2.2) diperoleh : W 

L





  (1   )



1  

Substitusi dari persamaan (4.2.3) diperoleh :

Wq 

Lq





Bila diperhatikan  

  (   )

 , maka jika  mendekati satu maka baik W maupun Wq 

keduanya akan sangat besar. Sedangkan untuk  mendekati nol, Wq akan mendekati nol dan W mendekati

1 yaitu nilai rata-rata service times. 

Berikut adalah contoh penggunaan formula tersebut : Contoh 1. Pada sebuah server drive-in teller rata-rata datang 10 mobil per jam. Diasumsikan ratarata service times untuk sebuah mobil adalah 4 menit, dan baik interarrival times maupun service times keduanya berdistribusi eksponensial. 1. Berapa probabilitas teller akan idle (bebas kerja) ? 2. Berapa jumlah rata-rata mobil yang antri ? 3. Berapa waktu rata-rata sebuah mobil di dalam sistem ? 4. Berapa rata-rata costumer yang dilayani server dalam satu jam ? Penyelesaian : Diketahui sistem antrian M/M/1/GD/  /  dengan   10 mobil per jam dan   15 mobil per jam. Berarti  

10 2  . 15 3

1. teller akan idle bila customer dalam sistem berjumlah nol.

0  1   1

2 1  . 3 3

Jadi teller akan idle rata-rata 1/3 dari waktu tugasnya.

2.

3.

Lq 

L

W 

( 2 )2 4 2  3 2  mobil. 1  1 3 3

 (1   ) L







2 3

1  23

 2 mobil

2 1  jam = 12 menit. 10 5

4. Diketahui   15 , jadi jika server terus sibuk maka akan ada rata-rata 15 customer yang telah dilayani selama satu jam. Dari no.1 diketahui bahwa server akan idle ratarata 1/3 waktu tugasnya. Jadi dalam satu jam rata-rata akan terdapat ( 23 )(15)  10 customer yang selesai dilayani server. Dalam kenyataan, karena sistem dalam keadaan steady-state, jika dalam satu jam terdapat 10 arrival maka akan terdapat pula 10 customer meninggalkan sistem dalam satu jam.

4.2.6 Model Optimisasi Antrian Berikut ini adalah contoh penggunaan teori antrian untuk optimisasi. Contoh 2. Masinis yang bekerja di sebuah tool-and-die plant harus mencari alat-alat dari pusat peralatan. Rata-rata dalam satu jam terdapat 10 masinis datang mencari peralatan. Pusat peralatan dipimpin oleh seorang juru tulis yang dibayar $6 per jam yang membutuhkan waktu rata-rata 5 menit untuk setiap permintaan alat. Setiap masinis memproduksi barang-barang senilai $10 per jam (berarti perusahaan akan membayar $10 untuk setiap satu jam yang digunakan masinis di pusat peralatan). Perusahaan mempertimbangkan perlu tidaknya menyewa pembantu juru tulis dengan bayaran $4 per jam. jika bersama pembantu maka juru tulis membutuhkan waktu rata-rata 4 menit untuk

setiap permintaan barang. Diasumsikan arrival times dan service times berdistribusi eksponensial. Perlukah disewa pembantu ? Penyelesaian : Penyelesaian optimum untuk problem di atas adalah meminimalkan service cost per jam (biaya untuk membayar juru tulis) dan delay cost per jam (biaya yang dikeluarkan selama masinis berhenti kerja karena harus ke pusat paralatan). Jadi perusahaan ingin meminimalkan pengeluaran per jam, yaitu :

harapan

pengeluara n service cos t harapan delay   jam jam jam

cos t

dengan,

harapan delay cos t harapan delay cos t harapan   jam customer

jumlah customer jam

 rata  rata jumlah jam ma sin is  harapan delay cos t $10     customer ma sin is  jam  di pusat perala tan  

jika tanpa pembantu untuk juru tulis, maka :

  10 masinis per jam, dan   12 masinis per jam. jadi diperoleh W 

1 1 1   jam. (w adalah waktu rata-rata masinis di pusat    12  10 2

peralatan) diperoleh

harapan delay jam

cos t

dari soal diketahui

service cos t  $6 jam

 10  12  10  $50

jadi tanpa pembantu, harapan pengeluaran per jam = 6 + 50 = $56



jika menyewa pembantu maka :

  10 masinis per jam, dan   15 customer per jam jadi diperoleh W 

1 1  jam 15  10 5

diperoleh

harapan delay jam

cos t

dari soal diketahui

service cos t  6  4  $10 jam

 10  15  10  $20

jadi dengan menyewa pembantu diharapkan pengeluaran per jam = 20 + 10 = $30. 

Kesimpulan dengan menyewa pembantu akan lebih menguntungkan.