Optimasi Stokastik

Metode optimasi stokastik (SO) merupakan metode optimasi yang menghasilkan dan menggunakan variabel acak. Dalam permasalahan stokastik, variabel acak muncul dalam rumusan masalah optimasi itu sendiri dan mencakup fungsi tujuan acak atau batasan acak. Metode optimasi stokastik juga mencakup metode dengan iterasi acak. Beberapa metode optimasi stokastik menggunakan iterasi acak untuk memecahkan masalah stokastik, menggabungkan kedua makna optimasi stokastik. metode optimasi stokastik menggeneralisasi metode deterministik ke masalah deterministik.

Metode fungsi stokastik

Dalam konteks analisis data, terdapat situasi di mana sebagian data masukan bersifat acak, seperti pada bidang estimasi dan kontrol waktu nyata. Selain itu, optimasi berbasis simulasi juga sering melibatkan penggunaan simulasi Monte Carlo sebagai perkiraan sistem sebenarnya. Masalah lain yang dihadapi adalah ketika terdapat kesalahan eksperimental atau kebisingan acak dalam pengukuran kriteria. Dalam kasus-kasus seperti itu, pemahaman bahwa nilai-nilai fungsi dapat terkontaminasi oleh kebisingan acak mendorong pengembangan algoritma yang menggunakan alat inferensi statistik untuk memperkirakan nilai-nilai "sebenarnya" dari fungsi dan/atau membuat keputusan optimal secara statistik terkait langkah-langkah selanjutnya.

Metode yang termasuk dalam kategori ini mencakup berbagai pendekatan seperti pendekatan stokastik (SA) oleh Robbins dan Monro (1951), penurunan gradien stokastik, SA perbedaan hingga oleh Kiefer dan Wolfowitz (1952), gangguan simultan SA oleh Spall (1992), dan optimasi skenario. Keseluruhan, metode-metode ini menyediakan kerangka kerja yang efektif untuk menangani data masukan yang bersifat acak dan kesalahan eksperimental, dengan menggunakan prinsip-prinsip inferensi statistik untuk membuat keputusan yang lebih akurat dan optimal.

Metode pencarian acak

Metode pencarian acak, sering disebut sebagai metaheuristik, memperkenalkan keacakan ke dalam proses pencarian untuk mempercepat kemajuan, terutama ketika kumpulan data terdiri dari pengukuran yang tepat. Keacakan yang diperkenalkan dapat membuat metode ini lebih toleran terhadap kesalahan pemodelan dan menghasilkan keuntungan lain, seperti memperkirakan interval fitur minimum menggunakan statistik nilai ekstrem. Selain itu, keacakan dalam proses pencarian memungkinkan kita untuk keluar dari optimal lokal dan mendekati optimal global, menjadikan prinsip pengacakan ini sebagai cara yang sederhana dan efektif untuk mengembangkan algoritma yang kinerjanya hampir pasti dan konsisten di berbagai kumpulan data dan masalah.

Beberapa metode optimasi stokastik yang menerapkan prinsip pencarian acak antara lain simulasi anil oleh S. Kirkpatrick, CD Gelatt dan MP Vecchi (1983), probabilitas kolektif oleh DH Wolpert, SR Bieniawski dan DG Rajnarayan (2011), dan algoritma genetika oleh Holland (2011). Ada pula metode lain seperti metode cross-entropy dari Rubinstein dan Kroese (2004), random search dari Anatoly Zhigljavsky (1991), dan stochastic tunneling.

Meskipun metode pencarian acak dianggap efektif, beberapa penulis berpendapat bahwa pengacakan hanya dapat meningkatkan algoritma deterministik jika algoritma deterministik dirancang dengan buruk. Ada juga argumen bahwa ketergantungan pada elemen acak dapat menghambat pengembangan komponen deterministik yang lebih cerdas dan unggul. Lebih jauh lagi, menyajikan hasil algoritma optimasi stokastik, misalnya dengan hanya mencantumkan rata-rata atau N run terbaik tanpa menyebutkan distribusi, dapat menghasilkan bias positif terhadap keacakan.

Beberapa permasalahan kompleksitas terbuka berkaitan dengan pertanyaan apakah keacakan dapat memungkinkan penyelesaian permasalahan dalam waktu yang lebih singkat, seperti pada permasalahan P = BPP.Konvergensi algoritma pencarian lokal stokastik menuju solusi optimal terkadang dapat terjadi sebagai akibat dari kemungkinan perpindahan dari satu solusi ke solusi lainnya dalam ruang pencarian pada setiap iterasi. Namun, sifat semantik penting dari algoritma pencarian lokal stokastik, termasuk kemampuannya untuk menemukan solusi optimal atau solusi dalam jarak tertentu dari nilai optimal, seringkali tidak dapat ditentukan secara umum. Hal ini disebabkan kemampuan algoritma ini untuk mensimulasikan programapa pun, terutama jika bahan dasarnya dimaksudkan sederhana.

Disadur dari : en.wikipedia.org

Metode optimasi stokastik

Pengendalian proses statistik (SPC) atau pengendalian kualitas statistik (SQC) adalah penerapan metode statistik untuk memantau dan mengendalikan kualitas suatu proses produksi. Hal ini untuk memastikan proses berjalan efisien dan menghasilkan produk yang memenuhi spesifikasi dan memiliki lebih sedikit limbah atau cacat. SPC dapat diterapkan pada berbagai proses dimana hasil dari “produk yang sesuai” (produk yang memenuhi spesifikasi) dapat diukur. Alat utama yang digunakan diSPC meliputi diagram proses, diagram kendali, fokus pada perbaikan berkelanjutan, dan desain eksperimen.

Contoh proses yang menerapkan SPC adalah lini produksi di bidang manufaktur.SPC harus diimplementasikan dalam dua tahap: tahap pertama adalah pembentukan awal proses dan tahap kedua adalah penggunaan proses produksi secara teratur. Pada fase kedua, keputusan harus dibuat mengenai periode pengujian, tergantung pada perubahan kondisi 5M&E (manusia, mesin, material, metode, pergerakan, lingkungan) dan tingkat keausan suku cadang yang digunakan dalam proses.

Manufaktur (suku cadang mesin, templat dan aksesori).Keuntungan SPC dibandingkan dengan metode pengendalian mutu lainnya seperti “inspeksi” adalah bahwa metode ini berfokus pada deteksi dini dan pencegahan masalah dibandingkan memperbaikinya setelah masalah terjadi. Selain mengurangi pemborosan, SPC juga dapat menghasilkan pengurangan waktu yang dibutuhkan untuk menghasilkan suatu produk. SPC mengurangi kemungkinan produk akhir perlu dikerjakan ulang atau dibuang.

Metode untuk fungsi stokastik

Data masukan acak sebagian muncul di berbagai bidang seperti estimasi dan kontrol waktu nyata, optimasi berbasis simulasi di mana simulasi Monte Carlo dilakukan sebagai perkiraan sistem nyata, dan masalah di mana kesalahan eksperimental (acak) terjadi dalam pengukuran kriteria. Dalam kasus seperti itu, mengetahui bahwa nilai fungsi terkontaminasi oleh "kebisingan" acak secara alami mengarah pada algoritma yang menggunakan alat inferensi statistik untuk memperkirakan nilai "sebenarnya" dari fungsi dan/atau keputusan optimal secara statistik tentang langkah selanjutnya yang harus dipenuhi. Metode di kelas ini meliputi:

• pendekatan stokastik (SA), oleh Robbins dan Monro (1951)
• penurunan gradien stokastik
• perbedaan hingga SA oleh Kiefer dan Wolfowitz (1952)
• gangguan simultan SA oleh Spall (1992)
• optimasi skenario

Metode pencarian acak

Di sisi lain, meskipun kumpulan data terdiri dari pengukuran yang tepat, beberapa metode memperkenalkan keacakan ke dalam proses pencarian untuk mempercepat kemajuan. Keacakan ini juga dapat membuat metode ini kurang rentan terhadap kesalahan pemodelan. Selain itu, keacakan yang disuntikkan dapat menyebabkan metode keluar dari optimal lokal dan akhirnya mendekati optimal global. Faktanya, prinsip pengacakan ini dikenal sebagai cara sederhana dan efektif untuk mendapatkan algoritmayang bekerja hampir secara seragam pada banyak kumpulan data dan untuk berbagai masalah. Jenis metode optimasi stokastik ini meliputi:

• simulasi anil oleh S. Kirkpatrick, C. D. Gelatt dan M. P. Vecchi (1983)
• anil kuantum
• Kolektif Probabilitas oleh D.H. Wolpert, S.R. Bieniawski dan D.G. Rajnarayan (2011)
• optimasi pencarian reaktif (RSO) oleh Roberto Battiti, G. Tecchiolli (1994),
• metode cross-entropy oleh Rubinstein dan Kroese (2004)
• pencarian acak oleh Anatoly Zhigljavsky (1991)
• Pencarian informasi
• terowongan stokastik
• tempering paralel alias pertukaran replika
• pendakian bukit stokastik
• algoritma kawanan
• algoritma evolusioner
• algoritma genetika oleh Holland (1975)
• strategi evolusi
• algoritma optimasi & modifikasi objek kaskade (2016)

Sebaliknya, beberapa penulis berpendapat bahwa pengacakan hanya dapat meningkatkan algoritma deterministik jika algoritma deterministik dirancang dengan buruk. Fred W. Glover berpendapat bahwa ketergantungan pada elemen acak dapat menghambat pengembangan komponen deterministik yang lebih baik dan lebih cerdas. Cara penyajian hasil algoritma optimasi stokastik (misalnya rata-rata atau bahkan N run terbaik tanpa menyebutkan variasi juga dapat menghasilkan bias positif terhadap keacakan.

Disadur dari: en.wikipedia.org

Simulated Annealing

Simulated Annealing (SA) adalah teknik probabilistik untuk memperkirakan maksimum global suatu fungsi tertentu. Secara khusus, ini adalah metaheuristik untuk memperkirakan optimasi global dalam ruang pencarian masalah optimasi yang besar. Untuk sejumlah besar optima lokal, SA dapat menemukan optima global. Ini sering digunakan ketika ruang pencariannya terpisah (misalnya masalah penjual keliling, masalah kepuasan logis, prediksi struktur protein, dan perencanaan lokakarya). Untuk permasalahan di mana menemukan perkiraan optimal global lebih penting daripada menemukan optimal lokal yang tepat pada waktu yang tetap, simulasi anil bisa lebih baik daripada algoritma yang tepat seperti penurunan gradien atau cabang dan batas.

Nama algoritme ini berasal dari anil dalam metalurgi, suatu teknik di mana suatu material dipanaskan dan didinginkan secara terkendali untuk mengubah sifat fisiknya. Keduanya merupakan sifat material yang bergantung pada energi bebas termodinamikanya. Bahan pemanas dan pendingin mempengaruhi suhu dan energi bebas termodinamika, atau energi Gibbs. Simulasi anil dapat diterapkan pada masalah optimasi yang sulit secara komputasi di mana algoritma yang tepat gagal; Meskipun pendekatan ini umumnya menghasilkan solusi yang mendekati nilai minimum global, namun pendekatan ini cukup untuk memecahkan banyak permasalahan praktis.Masalah yang dipecahkan oleh SA saat ini dirumuskan menggunakan fungsi tujuan multivariabel, yang tunduk pada banyak batasan matematis.Dalam praktiknya, batasan ini dapat dipandang sebagai bagian dari fungsi tujuan.

Teknik serupa telah diperkenalkan secara independen beberapa kali, termasuk Pincus (1970), Khachaturyan et al. (1979,  1981), Kirkpatrick, Gelatt dan Vecchi (1983) dan Cerny (1985). Pada tahun 1983, Kirkpatrick, Gelatt Jr., Vecchi, menggunakan pendekatan ini untuk memecahkan masalah penjual. Mereka juga menyarankan nama saat ini Simulated Annealing.

Gagasan pendinginan lambat yang diterapkan dalam algoritma simulasi anil ditafsirkan sebagai penurunan perlahan dalam kemungkinan menerima solusi yang lebih buruk seiring dengan eksplorasi ruang solusi.Menerima solusi yang lebih buruk memungkinkan pencarian solusi optimal global yang lebih komprehensif. Secara umum, algoritma simulasi anil bekerja sebagai berikut. Suhu turun dari nilai positif awal menjadi nol.

Pada setiap langkah waktu, algoritme secara acak memilih solusi yang mendekati solusi saat ini, mengukur kualitasnya, dan bergerak ke arah solusi tersebut sesuai dengan probabilitas yang bergantung pada suhu untuk memilih solusi yang lebih baik atau lebih buruk daripada tetap pada angka 1 selama pencarian
masing-masing solusi. (atau positif). ) dan menurun menuju nol.

Simulasi dapat dilakukan dengan menyelesaikan persamaan kinetik fungsi kepadatan probabilitas atau menggunakan metode stochastic sampling. Metode ini merupakan adaptasi dari algoritma Metropolis-Hastings, metode Monte Carlo untuk menghasilkan keadaan pola sistem termodinamika, yang diterbitkan oleh N. Metropolis et al. pada tahun 1953.

Gambaran umum

Keadaan suatu sistem fisik dan fungsi E(s) yang harus diminimalkan adalah analog dengan energi dalam sistem dalam keadaan tersebut. Tujuannya adalah untuk membawa sistem dari keadaan awal yang berubah-ubah ke keadaan dengan energi serendah mungkin.

Iterasi dasar
Pada setiap langkah, heuristik anil yang disimulasikan memperhitungkan beberapa keadaan tetangga s* dari keadaan s saat ini dan memutuskan secara probabilistik apakah sistem dipindahkan ke keadaan s* atau tetap dalam keadaan s. Kemungkinan ini pada akhirnya menyebabkan sistem bertransisi ke keadaan energi yang lebih rendah. Biasanya, langkah ini diulangi hingga sistem mencapai kondisi yang cukup baik untuk aplikasi atau hingga anggaran komputasi tertentu habis.

Tetangga suatu negara
Optimalisasi solusi melibatkan evaluasi tetangga dari keadaan masalah, yang merupakan keadaan baru yang diciptakan oleh perubahan konservatif pada keadaan tertentu. Misalnya, dalam masalah penjual, setiap negara bagian biasanya didefinisikan sebagai permutasi kota-kota yang akan dikunjungi, dan tetangga suatu negara bagian adalah himpunan permutasi yang dibuat dengan menukarkan kedua kota tersebut. Cara-cara perubahan negara-negara bagian yang terdefinisi dengan baik untuk menciptakan negara-negara tetangga disebut “pergerakan”, dan pergerakan yang berbeda menghasilkan kumpulan negara-negara tetangga yang berbeda. Langkah-langkah ini umumnya menghasilkan perubahan minimal pada keadaan akhir dalam upaya untuk meningkatkan solusi secara bertahap melalui perbaikan berulang pada bagian-bagiannya (misalnya koneksi kota dalam masalah penjual).

Tidak ada jaminan bahwa heuristik sederhana seperti pendakian bukit, yang bergerak mencari satu demi satu tetangga terbaik dan berhenti ketika mereka telah mencapai solusi yang tidak ada tetangganya, akan menjadi solusi yang lebih baik, tidak dapat dijamin akan mengarah pada solusi yang lebih baik. solusi terbaik yang ada; Hasilnya mungkin hanya berupa optimum lokal, sedangkan solusi terbaik sebenarnya adalah optimum global, yang mungkin berbeda-beda.

Metaheuristik menggunakan tetangga suatu solusi untuk mengeksplorasi ruang solusi. Meskipun mereka lebih memilih tetangga yang lebih baik, mereka juga menerima tetangga yang lebih buruk agar tidak terjebak dalam optimal lokal. Mereka dapat menemukan titik optimal global jika dijalankan dalam jangka waktu yang cukup lama.

Jadwal Annealing

suatu algoritma yang memerlukan integrasi fungsi-fungsi yang berkaitan dengan fluktuasi suhu ke dalam karakteristik operasinya. Algoritma ini memerlukan penurunan suhu secara bertahap selama simulasi, dimulai dari suhu tinggi dan kemudian menurun pada setiap langkah sesuai dengan jadwal anil yang dapat ditentukan pengguna. Pendekatan ini memungkinkan sistem untuk pertama-tama menjelajahi wilayah ruang pencarian yang luas, mengabaikan
fitur kecil dari fungsi energi, kemudian bergerak menuju wilayah energi rendah yang semakin sempit, dan akhirnya turun sesuai dengan heuristik penurunan paling curam.

Meskipun bersifat teoritis, kemungkinan algoritma ini mencapai solusi optimal global meningkat hingga mendekati 1 seiring dengan perluasan program anil untuk setiap permasalahan yang terbatas. Namun, hasil teoritis ini penggunaannya terbatas karena waktu yang diperlukan untuk mencapai keberhasilan yang signifikan kemungkinan besar melebihi waktu yang diperlukan untuk melakukan pencarian menyeluruh dalam ruang solusi.

Disadur dari: en.wikipedia.org

Alokasi Sumberdaya

Dalam ilmu ekonomi, alokasi sumber daya adalah penentuan alokasi sumber daya yang ada untuk berbagai tujuan. Pada tingkat makroekonomi, alokasi sumber daya dapat dilakukan melalui pasar atau perencanaan. Dalam konteks manajemen proyek, alokasi sumber daya adalah perencanaan kegiatan dan sumber daya yang diperlukan untuk suatu proyek, dengan mempertimbangkan ketersediaan sumber daya dan waktu proyek.

Ekonomi

Di bidang ekonomi, bidang keuangan publik berkaitan dengan tiga bidang utama: stabilisasi makroekonomi, distribusi pendapatan dan kekayaan, dan alokasi sumber daya. Sebagian besar studi alokasi sumber daya dikhususkan untuk menemukan kondisi di mana mekanisme alokasi sumber daya tertentu menghasilkan hasil yang efisien Pareto, di mana tidak ada pihak yang dapat memperbaiki situasi tanpa merugikan pihak lain.

Perencanaan strategis

Dalam perencanaan strategis, alokasi sumber daya adalah rencana penggunaan sumber daya yang tersedia, seperti sumber daya manusia, terutama dalam waktu dekat, untuk mencapai tujuan di masa depan. Ini adalah proses mengalokasikan sumber daya yang langka ke berbagai proyek atau unit bisnis.Ada berbagai pendekatan untuk menyelesaikan masalah alokasi sumber daya, misalnya alokasi sumber daya dapat dilakukan dengan pendekatan manual, pendekatan algoritmik (lihat di bawah), atau kombinasi keduanya.

Mungkin terdapat mekanisme kontinjensi, seperti pemeringkatan prioritas elemen-elemen yang tidak termasuk dalam rencana, yang menunjukkan elemen mana yang harus didanai jika diperlukan lebih banyak sumber daya, dan peringkat prioritas beberapa elemen yang termasuk dalam rencana, yang menunjukkan elemen mana, jika ada, harus dikorbankan Pembiayaan penuh diperlukan. harus dikurangi.

Algoritma

Alokasi sumber daya dapat diputuskan menggunakan program komputer yang diterapkan pada domain tertentu untuk mendistribusikan sumber daya secara otomatis dan dinamis kepada peminta.Hal ini sangat umum terjadi pada perangkat elektronik yang digunakan untuk penerusan dan komunikasi. Misalnya, alokasi saluran dalam komunikasi nirkabel dapat ditentukan oleh stasiun pemancar dasar dengan menggunakan algoritma yang tepat.

Kelas sumber daya di mana pelamar menawar sumber daya terbaik berdasarkan saldo "uang" mereka, seperti dalam model bisnis lelang online. Sebuah artikel tentang alokasi slot CPUmembandingkan algoritma lelang dengan penjadwalan pembagian proporsional.

Disadur dari : en.wikipedia.org

Variabel Acak

Variabel acak (disebut juga variabel acak, variabel acak, atau variabel stokastik) adalah formalisasi matematis suatu besaran atau objek yang bergantung pada kejadian acak. Secara informal, kebetulan biasanya merupakan unsur fundamental dari kebetulan, misalnya dalam pelemparan dadu; Hal ini juga dapat mewakili ketidakpastian, seperti kesalahan pengukuran.

Namun, penafsiran probabilitas secara filosofis rumit dan tidak selalu mudah bahkan dalam kasus tertentu. Analisis matematis murni terhadap variabel acak tidak menimbulkan kesulitan dalam penafsiran dan dapat didasarkan pada pengaturan aksiomatik yang ketat.

Dalam bahasa matematika formal teori pengukuran, variabel acak didefinisikan sebagai fungsi terukur dari ruang ukuran probabilitas (disebut ruang sampel) ke ruang terukur. Hal ini memungkinkan kita untuk mempertimbangkan ukuran kemajuan yang disebut distribusi variabel acak. Oleh karena itu, distribusi adalah ukuran probabilitas pada himpunan semua nilai yang mungkin dari suatu variabel acak. Ada kemungkinan dua variabel acak memiliki distribusi yang identik tetapi berbeda secara signifikan; Misalnyabisa mandiri.

Adalah umum untuk mempertimbangkan kasus-kasus khusus dari variabel acak diskrit dan variabel acak kontinu absolut, yang berkaitan dengan apakah suatu variabel acak mengevaluasi pada subset yang dapat dihitung atau pada interval bilangan real. Ada kemungkinan penting lainnya, terutama dalam teori proses stokastik, di mana wajar jika kita memperhitungkan barisan acak atau fungsi acak.Variabel acak terkadang diasumsikan dievaluasi secara otomatis sebagai bilangan real, dan besaran acak lebih sering disebut sebagai elemen acak.

Contoh

Variabel acak diskrit

Pertimbangkan sebuah eksperimen di mana satu orang dipilih secara acak. Contoh variabel acak adalah tinggi badan seseorang. Secara matematis, variabel acak didefinisikan sebagai fungsi yang mewakili tinggi badan seseorang. Variabel acak dikaitkan dengan distribusi probabilitas yang memungkinkan kita menghitung probabilitas bahwa tinggi badan berada dalam subkumpulan nilai apa pun yang mungkin, misalnya probabilitas bahwa tinggi badan antara 180 dan 190 cm, atau probabilitas bahwa tinggi badan lebih kecil adalah dari 180 cm. dari 150 atau lebih dari 200 cm.

Variabel acak lainnya bisa berupa jumlah anak yang dimiliki seseorang; adalah variabel acak diskrit dengan nilai integer non-negatif. Hal ini memungkinkan penghitungan probabilitas untuk nilai integer individual (fungsi massa probabilitas (PMF)) atau untuk himpunan nilai, termasuk himpunan tak hingga. Misalnya, peristiwa yang menarik mungkin berupa “jumlah anak genap”. Untuk rangkaian kejadian berhingga dan tak terhingga, probabilitas dapat dicari dengan menjumlahkan PMF elemen; Artinyacara mempunyai jumlah anak genap adalah jumlah yang tidak terhingga

Disadur dari: en.wikipedia.org

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