An Tri An

TEORI ANTRIAN

Kata Pengantar Dalam dunia nyata kita tidak suka menunggu. Tetapi pengurangan waktu menunggu umumnya membutuhkan investasi yang ekstra. Untuk memutuskan ya atau tidak untuk investasi adalah penting untuk mengetahui efek dari investasi untuk waktu antrian. Maka kita memerlukan model dan tehnik untuk menganalisis situasi seperti ini. Di dalam buku ini kita akan memerlukan beberapa model dasar teori antrian. Perhatian ditekankan pada metode untuk menganalisis model ini, dan juga aplikasi dari Antrian model. Area penting dari aplikasi model antrian adalah sistem produksi, transportasi dan sistem persediaan barang, sistem komunikasi, dan sistem pengolahan informasi. Antrian model bermanfaat untuk perancangan sistem dalam kaitannya dengan tata ruang, kapasitas dan kendali. Di dalam kuliah ini perhatian kami terbatas pada model dengan satu antrian. Situasi dengan lebih dari satu antrian diperlukan dalam kursus antrian jaringan. Merupakan tehnik lanjutan untuk bilangan eksak, aproksimasi dan analisis numerik dari antrian model akan menjadi pokok bahasan\ metode algoritma teori antrian. Silabusnya sebagai berikut. Bab 2 mendiskusikan sejumlah konsep dasar dan akibat dari teori peluang yang akan kita pakai. Antrian model sederhana yang sangat menarik akan kita perlukan pada bab 4, dan versi multi server akan diperlukan pada bab selanjutnya. Model yang berhubungan dengan layanan umum atau tentang distribusi waktu tiba diteliti pada bab 6, 7 dan 8 . Beberapa versi sederhana dari model ini dibahas dalam bab 10. bab 9 dikhususkan untuk model antrian dengan aturan prioritas. Bab terakhir mendiskusikan tentang sistem insentif. Buku ini berisi banyak latihan dan pembaca dihimbau untuk mencoba latihan ini. Ini sungguh diperlukan untuk memperoleh keterampilan tentang model dan situasi baru.

Contoh Di bawah ini kita akan menguraikan dengan singkat beberapa situasi dimana antrian sangat penting. Contoh 1.1.1 Supermarket Berapa lama pelanggan harus menunggu di kasir ? apa yang terjadi dengan waktu tunggu selama puncak kesibukan ? apakah jumlah kasir cukup ? Contoh 1.1.2 Sistem Produksi

Sebuah mesin menghasilkan jenis produk yang berbeda. Berapa waktu pasti dari suatu pesanan? Apa yang mengurangi waktu pasti jika kita memiliki sebuah mesin ekstra? Haruskah kita membuat prioritas dari pesanan? Contoh 1.1.3 Kantor Pos Dalam suatu kantor pos ada konter-konter khusus didalamnya seperti stempel, packaging, ternsaksi keuangan dll. Apakah konternya sudah cukup? Bisakah Antrian terpisah atau antrian umum di depan konter dengan spesialisasi yang sama? Contoh 1.1.4 Komunikasi Data Di dalam paket jaringan komunikasi standar komputer yang disebut sel ditransmisikan di dalam link dari satu switch ke yang lainnya. Pada setiap switch sel yang masuk dapat dibuffer ketika permintaan yang datang melebihi kapasitas link. Ketika buffer penuh cel yang masuk akan hilang. Apa yang menunda sel didalam switch? Pecahan sel yang mana yang akan hilang? Berapa ukuran buffer yang baik? Contoh 1.1.5 Tempat Parkir Mereka akan mendirikan suatu area parkir baru di depan suatu supermarket. Seberapa besar seharusnya ? Contoh 1.1.6 Perakitan Papan Sirkuit Printer Memasang komponen secara vertikal di atas papan printer dilakukan dalam suatu pusat perakitan yang terdiri dari sejumlah mesin penyisipan yang paralel. Masing-masing mesin mempunyai sebuah magazine untuk menyimpan komponen. Berapa waktu pasti yang dibutuhkan untuk produksi papan sirkuit itu? Bagaimana seharusnya pembagian komponen yang diperlukan untuk perakitan papan sirkuit printer disetiap mesin? Contoh 1.1.7 Call Center dari suatu perusahaan asuransi ? Pertanyaan melalui telepon, mengenai kondisi-kondisi asuransi, ditangani oleh sebuah call center. Dimana masing-masing regu membantu nasabah dari masing-masing daerah tertentu. Berapa lama pelanggan menunggu sebelum sampai operator bersedia? Apakah jumlah telefon yang masuk cukup? Apakah operatornya cukup? Regu polling? Contoh 1.1.8 Main Frame Komputer Banyak cashomat dihubungkan pada sebuah main frame komputer yang besar yang dapat menangani semua teransaksi finansial. Apakah kapasitas komputer mainframe cukup? Apa yang terjadi jika penggunaan cashomat meningkat? Contoh 1.1.9 Gardu Tol Pengendara motor harus membayar bea masuk untuk melewati sebuah jembatan. Apakah gardu tol cukup?

Contoh 1.1.9 Rambu Lalu Lintas Bagaimana kita harus mengatur rambu lalu lintas agar waktu tunggu dapat diterima?

BAB 2 Konsep Dasar Teori Peluang Bab ini dikhususkan untuk beberapa konsep dasar dari teori peluang. 2.1 Peubah Acak Peubah acak ditunjukkan dengan huruf kapital, X,Y, dll. Nilai harapan atau mean dari X ditunjukkan dengan E(X) dan variannya dengan σ 2 ( X ) dimana σ ( X ) adalah standar deviasi dari X. Jumlah yang penting adalah koefisien variansi dari peubah acak positif X didefinisikan sebagai

σ (X ) E( X ) Koefisien variansi adalah sebuah (non-dimensi) nilai kemajemukan dari peubah acak X. cX =

2.2 Fungsi Pembangkit X adalah peubah acak diskrit non negatif dengan P ( X = n) = p (n), n = 0,1,2... Kemudian fungsi pembangkit PX (z ) dari X didefinisikan sebagai

( ) ∑

PX ( z ) = E z X =

∞ n= 0

p( n ) z n .

Anggap bahwa PX ( z ) ≤ 1 untuk semua z ≤ 1 . Lebih lanjut PX ( 0) = p( 0) ,

PX (1) = 1,

P ' X (1) = E ( X ) ,

Dan, lebih umum, PX( k ) (1) = E ( X ( X − 1)...( X − k + 1) ) , Dimana (k) menunjukkan turunan ke-k. Dari fungsi pembangkit penjumlahan Z = X + Y dari dua peubah acak diskret X dan Y, berarti bahwa PZ ( z ) = PX ( z ) ⋅ PY ( z ). Dimana Z dengan peluang q sama dengan X dan dengan peluang 1 − q sama dengan Y, kemudian

PZ ( z ) = qPX ( z ) + (1 − q ) PY ( z ). 2.3 Transformasi Laplace – Stieltjes ~ Transformasi Laplace – Stieltjes X ( s ) dari peubah acak nonnegatif X dengan fungsi distribusi F(.) , didefinisikan sebagai

(

∞

) ∫e

~ X ( s ) = E e − sX =

− sx

dF ( x ) , s ≥ 0

x= 0

Dimana peubah acak X memiliki kepekatan f(.), kemudian transformasi disederhanakan menjadi ~ X ( s) =

∞

∫e

− sx

f ( x ) dx, s ≥ 0

x= 0

~ Anggap bahwa X ( s ) ≤ 1 untuk semua s ≥ 0 . Lebih lanjut ~ X ( 0) = 1,

( )

~ ~ k X ' ( 0 ) = − E ( X ) , X ( k ) ( 0) = ( − 1) E X k .

Untuk transformasi dengan jumlah Z = X +Y dari dua peubah acak independent X dan Y, kemudian ini dianggap ~ ~ ~ Z ( s ) = X ( s ) ⋅ Y ( s ). Dimana Z dengan peluang q sama dengan X dan dengan peluang 1 – q sama dengan Y, kemudian ~ ~ ~ Z ( s ) = qX ( s ) + (1 − q )Y ( s ). 2.4 Kegunaan Distribusi Peluang Sesi ini mendiskusikan beberapa distribusi penting yang sangat berguna untuk mendeskripsikan peubah acak di banyak aplikasi. 2.4.1 Distribusi Geometri Sebuah peubah acak geometrik X dengan parameter p memiliki distribusi peluang P( X = n ) = (1 − p ) p n , n = 0,1, 2, ...

Dari distribusi ini kita dapati PX ( z ) =

1− p , 1 − pz

E( X ) =

p , 1− p

σ

2

(X) =

p , (1 − p ) 2

2

cX =

1 . p

2.4.2 Distribusi Poisson Sebuah peubah acak poisson X dengan parameter µ memiliki distribusi peluang P( X = n ) =

µ n −µ e , n!

n = 0, 1, 2, ...

Dari distribusi poisson kita dapati PX ( z ) = e − µ ( 1− z ) ,

E( X ) = σ

2

(X) =

µ,

c X2 =

1 µ

2.4.3 Distribusi Eksponensial Kepekatan dari sebuah distribusi eksponensial dengan parameter µ adalah f (t ) = µ e− µ t ,

t > 0.

Untuk distribusi ini kita memiliki ~ X ( s) =

µ , µ + s

E( X ) =

1 , µ

σ

2

(X) =

1 , µ2

cX = 1

Sifat penting dari peubah acak eksponensial X dengan parameter µ memoryless. Sifat ini mentapkan bahwa untuk setiap x ≥ 0 dan t ≥ 0 ,

adalah sifat

P( X > x + t | X > t ) = P( X > x ) = e − µ x . Jadi sisa hidup X, menyajikan bahwa X tetap hidup pada waktu t, begitu juga distribusi eksponensial dengan mean sama 1 / µ . Kita sering menggunakan sifat memoryless didalam bentuk P ( X > x + t | X > t ) = 1 − e − µ ∆ t = µ ∆ t + o( ∆ t ) ,

( ∆ t → 0)

(2.1)

Dimana o( ∆ t ) , ( ∆ t → 0 ) , adalah notasi steno untuk sebuah fungsi, sebut g ( ∆ t ) , dimana g ( ∆ t ) / ∆ t cenderung ke 0 ketika ∆ t → 0 .

Jika X 1 ,  , X n adalah peubah acak eksponensial independen dengan parameter µ 1 ,  , µ n , kemudian min( X 1 ,  , X n ) adalah juga merupakan peubah acak eksponensial dengan parameter µ 1 +  + µ n dan peluang bahwa X i adalah yang terkecil yang didapat dari µ 1 / ( µ 1 +  + µ n ) , i = 1,  , n. 2.4.4 Distribusi Erlang Sebuah peubah acak X memiliki distribusi Erlang-k (k = 1,2,…) dengan mean k / µ jika X adalah jumlah dari k peubah acak independen X 1 ,  , X k memiliki distribusi eksponensial biasa dengan mean 1 / µ . Notasi biasanya adalah Ek ( µ ) atau disingkat Ek . kepekatan distribusi Ek ( µ ) adalah f (t) = µ

( µ t ) k− 1 e− µ t , ( k − 1) !

t > 0.

Fungsi distribusi ini sama dengan f (t) = 1−

( µ t ) k − 1 e− µ t , ∑j = 0 ( k − 1) ! k−1

t≥ 0