2.2 Multi-channel QS na may paghihintay
System na may limitadong haba ng pila. Isaalang-alang natin ang isang channel QS na may paghihintay, na tumatanggap ng daloy ng mga kahilingan na may intensity ; intensity ng serbisyo (para sa isang channel); bilang ng mga lugar sa pila.
Ang mga estado ng system ay binibilang ayon sa bilang ng mga kahilingang nauugnay sa system:
walang pila:
Lahat ng channel ay libre;
Ang isang channel ay inookupahan, ang natitira ay libre;
-Ang mga channel ay inookupahan, ang iba ay hindi;
Ang lahat ng mga channel ay inookupahan, walang mga libreng channel;
may pila:
Lahat ng n-channel ay inookupahan; isang application ang nasa pila;
Lahat ng n-channel, r-request sa pila ay inookupahan;
Lahat ng n-channel, r-request sa pila ay inookupahan.
Ang GSP ay ipinapakita sa Fig. 17. Ang bawat arrow ay minarkahan ng kaukulang intensity ng mga daloy ng kaganapan. Kasama ang mga arrow mula kaliwa hanggang kanan, ang system ay palaging inililipat sa pamamagitan ng parehong daloy ng mga kahilingan na may intensity na
kanin. 17. Multi-channel QS na may paghihintay
Ang graph ay tipikal para sa mga proseso ng pagpaparami at kamatayan, kung saan ang solusyon ay nakuha dati. Sumulat tayo ng mga expression para sa paglilimita ng mga probabilidad ng mga estado gamit ang notasyon: (dito ginagamit natin ang expression para sa kabuuan geometric na pag-unlad may denominator).
Kaya, ang lahat ng mga probabilidad ng estado ay natagpuan.
Alamin natin ang mga katangian ng pagganap ng system.
Ang posibilidad ng pagkabigo. Ang isang papasok na kahilingan ay tatanggihan kung ang lahat ng n-channel at lahat ng m-lugar sa pila ay inookupahan:
(18)
Ang kamag-anak na throughput ay umaakma sa posibilidad ng pagkabigo sa isa:
Ganap na throughput ng QS:
(19)
Average na bilang ng mga abalang channel. Para sa QS na may mga pagtanggi, kasabay ito ng average na bilang ng mga aplikasyon sa system. Para sa isang QS na may queue, ang average na bilang ng mga abalang channel ay hindi tumutugma sa average na bilang ng mga application sa system: ang huli na halaga ay naiiba mula sa una sa pamamagitan ng average na bilang ng mga application sa queue.
Tukuyin natin ang average na bilang ng mga channel na inookupahan ng . Ang bawat abalang channel ay nagsisilbi sa average na A-claim bawat unit ng oras, at ang QS sa kabuuan ay nagsisilbi sa average na A-claim bawat unit ng oras. Ang paghahati sa isa't isa, nakukuha natin:
Ang average na bilang ng mga application sa queue ay maaaring direktang kalkulahin bilang ang mathematical na inaasahan ng isang discrete random variable:
(20)
Dito muli (ang expression sa panaklong) ang hinango ng kabuuan ng geometric na pag-unlad ay nangyayari (tingnan sa itaas (11), (12) - (14)), gamit ang kaugnayan para dito, nakuha natin:
Average na bilang ng mga application sa system:
Average na oras ng paghihintay para sa isang aplikasyon sa pila. Isaalang-alang natin ang ilang sitwasyon na naiiba sa estado kung saan mahahanap ng bagong dating na kahilingan ang system at kung gaano ito katagal maghihintay para sa serbisyo.
Kung hindi makita ng isang kahilingan na abala ang lahat ng channel, hindi na ito kailangang maghintay pa (ang mga kaukulang miyembro sa inaasahan sa matematika ay katumbas ng zero). Kung ang isang kahilingan ay dumating sa isang oras na ang lahat ng mga n-channel ay abala at walang pila, ito ay kailangang maghintay sa average para sa isang oras na katumbas ng (dahil ang "release flow" ng -channels ay may intensity ). Kung nakita ng isang kahilingan na abala ang lahat ng channel at isang kahilingan ang nasa unahan nito sa pila, kakailanganin itong maghintay sa average para sa isang tagal ng panahon (para sa bawat kahilingan sa harap), atbp. Kung ang isang kahilingan ay nasa pila ng - mga kahilingan, kakailanganin itong maghintay sa average para sa oras Kung ang isang bagong dating na kahilingan ay nakakita ng mga m-hiling na nasa pila na, hindi na ito maghihintay (ngunit hindi ihahatid). Nahanap namin ang average na oras ng paghihintay sa pamamagitan ng pagpaparami ng bawat isa sa mga halagang ito sa mga kaukulang probabilidad:
(21)
Tulad ng kaso ng isang single-channel na QS na may paghihintay, napapansin namin na ang expression na ito ay naiiba sa expression para sa average na haba ng queue (20) sa pamamagitan lamang ng factor , i.e.
.
Ang average na oras ng paninirahan ng isang kahilingan sa system, pati na rin para sa isang solong channel na QS, ay naiiba sa average na oras ng paghihintay sa average na oras ng serbisyo na na-multiply sa relatibong throughput:
.
Mga system na may walang limitasyong haba ng pila. Isinaalang-alang namin ang isang channel QS na may paghihintay, kapag hindi hihigit sa m-request ang maaaring nasa queue nang sabay.
Tulad ng dati, kapag sinusuri ang mga sistema nang walang mga paghihigpit, kinakailangang isaalang-alang ang mga nakuhang relasyon para sa .
Nakukuha namin ang mga probabilidad ng mga estado mula sa mga formula sa pamamagitan ng pagpasa sa limitasyon (sa ). Tandaan na ang kabuuan ng kaukulang geometric na pag-unlad ay nagtatagpo sa at diverges sa >1. Ipagpalagay na<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Ang posibilidad ng pagkabigo, kamag-anak at ganap na throughput. Dahil ang bawat kahilingan ay maseserbisyuhan nang maaga o huli, ang mga katangian ng throughput ng QS ay magiging:
Ang average na bilang ng mga application sa queue ay nakuha mula sa (20):
,
at ang average na oras ng paghihintay ay mula sa (21):
.
Ang average na bilang ng mga inookupahang channel, tulad ng dati, ay tinutukoy sa pamamagitan ng absolute throughput:
.
Ang average na bilang ng mga application na nauugnay sa QS ay tinukoy bilang ang average na bilang ng mga application sa queue kasama ang average na bilang ng mga application na nasa ilalim ng serbisyo (average na bilang ng mga busy na channel):
Halimbawa 2. Ang isang gasolinahan na may dalawang bomba (n = 2) ay nagsisilbi sa daloy ng mga sasakyan na may intensity na =0.8 (mga kotse kada minuto). Average na oras ng serbisyo para sa isang makina:
Walang ibang gasolinahan sa lugar, kaya halos walang limitasyon ang linya ng mga sasakyan sa harap ng gasolinahan. Hanapin ang mga katangian ng QS.
Dahil ang<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
atbp.
Hahanapin namin ang average na bilang ng mga abalang channel sa pamamagitan ng paghahati ng ganap na kapasidad ng QS A = = 0.8 sa intensity ng serbisyo = 0.5:
Ang posibilidad na walang pila sa isang gasolinahan ay:
Average na bilang ng mga sasakyan sa pila:
Average na bilang ng mga sasakyan sa mga gasolinahan:
Average na oras ng paghihintay sa pila:
Karaniwang oras na ginugugol ng kotse sa isang gasolinahan:
QS na may limitadong oras ng paghihintay. Noong nakaraan, isinasaalang-alang namin ang mga system na may paghihintay na limitado lamang sa haba ng pila (ang bilang ng mga m-hiling nang sabay-sabay sa pila). Sa naturang QS, ang isang application na lumaki sa isang queue ay hindi iiwan ito hanggang sa maghintay para sa serbisyo. Sa pagsasagawa, mayroong iba pang mga uri ng QS kung saan ang isang aplikasyon, pagkatapos ng ilang oras na paghihintay, ay maaaring umalis sa pila (tinatawag na "impatient" na mga aplikasyon).
Isaalang-alang natin ang isang QS ng ganitong uri, sa pag-aakalang ang hadlang sa oras ng paghihintay ay isang random na variable.
Ipagpalagay natin na mayroong n-channel na QS na may paghihintay, kung saan ang bilang ng mga lugar sa pila ay walang limitasyon, ngunit ang oras na mananatili ang isang kahilingan sa pila ay ilang random na variable na may mean na halaga, kaya, ang bawat kahilingan sa ang queue ay napapailalim sa isang uri ng Poisson "flow of care" na may intensity:
Kung ang daloy na ito ay Poisson, kung gayon ang prosesong magaganap sa QS ay magiging Markovian. Hanapin natin ang mga probabilidad ng estado para dito. Ang pagbilang ng mga estado ng system ay nauugnay sa bilang ng mga aplikasyon sa system - parehong inihahatid at nakatayo sa pila:
walang pila:
Lahat ng channel ay libre;
Ang isang channel ay abala;
Dalawang channel ang abala;
Lahat ng n-channel ay inookupahan;
may pila:
Ang lahat ng mga n-channel ay inookupahan, isang kahilingan ang nasa pila;
Ang lahat ng mga n-channel ay okupado, ang mga r-hiling ay nasa pila, atbp.
Ang graph ng mga estado at mga transition ng system ay ipinapakita sa Fig. 23.
kanin. 23. QS na may limitadong oras ng paghihintay
Markahan natin ang graph na ito tulad ng dati; lahat ng mga arrow na humahantong mula kaliwa hanggang kanan ay magsasaad ng intensity ng daloy ng mga application. Para sa mga estadong walang pila, ang mga arrow na humahantong mula sa kanila mula kanan pakaliwa ay, tulad ng dati, ay magsasaad ng kabuuang intensity ng daloy na nagseserbisyo sa lahat ng mga sinasakop na channel. Para sa mga estadong may pila, ang mga arrow na humahantong mula sa kanila mula kanan pakaliwa ay magkakaroon ng kabuuang intensity ng daloy ng serbisyo ng lahat ng n-channel at ang katumbas na intensity ng daloy ng mga pag-alis mula sa pila. Kung may mga r-application sa pila, ang kabuuang intensity ng daloy ng mga pag-alis ay magiging katumbas ng .
Tulad ng makikita mula sa graph, mayroong isang pattern ng pagpaparami at kamatayan; gamit ang mga pangkalahatang expression para sa paglilimita ng mga probabilidad ng mga estado sa scheme na ito (gamit ang mga pinaikling notasyon, isinusulat namin:
(24)
Tandaan natin ang ilang feature ng isang QS na may limitadong paghihintay kumpara sa dating itinuturing na QS na may mga kahilingang "pasyente".
Kung ang haba ng pila ay hindi limitado at ang mga kahilingan ay "pasyente" (huwag umalis sa pila), kung gayon ang nakatigil na limitasyon ng rehimen ay umiiral lamang sa kaso (sa , ang kaukulang walang katapusang geometric na pag-unlad ay nag-iiba, na pisikal na tumutugma sa walang limitasyong paglago ng pila sa ).
Sa kabaligtaran, sa isang QS na may "impatient" na mga kahilingan na umaalis sa pila sa lalong madaling panahon o huli, ang itinatag na mode ng serbisyo sa ay palaging nakakamit, anuman ang pinababang intensity ng daloy ng mga kahilingan. Ito ay sumusunod sa katotohanan na ang serye para sa denominator ng formula (24) ay nagtatagpo para sa anumang positibong halaga ng at .
Para sa isang QS na may "impatient" na mga kahilingan, ang konsepto ng "probability of failure" ay walang saysay - ang bawat kahilingan ay naaayon, ngunit maaaring hindi maghintay para sa serbisyo, na aalis nang maaga.
Relatibong throughput, ang average na bilang ng mga kahilingan sa queue. Ang relatibong kapasidad q ng naturang QS ay maaaring kalkulahin bilang mga sumusunod. Malinaw, lahat ng mga aplikasyon ay maseserbisyuhan, maliban sa mga umalis sa pila nang mas maaga sa iskedyul. Kalkulahin natin ang average na bilang ng mga application na maagang umalis sa pila. Upang gawin ito, kinakalkula namin ang average na bilang ng mga application sa queue:
Ang bawat isa sa mga application na ito ay napapailalim sa isang "daloy ng mga pag-alis" na may intensity na . Nangangahulugan ito na mula sa average na bilang ng -mga aplikasyon sa pila, sa karaniwan, -aalis ang mga aplikasyon nang hindi naghihintay ng serbisyo, -mga aplikasyon sa bawat yunit ng oras at sa kabuuan sa bawat yunit ng oras, sa karaniwan -ihahatid ang mga aplikasyon. Ang relatibong kapasidad ng QS ay:
Nakukuha pa rin namin ang average na bilang ng mga inookupahang channel sa pamamagitan ng paghahati sa ganap na bandwidth A sa:
(26)
Average na bilang ng mga application sa queue. Hinahayaan ka ng Relation (26) na kalkulahin ang average na bilang ng mga application sa queue nang hindi nagsusuma ng walang katapusang serye (25). Mula sa (26) nakukuha natin ang:
at ang average na bilang ng mga inookupahang channel na kasama sa formula na ito ay makikita bilang ang matematikal na inaasahan ng isang random na variable Z, kumukuha ng mga halaga 0, 1, 2,..., n na may probabilities ,:
Sa konklusyon, tandaan namin na kung sa mga formula (24) pupunta tayo sa limitasyon sa (o, ano ang pareho, sa ), pagkatapos ay sa 
Ang isang pila na may haba na k ay nananatili dito na may probabilidad na Pk at hindi sumasali sa pila na may probabilidad gk=1 - Pk." Ganito mismo ang karaniwang pag-uugali ng mga tao sa mga pila. Sa mga sistema ng pagpila, na mga mathematical na modelo ng mga proseso ng produksyon, ang posibleng Ang haba ng pila ay nalilimitahan ng pare-parehong laki (halimbawa, ang kapasidad ng bunker).
Sa seksyong ito, titingnan natin ang ilan sa mga pinakasimpleng QS at kumukuha ng mga expression para sa kanilang mga katangian (mga tagapagpahiwatig ng pagganap). Kasabay nito, ipapakita namin ang pangunahing pamamaraan ng pamamaraan na katangian ng elementarya, "Markov" na teorya ng pagpila. Hindi namin hahabulin ang bilang ng mga sample ng QS kung saan kukunin ang mga huling pagpapahayag ng mga katangian; Ang aklat na ito ay hindi isang reference na libro sa teorya ng queuing (ang papel na ito ay mas mahusay na natupad sa pamamagitan ng mga espesyal na manwal). Ang aming layunin ay ipakilala sa mambabasa ang ilang "maliit na trick" na nagpapadali sa landas sa pamamagitan ng teorya ng pagpila, na sa ilang umiiral na (kahit na nagpapanggap na sikat) na mga libro ay maaaring mukhang isang hindi magkakaugnay na hanay ng mga halimbawa.
Sa seksyong ito, isasaalang-alang namin ang lahat ng daloy ng mga kaganapan na naglilipat ng QS mula sa estado patungo sa estado bilang ang pinakasimpleng (nang hindi partikular na nagtatakda nito sa bawat oras). Kabilang sa mga ito ay ang tinatawag na "daloy ng serbisyo". Ito ay tumutukoy sa daloy ng mga kahilingan na inihahatid ng isang patuloy na abalang channel.
Sa daloy na ito, ang agwat sa pagitan ng mga kaganapan, gaya ng nakasanayan sa pinakasimpleng daloy, ay may exponential distribution (sa maraming mga manual ay sa halip ay sinasabi nila: "Ang oras ng serbisyo ay exponential"; kami mismo ang gagamit ng terminong ito sa hinaharap). Sa seksyong ito, ang exponential distribution ng oras ng serbisyo ay hindi sasabihin, gaya ng nakasanayan para sa "pinakasimpleng" system.
Ipapakilala namin ang mga katangian ng pagganap ng QS na isinasaalang-alang habang nagpapatuloy kami.
1. n-channel QS na may mga pagkabigo (problema sa Erlang).
Dito ay isasaalang-alang natin ang isa sa mga una, "klasikal" na mga problema ng teorya ng pila; ang problemang ito ay lumitaw mula sa mga praktikal na pangangailangan ng telephony at nalutas sa simula ng siglong ito ng Danish na matematiko na si Erlang. Ang problema ay nabuo tulad ng sumusunod: may mga channel (linya ng komunikasyon) na tumatanggap ng daloy ng mga kahilingan na may intensity K. Ang daloy ng mga serbisyo ay may intensity (ang kabaligtaran na halaga ng average na oras ng serbisyo). Hanapin ang mga huling probabilidad ng mga estado ng QS, pati na rin ang mga katangian ng pagiging epektibo nito:
A - absolute throughput, ibig sabihin, ang average na bilang ng mga application na inihatid sa bawat yunit ng oras;
Relative throughput, ibig sabihin, ang average na bahagi ng mga papasok na application na inihatid ng system;
Ang Rotk ay ang posibilidad ng pagtanggi, ibig sabihin, na iiwan ng aplikasyon ang QS na hindi naihatid;
k ay ang average na bilang ng mga channel na inookupahan.
Solusyon. Bibilangin namin ang mga estado ng system na S (SMO) ayon sa bilang ng mga kahilingan na matatagpuan sa system (sa kasong ito ay tumutugma ito sa bilang ng mga sinasakop na channel):
Walang isang solong aplikasyon sa CMO,
Mayroong isang kahilingan sa QS (isang channel ay abala, ang iba ay libre),
Sa SMO, ang mga kahilingan para sa mga channel ay inookupahan, ang iba ay libre),
Mayroong mga kahilingan sa QS (lahat ng mga channel ay abala).
Ang graph ng estado ng QS ay tumutugma sa pattern ng kamatayan at pagpaparami (Larawan 20.1). Markahan natin ang graph na ito - ilagay ang intensity ng mga daloy ng kaganapan sa tabi ng mga arrow Mula sa system, ang isang daloy ng mga application na may intensity X ay inilipat (sa sandaling dumating ang isang application, ang system ay tumalon mula sa ).
Ang parehong daloy ng mga kahilingan ay naglilipat ng system mula sa anumang kaliwang estado patungo sa kalapit na kanan (tingnan ang mga tuktok na arrow sa Fig. 20.1).
Ilagay natin ang mga intensity sa ibabang mga arrow. Hayaang nasa estado ang system (ang isang channel ay gumagana). Nagsasagawa ito ng pagpapanatili sa bawat yunit ng oras. Ipinapahiwatig namin ang intensity ng arrow Ngayon isipin natin na ang system ay nasa estado (dalawang channel ang gumagana). Upang ito ay mapunta, alinman sa unang channel o ang pangalawa ay dapat tapusin ang servicing; ang kabuuang intensity ng kanilang mga daloy ng serbisyo ay katumbas ng katumbas na arrow. Ang kabuuang daloy ng mga serbisyong ibinigay ng tatlong channel ay may intensity na katumbas ng mga channel - Inilalagay namin ang mga intensity na ito sa mga arrow sa ibaba sa Fig. 20.1.
At ngayon, alam ang lahat ng intensity, gagamitin namin ang mga handa na formula (19.7), (19.8) para sa mga huling probabilidad sa pamamaraan ng kamatayan at pagpaparami. Gamit ang formula (19.8) nakukuha natin ang:
Ang mga tuntunin ng pagpapalawak ay ang mga coefficient sa mga expression para sa
Tandaan na sa mga pormula (20.1), (20.2) ang mga intensidad ng mga Itlog ay kasama hindi isa-isa, ngunit sa anyo lamang ng isang ratio
at tatawagin namin ang halaga na "binawasan ang intensity ng daloy ng mga aplikasyon." Ang kahulugan nito ay ang average na bilang ng mga kahilingang natanggap sa average na oras ng paglilingkod sa isang kahilingan. Gamit ang notasyong ito, isinusulat namin muli ang mga formula (20.1), (20.2) sa anyo:
Ang mga formula (20.4), (20.5) para sa mga huling probabilidad ng mga estado ay tinatawag na Erlang formula - bilang parangal sa nagtatag ng teorya ng queuing. Karamihan sa iba pang mga pormula ng teoryang ito (ngayon ay higit pa sa mga kabute sa kagubatan) ay walang mga espesyal na pangalan.
Kaya, ang mga huling probabilidad ay natagpuan. Gamit ang mga ito, kakalkulahin namin ang mga katangian ng pagganap ng QS. Una, hanapin natin ang posibilidad na ang isang papasok na aplikasyon ay tatanggihan (hindi maseserbisyuhan). Para magawa ito, dapat na abala ang lahat ng channel, ibig sabihin
Mula dito makikita natin ang relatibong throughput - ang posibilidad na maihatid ang kahilingan:
Nakukuha namin ang ganap na throughput sa pamamagitan ng pagpaparami ng intensity ng daloy ng mga application X sa pamamagitan ng
Ang natitira na lang ay upang mahanap ang average na bilang ng mga inookupahang channel k Ang halagang ito ay maaaring matagpuan nang "direkta", bilang ang matematikal na pag-asa ng isang discrete random variable na may mga posibleng halaga at probabilidad ng mga halagang ito.
Ang pagpapalit ng mga expression (20.5) para dito at pagsasagawa ng kaukulang mga pagbabagong-anyo, sa kalaunan ay makukuha natin ang tamang formula para sa k. ang absolute throughput A. Ito ay walang iba kundi ang intensity ng daloy ng mga application na inihatid ng system. Ang bawat abalang channel ay naghahatid ng average ng mga kahilingan sa bawat yunit ng oras. Nangangahulugan ito na ang average na bilang ng mga channel na inookupahan ay
At anong proporsyon ng mga channel ang magiging idle?
Mayroon nang ilang pahiwatig ng pag-optimize na nakikita dito. Sa katunayan, ang pagpapanatili ng bawat channel sa bawat yunit ng oras ay nagkakahalaga ng isang tiyak na halaga. Kasabay nito, ang bawat serbisyong aplikasyon ay bumubuo ng ilang kita. Ang pag-multiply ng kita na ito sa average na bilang ng mga application A na naseserbisyuhan sa bawat yunit ng oras, nakukuha natin ang average na kita mula sa QS bawat yunit ng oras. Naturally, habang tumataas ang bilang ng mga channel, tumataas ang kita na ito, ngunit tumataas din ang mga gastos na nauugnay sa pagpapanatili ng mga channel. Ano ang hihigit - pagtaas ng kita o gastos? Depende ito sa mga tuntunin ng operasyon, ang "bayad para sa pagseserbisyo sa aplikasyon" at ang halaga ng pagpapanatili ng channel. Ang pag-alam sa mga halagang ito, mahahanap mo ang pinakamainam na bilang ng mga channel, ang pinaka-epektibo sa gastos. Hindi namin malulutas ang ganoong problema, ipaubaya ito sa parehong "hindi tamad, mausisa na mambabasa" upang makabuo ng isang halimbawa at malutas ito. Sa pangkalahatan, ang pag-imbento ng mga problema ay nabubuo nang higit pa kaysa sa paglutas sa mga naidulot na ng isang tao.
Ang mga ML system ay bahagi ng mas malawak na klase ng mga dynamical system na kung minsan ay tinatawag na flow system. Sistema ng thread ay isang sistema kung saan ang ilang mga bagay ay inililipat sa isa o higit pang mga channel na may limitadong kapasidad para sa layunin ng paglipat mula sa isang punto patungo sa isa pa. Kapag sinusuri ang mga sistema ng daloy, nahahati sila sa dalawang pangunahing klase:
mga regular na sistema, ibig sabihin, mga sistema kung saan kumikilos ang mga daloy sa isang predictable na paraan (alam ang magnitude ng daloy at ang oras ng paglitaw nito sa channel). Sa kaso kung saan mayroon lamang isang channel, ang pagkalkula ng system ay walang halaga. Ito ay malinaw na sa pagitan ng intensity ng daloy λ at bilis ng serbisyo Sa may ratio λ < c;
mga hindi regular na sistema, ibig sabihin, mga sistema kung saan kumikilos ang mga thread sa mga hindi mahuhulaan na paraan.
Mas kawili-wili ang kaso ng isang regular na daloy na ipinamamahagi sa isang network ng mga channel. Ito ay malinaw na ang kondisyon λ < c na-save para sa bawat channel. Lumilikha ito ng isang kumplikadong problemang kombinatorial.
Mayroong pitong kalsada:
A→B→D→E→F
A→C→B→E→F
A→C→B→D→E→F
A→C→B→D→F
Kinakailangang maghatid ng kargamento mula sa A V F. Ang kapasidad ng bawat channel ay kilala. Ano ang kapasidad ng network at anong landas ang dapat tahakin ng daloy? Ang problemang ito ay maaaring malutas gamit ang maximum na flow theorem, na aming isinasaalang-alang nang mas maaga (Larawan 6).
Kasama sa pangalawang klase ang mga random na posibleng daloy kung saan ang oras ng pagtanggap ng isang kinakailangan ay hindi natukoy at ang bilang ng mga kinakailangan ay hindi mahuhulaan. Ang teorya ng pagpila ay tumatalakay sa paglutas ng mga ganitong problema.
Sa pangkalahatan, ang sistema ng pagpila ay maaaring katawanin sa Figure 7.
kanin. 7.
Ang paksa ng teorya ng pagpila ay upang maitaguyod ang kaugnayan sa pagitan ng likas na katangian ng daloy ng mga kahilingan, ang bilang ng mga channel, pagiging produktibo, tamang operasyon at kahusayan.
Bilang mga katangian ng pagganap Maaaring gamitin ang mga sumusunod na dami at function:
ang average na bilang ng mga application na maaaring ibigay ng QS sa bawat yunit ng oras;
ang average na bilang ng mga aplikasyon na tinatanggihan at umaalis sa CMO;
ang posibilidad na ang natanggap na aplikasyon ay agad na maserbisyuhan;
average na oras ng paghihintay sa pila;
average na bilang ng mga aplikasyon sa pila;
average na kita ng SMO bawat yunit ng oras at iba pa mga tagapagpahiwatig ng ekonomiya ng SMO.
Ang pagsusuri ng QS ay pinasimple kung ang isang proseso ng Markov ay nangyayari sa system, kung gayon ang sistema ay maaaring ilarawan sa pamamagitan ng mga ordinaryong differential equation, at ang paglilimita sa mga probabilidad - sa pamamagitan ng linear algebraic equation.
Ang proseso ng Markov ay nangangailangan na ang lahat ng mga daloy ay Poisson (walang mga epekto), ngunit ang kagamitan ng mga proseso ng Markov ay ginagamit din kapag ang proseso ay iba sa Markov. Sa kasong ito, ang mga katangian ng QS ay maaaring tantiyahin nang humigit-kumulang: kung mas kumplikado ang QS, mas tumpak ang pagtatantya.
Pag-uuri ng mga sistema ng pagpila
Ang QS ay maaaring may dalawang uri:
QS na may mga pagkabigo;
QS na may paghihintay (i.e. may pila).
Ang serbisyo sa mga system na may pila ay maaaring may ibang katangian:
maaaring gawing streamlined ang serbisyo;
random na serbisyo;
serbisyong may priyoridad, habang ang priyoridad ay maaaring may pagkaantala o walang pagkaantala.
Ang mga sistema ng pagpila ay nahahati sa:
mga sistema na may walang limitasyong paghihintay, sa kasong ito, ang gawain na natanggap ng QS ay nagiging queued at naghihintay para sa serbisyo. Maaga o huli siya ay paglilingkuran;
mga sistema na may limitadong inaasahan, habang ang mga paghihigpit ay ipinapataw sa application sa queue, halimbawa, isang limitadong oras na ginugol sa queue, ang haba ng pila, ang kabuuang oras na ginugol sa QS. Depende sa uri ng QS, maaaring gamitin ang iba't ibang indicator upang suriin ang pagiging epektibo.
Para sa QS na may mga pagkabigo, ang mga sumusunod na tagapagpahiwatig ng pagganap ay ginagamit:
ganap na throughput A– ang average na bilang ng mga aplikasyon na maaaring ibigay sa bawat yunit ng oras;
relatibong throughput Q– relatibong average na bilang ng mga aplikasyon. Sa kasong ito, ang relatibong throughput ay makikita gamit ang formula
Kung saan ang λ ay ang intensity ng mga kahilingang natanggap ng QS.
Para sa SMO na may inaasahan ganap na throughput A At relatibong throughput Q nawawala ang kanilang kahulugan, ngunit ang iba pang mga katangian ay nagiging mahalaga:
yunit ng oras ng paghihintay sa pila;
average na bilang ng mga application sa pila;
average na oras na ginugol sa system.
Para sa isang QS na may limitadong pila, ang parehong mga pangkat ng mga katangian ay kawili-wili.
Isaalang-alang ang n - channel queuing system na may paghihintay.
Ang intensity ng daloy ng serbisyo ay μ. Ang tagal ng serbisyo ay isang random na variable na napapailalim sa exponential distribution law. Ang daloy ng serbisyo ay ang pinakasimpleng daloy ng Poisson ng mga kaganapan.
Ang laki ng pila ay nagpapahintulot sa mga tao na makapasok dito m mga aplikasyon.
Upang mahanap ang marginal probabilities, maaari mong gamitin ang mga sumusunod na expression.
(0‑1)
saan.
Posibilidad ng pagtanggi sa serbisyo ng isang aplikasyon(mangyayari ang pagkabigo kung abala ang lahat ng channel at mayroon m mga kahilingan):
(0‑2)
Kamag-anak na Bandwidth.
(0‑3)
Ganap na throughput.
(0‑4)
Average na bilang ng mga abalang channel.
Para sa isang QS na may pila, ang average na bilang ng mga abalang channel ay hindi nag-tutugma (hindi katulad ng QS na may mga pagkabigo) sa average na bilang ng mga kahilingan sa system. Ang pagkakaiba ay katumbas ng bilang ng mga application na naghihintay sa pila.
Tukuyin natin ang average na bilang ng mga inookupahang channel. Ang bawat abalang channel ay nagsisilbi sa average na μ na mga claim sa bawat yunit ng oras, at ang QS sa kabuuan ay naghahatid ng A na mga claim sa bawat yunit ng oras. Dividing A by μ nakukuha natin
(0‑5)
Ang average na bilang ng mga application sa queue.
Upang mahanap ang average na bilang ng mga application na naghihintay sa queue kung χ≠1, maaari mong gamitin ang expression:
(0‑6)
(0‑7)
saan = .
Ang average na bilang ng mga application sa system.
(0‑8)
Average na oras ng paghihintay para sa isang application sa pila.
Ang average na oras ng paghihintay para sa isang aplikasyon sa queue ay makikita mula sa expression (χ≠1).
(0‑9)
Karaniwang oras na nananatili ang isang application sa system.
Tulad ng kaso ng isang solong channel na QS, mayroon kaming:
(0‑10)
Ang nilalaman ng gawain.
Paghahanda ng mga eksperimentong instrumento .
Isinasagawa alinsunod sa mga pangkalahatang tuntunin.
Pagkalkula gamit ang isang analytical na modelo .
1. Ihanda ang sumusunod na talahanayan sa Microsoft Excel.
|
Mga pagpipilian |
Analitikal |
Panggagaya |
|||||||||||||||
|
n |
m |
Ta |
Ts |
ρ |
χ |
P0 |
P1 |
p2 |
Rotk |
W |
nozh |
q |
A |
Rotk |
W |
q |
A |
2. Sa mga column para sa mga parameter ng QS ng talahanayan, isulat ang iyong paunang data, na tinutukoy ayon sa panuntunan:
n =1,2,3
m=1,3,5
Para sa bawat kumbinasyon ( n,m) kinakailangan upang mahanap ang teoretikal at pang-eksperimentong mga halaga ng mga tagapagpahiwatig ng QS para sa mga sumusunod na pares ng mga halaga:
= <порядковый номер в списке группы>
3. Ilagay ang mga naaangkop na formula sa mga column na may mga indicator ng analytical na modelo.
Mag-eksperimento sa isang modelo ng simulation.
1. Itakda ang launch mode na may exponentially distributed service time sa pamamagitan ng pagtatakda ng value ng kaukulang parameter sa 1.
2. Para sa bawat kumbinasyon ng n, m, at patakbuhin ang modelo.
Ipasok ang mga resulta ng mga run sa talahanayan.
3. Maglagay ng mga formula para sa pagkalkula ng average na halaga ng indicator na Ptk, q at A sa mga kaukulang column ng talahanayan.
Pagsusuri ng mga resulta .
1. Pag-aralan ang mga resulta na nakuha sa pamamagitan ng teoretikal at eksperimental na mga pamamaraan, paghahambing ng mga resulta sa bawat isa.
2. Para sa isa sa mga kumbinasyon (n,m), i-plot sa isang diagram ang pagtitiwala ng Ptk sa theoretically at experimentally na nakuhang data.
Pag-optimize ng mga parameter ng QS .
Lutasin ang problema sa pag-optimize ng laki ng bilang ng mga lugar sa isang queue m para sa dalawang device na may average na oras ng serbisyo = mula sa punto ng view ng pagkuha ng maximum na kita. Bilang mga kondisyon ng problema, kunin ang:
- kita mula sa paglilingkod sa isang aplikasyon na katumbas ng 80 USD/oras,
- ang halaga ng pagpapanatili ng isang device ay 1$/oras,
- ang halaga ng pagpapanatili ng isang lugar sa pila ay 0.2 USD/oras.
1. Para sa mga kalkulasyon, ipinapayong lumikha ng isang talahanayan:
Ang unang hanay ay puno ng mga halaga ng bilang ng mga device n =1.
Ang pangalawang hanay ay puno ng mga halaga ng mga numero sa natural na serye (1,2,3...).
Ang lahat ng mga cell sa ikatlo at ikaapat na hanay ay puno ng mga halaga.
Ang mga formula para sa mga column ng talahanayan sa seksyon 0 ay inililipat sa mga cell ng mga column mula lima hanggang labing-apat.
Sa mga hanay na may paunang data ng mga seksyon ng Kita, Gastos, Kita, ipasok ang mga halaga (tingnan sa itaas).
Sa mga hanay na may mga kinakalkula na halaga ng mga seksyon ng Kita, Gastos, Kita, isulat ang mga formula ng pagkalkula:
- bilang ng mga aplikasyon sa bawat yunit ng oras
N r =A
- kabuuang kita bawat yunit ng oras
I S = I r *N r
- kabuuang pagkonsumo bawat yunit ng oras
E S =E s *n + E q *m
- tubo bawat yunit ng oras
P = I S - E S
saan
Ir - kita mula sa isang aplikasyon,
E s - pagkonsumo bawat device,
Eq - gastos sa bawat lugar sa linya
2. Punan ang mga hilera ng talahanayan para sa n=2 at n=3.
Hanapin ang m opt para sa n =1,2,3.
3. Gumuhit ng mga graph ng dependence C(m) para sa n=1,2,3 sa isang diagram.
Ulat sa trabaho:
Ang ulat sa trabaho ay dapat na kasama ang:
- paunang datos,
- mga resulta ng mga kalkulasyon at eksperimento sa modelo ng software,
Mga graph para sa P bukas,
- talahanayan na may data upang mahanap ang pinakamahusay m at ang halaga ng m opt,
- mga graph ng tubo sa bawat yunit ng oras depende sa m para sa n=1,2,3.
Kontrolin ang mga tanong :
1) Magbigay ng maikling paglalarawan ng multi-channel na modelo ng QS na may limitadong pila.
2) Anong mga tagapagpahiwatig ang nagpapakilala sa paggana ng isang multi-channel na QS na may limitadong pila?
3) Paano kinakalkula ang marginal probabilities ng isang multi-channel QS na may limitadong queue?
4) Paano mahahanap ang posibilidad ng pagkabigo sa serbisyo ng isang aplikasyon?
5) Paano makahanap ng kamag-anak na bandwidth?
6) Ano ang ganap na throughput?
7) Paano kinakalkula ang average na bilang ng mga application sa system?
8) Magbigay ng mga halimbawa ng isang multi-channel na QS na may limitadong pila.
Mga gawain.
1) Ang gas station ay may 3 pumps at isang platform para sa 3 kotse upang maghintay para sa refueling. Sa karaniwan, isang kotse ang dumarating sa istasyon tuwing 4 na minuto. Ang average na oras ng serbisyo para sa isang makina ay 2.8 minuto. Tukuyin ang mga katangian ng pagpapatakbo ng isang gasolinahan.
2) Ang istasyon ng teknikal na inspeksyon ng sasakyan, na mayroong 3 poste ng inspeksyon, ay tumatanggap ng average ng 1 sasakyan bawat 0.4 na oras. Tumatanggap ng 3 kotse ang paradahan sa bakuran. Ang average na oras ng pagpapatakbo ng isang post ay 0.5 oras. Tukuyin ang mga katangian ng istasyon ng serbisyo.
3) Ang mga kalakal ay inihahatid sa tindahan sa pamamagitan ng mga sasakyan. Sa araw, may average na 6 na sasakyan ang dumarating. Ang mga utility room para sa paghahanda ng mga paninda para sa pagbebenta ay nagbibigay-daan sa iyo na magproseso at mag-imbak ng mga kalakal na dala ng dalawang sasakyan. Gumagamit ang tindahan ng tatlong packer ng produkto nang palipat-lipat, na ang bawat isa sa karaniwan ay maaaring magproseso ng mga produkto ng isang makina sa loob ng 5 oras. Ang araw ng trabaho ng mga packer ay 12 oras. Tukuyin ang mga katangian ng pagpapatakbo ng tindahan, pati na rin kung ano ang kapasidad ng mga silid ng utility upang ang posibilidad ng kumpletong pagproseso ng mga kalakal ay mas malaki kaysa sa 0.96.
4) May tatlong cash register ang tindahan. Ang average na oras ng serbisyo para sa isang customer ay 3 minuto. Ang intensity ng daloy ng customer ay 7 tao bawat minuto. Ang bilang ng mga customer na nakatayo sa linya sa checkout ay hindi maaaring lumampas sa 5 tao. Ang isang mamimili na pumupunta sa isang tindahan kung saan mayroong 5 tao sa bawat linya ng pag-checkout ay hindi naghihintay, ngunit umalis sa tindahan. Tukuyin ang mga katangian ng tindahan.
5) Ang pakyawan na bodega ay naglalabas ng mga kalakal sa mga customer. Ang paglo-load ng sasakyan ay isinasagawa ng tatlong pangkat ng mga loader, bawat isa ay binubuo ng 4 na tao. Ang bodega ay maaaring sabay-sabay na mag-accommodate ng 5 sasakyan at kung may bagong sasakyan na dumating sa oras na ito, hindi ito naseserbisyuhan. Ang intensity ng papasok na daloy ay 5 kotse kada oras. Ang loading rate ay 2 sasakyan kada oras. Magbigay ng pagtatasa sa pagpapatakbo ng bodega at isang opsyon para sa muling pagsasaayos nito.
6) May tatlong terminal ang customs office. Ang intensity ng daloy ng mga sasakyan na nagdadala ng mga kalakal at napapailalim sa customs control ay 30 units. kada araw. Ang average na oras ng pagproseso ng customs sa terminal para sa isang sasakyan ay 3 oras. Kung mayroong 5 sasakyan sa linya upang dumaan sa customs control, ang mga darating na sasakyan ay pupunta sa isa pang customs office. Maghanap ng mga tagapagpahiwatig ng pagganap ng customs.
7) Sa karaniwan, ang mga sasakyang may mga construction materials ay dumarating sa construction site sa loob ng 40 minuto. Ang average na oras para sa pagbabawas ng isang sasakyan ay 1.8 oras. Dalawang pangkat ng mga loader ang nakikibahagi sa pagbabawas. Hindi hihigit sa 5 sasakyan ang maaaring nakapila para sa pagbabawas sa lugar ng konstruksiyon. Tukuyin ang mga tagapagpahiwatig ng pagganap ng lugar ng konstruksiyon.
8) Sa karaniwan, 12 sasakyan ang dumarating kada oras sa isang car wash na may tatlong work station. Kung mayroon nang 6 na sasakyan sa pila, ang mga bagong dating na sasakyan ay hindi sumasali sa pila, ngunit umalis sa labahan. Ang average na oras ng paghuhugas ng kotse ay 20 minuto, ang average na halaga ng mga serbisyo sa paghuhugas ng kotse ay 150 rubles. Tukuyin ang mga indicator ng performance ng car wash at ang average na pagkawala ng kita sa araw ng trabaho (mula 9 a.m. hanggang 7 p.m.).
9) Ang intensity ng daloy ng mga sasakyan na nagdadala ng mga kalakal at napapailalim sa customs control ay 50 units. kada araw. Ang average na oras ng pagproseso ng customs sa terminal para sa isang sasakyan ay 2.8 oras. Ang maximum na pila para sa customs control ay dapat na hindi hihigit sa 8 kotse. Tukuyin kung gaano karaming mga terminal ang kailangang buksan sa customs upang ang posibilidad ng downtime ng sasakyan ay minimal.
System na may limitadong haba ng pila. Isaalang-alang natin ang isang channel QS na may paghihintay, na tumatanggap ng daloy ng mga kahilingan na may intensity ; intensity ng serbisyo (para sa isang channel); bilang ng mga lugar sa pila.
Ang mga estado ng system ay binibilang ayon sa bilang ng mga kahilingang nauugnay sa system:
walang pila:
Lahat ng channel ay libre;
Ang isang channel ay inookupahan, ang natitira ay libre;
Ang mga channel ay abala, ang iba ay hindi;
Ang lahat ng mga channel ay inookupahan, walang mga libreng channel;
may pila:
Ang lahat ng mga channel ay abala; isang application ang nasa pila;
Ang lahat ng mga channel ay abala, ang mga aplikasyon ay nasa pila;
Ang lahat ng mga channel ay abala, m mga application sa pila.
Ang GSP ay ipinapakita sa Fig. 5.9. Ang bawat arrow ay minarkahan ng kaukulang intensity ng mga daloy ng kaganapan. Kasama ang mga arrow mula kaliwa hanggang kanan, ang system ay palaging inililipat sa pamamagitan ng parehong daloy ng mga kahilingan na may intensity na
Multichannel exponential SMO naiiba sa single-channel gaya ng mga sumusunod. Mayroong higit sa isang channel sa loob nito. Makakapila ang isang papasok na kahilingan kung abala ang lahat ng channel. Kung hindi, ang kahilingan ay sumasakop sa isang libreng channel. 
(5.56)
Sumulat tayo ng mga expression para sa paglilimita ng mga probabilidad ng mga estado gamit ang notasyon: (tingnan ang 5.45)
Ang posibilidad ng pagkabigo. Ang isang aplikasyon na natanggap ay tinanggihan kung ang lahat ay okupado n mga channel at lahat m mga lugar sa linya:
(5.57)
Ang kamag-anak na throughput ay umaakma sa posibilidad ng pagkabigo sa isa:
Ganap na throughput ng QS:
(5.58)
Average na bilang ng mga abalang channel. Para sa SMO sa mga pagtanggi, ito ay kasabay ng average na bilang ng mga aplikasyon sa system. Para sa SMO sa isang queue, ang average na bilang ng mga abalang channel ay hindi tumutugma sa average na bilang ng mga application sa system: ang huling halaga ay naiiba mula sa una sa pamamagitan ng average na bilang ng mga application sa queue.
Tukuyin natin ang average na bilang ng mga channel na inookupahan ng . Ang bawat abalang channel ay nagsisilbi sa average na mga kahilingan sa bawat yunit ng oras, at SMO pangkalahatang serbisyo ay karaniwan A mga aplikasyon sa bawat yunit ng oras. Ang paghahati sa isa't isa, nakukuha natin:
Ang average na bilang ng mga kahilingan sa isang queue ay maaaring direktang kalkulahin bilang ang mathematical na inaasahan ng isang discrete random variable:
(5.59)
Dito muli (ang expression sa mga bracket) ang hinango ng kabuuan ng geometric na pag-unlad ay nangyayari (tingnan sa itaas (5.50), (5.51)-(5.53)), gamit ang kaugnayan para dito, nakuha natin:
Average na bilang ng mga application sa system:
Average na oras ng paghihintay para sa isang application sa pila. Isaalang-alang natin ang ilang sitwasyon na naiiba sa estado kung saan mahahanap ng bagong dating na kahilingan ang system at kung gaano ito katagal maghihintay para sa serbisyo.
Kung ang isang kahilingan ay hindi mahanap ang lahat ng mga channel na abala, ito ay hindi na kailangang maghintay sa lahat (ang kaukulang mga termino sa matematikal na inaasahan ay katumbas ng zero). Kung ang aplikasyon ay dumating sa oras na ang lahat ay abala P channel, ngunit walang pila, kailangan niyang maghintay sa average para sa isang oras na katumbas ng (dahil ang "daloy ng mga release" ng mga channel ay may intensity na ). Kung nakita ng isang application na abala ang lahat ng channel at isang application ang nasa unahan nito sa pila, kakailanganin itong maghintay sa average para sa isang haba ng oras (para sa bawat application sa harap), atbp. Kung ang isang application ay natagpuan ang sarili sa isang pila ng mga application , ito ay kailangang maghintay sa karaniwan para sa isang yugto ng panahon. Kung ang isang bagong dating na application ay natagpuan ang sarili sa pila m mga aplikasyon, pagkatapos ay hindi ito maghihintay sa lahat (ngunit hindi ihahatid).
Average na oras ng paghihintay nahanap namin sa pamamagitan ng pagpaparami ng bawat isa sa mga halagang ito sa pamamagitan ng kaukulang mga probabilidad:
(5.60)
Tulad ng kaso ng isang single-channel na QS na may paghihintay, napapansin namin na ang expression na ito ay naiiba sa expression para sa average na haba ng queue (5.59) sa pamamagitan lamang ng factor , i.e.
Karaniwang oras na nananatili ang isang application sa system, kapareho ng para sa single-channel SMO, ay naiiba sa average na oras ng paghihintay sa average na oras ng serbisyo na na-multiply sa relative throughput:
Mga system na may walang limitasyong haba ng pila.
Isinaalang-alang namin ang isang channel QS na may paghihintay, kapag hindi hihigit sa m mga aplikasyon.
Tulad ng dati, kapag sinusuri ang mga sistema nang walang mga paghihigpit, kinakailangang isaalang-alang ang mga nakuhang relasyon para sa .
Nakukuha namin ang mga probabilidad ng mga estado mula sa mga formula (5.56) sa pamamagitan ng pagpasa sa limitasyon (sa ). Tandaan na ang kabuuan ng kaukulang geometric progression ay nagtatagpo sa at diverges sa > 1. Ipagpalagay na< 1 и устремив в формулах (5.56) величину m hanggang sa kawalang-hanggan, nakakakuha kami ng mga expression para sa paglilimita ng mga probabilidad ng mga estado:
(5.61)
Ang posibilidad ng pagkabigo, kamag-anak at ganap na throughput. Dahil ang bawat kahilingan ay maseserbisyuhan nang maaga o huli, ang mga katangian ng throughput ng QS ay magiging:
Nakukuha namin ang average na bilang ng mga application sa queue mula sa (5.59):
at ang average na oras ng paghihintay ay mula sa (5.60):
Ang average na bilang ng mga inookupahang channel, tulad ng dati, ay tinutukoy sa pamamagitan ng absolute throughput:
Ang average na bilang ng mga application na nauugnay sa QS ay tinukoy bilang ang average na bilang ng mga application sa queue kasama ang average na bilang ng mga application na nasa ilalim ng serbisyo (average na bilang ng mga busy na channel):
Ang pagtaas ng pagiging kumplikado ng mga istraktura at mga mode ng mga tunay na sistema ay nagpapalubha sa paggamit ng mga klasikal na pamamaraan ng teorya ng pagpila dahil sa pagtaas ng dimensyon ng mga problemang nilulutas, na partikular na tipikal para sa mga system na may istraktura ng network. Isa sa mga posibleng paraan para malampasan ang dimensionality ay ang paggamit ng mga modelo sa anyo ng mga queuing network (Queuing).
SeMO ay isang koleksyon ng isang limitadong bilang ng mga serving node kung saan ang mga kahilingan ay umiikot, na gumagalaw alinsunod sa routing matrix mula sa isang node patungo sa isa pa. Palaging bukas ang node SMO. Sabay hiwalay SMO SMO− ang istraktura ng system, at ang mga kinakailangan na nagpapalipat-lipat SeMO, − mga bahagi ng mga daloy ng materyal (mga mensahe (packet) sa isang network ng komunikasyon, mga gawain sa mga multiprocessor system, mga lalagyan ng mga daloy ng kargamento, atbp.).
Sa turn nito, SeMO ginagamit upang matukoy ang pinakamahalagang katangian ng system ng mga sistema ng impormasyon: pagiging produktibo; oras ng paghahatid ng pakete; posibilidad ng pagkawala ng mensahe at pagharang sa mga node; mga lugar ng pinahihintulutang halaga ng pag-load kung saan tinitiyak ang kinakailangang kalidad ng serbisyo, atbp.
Sa teorya SeMO Ang konsepto ng estado ng network ay mahalaga. Ang pinakamahalagang katangian ng mga network MO− mga probabilidad ng kanilang mga estado. Upang matukoy ang mga probabilidad ng mga estado SeMO imbestigahan ang random na prosesong nagaganap sa network. Habang dumadaloy ang mga modelo SeMO Ang mga proseso ng Markov at semi-Markov ay madalas ding ginagamit.
3.3. Sistema ng pagpila bilang isang modelo
1.5. Mga network ng pagpila
Ang proseso ng Markov na may tuloy-tuloy na oras ay naglalarawan sa paggana ng exponential SeMO.
Tinatawag ang network exponential kung papasok na daloy ng mga kinakailangan sa bawat isa SMO Poisson, at ang mga oras ng bawat yugto ng serbisyong ipinatupad sa alinman SMO mayroon ang mga network exponential pamamahagi. Nagbibigay-daan ito sa amin na ipagpalagay na ang mga yugto ng serbisyo ay independyente sa isa't isa at hindi nakasalalay sa alinman sa mga parameter ng papasok na daloy, o sa estado ng network, o sa mga ruta ng mga kahilingan.
Teorya ng exponential SeMO pinaka-binuo, at malawak itong ginagamit kapwa para sa pag-aaral ng mga PD network at para sa pag-aaral ng multiprocessor mga sistema ng kompyuter (CS). Ang mga praktikal na formula ay binuo para sa pagkalkula ng probabilistic-temporal na katangian (PTC) ng naturang mga network at system.
Ang mga pagsisikap na malalim na pag-aralan ang mga hindi-Markov na modelo ng mga sistema ng network ay nakatagpo ng mga makabuluhang paghihirap, na sanhi, lalo na, sa kawalan ng kalayaan ng tagal ng pananatili ng mga kinakailangan sa iba't ibang mga node ng mga modelo ng mga sistema ng network na may mga hindi pamantayang disiplina. Kaya, halimbawa, na may medyo makatotohanang pag-aakala na ang haba ng kahilingan ay nananatiling pare-pareho sa panahon ng paghahatid nito sa pamamagitan ng mga node ng network, kinakailangan na subaybayan ang landas ng bawat kahilingan, na ginagawang imposibleng analytically kalkulahin ang mga katangian para sa isang network na may bilang ng mga node M>2.
Ang pagsusuri ng mga gawa na nakatuon sa pag-aaral o pagkalkula ng mga hindi-Markov na modelo ay nagpapakita na ang mga solusyon, bilang panuntunan, ay nakukuha ayon sa algorithm sa pamamagitan ng kumplikadong mga kalkulasyon ng numero gamit ang mga pagbabagong Laplace-Stieltjes, ay ipinatupad sa software, ay lubos na matrabaho, o may makabuluhang mga pagkakamali sa pagtatasa ng mga tagapagpahiwatig ng pagganap ng mga sistema ng impormasyon (IS) sa lugar ng katamtaman at mabigat na pagkarga. Samakatuwid, para sa pagmomodelo SeMO, umaalis sa klase ng mga multiplicative, gumagamit sila ng mga tinatayang pamamaraan.
Comparative analysis ng tinatayang pamamaraan ng pagmomodelo SeMO at ang mga halimbawang ibinigay sa nagpapakita na kinakailangang gumamit ng tinatayang mga pamamaraan para sa pagkalkula ng SeMO nang may malaking pag-iingat, na kapag kinakalkula ang partikular na SeMO, sa proseso ng paglutas ng iba't ibang mga problema, tila kinakailangan na magsagawa ng pananaliksik upang masuri ang katumpakan at pagiging sensitibo. ng paraang ginamit, pati na rin magsagawa ng simulation experiment ang orihinal na SeMO para sa isang sapat na malaking hanay ng mga halaga ng iba't ibang mga parameter.
Ang mga analytical na pamamaraan para sa pagkalkula ng mga katangian ng IS ay batay, bilang panuntunan, sa pagsusuri ng exponential CeMO. Gamit ang mathematical apparatus na ito, posible na makakuha ng mga analytical na modelo para sa paglutas ng malawak na hanay ng mga problema sa pag-aaral ng mga system. Ang SeMO ay, una sa lahat, isang hanay ng mga magkakaugnay na sistema ng pagpila. Samakatuwid, kinakailangang alalahanin ang mga pangunahing tampok ng mga sistemang ito.
Network ng pagpila kumakatawan sa isang koleksyon ng mga may hangganang numero N serving nodes, kung saan ang mga kahilingan ay umiikot, na gumagalaw alinsunod sa routing matrix mula sa isang node patungo sa isa pa. Ang isang node ay palaging isang bukas na QS (at ang QS ay maaaring maging sa anumang klase). Sabay hiwalay SMO ipakita ang functionally independent na mga bahagi ng isang tunay na system, mga koneksyon sa pagitan SMO- ang istraktura ng system, at ang mga kinakailangan na nagpapalipat-lipat SeMO,- mga bahagi ng mga daloy ng materyal (mga mensahe (packet) sa isang network ng komunikasyon, mga gawain sa mga multiprocessor system, mga lalagyan ng mga daloy ng kargamento, atbp.).
Para sa visual na representasyon SeMO ginagamit ang isang graph na ang mga vertex (node) ay tumutugma sa indibidwal SMO, at ang mga arko ay nagpapakita ng mga koneksyon sa pagitan ng mga node.
Ang paglipat ng mga aplikasyon sa pagitan ng mga node ay nangyayari kaagad alinsunod sa mga posibilidad ng paglipat 
, p ij- ang posibilidad na ang kahilingan pagkatapos ng serbisyo sa node i mapupunta sa node j. Naturally, kung ang mga node ay hindi direktang konektado sa isa't isa, kung gayon p ij= 0. Kung mula sa ako- th node transition sa isang node lang j, Iyon p ij= 1.
SeMO inuri ayon sa ilang pamantayan (Larawan 4).
Tinatawag ang network linear, kung ang intensity ng mga daloy ng aplikasyon sa mga node ay magkakaugnay ng isang linear na relasyon
l j= a ij l i,
saan a ij- koepisyent ng proporsyonalidad, o nauugnay sa pinagmulan
l j= a j l 0 ,.
Coefficient a j tinatawag na transmission coefficient, nailalarawan nito ang bahagi ng mga aplikasyon na natanggap sa j- th node mula sa pinagmulan ng mga application, o - ang average na dami ng beses na dumaan ang isang application sa node na ito sa panahong ang application ay nasa network.
Kung ang intensity ng mga daloy ng aplikasyon sa mga node ng network ay nauugnay sa isang hindi linear na relasyon (halimbawa, 
), pagkatapos ay tinawag ang network nonlinear..
Ang isang network ay palaging linear kung ang mga application ay hindi nawala o na-multiply dito.
Bukas Ang network ay isang bukas na network kung saan ang mga kahilingan ay nagmumula sa panlabas na kapaligiran at iniiwan ang network sa panlabas na kapaligiran pagkatapos na maserbisyuhan. Sa madaling salita, ang tampok ng open-loop SeMO(RSeMO) ay ang pagkakaroon ng isa o higit pang independiyenteng panlabas na pinagmumulan na bumubuo ng mga application na pumapasok sa network, gaano man karaming mga application ang nasa network. Sa anumang oras sa RSeMO maaaring mayroong arbitrary na bilang ng mga aplikasyon (mula 0 hanggang ¥).
kanin. 4. Pag-uuri ng mga network ng pila
SA saradong SeMO (ZSeMO) isang nakapirming bilang ng mga application ang umiikot, at walang panlabas na independiyenteng mapagkukunan. Batay sa pisikal na pagsasaalang-alang, sa ZSeM Tungkol sa panlabas na arko ay napili, kung saan ito ay minarkahan pseudo-zero isang punto na may kaugnayan sa kung aling mga katangian ng timing ang maaaring masukat.
pinagsama-sama ang network ay isang network kung saan ang isang tiyak na bilang ng mga application ay patuloy na umiikot at may mga application na nagmumula sa mga panlabas na independiyenteng mapagkukunan.
SA homogenous ang mga aplikasyon ng parehong klase ay umiikot sa network. At, sa kabaligtaran, sa magkakaiba ang network ay maaaring maglaman ng mga aplikasyon ng ilang mga klase. Ang mga application ay nabibilang sa iba't ibang klase kung naiiba ang mga ito sa hindi bababa sa isa sa mga sumusunod na katangian:
Ang batas ng pamamahagi ng tagal ng serbisyo sa mga node;
Mga Priyoridad;
Mga Ruta (mga landas ng paggalaw ng mga kahilingan sa network).
SA exponential Ang mga network ng tagal ng serbisyo sa lahat ng node ay ipinamamahagi ayon sa isang exponential law, at ang mga daloy na pumapasok sa open-loop network ay simple (Poisson). Sa lahat ng iba pang mga kaso ang network ay hindi exponential.
Kung ang priyoridad na serbisyo ay ibinibigay sa hindi bababa sa isang node, kung gayon ito ay - priority net. Ang priyoridad ay isang palatandaan na tumutukoy sa pagkakasunud-sunod ng serbisyo. Kung ang serbisyo ng mga kahilingan sa mga node ay isinasagawa sa pagkakasunud-sunod ng pagtanggap, kung gayon ang naturang network walang priority.
Kaya, tatawagin natin ang exponential SeMO, nakakatugon sa mga kinakailangan:
Mga stream ng input SeMO Poisson;
Sa lahat N SMO ang oras ng serbisyo ng mga kahilingan ay may exponential probability distribution function, at ang mga kahilingan ay sineserbisyuhan sa pagkakasunud-sunod ng pagdating;
Paglipat ng aplikasyon mula sa labasan i ika SMO sa pasukan j- ay isang independiyenteng random na kaganapan na may posibilidad p ij ; p i0- ang posibilidad na umalis ang aplikasyon sa CeMO.
Kung ang mga aplikasyon ay pumasok sa network at iniwan ito, kung gayon ang network ay tinatawag na bukas. Kung ang mga aplikasyon ay hindi pumasok o umalis sa network, ang network ay tinatawag na sarado. Ang bilang ng mga aplikasyon sa isang saradong network ay pare-pareho.
