TEORI ANTRIAN
MAKALAH Oleh
Ferry Prianto ( 1014290131 )
Fakultas / Jurusan : Ekonomi / Manajemen Hari / Jam Kuliah : Rabu 17:00 – 19:30
FE UPI YAI 2012 Jakarta
KATA PENGANTAR
Puji syukur saya ucapkan kepada Tuhan Yang Maha Esa atas segala nikmat dan rahmat-Nya, sehingga makalah ini dapat diselesaikan dengan baik dan tepat pada waktunya. Adapun tujuan dari penulisan makalah ini adalah untuk menambah pengetahuan kita tentang “Teori Antrian” serta dapat mempersiapkan diri sebaik-baiknya untuk menghadapinya. Dalam kesempatan ini perkenankan saya mengucapkan terima kasih kepada dosen “Manajemen Operasional 2” yang telah memberikan tugas ini kepada saya. Dan juga terima kasih kepada teman-teman yang mau membantu dalam pengerjaan tugas ini. Saya telah berusaha dengan sebaik mungkin dalam menyelesaikan makalah ini, dan dengan segala kerendahan hati saya sangat menghargai segala kritik dan saran yang membangun dari pembaca dan teman-teman untuk penyempurnaan tugas ini. Akhir kata saya berharap semoga makalah ini dapat bermanfaat bagi pembaca dan teman-teman.
Jakarta, 13 Juni 2012
Penulis
BAB I PENDAHULUAN 1.1 Latar Belakang Untuk mempertahankan pelanggan, sebuah organisasi selalu berusaha untuk memberikan pelayanan yang terbaik. Pelayanan yang terbaik tersebut diantaranya adalah memberikan pelayanan yang cepat sehingga pelanggan tidak dibiarkan menunggu (mengantri) terlalu lama. Namun demikian, dampak pemberian layanan yang cepat ini akan menimbulkan biaya bagi organisasi, karena harus menambah fasilitas layanan. Oleh karena itu, layanan yang cepat akan sangat membantu untuk mempertahankan pelanggan, yang dalam jangka panjang tentu saja akan meningkatkan keuntungan perusahaan. Kata antrian datang, melalui perancis, dari bahasa Latin cauda, yang berarti ekor. Teori queueing umumnya dianggap sebagai sebuah cabang dari riset operasi karena hasil sering digunakan ketika membuat keputusan yang dibutuhkan untuk menyediakan layanan. Aplikasi yang sering ditemui dalam layanan pelanggan situasi serta transportasi dan telekomunikasi. Teori queueing langsung diterapkan pada sistem transportasi cerdas, call center, PABXs, jaringan, telekomunikasi, server queueing, mainframe komputer terminal queueing telekomunikasi, sistem telekomunikasi maju, dan arus lalu lintas.
1.2 Tujuan Penulis Tulisan ini bertujuan untuk menambah wawasan para pembaca, khususnya para mahasiswa/i jurusan manajemen, fakultas ekonomi Universitas Persada Indonesia Y.A.I agar mengetahui dan mengerti tentang Teori Antrian. Dan sebagai tugas mata kuliah “Manajemen Operasional 2”.
1.3 Metode Penulisan Metode yang penulis pakai dalam penulisan makalah ini adalah mengkumpulkan artikel-artikel dari teman-teman dan dari berbagai sumber, lalu kemudian dirangkum menjadi satu dalam sebuah makalah yang berisikan tentang “ Teori Antrian “. Metode penulisan bisa Dengan cara apa saja, seperti : mengutipnya dari internet.
BAB II ISI MATERI
DEFINISI Antrian terdapat pada kondisi apabila obyek-obyek menuju suatu area untuk dilayani, namun kemudian menghadapi keterlambatan disebabkan oleh mekanisme
pelayanan
mengalami
kesibukan.
Antrian
timbul
karena
adanya
ketidakseimbangan antara yang dilayani dengan pelayanannya.
Tujuan penggunaan teori antrian adalah untuk adalah untuk merancang fasilitas pelayanan, untuk mengatasi permintaan pelayanan yang berfluktuasi secara random dan menjaga keseimbangan antara biaya (waktu nganggur) pelayanan dan biaya (waktu) yang diperlukan selama antri.
Teori antrian pertama kali dikemukakan oleh A.K.Erlang, seorang ahli matematika bangsa Denmark pada Erlang, seorang ahli matematika bangsa Denmark pada tahun 1913 dalam bukunya Solution of Some Problem in the Theory of Probability of Significance in Automatic Telephone Exchange.
5
KARAKTERISTIK SISTIM ANTRIAN
Terdapat empat karakteristik system antrian yaitu,
1. Sumber Input Menggambarkan bentuk dan ukuran kedatangan konsumen pada fasilitas pelayanan yang kedatangannya mungkin saja tidak merata atau dapat mengikuti pola kedatangan poisson atau pola lain. Ukuran kedatangan konsumen yaitu jumlah total unit yang memerlukan pelayanan dari waktu ke waktu disebut juga total langganan potensial. 2. Antrian Karakteristik suatu antrian ditentukan oleh unit maksimum yang boleh ada didalam sistemnya yang terbatas maupun tidak terbatas. 3. Distribusi Pelayanan Distribusi pelayanan berkaitan dengan cara memilih anggota antrian yang akan dilayani. Bentuk disiplin pelayanannya dapat berupa: a. First Come First Serve (FCFS) atau FIFO adalah system antrian yang mendahulukan yang dating lebih awal b. Last Come First Served (LCFS) atau LIFO, adalah yang datang terakhir akan lebih dahulu dilayani atau lebih dahulu keluar. c. Service In Random Order (SIRO) adalah pemanggilan didasarkan pada peluang secara acak, tidak jadi persoalan siapa yang lebih dahulu datang.
6
d. Priority Service (PS) , melayani lebih dahulu orang yang mempunyai prioritas lebih tinggi ketibang orang yang mempunyai prioritas lebih rendah. 4. Mekanisme Pelayanan Mekanisme pelayanan terdiri atas satu atau lebih fasilitas pelayanan yang masingmasing terdiri dari satu atau lebih saluran pelayanan.
MODEL DASAR ANTRIAN Sebuah model dasar dari sebuah pusat layanan. Pelanggan datang ke pusat layanan disecara acak. Fasilitas pelayanan dapat memiliki satu atau beberapa server, setiap server yang mampu melayani satu pelanggan pada waktu (dengan satu perkecualian), layanan waktu yang dibutuhkan untuk setiap pelanggan juga dimodelkan sebagai variabel acak. Penjelasan lebih lengkapnya dapat dilihat sebagai berikut :
7
Sistem antrian mungkin tidak hanya berbeda dalam distribusi mereka dari interarrival-dan waktu pelayanan, tetapi juga dalam jumlah server, ukuran garis tunggu (tak terbatas atau terbatas). Skema ini dapat menggunakan preemption atau tidak. Notasi Kendall digunakan untuk karakterisasi sistem antrian pendek. Sebuah sistem antrian deskripsi terlihat sebagai berikut:
Dimana A menunjukkan distribusi dari waktu antar, B menunjukkan distribusi layanan kali, mdenotes jumlah server, N menunjukkan ukuran maksimum baris menunggu di terbatas kasus (jika N = 1 maka surat ini diabaikan) dan S opsional menunjukkan disiplin layanan yang digunakan (FIFO, LIFO dan sebagainya). Jika S adalah layanan dihilangkan disiplin selalu FIFO. Sistem antrian yang paling sederhana, sistem M/M/1 (dengan FIFO layanan) kemudian dapat digambarkan sebagai berikut: kita memiliki sebuah server tunggal, sebuah jalur menunggu tak terbatas, yang interarrival pelanggan dan waktu iid berdistribusi eksponensial dengan parameter λ dan layanan pelanggan kali juga iid dan berdistribusi eksponensial dengan parameter μ. Kita terutama tertarik dalam solusi konstan, yaitu dimana sistem setelah waktu berjalan lama cenderung
8
mencapai keadaan stabil, misalnya dimana distribusi pelanggan di sistem tidak berubah (membatasi distribusi).
Hal ini juga harus dibedakan dari solusi sementara, di mana jangka pendek respon sistem terhadap berbagai aktivitas diselidiki (misalnya kedatangan batch). Tren umum dalam teori antrian adalah sebagai berikut: jika kedua waktu dan waktu interarrival layanan adalah eksponensial (Markov), mudah untuk menghitung berapa pun sistem antrian.
TEKNIK-TEKNIK ANTRIAN Queuing adalah salah satu fungsi QoS yang menyimpan sementara paket-paket sebelum ditransmisikan. Jika paket-paket datang pada antrian paling akhir dari sebuah queue, maka paket-paket tersebut akan mengalami keterlambatan (delay). Berikut ini adalah beberapa teknik queuing dan penjelasannya:
1. First In First Out Teknik antrian FIFO mengacu pada FCFS (First Come First Server), paket data yang pertama datang diproses terlebih dahulu. Paket data yang keluar terlebih dahulu di masukan ke dalam antrian FIFO, kemudian dikeluarkan sesuai dengan urutan kedatangan. Teknik antrian FIFO sangat cocok untuk jaringan dengan bandwidth menengah 64kbps tetapi cukup menghabiskan sumber daya prosessor dan memori.
9
Gambar diatas menunjukkan kedatangan beberapa paket data yang berbeda waktu, paket pertama dari flow 8 yang tiba lebih awal dikeluarkan ke port terlebih dahulu oleh antrian FIFO.
2. Prioritas antrian Pada situasi tertentu kadangkala kita harus memutuskan suatu permasalahan dengan memilih salah satu solusi yang perlu di laksanakan terlebih dahulu dan hal ini di sebut prioritas. Hal ini sama jika kita memiliki bandwidth internet yang sempit, sedangkan ada transaksi penting yang tidak boleh di interupsi seperti layanan email smtp dan pop3. Traffic controll pada linux memberikan kita suatu fasilitas pengendalian prioritas trafik TCP/IP, kita dapat memberikan prioritas berdasarkan alamat port, IP address, subnet maupun jenis type of service. Prioritas di tandai dengan angka numerik 1 sampai dengan 100 misalnya, prioritas tertinggi dimiliki oleh angka 1 kemudian di ikuti dengan angka berikutnya.
10
3. Stochastic Fairness Queuing (SFQ) Stochastic Fairness Queuing (SFQ) memiliki kemampuan membagi setiap paket data yang diterima dalam jumlah yang sama rata, setiap paket data yang telah terbagi dimasukkan ke dalam suatu antrian dan menunggu dikeluarkan oleh penjadwalan, antrian dikeluarkan dengan algoritma round robin. Berikut ini adalah opsi dari teknik antrian SFQ: a. Perturb nilai[detik] algoritma hash akan di konfigurasi ulang secara otomatis tergantung dari nilai yang diberikan [detik]. b. Quantum nilai[bytes] Jumlah paket data stream yang dizinkan untuk di keluarkan (dequeue) sebelum antrian lain diproses. Nilainya tidak boleh dibawah MTU (Maximum Transfer Unit), untuk ethernet 10/100Mbit nilai MTU nya 1500 bytes, periksa dengan perintah “ifconfig”.
11
4. Token bucket filter Token bucket filter (TBF) membatasi bandwidth dengan metode shape & drop, prinsip kerja menggunakan aliran token yang memasuki bucket dengan kecepatan (rate) konstan, jika token dalam bucket habis maka paket data akan di antri dan kelebihannya dibuang, setiap paket data yang dikeluarkan identik dengan token. Token dalam bucket akan lebih cepat habis jika aliran paket data melampaui kecepatan token memasukki bucket, jadi kita asumsikan bahwa trafik melebihi batas konfigurasi.
12
5. Filtering Paket data yang akan memasuki antrian melalui klasifikasi (class) sebelumnya disaring filter) terlebih dahulu, agar setiap paket bisa ditentukan jenisnya, alamat IP, alamat PORT dan TOS nya. Kemudian fungsi yang kedua, filtering digunakan untuk mengarahkan suatu paket agar ke tujuan yang benar, ke klasifikasi paket (class) sesuai dengan arah alirannya, contoh:
Pada gambar diatas menunjukkan paket dibagi menjadi 3 bagian, untuk dari port ssh (22), alamat tujuan 192.168.1.0/24 dan dari port POP3 (110), sedangkan bilangan heksadesimal 0xfff menunjukkan semua paket dari sport xx.
13
Klasifikasi paket merupakan cara memberikan suatu kelas atau perbedaan pada setiap paket, hal ini dilakukan untuk mempermudah penanganan paket oleh antrian. Klasifikasi berbeda dengan filtering yang berfungsi mengarahkan dan menyaring aliran paket data. Contoh pada gambar dibawah ini menunjukkan paket data dibagi menjadi tiga kelas 1:1, 1:2 dan 1:3 dan tiap kelas tersebut ditangani oleh teknik antrian (qdisc) 10: (tbf), 20:(sfq) dan 30: (pfifo).
6. Class Based Queue (CBQ) Teknik klasifikasi paket data yang paling terkenal adalah CBQ, mudah dikonfigurasi, memungkinkan sharing bandwidth antar kelas (class) dan memiliki fasilitas user interface. CBQ mengatur pemakaian bandwidth jaringan yang dialokasikan untuk tiap user, pemakaian bandwidth yang melebihi nilai set akan dipotong (shaping), CBQ juga dapat diatur untuk sharing dan meminjam bandwidth antar class jika diperlukan.
14
Class Based Queueing (CBQ) adalah suatu mekanisme penjadwalan, bertujuan menyediakan Link Sharing antar kelas yang menggunakan jalur fisik yang sama, sebagai acuan untuk membedakan trafik ysng memiliki prioritas-prioritas yang berlainan. Dengan CBQ, setiap kelas dapat mengalokasikan bandwidth miliknya untuk berbagai jenis trafik yang berbeda, sesuai dengan pembagiannya yang tepat untuk masing-masing trafik.
Cara kerja Class Based Queueing (CBQ) dimulai saat classifier menentukan paket yang datang dan menempatkan ke kelas yang tepat. Kemudian general scheduler menentukan bandwidth yang diperuntukkan untuk suatu kelas, estimator memeriksa apakah kelas-kelas mendapatkan bandwidth sesuai dengan yang dialokasikan. Jika suatu kelas kekurangan maka dengan bantuan link-sharing scheduler kelas yang memiliki bandwidth yang tidak terpakai bisa dipinjamkan ke kelas yang membutuhkan tambahan bandwidth. CBQ dapat menerapkan pembagian kelas dan menshare link bandwidth melalui struktur kelas-kelas secara hirarki. Setiap kelas memiliki antriannya masingmasing dan diberikan jatah bandwidthnya. Sebuah kelas child dapat meminjam bandwidth dari kelas parent selama terdapat kelebihan bandwidth. Gambar di atas ini menunjukkan model dasar dari CBQ. Classifier akan mengarahkan paket-paket yang datang ke kelas-kelas yang bersesuaian. Estimator akan mengestimasi bandwidth yang sedang digunakan oleh sebuah kelas. Jika sebuah kelas telah melampaui limit yang telah ditentukannya, maka estimator akan menandai kelas tersebut sebagai kelas yang overlimit. Scheduler menentukan paket selanjutnya yang akan dikirim dari kelas-kelas
15
yang berbeda-beda, berdasarkan pada prioritas dan keadaan dari kelas-kelas. Weighted round robin scheduling digunakan antara kelas-kelas dengan prioritas yang sama
CBQ dengan link sharing memberikan keunggulan yaitu pemberian bandwidth yang tak terpakai bagi leaf class-nya. Ketika paket dating ke router akan mengantrikannya pada queue yang sesuai dengan priority class paket tersebut. Selanjutnya, router dapat menerapkan priority control yang akan mentransfer lebih banyak paketpaket berprioritas tinggi daripada paket berprioritas rendah. Pada CBQ terdapat beberapa komponen diantaranya adalah:
1. Classifier, bekerja dengan cara mengklasifikasikan paket-paket ke dalam classclass yang sesuai dengan menggunakan informasi yang ada di packet header. 2. General Scheduler, merupakan mekanisme penjadwalan bertujuan untuk membagi bandwidth saat seluruh kelas memiliki antrian paket. General Scheduler menjamin hak kuantitas layanan untuk tiap cabang class (leaf classes), dengan membagikan bandwidth sesuai dengan alokasinya masing-masing. General Scheduler bekerja apabila tidak terjadi kongesti pada router. 3. Link-sharing Scheduler, yang bertujuan membagikan bandwidth yang tak terpakai sesuai dengan struktur link-sharingnya. Link-sharing scheduler digunakan apabila terjadi kongesti pada router. 4. Estimator, akan menghitung bandwidth yang terpakai pada tiap kelas pada selang waktu tertentu untuk memastikan bahwa tiap kelas telah mendapatkan bandwidth sesuai bagiannya.
16
Pada jenis antrian CBQ mempunyai beberapa parameter yang digunakan yaitu: a. avpkt Jumlah paket rata – rata saat pengiriman b. Bandwidth lebar bandwidth kartu ethernet biasanya 10 – 100Mbit c. Rate Kecepatan rata – rata paket data saat meninggalkan qdisc, ini parameter untuk men-set bandwidth. d. Cell Peningkatan paket data yang dikeluarkan ke kartu ethernet berdasarkan jumlah byte, misalnya 800 ke 808 dengan nilai cell 8. e. Isolated / sharing Parameter isolated mengatur agar bandwidth tidak bisa dipinjam oleh klas (class) lain yang sama tingkat / sibling. Parameter sharing menunjukkan bandwidth kelas (class) bisa dipinjam oleh kelas lain. f. Bounded / borrow Parameter borrow berarti kelas (class) dapat meminjam bandwidth dari klas lain, sedangkan bounded berarti sebaliknya.
17
Disini kita akan menganalisa throughputnya. Throughput merupakan laju data aktual yang terukur pada suatu ukuran dalam waktu tertentu. Walaupun throughput memiliki satuan dan rumus yang sama dengan laju data, tetapi throughput lebih pada menggambarkan laju data yang sebenarnya (aktual) pada suatu waktu tertentu dan pada kondisi dan jaringan internet tertentu yang digunakan untuk mendownload suatu file atau data dengan ukuran tertentu. Throughput = Ukuran Data Yang Diterima / Total Waktu Pengiriman Data
7. Hierarchy Token Bucket (HTB) Teknik antrian HTB mirip dengan CBQ hanya perbedaannya terletak pada opsi, HTB lebih sedikit opsi saat konfigurasi serta lebih presisi. Teknik antrian HTB memberikan kita fasilitas pembatasan trafik pada setiap level maupun klasifikasi, bandwidth yang tidak terpakai bisa digunakan oleh klasifikasi yang lebih rendah. Kita juga dapat melihat HTB seperti suatu struktur organisasi dimana pada setiap bagian memiliki wewenang dan mampu membantu bagian lain yang memerlukan, teknik antrian HTB sangat cocok diterapkan pada perusahaan dengan banyak struktur organisasi. Pada antrian HTB mempunya parameter yang menyusunnya dalam antrian yaitu: 1. Rate parameter rate menentukan bandwidth maksimum yang bisa dipakai oleh setiap class, jika bandwidth melebihi nilai “rate” maka paket data akan dipotong atau di jatuhkan (drop). 2. Ceil parameter ceil di set untuk menentukan peminjaman bandwidth antar class (kelas), peminjaman bandwith dilakukan class paling bawah ke kelas di atasnya, teknik ini disebut link sharing.
18
8. Random Early Detection (RED) Random Early Detection atau bisa disebut Random Early Drop biasanya dipergunakan untuk gateway / router backbone dengan tingkat trafik yang sangat tinggi. RED mengendalikan trafik jaringan sehingga terhindar dari kemacetan pada saat trafik tinggi berdasarkan pemantauan perubahan nilai antrian minimum dan maksimum. Jika isi antrian dibawah nilai minimum maka mode 'drop' tidak berlaku, saat antrian mulai terisi hingga melebihi nilai maksimum maka RED akan membuang (drop) paket data secara acak sehingga kemacetan pada jaringan dapat dihindari. Pada antrian RED juga mempunya parameter yang menyusunnya yaitu:
a. min Nilai rata – rata minimum antrian (queue) b. max Nilai rata – rata maksimum antrian, biasanya dua kali nilai minimum atau dengan rumus; max = bandwidth [Bps] * latency [sec] c. probability Jumlah maksimum probabilitas penandaan paket data nilainya berkisar 0.0 sampai dengan 1.0.
19
d. limit Batas paling atas antrian secara riil, jumlah paket data yang melewati nilai limit pasti dibuang. Nilai limit harus lebih besar daripada 'max' dan dinyatakan dengan persamaan. limit = max + burst e. burst Digunakan untuk menentukan kecepatan perhitungan nilai antrain mempengaruhi antrian riil (limit). Untuk praktek nilainya kita set dengan rumus; burst = (min+min+max) / 3 * avpkt f. avpkt Nilai rata – rata paket data / trafik yang melintasi gateway RED, sebaiknya diisi 1000. g. bandwidth Lebar band (bandwidth) kartu ethernet. h. ecn Explicit Congestion Notification memberikan fasilitas gateway RED untuk memberitahukan kepada klien jika terjadi kemacetan. Device egress mengendalikan paket data yang keluar dari ethernet tapi tidak bisa membatasi jumlah rata – rata paket yang memasuki ethernet. Policing mengendalikan paket data yang memasuki kartu ethernet melalui device ingress, administrator memberikan batas maksimum paket yang boleh melewati ingress dan policing akan membuang paket jika melebihi batas maksimum konfigurasi.
20
Setting policing dapat dilakukan dengan dua cara, pertama dengan iptables mangle dan kedua melalui cara manual. Pada iptables mangle paket yang memasuki device ingress diberikan tanda dengan opsi mangle dari iptables, paket tersebut kemudian diproses oleh policing. Pada cara manual paket data di filter dengan opsi “match ip” secara langsung. Klasifikasi paket data pada policing ada beberapa macam seperti berikut: a. fw Menggunakan iptables mangle untuk klasifikasi paket data. b. route Menggunakan ip route untuk klasifikasi paket data yang akan dikirimkan / di route ke lain subnet. c. drop Paket data akan di buang atau di antrikan jika melampaui batas maksimum konfigurasi. d. continue Paket data jika melebihi batas maksimum konfigurasi akan di berikan ke klasifikasi berikutnya, jadi kita dapat membuat skala bandwidth pada device ingress. e. pass / ok Paket data yang melampaui batas maksimum konfigurasi boleh melintas. f. reclassify Paket data di klasifikasi oleh kelas berikutnya.
21
BAB III KESIMPULAN
Ada empat karakteristik sistem antrian yaitu Sumber Input, Antrian, Distribusi Pelayanan, Mekanisme Pelayanan. Queuing adalah salah satu fungsi QoS yang menyimpan sementara paket-paket sebelum ditransmisikan. Jika paket-paket datang pada antrian paling akhir dari sebuah queue, maka paket-paket tersebut akan mengalami keterlambatan (delay). Teknik-teknik queuing ada delapan yaitu First In First Out, Prioritas antrian, Stochastic Fairness Queuing (SFQ), Token bucket filter, Filtering, Class Based Queue (CBQ), Hierarchy Token Bucket (HTB), Random Early Detection (RED). Sistem antrian mengungkap utilisasi fasilitas, rata-rata waktu dalam sistem dan antrian, serta rata-rata jumlah pelanggan dalam sistem dan antrian.
22
KATA PENUTUP Demikian makalah ini saya buat, saya sangat mengharapkan kritik dan saran yang membangun demi kesempurnaan makalah ini. Saya mohon maaf jika ada kekurangan dari isi makalah saya. Atas perhatiannya saya ucapkan terima kasih.
23
Daftar Pustaka
www.google.com
24
