teori antrian 2

Universitas Bengkulu 2011 Teori Antrian

Kuliah #2Teori Antrian

Arie Vatresiaarie.vatresia@unib.ac.id

Outline

Overview Sistem Antrian Karakteristik proses antrian Notasi Dasar sistem antrian

Universitas Bengkulu 2011 Teori Antrian

Saya dan Antrian Situasi kehidupan nyata

Menunggu untuk membeli bensin Menunggu untuk naik wahana di Dufan Menunggu utk ambil uang di ATM Menunggu lampu hijau Menunggu … Dll.

Universitas Bengkulu 2011 Teori Antrian

Siapa yang Senang Menunggu? Pelanggan/customer jelas tidak Pengusaha juga tidak

Biaya lebih Membutuhkan biaya ruang lebih utk

menunggu Kehilangan pelanggan Pelanggan tidak bahagia

Lalu Mengapa Menunggu? Permintaan/demand > Layanan/service yg

tersedia Mengapa layanan tdk mencukupi?

Tidak ekonomis Tidak ada ruang Kedatangan yg tdk dp diprediksi

Masih Menunggu … Pertanyaan menarik untuk pelanggan?

Berapa lama saya harus menunggu? Berapa orang dlm barisan? Kapan sebaiknya saya datang utk

mendapatkan layanan lebih cepat?

Masih Menunggu … Pertanyaan menarik utk service provider?

Seberapa besar area tunggu? Berapa banyak pelanggan pergi? Apakah sebaiknya teler ditambah? Apakah sebaiknya sistem membentuk 1

atau 3 barisan antrian? Apakah sebaiknya sistem menyediakan jalur

cepat?

Akhirnya … Datang Teori Antrian

Menjelaskan fenomena antrian Menunggu dan melayani

Memodelkan sistem secara matematis Mencoba menjawab pertanyaan-pertanyaan

tadi

Sistem Antrian Kedatangan utk layanan Menunggu utk layanan Mendapat layanan Meninggalkan sistem

Sistem Antrian Umum

Karakteristik Proses Antrian Pola kedatangan Pola layanan Disiplin antrian Kapasitas sistem Jumlah kanal layanan Jumlah tingkat/stages layanan

Pola Kedatangan Stochastic

Distribusi probabilitas Kedatangan tunggal/single atau batch

Kelakuan pelanggan Pelanggan sabar

Menunggu selamanya Pelanggan tidak sabar

Menunggu utk suatu perioda waktu dan memutuskan utk pergi

Melihat antrian panjang dan memutuskan tdk bergabung

Mengubah barisan utk menunggu

Pola Kedatangan Apakah time dependent?

Pola kedatangan Stationary (time independent – probability distribution)

Pola kedatangan Nonstationary

Pola Layanan Distribusi utk waktu layanan Layanan tunggal/single atau batch (mesin

paralel) Proses layanan tergantung jumlah

pelanggan menunggu (state dependent) Layanan sangat cepat masih memerlukan

antrian? Tergantung juga pada kedatangan Mengasumsikan mutually independent

Disiplin Antrian

Cara pelanggan-pelanggan mendapatkan layanan First come, first serve Last come, first serve Random serve Priority serve

Preemptive Nonpreemptive

Kapasitas Sistem Kapasitas terbatas

Ukuran sistem maksimum Kapasitas tdk terbatas

Jumlah Kanal Layanan Sistem antrian multiserver

Single line service Multiple line service

Tingkat/Stages Layanan Single stage Multiple stages

Tanpa feedback (Entrance Exam) Dg feedback (Manufacturing)

Notasi Antrian Notasi Kendall (1953)

A / B / X / Y / Z

A : Distribusi waktu antar kedatanganB : Distribusi waktu layananX : # kanal layanan paralelY : Kapasitas sistemZ : Disiplin antrian

Notasi Antrian A/B/X/Y/Z

Notasi Antrian A/B/X/Y/Z M/M/3/∞/FCFS

Waktu antar kedatangan exponential Waktu layanan exponential 3 server paralel Ruang tunggu tdk terbatas Disiplin antrian First-Come First-Serve

Notasi Antrian A/B/X/Y/Z M/D/1

Waktu antar kedatangan exponential Waktu layanan Deterministic 1 server Ruang tunggu tdk terbatas (default) Disiplin antrian FCFS (default)

Notasi Antrian A/B/X/Y/Z M/M/1 M/M/c/k M/M/∞ Ek/M/1 M/G/1 G/M/m G/G/1

Lab. Telematika ITB 2006hend@telecom.ee.itb.ac.id

ET6040 Jaringan Antrian

Sistem Antrian - Dasar G/G/m

Waktu antar kedatangan dg distribusi A(t) Waktu layanan dg distribusi B(x) m servers

Cn: pelanggan ke-n memasuki sistem

Sistem Antrian - Dasar

n: waktu kedatangan utk Cn

tn: Waktu antar kedatangan (n – n-1)

xn: service time utk Cn

Sistem Antrian - Dasar

wn: waktu tunggu dlm antrian utk Cn

sn: waktu dlm sistem utk Cn (wn + xn) λ : laju kedatangan rata-rata µ : laju layanan rata-rata

Notasi Diagram Waktu

Sistem Antrian - Dasar N(t): # pelanggan dlm sistem @waktu t U(t): pekerjaan belum selesai/ unfinished

@waktu t U(t) = 0 Sistem idle U(t) > 0 Sistem busy

(t): # kedatangan pada (0,t) (t): # keberangkatan pada (0,t)

Sistem Antrian - Dasar

Sistem Antrian - Dasar

t : laju kedatangan

t = (t)/t = # kedatangan/waktu (t) : waktu total semua pelanggan dlm

sistem (pelanggan-detik) Tt = (t)/t = waktu sistem/pelanggan

Sistem Antrian - Dasar

Rata-rata # pelanggan dlm sistem

Hasil Little

Jumlah rata-rata pelanggan dlm sistem antrian sama dg laju kedatangan pelanggan ke sistem tsb, dikalikan rata-rata waktu yg dihabiskan dlm sistem”

Hasil Little

Nq = rata-rata # pelanggan dlm antrian = laju kedatangan W = rata-rata waktu dihabiskan dlm antrian

Hasil Little

Ns = rata-rata # pelanggan dlm fasilitas layanan = laju kedatangan x = rata-rata waktu dihabiskan dlm fasilitas layanan

Sistem Antrian - Dasar

= faktor utilisasi = laju kerja/ laju kapasitas max

Utk G/G/1 stabil : 0 < 1

Utk single server

Utk m server

Teknik-Teknik Performansi Tiga teknik dasar utk analisa performansi

Pengukuran/Measurements Mengumpulkan data eksperimental dari prototype

atau sistem eksisting

Simulasi Eksperimen dg model komputer dari sistem

Analisis Teori Antrian/Queueing Theory Model analitis dari sistem

Teori Antrian Model analitis dari sistem

Kelebihan Cepat Aplikasi utk semua tingkatan dari sistem Memungkinkan tradeoffs dan sensitivitas utk

dipelajari

Kelemahan Mungkin mencakup aproksimasi Abstraksi detail Perlu waktu untuk mengembangkan model

Memilih Teknik Performansi Tiap metoda punya rentang aplikabilitas Sebaiknya cross check hasil

Model Network Bagaimana kita memodelkan? Jaringan (network) secara umum dimodelkan

dlm tiga kategori: Resource sharing networks Process networks Switching networks

Resource Sharing Network (1)

Time-shared computer (Programs : CPU/Disk/IO) Statistical multiplexer/concentrator Packet-based (Packets : Links) Channel-based (Calls : Channels) Multiple-Access and random access networks

(Packets : Shared Medium)

Resource Sharing Network (2)

Ukuran performansi Waktu tunggu (waiting time) Probabilitas blocking

Pertanyaan Bagaimana relasi antara jumlah user, pola

penggunaan, jumlah sumberdaya (resources), dan performansi?

Apakah resources diduduki secara adil (atau tepat) oleh user?

Proces Network (1)

Multi-stage switch Distributed simulation system Manufacturing process

Proces Network (2) Ukuran performansi

Waktu penyelesaian (delay) Throughput (penyelesaain per unit waktu)

Pertanyaan Bagaimana performansi dipengaruhi oleh pola

penggunaan yg berbeda? Proses mana yang “bottlenecks” yang membatasi

performansi? Apakah input-input berbeda diperlakukan secara

adil dlm kaitannya dg performansi?

Switching Network (1)

Telephone network (Telepon : Circuit Switches) Telephone signaling network (Switches : STPs) X.25 packet network (Komputer : Packet Switches) Internet (Komputer : Routers)

Switching Network (2) Ukuran performansi

Delay (endpoint to endpoint) Throughput Utilisasi Probabilitas blocking Losses

Pertanyaan Apakah topologi terbaik? Bagaimana kita me-route-kan? Bagaimana kita menjamin Quality of Service?