Teori Antrian
Teori antrian merupakan kajian matematis terkait antrian yang menciptakan model untuk memprediksi panjang antrian dan waktu tunggu. Sebagai salah satu cabang riset operasi, teori antrian banyak digunakan untuk mengambil keputusan bisnis mengenai sumber daya yang dibutuhkan untuk menyediakan layanan. Teori antrian yang ditemukan oleh Agner Krarup Erlang didasarkan pada model sistem panggilan masuk di Copenhagen Telephone Exchange Company. Penerapan ide-ide ini meluas ke berbagai bidang, termasuk telekomunikasi, teknik transportasi, ilmu komputer, manajemen proyek dan khususnya teknik industri, yang dapat diterapkan pada desain pabrik, pertokoan, perkantoran, dan rumah sakit.
Jaringan antrian adalah sistem di mana antrian individu dihubungkan oleh jaringan perutean. Pada gambar ini, server diwakili oleh lingkaran, antrian diwakili oleh serangkaian persegi panjang, dan jaringan routing diwakili oleh panah. Ketika mempelajari jaringan antrian, seseorang biasanya mencoba untuk mencapai distribusi keseimbangan jaringan, meskipun mempelajari keadaan transisi sangat sederhana dalam banyak penerapan.
Node antrian tunggal
Node antrian atau simpul antrian hampir dapat dianggap sebagai kotak hitam. Pekerjaan (juga dikenal sebagai klien atau permintaan tergantung pada bidangnya) tiba dalam antrean, mungkin menunggu beberapa saat, memerlukan waktu untuk diproses, dan kemudian meninggalkan antrean.
Sebuah kotak hitam (blackbox). Pekerjaan datang ke, dan berangkat dari, antrian.
Namun, node akhir bukanlah kotak hitam murni karena diperlukan beberapa informasi tentang bagian dalam node akhir. Antrian memiliki satu atau lebih server dan masing-masing server dapat dipasangkan dengan pekerjaan masuk. Ketika suatu pekerjaan selesai dan keluar, server tersebut dapat kembali berkomunikasi dengan semua pekerjaan masuk lainnya.
Node antrian dengan 3 server. Server a sedang down sehingga data yang masuk diteruskan untuk diproses. Server b sedang sibuk dan perlu beberapa saat untuk menyelesaikan tugasnya. Server c baru saja selesai memproses pekerjaan dan kemudian menerima pekerjaan masuk.
Analogi yang umum digunakan adalah analogi seorang kasir di supermarket.(Ada model lain, tapi model ini sering ditemukan dalam literatur). Pelanggan datang, diproses oleh kasir dan pergi lagi. Setiap ATM memproses satu pelanggan pada satu waktu dan oleh karena itu merupakan node antrian dengan satu server. Pengaturan dimana pelanggan segera pergi jika kasir sedang sibuk ketika pelanggan datang disebut antrian tanpa buffer (atau non-menunggu). Konfigurasi dengan ruang tunggu hingga n klien disebut antrian dengan buffer berukuran n.
Sejarah
Pada tahun 1909, Agner Krarup Erlang, seorang insinyur Denmark di bursa telepon Kopenhagen, memulai teori antrian dengan memodelkan jumlah panggilan telepon masuk menggunakan proses Poisson dan pada tahun 1917 mengembangkan antrian M/D/1 dan M/D/k- Antrian terpecahkan. model pada tahun 1920. Notasi Kendall diperkenalkan pada tahun 1953 oleh David George Kendall, yang kemudian memecahkan antrian GI/M/k. Felix Pollaczek dan Aleksandr Khinchine mengembangkan rumus Pollaczek-Khinchine untuk antrian M/G/1 pada tahun 1930.Pada tahun 1957, Pollaczek mempelajari GI/G/1 dan John Kingman mengembangkan rumus untuk waktu tunggu rata-rata dalam antrian G/G/ 1., yang dikenal sebagai rumus Kingman. Leonard Kleinrock menerapkan teori antrian pada perpindahan pesan dan paket pada tahun 1960an dan 1970an dan menganjurkan penggunaan perpindahan paket di ARPANET.Metode matriks geometris dan analisis matriks memungkinkan pertimbangan antrian dengan distribusi kedatangan dan distribusi waktu pelayanan. Sistem orbit berpasangan penting dalam teori antrian, khususnya dalam jaringan nirkabel dan pemrosesan sinyal. Penerapan teori antrian modern mencakup pengembangan produk dengan keberadaan spatiotemporal, serta pertanyaan seperti metrik kinerja untuk antrian M/G/K, yang masih terbuka.
Disiplin layanan
.
Contoh antrian masuk pertama keluar pertama (FIFO).
Beberapa kebijakan penjadwalan di node akhir meliputi: First in, First out (FCFS), dimana pelanggan dilayani berdasarkan siapa cepat dia dapat; “Masuk terakhir, keluar pertama”, di mana pelanggan dilayani satu per satu dan pelanggan dengan waktu tunggu tersingkat dilayani terlebih dahulu (juga dikenal sebagai “penumpukan”); Pemroses bersama dengan kapasitas layanan dibagi rata antar klien berdasarkan prioritas, dengan klien berprioritas tinggi dilayani terlebih dahulu () (dengan jenis antrian prioritas non-preemptive dan preemptive); pekerjaan terpendek terlebih dahulu, dengan tugas dengan waktu pelaksanaan terpendek diselesaikan terlebih dahulu; pertama pekerjaan persiapan terpendek, dimana pesanan dikirimkan dengan ukuran asli terkecil; Sisa waktu pemrosesan terpendek, dengan pesanan dengan sisa pemrosesan paling sedikit harus diselesaikan terlebih dahulu.Selain itu, terdapat berbagai model instalasi pelayanan, seperti: Misalnya, satu server, beberapa server paralel dengan satu atau beberapa antrian, dan server tidak tepercaya yang gagal setelah proses stokastik diikuti dengan fase konfigurasi di mana server tidak tersedia. . Perilaku menunggu pelanggan meliputi penolakan, ketika pelanggan memilih untuk tidak mengantri jika terlalu panjang; Scramble, dimana pelanggan mengubah antrian jika dirasa akan dilayanilebih cepat; dan penolakan ketika pelanggan meninggalkan antrian jika menunggu terlalu lama untuk dilayani. Pelanggan yang datang dan tidak dilayani baik karena tidak ada buffer antrian atau karena pelanggan menolak disebut juga pengabai, dan rata-rata tingkat pengabaian merupakan parameter penting untuk menggambarkan antrian.
Jaringan antrian (Queueing networks)
Jaringan antrian adalah sistem di mana beberapa antrian dihubungkan melalui perutean pelanggan. Ketika klien menerima layanan pada sebuah node, mereka dapat bergabung dengan node lain untuk mengantri layanan atau meninggalkan jaringan. Dalam jaringan dengan m node, keadaan sistem dapat digambarkan dengan vektor berdimensi m (x1, x2, ...)., xm), dimana xi mewakili jumlah klien pada setiap node. Jaringan antrian nontrivial yang paling sederhana adalah antrian tandem. Jaringan Jackson adalah pencapaian signifikan pertama di bidang ini dan memungkinkan penghitungan metrik rata-rata seperti throughput dan waktu tunggu. Jika jumlah pelanggan dalam jaringan tetap konstan, kita berbicara tentang jaringan tertutup dan distribusi produk stasioner menurut teorema Gordon-Newell. Hasil ini meluas ke jaringan BCMP dan menunjukkan bahwajaringan dengan waktu layanan, rezim, dan rute pelanggan yang sangat umum juga memiliki distribusi bentuk produk yang tetap.Jaringan pelanggan lain juga telah dipelajari, seperti jaringan Kelly, yang memiliki kelas pelanggan berbeda dengan tingkat prioritas berbeda pada node layanan berbeda. Misalnya, jaringan G yang diusulkan oleh Erol Gelenbe pada tahun 1993 tidak mengasumsikan distribusi waktu eksponensial seperti jaringan Jackson klasik.
Algoritma perutean (Routing algorithms)
Dalam jaringan waktu diskrit, di mana jumlah node layanan yang dapat aktif kapan saja terbatas, algoritma penjadwalan bobot maksimum memilih kebijakan layanan untuk memberikan kinerja optimal ketika setiap pekerjaan hanya mengunjungi satu node layanan orang. Dalam kasus yang lebih umum di mana pekerjaan dapat mengunjungi lebih dari satu node, perutean BackPressure memberikan kinerja yang optimal. Perencana jaringan harus memilih algoritma antrian yang berdampak pada karakteristik jaringan
yang lebih besar.
Batas rata-rata bidang
Model medan rata-rata memperhitungkan perilaku pembatas dari ukuran empiris (proporsi ekor di berbagai negara bagian) ketika jumlah ekor m mendekati tak terhingga. Pengaruh antrian lain pada antrian tertentu dalam jaringan diperkirakan dengan persamaan diferensial. Model deterministik menyatu pada distribusi stasioner yang sama dengan model aslinya.
Perkiraan lalu lintas / difusi yang padat
Dalam sistem dengan tingkat hunian tinggi (pemanfaatan mendekati 1), perkiraan lalu lintas yang kuat dapat digunakan untuk memperkirakan proses panjang antrian gerak Brown yang tercermin, proses Ornstein-Uhlenbeck, atau proses difusi yang lebih umum. Jumlah dimensi proses Brown sama dengan jumlah node akhir, dengan difusi terbatas pada speaker non-negatif.
Batas cairan
Model fluida adalah analog deterministik kontinu dari jaringan antrian, yang diperoleh dengan menetapkan batasan ketika menskalakan proses dalam ruang dan waktu dan dengan mempertimbangkan objek yang heterogen. Lintasan berskala ini menyatu dengan persamaan deterministik yang memungkinkan pengujian stabilitas sistem. Diketahui bahwa suatu jaringan antrian dapat stabil namun mempunyai batas fluida yang tidak stabil.
Disadur dari: en.wikipedia.org