MODEL TEORI ANTRIAN

Model Teori Antrian

Pendahuluan
Teori antrian adalah teori yang menyangkut studi matematis dari antrian-antrian atau baris baris penungguan.

Contoh contoh kasus antrian :
1. Para pembelanja yang berdiri didepan kounter di supermarket.
2. Mobil-mobil yang menunggu di lampu merah.
3. Pasien yang menunggu diklinik rawat jalan.
4. Pesawat yang menunggu lepas landas dibandara udara.
5. Mesin-mesin rusak yang menunggu untuk diperbaiki oleh petugas perbaikan mesin.
6. Surat yang menunggu diketik oleh seorang sekretaris.
7. Program yang menunggu untuk diproses oleh komputer digital.
Fenomena menunggu adalah hasil langsung dari keacakan dalam operasi sarana pelayanan secara umum, kedatangan pelangan dan waktu pelayanan tidak diketahui sebelumnya karena jika bisa diketahui, pengoperasian sarana tersebut dapat dijadwalkan sedemikian rupa sehingga akan sepenuhnya menghilangkan keharusan untuk menunggu.
Tujuan mempelajari pengoeprasian sebuah sarana pelayanan dalam kondisi acak adalah untuk memperoleh beberapa karakteristik yang mengukur kinerja sistem yang sedang dipelajari.Dalam model antrian, interaksi antara pelanggan dan pelayan adalah berkaitan dengan periode waktu yang diperoleh pelanggan untuk menyelesaikan sebuah pelayanan, dalam antrian kedatangan pelanggan umumnya disebut sebagai distribusi kedatangan (arrival distribution) dan distribusi waktu pelayanan (service time distribution)
Faktor faktor penting dalam pengembangan model antrian :
• Cara memilih pelanggan dari antrian untuk memulai pelayanan
FCFS ( first come first served)
LCFS ( last come first served)
SIRO ( served in random order)

• Berkaitan dengan rancangan sarana dan pelaksanaan pelayanan
Parralel served
Serial served
Random served
• Berkaitan dengan rancangan sarana tersebut dan pelaksanaan pelayanan.
• Berkaitan dengan ukuran antrian yang diijinkan.
• Berkaitan dengan sifat sumber yang meminta pelayanan.
Unsur unsur dasar model antrian bergantung pada faktor :
1. Distribusi kedatangan( kedatangan tunggal atau kelompok )
2. Distribusi waktu pelayanan ( pelayanan tunggal atau kelompok )
3. Rancangan sarana pelayanan (stasiun serial, paralel atau jaringan )
4. Peraturan pelayanan(FCFS, LCFS, SIRO) dan prioritas utama.
5. Ukuran antrian( terhingga atau tidak hingga )
6. Sumber pemanggilan(terhingga atau tidak terhingga)
7. Perilaku manusia( perpindahan, penolakan atau pembatalan).
Peran Distribusi Poisson dan Eksponensial
Situasi antrian dimana kedatangan dan keberangkatan (kejadian) yang timbul selama interval waktu dikendalikan dengan kondisi berikut :
Kondisi 1 : Probabilitas dari sebuah kejadian( kedatangan atau keberangkatan)yang timbul antara t dan t +s bergantung hanya pada panjang s, yang berarti bahwa probabilitas tidak bergantung pada t atau jumlah kejadian yang timbul selama periode waktu (0,t).
Kondisi 2 : Probabilitas kejadian yang timbul selama interval waktu yang sangat kecil h adalah positif tapi kurang dari satu.
Kondisi 3: Paling banyak satu kejadian dapat timbul selama interval waktu yang sangat kecil h.
Ketiga kondisi diatas menjabarkan sebuah proses dimana julah kejadian selama satu interval waktu yang diberikan adalah Poisson, dan karena itu interval waktu antara beberapa kejadian yang berturut turut adalah eksponensial. Dengan kasus demikian, kita katakan bahwa kondisi kondisi tersebut mewakili proses Poisson.
Dalam mengelompokkan model-model antrian yang berbeda-beda, akan digunakan suatu notasi yang disebut Kendall’s Notation. Notasi ini sering dipergunakan karena beberapa alasan. Pertama, karena notasi tersebut merupakan alat yang efisien untuk mengidentifikasi tidak hanya model-model antrian, tetapi juga asumsi-asumsi yang harus dipenuhi. Kedua, hampir semua buku yang membahas teori antrian menggunakan notasi ini.
Gambar berikut ini akan memperjelas penggunaan notasi tersebut, dan contoh model yang disajikan adalah model M/M/I/I/I.
Populasi(I) Antrian (M) FCFS Fasilitas Pelayanan (M/I)


Kepanjangan
Antrian Tak
Terbatas (I)
Bentuk Model Umum :

Tingkat Tingkat Jumlah Besarnya Kedatangan
Kepanjangan Pelayanan Fasilitas Pelayanan Populasi antrian

Notasi yang sering dipakai adalah :
Singkatan Penjelasan
M Tingkat kedatangan dan/atau pelayanan Poisson
D Tingkat kedatangan dan/atau pelayanan Deterministik (diketahui konstan)
K Distribusi Erlang waktu antar kedatangan atau pelayanan
S Jumlah fasilitas pelayanan
I Sumber populasi atau kepanjangan antrian tak-terbatas (infinite)
F Sumber populasi atau kepanjangan antrian terbatas (finite)

Tanda pertama notasi selalu menunjukkan distribusi tingkat kedatangan. Dalam hal ini, M menunjukkan tingkat kedatangan mengikuti distribusi probabilitas Poisson. Tanda kedua menunjukkan distribusi tingkat pelayanan. Tanda ketiga menunjukkan jumlah fasilitas pelayanan dalam sistem. Tanda keempat dan kelima ditambahkan untuk menunjukkan apakah sumber populasi dan kepanjangan antrian adalah tak-terbatas (I) atau terbatas (F).

Lebih jelasnya model-model antrian yang ada adalah sebagai berikut :
1. Single Channel dengan kedatangan Poisson dan waktu pelayanan Eksponensial
Antrian dengan saluran tunggal merupakan model antrian yang paling sederhana dan banyak dijumpai. Asumsi yang digunakan dalam model ini adalah :
- kedatangan digambarkan berdistribusi poisson
- kedatangan berasal dari populasi tak terbatas
- pelayanan didasarkan pada first come first served
- tak ada kasus “balking” atau “renege”
- laju kedatangan rata-rata konstan sepanjang waktu
- waktu pelayanan dideskripsikan berdistribusi eksponensial negatif
- rata-rata waktu pelayanan konstan
- rata-rata laju pelayanan lebih besar dari rata-rata laju kedatangan.
Berdasar pada delapan asumsi ini, maka sejumlah persamaan yang menggambarkan kondisi antrian dengan single channel yang sudah steady-state dapat dikembangkan.

Berikut ini notasi yang akan dipakai dalam persamaan :
 = rata-rata jumlah kedatangan per periode atau rata-rata tingkat/laju kedatangan
 = rata-rata jumlah customer yang dilayani per periode atau rata-rata tingkat/laju pelayanan
Dengan menggunakan notasi tersebut, maka karakteristik operasi dari antrian single channel adalah sebagai berikut :
• Probabilitas bahwa sistem antrian idle = probabilitas bahwa tidak ada individu di dalam sistem antrian = P0 = (1-/)
• Probabilitas bahwa terdapat n individu dalam sistem antrian = Pn = (/)nP0
• Jumlah individu rata-rata dalam sistem antrian = L = /( - )
• Jumlah individu rata-rata dalam antrian = Lq = 2/( - ) = L - /
• Waktu tunggu rata-rata dalam sistem antrian = W = 1/( - ) = L/
• Waktu tunggu rata-rata dalam antrian = Wq = /( - ) = Lq/ = W – 1/
• Probabilitas bahwa suatu kedatangan harus menunggu untuk dilayani = faktor utilisasi sistem antrian = Pw =  = /

2. Model antrian Multiple channel dengan distribusi kedatangan Poisson dan waktu pelayananan eksponensial
Model antrian ini digambarkan dengan adanya antrian tunggal dan kemudian dilayani satu stage, dimana ada s (lebih dari satu server) yang bekerja secara pararel.

Dengan menggunakan notasi yang sama bisa diperoleh persamaan berikut
• Probabilitas bahwa sistem antrian idle = probabilitas bahwa tidak ada individu di dalam sistem antrian = P0
untuk s >2
• Probabilitas bahwa terdapat n individu dalam sisem antrian = Pn =
untuk n  s
atau
untuk n > s
• Jumlah individu rata-rata dalam antrian = Lq =

• Jumlah individu rata-rata dalam sistem antrian = L = Lq + /
• Waktu tunggu rata-rata dalam antrian = Wq = Lq/
• Waktu tunggu rata-rata dalam sistem antrian = W = Wq + 1/ = L/
• Faktor utilisasi sistem antrian =  = /(s)
• Probabilitas bahwa suatu kedatangan harus menunggu untuk dilayani = Pw

3. Model antrian Multiple channel-multiple stage
Model antrian Multiple channel-multiple stage dapat dipandang sebagai proses produksi flow shops atau job shops. Proses produksi flow shop adalah proses poduksi dimana semua pekerjaan melalui urutan proses pengerjaan yang sama, sedangkan pada job shop, masing-masing pekerjaan mempunyai urutan pengerjaan yang berbeda-beda, tergantung dari jenis pekerjaan tersebut.
Kondisi job shop yang ekstrim dinamakan randomly-routed job shop, dimana tidak ada pola yang umum bagi urutan pengerjaan dari mesin ke mesin untuk masing-masing pekerjaan.
Flow shops dan job shops dapat divisualisasikan sebagai antrian dimana terdapat pengaturan terhadap multiple server (multiple stage) dengan konsumen mendatangi lebih dari satu server sebelum meninggalkan sistem. Hasil-hasil teori yang ada ditekankan pada identifikasi kondisi khusus pada mesin individu yang independent dan antrian pada tiap mesin dianalisa secara terpisah. Secara umum kondisi ini membutuhkan asumsi-asumsi sebagai berikut :
a. Input proses berdistribusi Poisson
b. Routing dari pekerjaan independen terhadap status sistem
c. Waktu proses berdistribusi eksponensial (beberapa generalisasi masih dimungkinkan)
d. Order pengurutan pekerjaan pada sebuah mesin, independen terhadap:
• waktu proses
• routing pekerjaan
• pengetahuan tentang kedatangan pekerjaan mendatang pada sebuah mesin
Notasi dengan empat-parameter digunakan untuk mengidentifikasi permasalahan penjadwalan individual, yang dituliskan menjadi A/B/C/D, dimana :
A Menggambarkan kedatangan pekerjaan. Untuk permasalahan dinamis, A mengidentifikasi distribusi probabilitas dari waktu antar kedatangan pekerjaan. Untuk permasalahan statis, menggambarkan jumlah pekerjaan, yang datang secara simultan. Jika dinotasikan dengan n maka berarti mengindikasikan sejumlah perkerjaan yang terbatas.
B Menggambarkan jumlah mesin yang ada. Jika dinotasikan dengan m berarti menandakan sejumlah mesin tertentu yang terbatas.
C Menggambarkan pola aliran pekerjaan. Simbol utama yang digunakan adalah :
F untuk kasus flow shop
R untuk kasus randomly-routed job shop
G untuk kasus pola aliran yang umum secara total
D Menggambarkan kriteria evaluasi penjadwalan
Contoh :
n/2/F/Fmax : urutan sejumlah pekerjaan pada 2 mesin untuk proses produksi flow shop yang bertujuan untuk meminimalkan maksimum flow time.
n/m/G/Fmax : penjadwalan n pekerjaan pada m mesin sehingga pekerjaan terakhir dapat diselesaikan secepat mungkin

Atas dasar sifat proses pelayanannya, struktur antrian dapat diklasifikasikan menurut susunan saluran (channel) dan phase, yang akan membentuk suatu struktur antrian yang berbeda-beda. Istilah saluran atau channel menunjukkan jumlah jalur untuk memasuki sistem, atau dengan kata lain menunjukkan jumlah fasilitas pelayanan. Sedangkan istilah phase berarti jumlah stasiun pelayanan dimana customer harus melaluinya sebelum pelayanan dinyatakan lengkap.
Ada 4 model struktur antrian dasar yang umum terjadi, yakni :
Single channel – single phase, berarti hanya ada satu jalur untuk memasuki sistem dan hanya ada satu stasiun pelayanan. Contoh untuk model struktur ini adalah pelayanan pada pembelian tiket KA, supermarket, tukang cukur, dan sebagainya.
Sistem Antrian


Sumber populasi Keluar
Keterangan : M = antrian
S = stasiun pelayanan

Gambar 3.3. Sistem Antrian Single channel-Single phase

Single channel – multiphase, yang berarti hanya ada satu jalur untuk memasuki sistem, tetapi ada lebih dari satu stasiun pelayanan yang berurutan. Contoh model antrian ini adalah pada lini produksi massa, pencucian mobil, bengkel motor, dan sebagainya.
Sistem Antrian


Sumber populasi keluar

Phase 1 Phase 2

Gambar 3.4. Sistem Antrian Single channel – multiphase
Multichannel – single phase, yang berarti ada lebih dari satu jalur untuk memasuki sistem, namun hanya ada satu stasiun pelayanan. Contoh model ini terdapat pada sistem pembayaran di supermarket, pembelian tiket yang dilayani oleh lebih dari satu loket, pelayanan potong rambut oleh beberapa tukang potong, dan sebagainya.
Sistem Antrian


Sumber populasi Keluar

Gambar 3.5. Sistem Antrian Multichannel – single phase
Multichannel – multiphase, yang berarti ada lebih dari satu jalur untuk memasuki sistem dan ada lebih dari satu stasiun pelayanan. Contoh model struktur antrian ini terdapat pada pelayanan pasien di rumah sakit, produksi massa dengan lebih dari satu lini produksi, dan lain-lain.
Sistem Antrian



Sumber populasi Keluar

Phase 1 Phase 2
Gambar Sistem Antrian Multichannet – multiphase
Minimasi Biaya
Tujuan dari model antrian adalah untuk minimasi biaya. Biaya dalam sistem antrian umumnya meliputi biaya menunggu dan biaya pelayanan. Jika biaya menunggu per unit waktu per individu sebesar cw dan biaya per periode waktu per fasilitas pelayanan sebesar cs, sedangkan dan S adalah jumlah fasilitas pelayanan; maka biaya total rata-rata
(expected total cost) = E(Ct) = E(Cs) + E(Cw) = Scs + Lcw