Mga modelo ng matematika ng pinakasimpleng sistema ng pagpila. Ang pinakasimpleng sistema ng pagpila, mga halimbawa ng paggamit sa paglutas ng mga problema sa ekonomiya

Gawain 1. Ang dispatching console ay tumatanggap ng daloy ng mga kahilingan, na isang pangalawang-order na daloy ng Erlang. Ang intensity ng daloy ng mga aplikasyon ay 6 na aplikasyon kada oras. Kung ang dispatcher ay umalis sa console sa isang random na sandali, pagkatapos ay sa unang susunod na kahilingan ay dapat siyang bumalik sa console. Hanapin ang density ng pamamahagi ng oras ng paghihintay para sa susunod na kahilingan at i-plot ang graph nito. Kalkulahin ang posibilidad na ang dispatcher ay maaaring lumiban mula 10 hanggang 20 minuto. Solusyon. Dahil ang daloy ng Erlang ng pangalawang order ay isang nakatigil na daloy na may limitadong epekto, kung gayon ang formula ng Palm ay may bisa para dito

saan f1(θ)- density ng pamamahagi ng posibilidad para sa oras ng paghihintay ng unang pinakamalapit na kaganapan;
λ - intensity ng daloy;
- pagkakasunud-sunod ng daloy;
(θ) ay ang probability distribution function para sa oras sa pagitan ng dalawang magkatabing kaganapan ng Erlang flow of order (E).
Ito ay kilala na ang distribution function para sa daloy E ay may anyo

. (2)

Ayon sa mga kondisyon ng problema, ang daloy ng mga aplikasyon ay Erlang ng order =2. Pagkatapos mula sa (1) at (2) makuha namin
.
Mula sa huling kaugnayan para sa λ=6 magkakaroon tayo

f1(θ)=3е-6θ(1+6θ), θ≥0. (3)

I-plot natin ang function f1(θ) . Sa θ <0 meron kami f1(θ) =0 . Sa θ =0 , f1(0)=3. Isaalang-alang ang limitasyon

Kapag kinakalkula ang limitasyon para sa pagsisiwalat ng uri ng kalabuan, ginamit ang panuntunang L'Hopital. Batay sa mga resulta ng pananaliksik, bumuo kami ng isang graph ng function f1(θ) (Larawan 1).

Bigyang-pansin natin ang mga sukat ng oras sa teksto ng gawain: para sa intensity, ito ay mga aplikasyon bawat oras, para sa oras, minuto. Lumipat tayo sa isang yunit ng oras: 10 minuto = 1/6 oras, 20 minuto = 1/3 oras. Para sa mga halagang ito, maaaring kalkulahin ng isa f1(θ) at pinuhin ang likas na katangian ng kurba

Ang mga ordinate na ito ay ipinahiwatig sa graph sa itaas ng kaukulang mga curve point.
Mula sa kurso ng probability theory alam na ang posibilidad ng pagpindot sa isang random variable X sa segment na [α, β] ay katumbas ng numero sa lugar sa ilalim ng probability density curve f(x). Ang lugar na ito ay ipinahayag ng isang tiyak na integral

Samakatuwid, ang nais na posibilidad ay katumbas ng

Ang integral na ito ay madaling makalkula ng mga bahagi kung ilalagay natin
U=1+6θ at dV=e-6θdθ. Pagkatapos dU=6dθ at V= .
Gamit ang formula nakukuha namin

Sagot: ang posibilidad na mawala ang dispatcher mula 10 hanggang 20 minuto ay 0.28.

Gawain 2. Ang display room ay may 5 display. Ang daloy ng mga gumagamit ay ang pinakasimpleng. Ang average na bilang ng mga user na bumibisita sa display room bawat araw ay 140. Ang oras ng pagpoproseso ng impormasyon ng isang user sa isang display ay ipinamamahagi ayon sa isang exponential law at may average na 40 minuto. Tukuyin kung mayroong isang nakatigil na mode ng pagpapatakbo ng bulwagan; ang posibilidad na makita ng user na abala ang lahat ng display; average na bilang ng mga user sa display room; average na bilang ng mga gumagamit sa pila; average na idle display time; ang average na oras na ginugol ng user sa display room. Solusyon. Ang QS na isinasaalang-alang sa problema ay kabilang sa klase ng mga multichannel system na may walang limitasyong pila. Bilang ng mga channel =5. Hanapin natin ang λ-intensity ng daloy ng mga application: kung saan (oras) - ang average na oras sa pagitan ng dalawang magkasunod na application ng papasok na daloy ng mga user. Pagkatapos gumagamit/oras

Hanapin natin - ang intensity ng daloy ng serbisyo: , kung saan M[T service]=40 min=0.67 oras - average na oras ng serbisyo para sa isang user na may isang display,

pagkatapos gumagamit/oras

Kaya, ang classifier ng sistemang ito ay may anyong CMO (5, ∞; 5.85; 1.49).
Kalkulahin ang QS load factor . Ito ay kilala na para sa isang QS ng klase na ito, ang isang nakatigil na mode ay umiiral kung ang ratio ng system load factor sa bilang ng mga channel ay mas mababa sa isa. Ang paghahanap ng relasyong ito
.
Samakatuwid, umiiral ang nakatigil na rehimen. Ang paglilimita sa pamamahagi ng probabilidad ng estado ay kinakalkula ng mga formula

Since =5, meron na tayo

Kalkulahin natin ang P* - ang posibilidad na makita ng user na abala ang lahat ng display. Malinaw, ito ay katumbas ng kabuuan ng mga probabilidad ng naturang mga kaganapan: lahat ng mga pagpapakita ay abala, walang pila (p5); lahat ay nagpapakita ng abala, isang user sa pila (p6); lahat ng display ay abala, dalawang user ang nakapila (p7), at iba pa. Dahil para sa isang kumpletong pangkat ng mga kaganapan ang kabuuan ng mga probabilidad ng mga kaganapang ito ay katumbas ng isa, kung gayon ang pagkakapantay-pantay

P * \u003d p5 + p6 + p7 + ... \u003d 1 - ro - p1 - p2 - p3 - p4.

Hanapin natin ang mga probabilidad na ito: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
Ang pagkuha ng karaniwang kadahilanan mula sa mga bracket, nakukuha namin
P*=1-0.0148*(1+3.93+7.72+10.12+9.94)=1-0.014*32.71=1-0.46=0.54.
Gumagamit ng mga formula upang kalkulahin ang mga tagapagpahiwatig ng pagganap? hanapin:

• 1. average na bilang ng mga user sa pila

2. average na bilang ng mga user sa display room

3. Average na Oras ng Paghihintay sa Libreng Display

4. average na oras na ginugol ng user sa display room

Sagot: ang nakatigil na mode ng pagpapatakbo ng display room ay umiiral at nailalarawan sa pamamagitan ng mga sumusunod na tagapagpahiwatig R*=0.54; gumagamit; gumagamit; ; .

Gawain 3. Ang isang nakatigil na daloy ng Poisson ng mga kahilingan ay pumapasok sa isang two-channel queuing system (QS) na may mga pagkabigo. Ang oras sa pagitan ng pagdating ng dalawang magkasunod na kahilingan ay ibinahagi ayon sa exponential law na may parameter na λ=5 na kahilingan kada minuto. Ang tagal ng pagseserbisyo sa bawat kahilingan ay 0.5 min. Gamit ang pamamaraang Monte Carlo, hanapin ang average na bilang ng mga naserbisyuhan na kahilingan sa loob ng 4 na minuto. Pahiwatig: magsagawa ng tatlong pagsubok. Solusyon. Ilarawan natin ang istatistikal na pagmomodelo ng pagpapatakbo ng isang ibinigay na QS gamit ang mga diagram ng oras. Ipakilala natin ang sumusunod na notasyon para sa mga time axes:
Vx- papasok na daloy ng mga aplikasyon, dito ti- sandali ng pagtanggap ng mga aplikasyon; Ti- mga agwat ng oras sa pagitan ng dalawang magkasunod na aplikasyon. Obvious naman yun ti=ti-1 +Ti.
K1 - ang unang channel ng serbisyo;
K2-segundong channel ng serbisyo; dito, ang mga makapal na linya sa axis ng oras ay kumakatawan sa mga agwat ng abala ng channel. Kung ang parehong mga channel ay libre, ang kahilingan ay magiging serbisyo sa channel K1, kung ito ay abala, ang kahilingan ay sineserbisyuhan ng channel K2.
Kung abala ang parehong channel, iiwan ng kahilingan ang QS na hindi naihatid.
Out OB - papalabas na daloy ng mga kahilingan sa serbisyo.
Ang Out PT ay ang papalabas na daloy ng mga nawalang kahilingan dahil sa mga pagkabigo ng QS (parehong abala ang mga channel).
Nagpapatuloy ang pagsusuri sa istatistika para sa isang agwat ng oras. Obviously, kahit anong overtime tmax nangangailangan ng pag-drop sa kahilingan sa papalabas na stream Out PT. Kaya sa fig. 3 application No. 10, na pumasok sa system noong panahong iyon t10, ay walang oras upang ihain hanggang sa sandaling ito tmax, dahil t10+Tmont.>tmax. Samakatuwid, hindi ito tinatanggap ng libreng channel na K1 para sa serbisyo at na-reset sa Out PT, na tumatanggap ng pagtanggi.

kanin. 3

Mula sa mga timing diagram, makikita na kailangang matutunan kung paano magmodelo ng mga agwat Ti. Inilapat namin ang paraan ng mga inverse function. Dahil ang random variable Ti ibinahagi ayon sa exponential law na may parameter λ =5, kung gayon ang density ng pamamahagi ay may anyo f(τ)=5е-5τ. Pagkatapos ang halaga F(Ti) ang probability distribution function ay tinutukoy ng integral

.

Ito ay kilala na ang hanay ng mga function ng pamamahagi F(T) may hiwa. Pumili kami ng isang numero mula sa talahanayan ng mga random na numero at tinutukoy Ti mula sa pagkakapantay - pantay , kung saan . Gayunpaman, kung . Samakatuwid, maaari kang agad na makakuha ng mga pagpapatupad mula sa talahanayan ng mga random na numero. Dahil dito,
e-5Ti= ri, o -5Ti= lnri, saan . Ito ay maginhawa upang ipasok ang mga resulta ng mga kalkulasyon sa isang talahanayan.
Para sa pagsubok No. 1, ang mga random na numero ay kinuha mula sa Appendix 2, simula sa unang numero ng unang linya. Ang karagdagang sampling ay isinagawa sa pamamagitan ng mga hilera. Gumawa tayo ng dalawa pang pagsubok.
Bigyang-pansin ang pagpili ng mga random na numero mula sa talahanayan ng Appendix 2, kung sa pagsubok No. 1 ang huling random na numero para sa aplikasyon No. 16 ay 0.37 (ang unang random na numero sa pangalawang linya), pagkatapos ay ang pagsubok No. 2 ay nagsisimula sa ang susunod na random na numero 0.54 . Ang pagsubok #2 ay naglalaman ng huling random na numero 0.53 (ang ikalimang numero sa ikatlong hilera). Samakatuwid, ang ikatlong pagsubok ay magsisimula sa bilang na 0.19. Sa pangkalahatan, sa loob ng parehong serye ng mga pagsubok, ang mga random na numero mula sa talahanayan ay pinili nang walang mga puwang at pagpapasok sa isang tiyak na pagkakasunud-sunod, halimbawa, sa mga hilera.

Talahanayan 1. PAGSUSULIT #1

Application No. i	Sl. numero ri		-ln ri Ti	Ang sandali ng pagtanggap ng aplikasyon ti=ti-1+Ti	Oras ng pagtatapos ng serbisyo. ti+0.50		Counter ng aplikasyon
					K1

Talahanayan 2 PAGSUSULIT #2

Application No. i	Sl. numero ri		-ln ri Ti	Ang sandali ng pagtanggap ng aplikasyon ti=ti-1+Ti	Oras ng pagtatapos ng serbisyo. ti+0.50		Counter ng aplikasyon

Talahanayan #3 PAGSUSULIT #3

Application No. i		Sl. numero ri		-ln ri Ti	Ang sandali ng pagtanggap ng aplikasyon ti=ti-1+Ti	Oras ng pagtatapos ng serbisyo. ti+0.50		Counter ng aplikasyon
						K1

Kaya, ayon sa mga resulta ng tatlong pagsubok, ang bilang ng mga serbisyong aplikasyon ay ayon sa pagkakabanggit: x1=9, x2=9, x3=8. Hanapin ang average na bilang ng mga kahilingan sa serbisyo:

Sagot: ang average na bilang ng mga application na inihatid ng QS sa 4 na minuto ay 8.6(6).

Mga layunin

Ang mga pundasyon ng kaalaman sa pagpila, na kung minsan ay tinutukoy bilang teorya ng pagpila o teorya ng pagpila, ay bumubuo ng isang mahalagang bahagi ng teorya ng pamamahala ng produksiyon. Karaniwan ang mga pila. Maaari silang magsuot ng uniporme habang naghihintay ng pagkukumpuni ng sasakyan sa isang service center ng sasakyan o mga mag-aaral na naghihintay ng konsultasyon sa isang propesor. Ang talahanayan ay naglilista ng ilang mga halimbawa ng pagpila sa mga sistema ng pagpila:

Ang mga modelo ng queue (pati na rin ang linear programming, mga modelo ng pamamahala ng imbentaryo, mga pamamaraan ng pagsusuri sa network para sa mga proyekto) ay ginagamit sa larangan ng pamamahala ng produksyon ng materyal at sa sektor ng serbisyo. Ang pagsusuri sa mga pila sa mga tuntunin ng haba ng pila, average na oras ng paghihintay, average na oras ng serbisyo, at iba pang mga kadahilanan ay nakakatulong sa amin na mas maunawaan kung paano nakaayos ang isang sistema ng serbisyo. Ang paghihintay para sa isang pasyente sa waiting room ng isang doktor at paghihintay para sa isang sirang drill na ayusin sa isang repair shop ay may maraming pagkakatulad sa mga tuntunin ng pamamahala ng serbisyo. Ang parehong mga proseso ay gumagamit ng mga mapagkukunan ng tao at kagamitan upang matugunan ang mga pangangailangan ng customer.

Ang isang propesyonal na tagapamahala, na kumukuha ng pagpapabuti ng sistema ng pagpila, ay sinusuri ang mga pagbabagong lalabas sa mga gastos sa pagpapatakbo ng system at sa mga gastos na nauugnay sa paghihintay sa mga customer. Maaari kang kumuha ng malaking bilang ng mga empleyado na mabilis na maglilingkod sa mga customer. Halimbawa, maaaring bawasan ng isang administrator ng supermarket ang mga pila sa mga cash register sa pamamagitan ng pagtaas ng bilang ng mga nagbebenta at cashier sa mga oras ng kasiyahan. Maaaring kasangkot ang mga karagdagang empleyado upang magtrabaho sa mga cash desk ng mga bangko o paliparan sa mga oras ng kasiyahan. Gayunpaman, ang pagbawas sa oras ng paghihintay ay kadalasang nauugnay sa mga gastos sa paglikha at pagbibigay ng mga trabaho, kasama ang pagbabayad ng karagdagang kawani. Ang mga gastos na ito ay maaaring maging makabuluhan.

Makakatipid ka sa mga gastos sa paggawa. Ngunit pagkatapos ay ang kliyente ay maaaring hindi maghintay para sa serbisyo o mawalan ng pagnanais na bumalik muli. Sa huling kaso, ang sistema ng pagpila ay magkakaroon ng mga pagkalugi, na matatawag na mga gastos sa paghihintay. Sa ilang mga sistema ng serbisyo, tulad ng mga ambulansya, ang mga gastos na nauugnay sa mahabang oras ng paghihintay ay maaaring napakataas. Ang pangunahing prinsipyong pang-ekonomiya ng pagpapabuti ng mga sistema ng pagpila ay upang tantiyahin ang kabuuang inaasahang gastos, kabilang ang mga gastos sa serbisyo at ang mga pagkalugi na natamo ng system bilang resulta ng paghihintay sa kliyente.

Pagkatapos mong makumpleto ang mga gawain sa kabanatang ito, magagawa mong tukuyin at gamitin ang mga sumusunod na konsepto para sa pagsusuri sa ekonomiya:

Sistema ng pagpila;

Lumiko;

Ang rate ng pagtanggap ng mga aplikasyon;

Ang bilis ng serbisyo;

Ang average na oras na ginugugol ng application sa pila;

Average na haba ng pila;

Ang average na oras na ginugugol ng application sa sistema ng serbisyo;

Average na bilang ng mga kliyente sa sistema ng serbisyo;

Mga gastos sa paggana ng sistema ng serbisyo;

Mga gastos sa paghihintay.

Mga modelo

Mga tampok ng pag-uuri ng mga sistema ng pagpila.

Sa mga sistema ng pagpila, mayroong tatlong pangunahing yugto na pinagdadaanan ng bawat aplikasyon:

1) ang hitsura ng isang application sa pasukan sa system;

2) pagpasa sa pila;

3) ang proseso ng serbisyo, pagkatapos kung saan ang application ay umalis sa system.

Sa bawat yugto, ginagamit ang ilang mga katangian, na dapat talakayin bago bumuo ng mga modelo ng matematika.

Mga Detalye ng Input:

1) ang bilang ng mga aplikasyon sa pasukan (laki ng populasyon);

2) ang mode ng pagtanggap ng mga aplikasyon sa sistema ng serbisyo;

3) pag-uugali ng customer.

Ang bilang ng mga aplikasyon sa pasukan. Ang bilang ng mga potensyal na aplikasyon (laki ng populasyon) ay maaaring ituring na walang hanggan (walang limitasyong populasyon) o may hangganan (limitadong populasyon). Kung ang bilang ng mga customer na pumapasok sa system mula sa simula ng proseso ng serbisyo hanggang sa anumang naibigay na punto sa oras ay maliit na bahagi lamang ng potensyal na bilang ng mga customer, ang input na populasyon ay ituturing bilang Walang limitasyon. Mga halimbawa ng hindi pinaghihigpitang populasyon: mga sasakyang dumadaan sa mga checkpoint sa mga expressway, mga mamimili sa isang supermarket, atbp. Sa karamihan ng mga modelo ng mga pila sa pagpasok, hindi pinaghihigpitang populasyon ang isinasaalang-alang.

Kung ang bilang ng mga customer na maaaring pumasok sa system ay maihahambing sa bilang ng mga customer na nasa queuing system, ang populasyon ay isinasaalang-alang Limitado. Halimbawa ng bounded population: Mga computer na pagmamay-ari ng isang partikular na organisasyon na sineserbisyuhan ng isang repair shop.

Ang mode ng pagtanggap ng mga aplikasyon sa sistema ng serbisyo. Ang mga aplikasyon ay maaaring pumasok sa sistema ng serbisyo ayon sa isang tiyak na iskedyul (halimbawa, isang pasyente sa dentista tuwing 15 minuto, isang kotse sa linya ng pagpupulong bawat 20 minuto) o random. Bilang ng mga pagbisita ng customer random, kung sila ay independyente sa isa't isa at eksaktong hindi mahuhulaan. Kadalasan sa mga problema sa pagpila, ang bilang ng mga paglitaw sa bawat yunit ng oras ay maaaring matantya gamit ang isang Poisson probability distribution. Para sa ibinigay na rate ng pagdating (halimbawa, dalawang customer kada oras o apat na trak kada minuto), ang hiwalay na pamamahagi ng Poisson ay inilalarawan ng sumusunod na formula:

saan P(x) - posibilidad ng pagpasok X mga aplikasyon sa bawat yunit ng oras;

X - ang bilang ng mga aplikasyon sa bawat yunit ng oras;

L ay ang average na bilang ng mga aplikasyon sa bawat yunit ng oras (ang rate ng pagtanggap ng mga aplikasyon);

Ang mga kaukulang probabilidad P(x) ay madaling matukoy gamit ang talahanayan ng pamamahagi ng Poisson. Kung, halimbawa, ang average na rate ng mga papasok na kahilingan ay dalawang kliyente kada oras, kung gayon ang posibilidad na walang mga kahilingan na papasok sa system sa loob ng isang oras ay 0.135, ang posibilidad ng isang kahilingan ay humigit-kumulang 0.27, at dalawa ay humigit-kumulang 0.27 , tatlo. maaaring lumabas ang mga claim na may probabilidad na 0.18, apat na may probabilidad na humigit-kumulang 0.09, at iba pa. Ang posibilidad na 9 o higit pang mga claim ang papasok sa system sa loob ng isang oras ay malapit sa zero.

Sa pagsasagawa, ang mga posibilidad ng paglitaw ng mga aplikasyon, siyempre, ay hindi palaging sumusunod sa pamamahagi ng Poisson (maaaring mayroon silang ibang pamamahagi). Samakatuwid, ang mga paunang pag-aaral ay kinakailangan upang suriin na ang Poisson distribution ay maaaring magsilbi bilang isang mahusay na pagtatantya.

Pag-uugali ng customer. Karamihan sa mga modelo ng queuing ay nakabatay sa pagpapalagay na ang gawi ng customer ay karaniwan, ibig sabihin, ang bawat customer na papasok sa system ay pumila, naghihintay para sa serbisyo, at hindi umaalis sa system hanggang sa ito ay maihatid. Sa madaling salita, ang isang customer (tao o makina) na pumasok sa isang pila ay naghihintay hanggang sa ito ay maihatid, umalis sa pila, at lumipat mula sa isang pila patungo sa isa pa.

Ang buhay ay mas mahirap. Sa pagsasagawa, maaaring umalis ang mga customer sa pila dahil ito ay masyadong mahaba. Ang isa pang sitwasyon ay maaaring lumitaw: ang mga customer ay naghihintay para sa kanilang pagkakataon, ngunit sa ilang kadahilanan ay umalis sila nang hindi naseserbisyuhan. Ang mga kasong ito ay paksa din ng teorya ng queuing, ngunit hindi isinasaalang-alang dito.

Mga katangian ng pila:

2) tuntunin sa serbisyo.

Haba ng pila. Ang haba ay maaaring limitado o hindi. Haba ng pila (pila) Limitado kung sa ilang kadahilanan (halimbawa, dahil sa mga pisikal na limitasyon) hindi ito maaaring tumaas nang walang katiyakan. Kung ang queue ay umabot sa maximum na laki nito, ang susunod na kahilingan sa system ay hindi pinapayagan at ang isang pagkabigo ay magaganap. Haba ng pila Hindi limitado, Kung maaaring mayroong anumang bilang ng mga aplikasyon sa pila. Halimbawa, isang pila ng mga sasakyan sa isang gasolinahan.

tuntunin sa serbisyo. Karamihan sa mga totoong system ay gumagamit ng first-in, first-out na panuntunan. (FIFO- unang pumasok, unang lumabas). Sa ilang mga kaso, tulad ng sa emergency room ng isang ospital, bilang karagdagan sa panuntunang ito, iba't-ibang Mga Priyoridad. Ang isang kritikal na pasyente na may atake sa puso ay malamang na magkakaroon ng priyoridad sa pangangalaga kaysa sa isang pasyente na may sirang daliri. Ang pagkakasunud-sunod kung saan sinimulan ang mga program sa computer ay isa pang halimbawa ng pagbibigay-priyoridad sa serbisyo.

Mga katangian ng proseso ng serbisyo:

1) pagsasaayos ng sistema ng serbisyo (bilang ng mga channel at bilang ng mga yugto ng serbisyo);

2) mode ng pagpapanatili.

Configuration ng system ng serbisyo. Ang mga sistema ng serbisyo ay naiiba sa Ang bilang ng mga channel ng serbisyo. Karaniwan, ang bilang ng mga channel ay maaaring tukuyin bilang ang bilang ng mga kliyente na maaaring ihatid nang sabay-sabay, halimbawa: ang bilang ng mga master sa isang hairdresser. Mga halimbawa iisang channel mga sistema ng serbisyo: isang bangko na may iisang window para sa serbisyo sa customer, o isang restaurant na nagsisilbi sa mga customer sa mga sasakyan. Kung maraming mga window ng serbisyo ay bukas sa bangko, ang kliyente ay naghihintay sa pangkalahatang pila at papalapit sa unang bakanteng window, pagkatapos ay haharapin namin ang Multichannel single phase maintenance system. Karamihan sa mga bangko, pati na rin ang mga post office at air ticket office, ay mga multi-channel service system.

Isa pang tampok - Bilang ng mga yugto(o sunud-sunod na yugto) Mga serbisyo isang kliyente. iisang yugto ay mga ganoong sistema kung saan inihahatid ang kliyente sa isang punto (sa isang lugar ng trabaho), pagkatapos ay umalis sa system. Ang isang car service restaurant kung saan tinatanggap ng waiter ang pera at dinadala ang order sa kotse ay isang halimbawa ng isang single-phase system. Kung sa isang restawran kailangan mong mag-order sa isang lugar, bayaran ito sa isa pa at kumuha ng pagkain sa isang pangatlo, pagkatapos ay haharapin namin ang multiphase(tatlong yugto) sistema ng serbisyo.

Sa fig. Ang 1 ay nagpapakita ng mga sistema ng serbisyo ng iba't ibang mga pagsasaayos.

Mode ng pagpapanatili. Pati na rin ang mode ng pagtanggap ng mga kahilingan, ang mode ng serbisyo ay maaaring mailalarawan sa pamamagitan ng alinman sa pare-pareho o random na oras ng serbisyo. Sa Permanente Ang parehong dami ng oras na ginugugol sa paglilingkod sa bawat customer. Ang sitwasyong ito ay maaaring maobserbahan sa isang awtomatikong paghuhugas ng kotse. Gayunpaman, mas madalas may mga sitwasyon kung kailan ang oras ng serbisyo ay mayroon Random pamamahagi. Sa maraming mga kaso, maaaring ipagpalagay na ang oras ng serbisyo ay sumusunod sa isang exponential distribution na may isang distribution function

F( T ) = P(T< t) =1 – e–tm, kung saan R (T< t) ay ang posibilidad na ang aktwal na oras T ang kahilingan sa serbisyo ay hindi lalampas sa tinukoy na halaga t;

M - ang average na bilang ng mga aplikasyon na inihatid sa bawat yunit ng oras;

E \u003d 2.7182 - ang base ng natural na logarithm.

Mga parameter ng mga modelo ng pila. Sa pagsusuri ng mga sistema ng pagpila, ginagamit ang mga teknikal at pang-ekonomiyang katangian.

Ang mga sumusunod ay ang pinakakaraniwang ginagamit Mga pagtutukoy:

1) ang karaniwang oras na ginugugol ng isang customer sa isang pila;

2) ang average na haba ng pila;

3) ang karaniwang oras na ginugugol ng isang customer sa sistema ng serbisyo (oras ng paghihintay kasama ang oras ng serbisyo);

4) ang average na bilang ng mga kliyente sa sistema ng serbisyo;

5) ang posibilidad na ang sistema ng serbisyo ay magiging idle;

6) ang posibilidad ng isang tiyak na bilang ng mga kliyente sa system.

Among Mga katangiang pang-ekonomiya ang pinakainteresante ay ang mga sumusunod:

1) ang halaga ng paghihintay sa pila;

2) mga gastos sa paghihintay sa sistema;

3) mga gastos sa pagpapanatili.

Mga modelo ng mga sistema ng pagpila. Depende sa kumbinasyon ng mga katangian sa itaas, maaaring isaalang-alang ang iba't ibang mga modelo ng mga sistema ng pagpila.

Dito ay titingnan natin ang ilan sa mga pinakasikat na modelo. Lahat sila ay may mga sumusunod na karaniwang katangian:

A) Poisson distribution ng probabilidad ng pagtanggap ng mga aplikasyon;

B) karaniwang pag-uugali ng customer;

B) tuntunin ng serbisyo FIFO(first come, first served);

D) ang tanging yugto ng serbisyo.

ako. Model A - single-channel queuing system model MM/ 1 s Poisson papasok na daloy ng mga aplikasyon at Exponential oras ng serbisyo.

Ang pinakakaraniwang problema sa pagpila sa isang channel. Sa kasong ito, ang mga customer ay bumubuo ng isang queue sa isang solong service point. Ipagpalagay natin na ang mga sumusunod na kondisyon ay nasiyahan para sa mga sistema ng ganitong uri:

1. Ang mga aplikasyon ay inihahatid sa batayan ng first-come-first-served (FIFO) bukod pa rito, hinihintay ng bawat kliyente ang pila nito hanggang sa dulo, anuman ang haba ng pila.

2. Ang mga pagpapakita ng mga aplikasyon ay mga independiyenteng kaganapan, gayunpaman, ang average na bilang ng mga aplikasyon na dumarating sa bawat yunit ng oras ay hindi nagbabago.

3. Ang proseso ng pagtanggap ng mga aplikasyon ay inilarawan ng pamamahagi ng Poisson, at ang mga aplikasyon ay nagmumula sa isang walang limitasyong hanay.

4. Ang oras ng serbisyo ay inilalarawan ng exponential probability distribution.

5. Ang rate ng serbisyo ay mas mataas kaysa sa rate ng pagtanggap ng mga aplikasyon.

Hayaang l ang bilang ng mga aplikasyon sa bawat yunit ng oras;

Ang M ay ang bilang ng mga kliyenteng pinaglilingkuran bawat yunit ng oras;

P - ang bilang ng mga aplikasyon sa system.

Pagkatapos ang queuing system ay inilalarawan ng mga equation na ibinigay sa ibaba.

Mga formula para sa paglalarawan ng M/M/ system 1:

- average na bilang ng mga kliyente sa system;

Average na oras ng serbisyo bawat kliyente sa system (oras ng paghihintay kasama ang oras ng serbisyo);

Average na bilang ng mga kliyente sa pila;

Average na oras ng paghihintay para sa isang customer sa isang queue;

Mga katangian ng system load (ang proporsyon ng oras kung kailan abala ang system sa pagseserbisyo);

Ang posibilidad ng kawalan ng mga aplikasyon sa system;

Ang posibilidad na naglalaman ang system ng higit sa K mga aplikasyon.

II. Model B - multichannel na sistema ng serbisyo M/M/S. Sa isang multichannel system, dalawa o higit pang channel ang bukas para sa serbisyo. Ipinapalagay na naghihintay ang mga kliyente sa pangkalahatang pila at mag-aplay sa unang libreng channel ng serbisyo.

Ang isang halimbawa ng tulad ng isang multi-channel na single-phase system ay makikita sa maraming mga bangko: mula sa pangkalahatang pila, ang mga customer ay pumunta sa unang libreng window para sa serbisyo.

Sa isang multichannel system, ang daloy ng mga kahilingan ay napapailalim sa Poisson batas, at oras ng serbisyo - Exponential. Unang dumating ang unang inihain, at lahat ng mga channel ng serbisyo ay gumagana sa parehong bilis. Mga formula na naglalarawan sa modelo SA, medyo mahirap gamitin. Upang kalkulahin ang mga parameter ng isang multi-channel queuing system, ito ay maginhawa upang gamitin ang naaangkop na software.

Ang oras na ang aplikasyon ay nasa pila;

Oras na ginugol ng application sa system.

III. Modelo C- modelo na may pare-parehong oras ng serbisyo M/D/ 1.

Ang ilang mga sistema ay mayroon permanente, kaysa sa exponentially distributed service time. Sa ganitong mga sistema, ang mga customer ay pinaglilingkuran para sa isang nakapirming yugto ng panahon, tulad ng sa isang awtomatikong paghuhugas ng kotse. Para sa Modelo MULA SA Sa patuloy na rate ng mga halaga ng serbisyo Lq at wq Kalahati ng kaukulang mga halaga sa modelo PERO, na may variable na rate ng serbisyo.

Mga formula na naglalarawan sa modelo C:

- average na haba ng pila;

- average na oras ng paghihintay sa pila;

Average na bilang ng mga kliyente sa system;

Average na oras ng paghihintay sa system.

IV. Modelo D - modelo na may limitadong populasyon.

Kung ang bilang ng mga potensyal na customer ng sistema ng serbisyo limitado, nakikipag-usap kami sa isang espesyal na modelo. Ang ganitong gawain ay maaaring lumitaw, halimbawa, pagdating sa pagpapanatili ng kagamitan ng isang pabrika na may limang makina.

Ang kakaiba ng modelong ito kung ihahambing sa tatlong isinasaalang-alang na mas maaga ay mayroon Pagkakaisa sa pagitan ng haba ng pila at ang rate ng pagtanggap ng mga aplikasyon.

v. Modelo E - limitadong modelo ng pila. Ang modelo ay naiiba sa mga nauna dahil ang bilang ng mga lugar sa pila Limitado. Sa kasong ito, ang kahilingan, na dumating sa system kapag ang lahat ng mga channel at lugar sa pila ay inookupahan, ay iniiwan ang system na hindi naihatid, ibig sabihin, ay tinanggihan.

Bilang isang espesyal na kaso ng limitadong modelo ng pila, maaaring isaalang-alang ng isa modelo ng pagkabigo, kung ang bilang ng mga lugar sa pila ay nabawasan sa zero.

Ang mga paghahambing na katangian ng iba't ibang modelo ng mga sistema ng pagpila ay ibinibigay sa sumusunod na talahanayan.

Mathematical (abstract) object, ang mga elemento nito ay (Fig. 2.1):

• input (papasok) na daloy ng mga aplikasyon (mga kinakailangan) para sa serbisyo;
• mga aparato ng serbisyo (mga channel);
• isang pila ng mga aplikasyon na naghihintay ng serbisyo;
• output (papalabas) daloy ng mga kahilingan sa serbisyo;
• ang daloy ng mga kahilingan para sa aftercare pagkatapos ng pagkaantala ng serbisyo;
• daloy ng mga hindi naibigay na kahilingan.

Kahilingan(kahilingan, kinakailangan, tawag, kliyente, mensahe, pakete) - isang bagay na pumapasok sa QS at nangangailangan ng serbisyo sa device. Ang hanay ng mga magkakasunod na aplikasyon na ibinahagi sa anyo ng oras daloy ng input ng mga application.

kanin. 2.1.

aparato ng serbisyo(aparato, device, channel, linya, tool, kotse, router, atbp.) - QS element, ang layunin nito ay magserbisyo ng mga kahilingan.

Serbisyo- pagkaantala ng kahilingan sa device ng serbisyo nang ilang panahon.

Tagal ng serbisyo- oras ng pagkaantala (serbisyo) ng application sa device.

Storage device(buffer, input buffer, output buffer) - isang hanay ng mga lugar para sa paghihintay para sa mga application sa harap ng paghahatid ng aparato. Bilang ng mga lugar na naghihintay - kapasidad ng imbakan.

Ang isang aplikasyon na natanggap ng CMO ay maaaring nasa dalawang estado:

• 1) serbisyo(sa device);
• 2) mga inaasahan(sa accumulator), kung abala ang lahat ng device sa pagseserbisyo sa iba pang kahilingan.

Ang mga claim sa accumulator at naghihintay na form ng serbisyo lumiko mga aplikasyon. Ang bilang ng mga aplikasyon sa nagtitipon na naghihintay ng serbisyo - haba ng pila.

Buffering disiplina(disiplina sa pagpila) - ang panuntunan para sa pagpasok ng mga papasok na aplikasyon sa drive (buffer).

Disiplina sa paglilingkod- ang panuntunan para sa pagpili ng mga kahilingan mula sa pila para sa serbisyo sa device.

Ang prioridad- ang preemptive right (upang makuha ang mga mapagkukunan) upang makapasok sa accumulator o pumili mula sa queue para sa servicing sa mga application ng device ng isang klase na may kaugnayan sa mga application ng iba pang mga klase.

Maraming mga queuing system na naiiba sa istruktura at functional na organisasyon. Kasabay nito, ang pagbuo ng mga analytical na pamamaraan para sa pagkalkula ng mga tagapagpahiwatig ng pagganap ng QS sa maraming mga kaso ay nagsasangkot ng isang bilang ng mga paghihigpit at pagpapalagay na nagpapaliit sa hanay ng mga QS na pinag-aaralan. kaya lang walang pangkalahatang analytical na modelo para sa isang arbitraryong kumplikadong istraktura QS.

Ang QS analytical model ay isang hanay ng mga equation o formula na nagbibigay-daan sa pagtukoy ng mga probabilidad ng mga estado ng system sa kurso ng operasyon nito at mga tagapagpahiwatig ng pagganap batay sa mga kilalang parameter ng papasok na daloy at mga channel ng serbisyo, buffering at mga disiplina ng serbisyo.

Ang analytical modelling ng QS ay lubos na pinapadali kung ang mga prosesong nagaganap sa QS ay Markovian (ang mga daloy ng mga application ay ang pinakasimpleng, ang mga oras ng serbisyo ay ipinamamahagi nang exponentially). Sa kasong ito, ang lahat ng mga proseso sa QS ay maaaring ilarawan sa pamamagitan ng mga ordinaryong differential equation, at sa limitadong kaso - para sa mga nakatigil na estado - sa pamamagitan ng mga linear algebraic equation at, nang malutas ang mga ito sa pamamagitan ng anumang mga pamamaraan na magagamit sa mathematical software packages, matukoy ang napiling mga tagapagpahiwatig ng pagganap .

Sa mga IM system, kapag nagpapatupad ng QS, tinatanggap ang mga sumusunod na paghihigpit at pagpapalagay:

• application na ipinasok sa system kaagad nahuhulog sa serbisyo kung walang mga kahilingan sa pila at ang aparato ay libre;
• sa device para sa pagpapanatili sa anumang oras ay maaari lamang isa kahilingan;
• pagkatapos ng pagtatapos ng serbisyo ng anumang kahilingan sa device, ang susunod na kahilingan ay pipiliin mula sa queue para sa agad na serbisyo, ibig sabihin, ang device hindi idle kung mayroong kahit isang aplikasyon sa pila;
• ang pagtanggap ng mga aplikasyon sa QS at ang tagal ng kanilang serbisyo ay hindi nakasalalay sa bilang ng mga aplikasyon na nasa system na, o sa anumang iba pang mga kadahilanan;
• ang tagal ng mga kahilingan sa paglilingkod ay hindi nakadepende sa tindi ng mga kahilingang pumapasok sa system.

Pag-isipan natin ang ilang elemento ng QS nang mas detalyado.

Input (papasok) na daloy ng mga application. Ang daloy ng mga pangyayari ay tinatawag na pagkakasunud-sunod ng magkakatulad na mga pangyayari na sumusunod sa isa't isa at nagaganap sa ilan, sa pangkalahatan, random puntos sa oras. Kung ang kaganapan ay binubuo sa hitsura ng mga claim, mayroon kami daloy ng aplikasyon. Upang ilarawan ang daloy ng mga aplikasyon sa pangkalahatang kaso, kinakailangan upang itakda ang mga agwat ng oras t = t k - t k-1 sa pagitan ng mga katabing sandali t k _ k at t k pagtanggap ng mga application na may mga serial number sa - 1 at sa ayon sa pagkakabanggit (sa - 1, 2, ...; t 0 - 0 - paunang sandali ng oras).

Ang pangunahing katangian ng daloy ng aplikasyon ay nito X intensity- ang average na bilang ng mga application na dumarating sa QS input bawat yunit ng oras. Halaga t = 1/X tumutukoy ang average na agwat ng oras sa pagitan ng dalawang magkasunod na order.

Ang daloy ay tinatawag deterministiko kung agwat ng oras t sa sa pagitan ng mga katabing application ay tumatagal ng ilang mga pre-known value. Kung ang mga pagitan ay pareho (x sa= t para sa lahat k = 1, 2, ...), pagkatapos ay tinatawag ang stream regular. Para sa kumpletong paglalarawan ng regular na daloy ng mga kahilingan, sapat na upang itakda ang intensity ng daloy X o ang halaga ng pagitan t = 1/X.

Isang stream kung saan ang mga pagitan ng oras x k sa pagitan ng mga katabing application ay mga random na variable, na tinatawag random. Para sa kumpletong paglalarawan ng isang random na daloy ng mga aplikasyon sa pangkalahatang kaso, kinakailangang itakda ang mga batas sa pamamahagi F fc (x fc) para sa bawat agwat ng oras. x k, k = 1,2,....

Random na stream kung saan ang lahat ng agwat ng oras x b x 2,... sa pagitan ng magkakasunod na mga customer ay mga independiyenteng random na variable na inilarawan ng mga function ng pamamahagi FjCij), F 2 (x 2), ... ayon sa pagkakabanggit, ay tinatawag na daloy na may limitadong epekto.

Ang random na stream ay tinatawag paulit-ulit, kung lahat ng mga pagitan ng oras xb t 2 , ... ibinahagi sa pagitan ng mga aplikasyon sa ilalim ng parehong batas F(t). Mayroong maraming mga paulit-ulit na stream. Ang bawat batas sa pamamahagi ay bumubuo ng sarili nitong paulit-ulit na daloy. Ang mga umuulit na stream ay kilala rin bilang mga Palm stream.

Kung ang tindi X at ang batas sa pamamahagi F(t) ng mga agwat sa pagitan ng magkakasunod na kahilingan ay hindi nagbabago sa paglipas ng panahon, kung gayon ang daloy ng mga kahilingan ay tinatawag nakatigil Kung hindi, ang daloy ng aplikasyon ay hindi nakatigil.

Kung sa bawat sandali ng panahon t k isang customer lamang ang maaaring lumitaw sa input ng QS, pagkatapos ay tinawag ang daloy ng mga customer karaniwan. Kung higit sa isang application ang maaaring lumabas anumang oras, ang daloy ng mga application ay pambihira, o pangkat.

Ang daloy ng mga kahilingan ay tinatawag na daloy walang epekto, kung natanggap ang mga aplikasyon hindi alintana mula sa isa't isa, i.e. ang sandali ng pagtanggap ng susunod na aplikasyon ay hindi nakasalalay sa kung kailan at kung gaano karaming mga aplikasyon ang natanggap bago ang sandaling ito.

Ang isang nakatigil na ordinaryong daloy na walang epekto ay tinatawag ang pinakasimple.

Ang mga pagitan ng oras t sa pagitan ng mga kahilingan sa pinakasimpleng daloy ay ipinamamahagi ayon sa exponential (huwaran) batas: na may function ng pamamahagi F(t) = 1 - e~ m; density ng pamamahagi/(f) = Heh~"l, saan X > 0 - parameter ng pamamahagi - ang intensity ng daloy ng mga application.

Ang pinakasimpleng daloy ay madalas na tinatawag Poisson. Ang pangalan ay nagmula sa katotohanan na para sa daloy na ito ang posibilidad na P fc (At) ng paglitaw nang eksakto sa ang mga kahilingan para sa isang tiyak na agwat ng oras Sa ay tinutukoy Batas ni Poisson:

Dapat pansinin na ang daloy ng Poisson, hindi katulad ng pinakasimpleng isa, ay maaaring:

• nakatigil, kung intensity X hindi nagbabago sa paglipas ng panahon;
• hindi nakatigil, kung ang daloy ng rate ay depende sa oras: X= >.(t).

Kasabay nito, ang pinakasimpleng daloy, sa pamamagitan ng kahulugan, ay palaging nakatigil.

Ang mga analytical na pag-aaral ng mga modelo ng queuing ay madalas na isinasagawa sa ilalim ng pagpapalagay ng pinakasimpleng daloy ng mga kahilingan, na dahil sa isang bilang ng mga kapansin-pansin na tampok na likas dito.

1. Pagsusuma (unification) ng mga daloy. Ang pinakasimpleng daloy sa teorya ng QS ay katulad ng normal na batas sa pamamahagi sa teorya ng posibilidad: ang paglipat sa limitasyon para sa isang daloy na ang kabuuan ng mga daloy na may mga arbitrary na katangian na may walang katapusang pagtaas sa bilang ng mga termino at pagbaba sa kanilang intensity ay humahantong. sa pinakasimpleng daloy.

Sum N independiyenteng nakatigil na ordinaryong daloy na may mga intensidad x x x 2 ,..., XN bumubuo ng pinakasimpleng daloy na may intensity

X=Y,^i sa kondisyon na ang mga idinagdag na daloy ay may higit o

mas kaunting epekto sa kabuuang daloy. Sa pagsasagawa, ang kabuuang daloy ay malapit sa pinakasimpleng sa N > 5. Kaya kapag nagsusuma ng mga independiyenteng pinakasimpleng daloy, ang kabuuang daloy ang magiging pinakasimple para sa anumang halaga N.

• 2. Probabilistic rarefaction ng daloy. probabilistiko(ngunit hindi deterministiko) rarefaction ang pinakasimpleng daloy mga application, kung saan ang anumang aplikasyon ay random na may ilang posibilidad R ay hindi kasama sa daloy hindi alintana kung ang iba pang mga application ay hindi kasama o hindi, ay humahantong sa pagbuo ang pinakasimpleng daloy may intensity X* = pX, saan X- intensity ng paunang daloy. Ang daloy ng mga ibinukod na application na may intensity X** = (1 - p)X- masyadong protozoan daloy.
• 3. Kahusayan. Kung ang mga channel sa paghahatid (mga device) ay idinisenyo para sa pinakasimpleng daloy ng mga kahilingan na may intensity x, pagkatapos ang paglilingkod sa iba pang mga uri ng daloy (na may parehong intensity) ay bibigyan ng hindi bababa sa kahusayan.
• 4. pagiging simple. Ang pagpapalagay ng pinakasimpleng daloy ng mga application ay nagbibigay-daan para sa maraming mga modelo ng matematika na makuha sa isang tahasang anyo ang pagtitiwala ng mga tagapagpahiwatig ng QS sa mga parameter. Ang pinakamalaking bilang ng mga analytical na resulta ay nakuha para sa pinakasimpleng daloy ng mga kahilingan.

Ang pagsusuri ng mga modelo na may mga daloy ng aplikasyon na iba sa pinakasimpleng mga ito ay kadalasang nagpapalubha sa mga kalkulasyon sa matematika at hindi palaging nagbibigay-daan sa pagkuha ng isang tahasang analytical na solusyon. Ang "pinakasimpleng" daloy ay nakuha ang pangalan nito nang tumpak dahil sa tampok na ito.

Maaaring may iba't ibang karapatan ang mga aplikasyon para simulan ang serbisyo. Sa kasong ito, ang mga aplikasyon ay sinasabing magkakaiba. Ang mga bentahe ng ilang daloy ng mga aplikasyon sa iba sa simula ng serbisyo ay itinakda ng mga priyoridad.

Ang isang mahalagang katangian ng input stream ay ang koepisyent ng pagkakaiba-iba

kung saan t int - mathematical na inaasahan ng haba ng agwat; tungkol sa- standard deviation ng haba ng interval x int (random variable) .

Para sa pinakasimpleng daloy (a = -, m = -) mayroon kaming v = 1. Para sa karamihan

totoong daloy 0

Mga channel ng serbisyo (mga device). Ang pangunahing katangian ng channel ay ang tagal ng serbisyo.

Tagal ng serbisyo- ang oras na ginugol ng application sa device - sa pangkalahatang kaso, random ang value. Sa kaso ng hindi pare-parehong pagkarga ng QS, ang mga oras ng serbisyo para sa mga kahilingan ng iba't ibang klase ay maaaring mag-iba ayon sa mga batas sa pamamahagi o sa pamamagitan lamang ng mga average na halaga. Sa kasong ito, karaniwang ipinapalagay na ang mga oras ng serbisyo para sa mga kahilingan ng bawat klase ay independyente.

Kadalasan, ipinapalagay ng mga practitioner na ang tagal ng mga kahilingan sa paglilingkod ay naipamahagi na batas ng exponential na lubos na pinapasimple ang analytical kalkulasyon. Ito ay dahil sa ang katunayan na ang mga prosesong nagaganap sa mga system na may exponential distribution ng mga agwat ng oras ay Markov mga proseso:

saan c - intensity ng serbisyo, dito p = _--; t 0 bsl - matematika-

oras ng paghihintay para sa serbisyo.

Bilang karagdagan sa exponential distribution, mayroong Erlang /c-distributions, hyperexponential distributions, triangular distributions, at ilang iba pa. Hindi tayo dapat malito nito, dahil ipinapakita na ang halaga ng pamantayan sa kahusayan ng QS ay nakadepende nang kaunti sa anyo ng batas sa pamamahagi ng oras ng serbisyo.

Sa pag-aaral ng QS, ang kakanyahan ng serbisyo, ang kalidad ng serbisyo, ay hindi isinasaalang-alang.

Ang mga channel ay maaaring ganap na maaasahan mga. huwag mabigo. Bagkus, maaari itong tanggapin sa pag-aaral. Maaaring mayroon ang mga channel tunay na pagiging maaasahan. Sa kasong ito, ang modelo ng QS ay mas kumplikado.

Ang kahusayan ng QS ay nakasalalay hindi lamang sa mga parameter ng mga stream ng input at mga channel ng serbisyo, kundi pati na rin sa pagkakasunud-sunod kung saan sineserbisyuhan ang mga papasok na kahilingan, i.e. mula sa mga paraan upang pamahalaan ang daloy ng mga application kapag pumasok sila sa system at ipinadala para sa serbisyo.

Ang mga paraan upang pamahalaan ang daloy ng mga aplikasyon ay tinutukoy ng mga disiplina:

• buffering;
• serbisyo.

Ang mga disiplina sa buffering at pagpapanatili ay maaaring uriin ayon sa mga sumusunod na pamantayan:

• pagkakaroon ng mga priyoridad sa pagitan ng mga aplikasyon ng iba't ibang klase;
• isang paraan para sa pagtulak ng mga aplikasyon sa labas ng pila (para sa pag-buffer ng mga disiplina) at pagtatalaga ng mga kahilingan sa serbisyo (para sa mga disiplina sa serbisyo);
• isang panuntunan para sa pag-preempting o pagpili ng mga kahilingan sa serbisyo;
• kakayahang baguhin ang mga priyoridad.

Ang isang variant ng pag-uuri ng mga buffering disciplines (queuing) alinsunod sa mga nakalistang feature ay ipinapakita sa fig. 2.2.

Depende sa pagkakaroon o kakulangan ng mga priyoridad sa pagitan ng mga aplikasyon ng iba't ibang klase, ang lahat ng buffering disciplines ay maaaring hatiin sa dalawang grupo: non-priority at priority.

Sa pamamagitan ng paraan ng pagtulak ng mga application palabas ng storage ang mga sumusunod na klase ng buffering disciplines ay maaaring makilala:

• nang walang pagsisiksikan sa mga kahilingan - ang mga kahilingan na pumasok sa system at natagpuan ang drive na ganap na napuno ay nawala;
• kasama ang paglilipat ng aplikasyon ng klase na ito, i.e. ang parehong klase ng natanggap na aplikasyon;
• kasama ang paglilipat ng aplikasyon mula sa klase ng pinakamababang priyoridad;
• kasama ang paglilipat ng aplikasyon mula sa pangkat ng mga mababang priyoridad na klase.

kanin. 2.2.

Maaaring gamitin ng mga buffering discipline ang sumusunod mga patakaran para sa pagpapaalis ng mga kahilingan mula sa nagtitipon:

• hindi sinasadyang pag-aalis;
• pagbubukod ng huling order, i.e. pumasok sa system nang mas huli kaysa sa lahat;
• siksikan ang isang "mahabang" order, i.e. na matatagpuan sa accumulator na mas mahaba kaysa sa lahat ng naunang natanggap na mga aplikasyon.

Sa fig. Ang 2.3 ay nagpapakita ng pag-uuri ng mga disiplina para sa mga aplikasyon ng serbisyo alinsunod sa parehong mga tampok tulad ng para sa mga disiplina ng buffering.

Minsan ang kapasidad ng imbakan sa mga modelo ay itinuturing na walang limitasyon, bagaman sa isang tunay na sistema ito ay limitado. Ang ganitong palagay ay makatwiran kapag ang posibilidad na mawala ang isang order sa isang tunay na sistema dahil sa pag-apaw ng kapasidad ng imbakan ay mas mababa sa 10 _3 . Sa kasong ito, halos walang epekto ang disiplina sa pagganap ng mga kahilingan.

Depende sa pagkakaroon o kakulangan ng mga priyoridad sa pagitan ng mga kahilingan ng iba't ibang klase, lahat ng mga disiplina sa serbisyo, pati na rin ang mga buffering disciplines, ay maaaring hatiin sa dalawang grupo: mga hindi priyoridad at priyoridad.

Sa pamamagitan ng kung paano itinalaga ang mga ticket sa serbisyo Ang mga disiplina sa serbisyo ay maaaring nahahati sa mga disiplina:

• Single mode;
• mode ng grupo;
• pinagsamang mode.

kanin. 2.3.

Sa mga disiplina sa paglilingkod Single mode serbisyo sa bawat oras isa lang ang nakatalaga kahilingan, kung saan ang mga pila ay ini-scan pagkatapos ng pagtatapos ng paglilingkod sa nakaraang kahilingan.

Sa mga disiplina sa paglilingkod mode ng grupo serbisyo sa bawat oras isang pangkat ng mga kahilingan ang itinalaga isang pila, kung saan ang mga pila ay ini-scan lamang pagkatapos na maserbisyuhan ang lahat ng mga kahilingan mula sa dating nakatalagang grupo. Ang bagong itinalagang pangkat ng mga tiket ay maaaring isama ang lahat ng mga tiket ng ibinigay na pila. Nakatalagang mga kahilingan sa pangkat sunud-sunod na pinili mula sa pila at sineserbisyuhan ng aparato, pagkatapos nito ang susunod na pangkat ng mga aplikasyon ng isa pang pila ay itinalaga para sa serbisyo alinsunod sa tinukoy na disiplina sa serbisyo.

Pinagsamang mode- isang kumbinasyon ng mga single at group mode, kapag ang bahagi ng kahilingan ay naproseso sa single mode, at ang iba pang bahagi - sa group mode.

Maaaring gamitin ng mga disiplina sa serbisyo ang sumusunod na mga panuntunan sa pagpili ng kahilingan sa serbisyo.

Hindi priority(walang mga pribilehiyo ng maagang serbisyo ang mga application - pagkuha ng mapagkukunan):

• serbisyong first come first served FIFO (una sa -unang lumabas, unang pumasok - unang lumabas)
• baliktad na serbisyo- Ang application ay pinili mula sa queue sa mode LIFO (huling pumasok - unang lumabas, huling pumasok Unang lumabas)
• random na serbisyo- Ang application ay pinili mula sa queue sa mode RAND (random- random);
• paikot na serbisyo- Pinipili ang mga aplikasyon sa proseso ng paikot na botohan ng mga drive sa sequence 1, 2, H MULA SA H- ang bilang ng mga drive), pagkatapos kung saan ang tinukoy na pagkakasunud-sunod ay paulit-ulit;

Priyoridad(Ang mga application ay may mga pribilehiyo para sa maagang serbisyo - pagkuha ng mapagkukunan):

• Sa kamag-anak na mga priyoridad- kung sa kurso ng kasalukuyang pagseserbisyo ng isang kahilingan, ang mga kahilingan na may mas mataas na priyoridad ay pumasok sa system, kung gayon ang paglilingkod sa kasalukuyang kahilingan, kahit na walang priyoridad, ay hindi maaantala, at ang mga natanggap na kahilingan ay ipinadala sa pila; Ang mga kamag-anak na priyoridad ay gumaganap lamang ng isang papel sa dulo ng kasalukuyang serbisyo ng aplikasyon kapag ang isang bagong kahilingan sa serbisyo ay napili mula sa pila.
• Sa ganap na priyoridad- sa pagtanggap ng isang kahilingan na may mataas na priyoridad, ang serbisyo ng isang kahilingan na may mababang priyoridad ay naaantala at ang natanggap na kahilingan ay ipinadala para sa paglilingkod; ang isang nagambalang aplikasyon ay maaaring ibalik sa pila o alisin sa system; kung ang aplikasyon ay ibinalik sa pila, ang karagdagang serbisyo nito ay maaaring isagawa mula sa nagambalang lugar o bago;
• co magkahalong priyoridad- Ang mahigpit na mga paghihigpit sa oras ng paghihintay sa pila para sa paglilingkod sa mga indibidwal na aplikasyon ay nangangailangan ng pagtatalaga ng mga ganap na priyoridad sa kanila; bilang resulta, ang oras ng paghihintay para sa mga aplikasyon na may mababang priyoridad ay maaaring lumabas na hindi katanggap-tanggap na malaki, bagaman ang mga indibidwal na aplikasyon ay may margin ng oras ng paghihintay; upang matupad ang mga paghihigpit sa lahat ng uri ng mga kahilingan, kasama ang mga ganap na priyoridad, ang ilang mga kahilingan ay maaaring italaga ng mga kamag-anak na priyoridad, at ang iba ay maaaring ihatid sa isang non-priority mode;
• Sa salit-salit na mga priyoridad- isang analogue ng mga kamag-anak na priyoridad, ang priyoridad ay isinasaalang-alang lamang sa mga sandali ng pagkumpleto ng kasalukuyang serbisyo ng isang pangkat ng mga kahilingan ng isang pila at ang appointment ng isang bagong grupo para sa paglilingkod;
• nakatakdang serbisyo- Ang mga kahilingan ng iba't ibang mga klase (na matatagpuan sa iba't ibang mga imbakan) ay pinili para sa serbisyo ayon sa isang tiyak na iskedyul na tumutukoy sa pagkakasunud-sunod ng mga pila ng botohan ng mga aplikasyon, halimbawa, sa kaso ng tatlong klase ng mga aplikasyon (mga tindahan), ang iskedyul ay maaaring magmukhang (2, 1, 3, 3, 1, 2) o (1, 2, 3, 3, 2, 1).

Sa mga sistema ng IM ng computer, bilang panuntunan, ang disiplina ay ipinatupad bilang default FIFO. Gayunpaman, mayroon silang mga tool na nagbibigay ng pagkakataon sa user na ayusin ang mga disiplina ng serbisyo na kailangan niya, kabilang ang ayon sa iskedyul.

Ang mga aplikasyon na natanggap ng CMO ay nahahati sa mga klase. Sa QS, na isang abstract mathematical model, nabibilang ang mga aplikasyon sa iba't ibang klase sakaling magkaiba ang mga ito sa simulate na tunay na system sa pamamagitan ng hindi bababa sa isa sa mga sumusunod na feature:

• tagal ng serbisyo;
• mga priyoridad.

Kung ang mga aplikasyon ay hindi naiiba sa tagal ng serbisyo at mga priyoridad, maaari silang katawanin ng mga aplikasyon ng parehong klase, kabilang ang kapag sila ay nagmula sa iba't ibang pinagmulan.

Para sa isang matematikal na paglalarawan ng mga disiplina ng serbisyo na may magkahalong priyoridad, ginagamit namin priority matrix, na isang parisukat na matrix Q = (q, ;), ako, j - 1,..., I, I - ang bilang ng mga klase ng mga application na pumapasok sa system.

Elemento q(j itinatakda ng matrix ang priyoridad ng mga kahilingan sa klase i kaugnay ng mga aplikasyon sa klase; at maaaring kunin ang mga sumusunod na halaga:

• 0 - walang priyoridad;
• 1 - kamag-anak na priyoridad;
• 2 - ganap na priyoridad.

Ang mga elemento ng priority matrix ay dapat matugunan ang mga sumusunod kinakailangan:

• q n= 0, dahil walang priyoridad ang maaaring itakda sa pagitan ng mga kahilingan ng parehong klase;
• kung q (j = 1 o 2 pagkatapos q^ = 0, dahil kung ang mga aplikasyon ng klase i unahin ang mga kahilingan sa klase j, kung gayon ang huli ay hindi maaaring mauna kaysa sa mga claim ng klase i (ako, j = 1, ..., ako).

Depende sa mga pagkakataon upang baguhin ang mga priyoridad Sa panahon ng pagpapatakbo ng system, ang mga prayoridad na disiplina ng buffering at servicing ay nahahati sa dalawang klase:

• 1) kasama static na priyoridad, na hindi nagbabago sa paglipas ng panahon;
• 2) kasama pabago-bagong mga priyoridad, na maaaring magbago sa panahon ng pagpapatakbo ng system depende sa iba't ibang mga kadahilanan, halimbawa, kapag ang isang tiyak na kritikal na halaga ay naabot para sa haba ng pila ng mga aplikasyon ng isang klase na walang priyoridad o may mababang priyoridad, maaari itong binigyan ng mas mataas na priyoridad.

Sa mga sistema ng computer ng IM, kinakailangang mayroong isang solong elemento (object) kung saan, at sa pamamagitan lamang nito, ang mga kahilingan ay ipinasok sa modelo. Bilang default, ang lahat ng inilagay na application ay hindi priyoridad. Ngunit may mga posibilidad para sa pagtatalaga ng mga priyoridad sa pagkakasunud-sunod 1, 2, ..., kabilang ang sa panahon ng pagpapatupad ng modelo, i.e. sa dynamics.

Papalabas na stream ay ang daloy ng mga serbisyong kahilingan na umaalis sa QS. Sa mga totoong system, dumaan ang mga application sa ilang QS: komunikasyon sa transit, pipeline ng produksyon, atbp. Sa kasong ito, ang papalabas na stream ay ang papasok na stream para sa susunod na QS.

Ang papasok na stream ng unang QS, na dumaan sa mga kasunod na QS, ay na-distort, at ito ay nagpapalubha ng analytical modelling. Gayunpaman, dapat itong tandaan na na may pinakasimpleng input stream at exponential service(mga. sa mga sistema ng Markov) ang output stream ay ang pinakasimpleng din. Kung ang oras ng serbisyo ay may di-exponential na pamamahagi, kung gayon ang papalabas na stream ay hindi lamang hindi simple, ngunit hindi rin paulit-ulit.

Tandaan na ang mga agwat ng oras sa pagitan ng mga papalabas na kahilingan ay hindi kapareho ng mga agwat ng serbisyo. Pagkatapos ng lahat, maaaring lumabas na pagkatapos ng pagtatapos ng susunod na serbisyo, ang QS ay idle nang ilang oras dahil sa kakulangan ng mga aplikasyon. Sa kasong ito, ang papalabas na agwat ng daloy ay binubuo ng idle time ng QS at ang agwat ng serbisyo ng unang kahilingan na dumating pagkatapos ng downtime.

Sa QS, bilang karagdagan sa papalabas na daloy ng mga kahilingan sa serbisyo, maaaring mayroong daloy ng mga hindi naibigay na kahilingan. Kung ang naturang QS ay tumatanggap ng paulit-ulit na daloy, at ang serbisyo ay exponential, kung gayon ang daloy ng mga hindi naihatid na customer ay paulit-ulit din.

Libreng channel queue. Sa multi-channel QS, maaaring bumuo ng mga pila ng mga libreng channel. Ang bilang ng mga libreng channel ay isang random na halaga. Maaaring interesado ang mga mananaliksik sa iba't ibang katangian ng random variable na ito. Karaniwan, ito ang average na bilang ng mga channel na inookupahan ng serbisyo sa bawat agwat ng survey at ang kanilang mga salik sa pagkarga.

Tulad ng nabanggit namin kanina, sa mga totoong bagay, ang mga kahilingan ay sunud-sunod na sineserbisyuhan sa ilang QS.

Ang isang may hangganan na hanay ng magkakasunod na magkakaugnay na mga QS na nagpoproseso ng mga application na nagpapalipat-lipat sa mga ito ay tinatawag na network ng pagpila (Semo) (Larawan 2.4, a).

kanin. 2.4.

SEMO din ang tawag multiphase QS.

Isasaalang-alang namin ang isang halimbawa ng pagbuo ng isang QEMO IM sa ibang pagkakataon.

Ang mga pangunahing elemento ng QS ay mga node (U) at mga source (generators) ng mga kahilingan (G).

Knot Ang mga network ay isang sistema ng pagpila.

Pinagmulan- isang generator ng mga application na pumapasok sa network at nangangailangan ng ilang mga yugto ng serbisyo sa mga node ng network.

Ang isang graph ay ginagamit para sa isang pinasimpleng larawan ng QEMO.

Bilangin si Semo- isang nakadirekta na graph (digraph), ang mga vertices na tumutugma sa mga QEM node, at ang mga arc ay kumakatawan sa mga transition ng mga application sa pagitan ng mga node (Larawan 2.4, b).

Kaya, isinasaalang-alang namin ang mga pangunahing konsepto ng QS. Ngunit sa pagbuo ng mga computer system para sa IM at ang kanilang pagpapabuti, ang malaking potensyal na malikhaing kasalukuyang nakapaloob sa analytical modelling ng QS ay kinakailangan ding gamitin.

Para sa isang mas mahusay na pang-unawa sa malikhaing potensyal na ito, bilang unang pagtataya, pag-isipan natin ang pag-uuri ng mga modelo ng QS.

Ito ay kinakailangan upang malutas ang mga problema 1-3. Ang paunang data ay ibinigay sa talahanayan. 2-4.

Ilang notasyong ginamit sa teorya ng pagpila para sa mga formula:

n ay ang bilang ng mga channel sa QS;

λ - intensity ng papasok na daloy ng mga application P sa;

v - ang intensity ng papalabas na daloy ng mga application P out;

μ - ang intensity ng daloy ng serbisyo P tungkol sa;

ρ - tagapagpahiwatig ng pagkarga ng system (trapiko);

m - ang maximum na bilang ng mga lugar sa pila, nililimitahan ang haba ng pila ng mga application;

i - bilang ng mga mapagkukunan ng aplikasyon;

p hanggang - ang posibilidad ng k-th na estado ng system;

p about - ang posibilidad ng idle time ng buong system, i.e. ang posibilidad na ang lahat ng mga channel ay libre;

p syst - ang posibilidad ng pagtanggap ng isang aplikasyon sa system;

p otk - ang posibilidad ng pagtanggi sa aplikasyon sa pagtanggap nito sa system;

p tungkol - ang posibilidad na maihatid ang aplikasyon;

Ang A ay ang ganap na throughput ng system;

Ang Q ay ang relatibong throughput ng system;

och - ang average na bilang ng mga application sa queue;

o - ang average na bilang ng mga aplikasyon sa ilalim ng serbisyo;

syst - ang average na bilang ng mga application sa system;

pt - average na oras ng paghihintay para sa isang aplikasyon sa pila;

o - ang average na oras ng serbisyo ng aplikasyon, na nauugnay lamang sa mga kahilingan sa serbisyo;

sys - ang average na oras ng pananatili ng application sa system;

exp - karaniwang oras na nililimitahan ang paghihintay para sa isang aplikasyon sa pila;

Average na bilang ng mga abalang channel.

Ang absolute throughput ng QS A ay ang average na bilang ng mga application na maaaring ihatid ng system bawat yunit ng oras.

Ang Relative QS throughput Q ay ang ratio ng average na bilang ng mga application na inihatid ng system sa bawat unit ng oras sa average na bilang ng mga application na natanggap sa panahong ito.

Kapag nilulutas ang mga problema sa pagpila, kinakailangan na sumunod sa sumusunod na pagkakasunud-sunod:

1) pagpapasiya ng uri ng QS ayon sa Talahanayan. 4.1;

2) ang pagpili ng mga formula alinsunod sa uri ng QS;

3) paglutas ng problema;

4) pagbabalangkas ng mga konklusyon sa problema.

1. Scheme ng kamatayan at pagpaparami.

Alam namin na, dahil sa may label na graph ng estado, madali naming maisusulat ang Kolmogorov equation para sa state probabilities, gayundin ang pagsulat at paglutas ng mga algebraic equation para sa huling probabilities. Para sa ilang mga kaso, posibleng malutas nang maaga ang mga huling equation, sa literal na anyo. Sa partikular, ito ay maaaring gawin kung ang state graph ng system ay ang tinatawag na "death and reproduction scheme".

Ang graph ng estado para sa scheme ng kamatayan at pagpaparami ay may form na ipinapakita sa Fig. 19.1. Ang kakaiba ng graph na ito ay ang lahat ng mga estado ng system ay maaaring iguhit sa isang chain, kung saan ang bawat isa sa mga karaniwang estado ( S 1 , S 2 , …, S n-1) ay konektado sa pamamagitan ng isang pasulong at paatras na arrow sa bawat isa sa mga kalapit na estado - kanan at kaliwa, at ang mga matinding estado (S 0 , S n) — na may isang kalapit na estado lamang. Ang terminong "scheme of death and reproduction" ay nagmula sa mga biyolohikal na problema, kung saan ang pagbabago sa laki ng populasyon ay inilalarawan ng naturang iskema.

Ang pamamaraan ng kamatayan at pagpaparami ay madalas na nakatagpo sa iba't ibang mga problema sa pagsasanay, lalo na - sa teorya ng pagpila, samakatuwid ito ay kapaki-pakinabang, minsan at para sa lahat, upang mahanap ang pangwakas na mga probabilidad ng mga estado para dito.

Ipagpalagay natin na ang lahat ng mga daloy ng kaganapan na naglilipat ng system kasama ang mga arrow ng graph ay ang pinakasimpleng (para sa kaiklian, tatawagin din natin ang system S at ang prosesong nagaganap dito ay ang pinakasimple).

Gamit ang graph sa Fig. 19.1, binubuo at nilulutas namin ang mga algebraic equation para sa mga huling probabilidad ng estado), ang pagkakaroon ay sumusunod sa katotohanan na mula sa bawat estado ay maaari kang pumunta sa bawat isa, ang bilang ng mga estado ay may hangganan).

Para sa unang estado S 0 mayroon kaming:

(19.1)

Para sa pangalawang estado S1:

Dahil sa (19.1), ang huling pagkakapantay-pantay ay nabawasan sa anyo

saan k kinukuha ang lahat ng halaga mula 0 hanggang P. Kaya ang mga huling probabilidad p0, p1,..., p n masiyahan ang mga equation

(19.2)

bilang karagdagan, dapat nating isaalang-alang ang kondisyon ng normalisasyon

p 0 + p 1 + p 2 +…+ p n=1. (19.3)

Lutasin natin ang sistemang ito ng mga equation. Mula sa unang equation (19.2) ipinapahayag namin p 1 hanggang R 0 :

p 1 = p 0. (19.4)

Mula sa pangalawa, isinasaalang-alang ang (19.4), nakuha namin ang:

(19.5)

mula sa ikatlo, isinasaalang-alang (19.5),

(19.6)

at sa pangkalahatan, para sa alinman k(mula 1 hanggang n):

(19.7)

Bigyang-pansin natin ang formula (19.7). Ang numerator ay produkto ng lahat ng intensity sa mga arrow na humahantong mula kaliwa hanggang kanan (mula sa simula hanggang sa ibinigay na estado S k), at ang denominator ay ang produkto ng lahat ng intensity sa mga arrow na humahantong mula kanan pakaliwa (mula sa simula hanggang Sk).

Kaya, ang lahat ng mga probabilidad ng estado R 0 , p 1 , ..., р n ipinahayag sa pamamagitan ng isa sa kanila ( R 0). Ipalit natin ang mga ekspresyong ito sa kondisyon ng normalisasyon (19.3). Nakukuha namin sa pamamagitan ng panaklong R 0:

kaya nakuha namin ang expression para sa R 0 :

(tinaas namin ang panaklong sa kapangyarihan ng -1 upang hindi magsulat ng dalawang-kuwento na mga praksiyon). Ang lahat ng iba pang mga probabilidad ay ipinahayag sa mga tuntunin ng R 0 (tingnan ang mga formula (19.4)-(19.7)). Tandaan na ang mga coefficient para sa R 0 sa bawat isa sa kanila ay walang iba kundi ang magkakasunod na miyembro ng serye pagkatapos ng yunit sa formula (19.8). Kaya, pagkalkula R 0 , nahanap na namin ang lahat ng mga coefficient na ito.

Ang mga nakuhang formula ay lubhang kapaki-pakinabang sa paglutas ng mga pinakasimpleng problema ng teorya ng pagpila.

2. Maliit na formula.

Ngayon nakukuha namin ang isang mahalagang formula na nauugnay (para sa paglilimita, nakatigil na rehimen) ang average na bilang ng mga aplikasyon L syst, na matatagpuan sa queuing system (i.e. nagsilbi o nakatayo sa linya), at ang average na oras ng paninirahan ng application sa system W syst.

Isaalang-alang natin ang anumang QS (single-channel, multi-channel, Markovian, non-Markovian, na may unlimited o bounded queue) at dalawang daloy ng mga kaganapan na nauugnay dito: ang daloy ng mga customer na dumarating sa QS at ang daloy ng mga customer na umaalis sa QS. Kung ang isang paglilimita, nakatigil na rehimen ay naitatag sa system, kung gayon ang average na bilang ng mga aplikasyon na dumarating sa QS bawat yunit ng oras ay katumbas ng average na bilang ng mga aplikasyon na umaalis dito: ang parehong mga daloy ay may parehong intensity λ.

Ipahiwatig: X(t) — ang bilang ng mga aplikasyon na dumating sa CMO bago ang sandali t. Y(t) — ang bilang ng mga application na umalis sa CMO

hanggang sa sandaling ito t. Ang parehong mga function ay random at biglang nagbabago (tumaas ng isa) sa sandali ng pagdating ng mga kahilingan (X(t)) at pag-alis ng mga aplikasyon (Y(t)). Uri ng mga function X(t) at Y(t) ipinapakita sa fig. 19.2; parehong linya ay stepped, ang itaas ay X(t), mas mababa— Y(t). Malinaw, sa anumang sandali t kanilang pagkakaiba Z(t)= X(t) - Y(t) ay walang iba kundi ang bilang ng mga aplikasyon sa QS. Kapag ang mga linya X(t) at Y(t) pagsamahin, walang mga kahilingan sa system.

Isaalang-alang ang napakahabang yugto ng panahon T(sa isip na ipagpatuloy ang graph na lampas sa pagguhit) at kalkulahin para dito ang average na bilang ng mga aplikasyon sa QS. Ito ay magiging katumbas ng integral ng function Z(t) sa pagitan na ito na hinati sa haba ng pagitan T:

L syst. = . (19.9) o

Ngunit ang integral na ito ay walang iba kundi ang lugar ng figure na may kulay sa Fig. 19.2. Tingnan nating mabuti ang guhit na ito. Ang figure ay binubuo ng mga parihaba, ang bawat isa ay may taas na katumbas ng isa, at isang base na katumbas ng oras ng paninirahan sa sistema ng kaukulang pagkakasunud-sunod (ang una, pangalawa, atbp.). Markahan natin ang mga oras na ito t1, t2,... Totoo, sa dulo ng pagitan T ang ilang mga parihaba ay papasok sa shaded figure hindi ganap, ngunit bahagyang, ngunit may isang sapat na malaki T hindi mahalaga ang maliliit na bagay na ito.

(19.10)

kung saan ang halaga ay nalalapat sa lahat ng mga aplikasyon na natanggap sa panahong iyon T.

Hatiin ang kanan at kaliwang gilid (.19.10) sa haba ng pagitan T. Nakukuha namin, isinasaalang-alang ang (19.9),

L syst. = . (19.11)

Hinahati at i-multiply natin ang kanang bahagi ng (19.11) sa intensity X:

L syst. = .

Pero ang laki Tλ ay hindi hihigit sa average na bilang ng mga aplikasyon na natanggap sa panahong iyon ^ T. Kung hahatiin natin ang kabuuan ng lahat ng oras t i sa average na bilang ng mga application, pagkatapos ay makuha namin ang average na oras ng pananatili ng application sa system W syst. Kaya,

L syst. = λ W syst. ,

W syst. = . (19.12)

Ito ang kahanga-hangang formula ni Little: para sa anumang QS, para sa anumang uri ng daloy ng mga aplikasyon, para sa anumang pamamahagi ng oras ng serbisyo, para sa anumang disiplina sa serbisyo ang average na oras ng paninirahan ng isang kahilingan sa system ay katumbas ng average na bilang ng mga kahilingan sa system na hinati sa intensity ng daloy ng mga kahilingan.

Sa eksaktong parehong paraan, ang pangalawang formula ni Little ay nakuha, na nag-uugnay sa average na oras na ginugugol ng application sa pila. ^ O sige at ang average na bilang ng mga application sa queue L och:

W och = . (19.13)

Para sa output, ito ay sapat na sa halip na ang ilalim na linya sa Fig. 19.2 kumuha ng isang function U(t)- ang bilang ng mga application na natitira hanggang sa sandaling ito t hindi mula sa system, ngunit mula sa queue (kung ang isang application na pumasok sa system ay hindi nakapasok sa queue, ngunit agad na napupunta sa ilalim ng serbisyo, maaari pa rin nating isaalang-alang na ito ay nakapasok sa queue, ngunit nananatili dito para sa zero na oras) .

Ang mga formula ni Little (19.12) at (19.13) ay may mahalagang papel sa teorya ng pagpila. Sa kasamaang palad, sa karamihan ng mga umiiral na manwal, ang mga formula na ito (napatunayan sa isang pangkalahatang anyo na medyo kamakailan) ay hindi binibigyan ng 1).

Ang pinakasimpleng sistema ng pagpila at ang kanilang mga katangian

Sa seksyong ito, isasaalang-alang namin 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, "Markovian" na teorya ng pagpila.

Hindi namin ituloy ang bilang ng mga sample ng QS kung saan kukunin ang mga huling pagpapahayag ng mga katangian; ang aklat na ito ay hindi isang gabay sa teorya ng pagpila (ang mga espesyal na gabay ay pinupuno ang papel na ito nang mas mahusay). Ang aming layunin ay ipakilala sa mambabasa ang ilang "maliit na trick" upang mapagaan ang paraan sa pamamagitan ng teorya ng queuing, na sa ilang available (kahit na sinasabing sikat) na mga libro ay maaaring magmukhang isang nagkakagulong koleksyon ng mga halimbawa.

Lahat ng mga daloy ng mga kaganapan na naglilipat ng QS mula sa estado patungo sa estado, sa seksyong ito, isasaalang-alang namin ang pinakasimpleng (nang hindi partikular na itinatakda ito sa bawat oras). Kabilang sa mga ito ay ang tinatawag na "daloy ng serbisyo". Nangangahulugan ito ng daloy ng mga kahilingan na sineserbisyuhan ng isang patuloy na abalang channel. Sa stream na ito, ang agwat sa pagitan ng mga kaganapan, gaya ng nakasanayan sa pinakasimpleng stream, ay may exponential distribution (sa halip, maraming mga manual ang nagsasabi: "Ang oras ng serbisyo ay exponential", kami mismo ang gagamit ng terminong ito sa hinaharap).

Sa isang sikat na libro, isang medyo naiiba, kumpara sa itaas, ang derivation ng Little's formula ay ibinigay. Sa pangkalahatan, ang kakilala sa aklat na ito (“Ikalawang Pag-uusap”) ay kapaki-pakinabang para sa isang paunang kakilala sa teorya ng pagpila.

Sa seksyong ito, ang exponential distribution ng oras ng serbisyo ay ipagkakaloob, gaya ng nakasanayan para sa "pinakasimpleng" system.

Ipapakilala namin ang mga katangian ng kahusayan ng QS na isinasaalang-alang sa kurso ng pagtatanghal.

1. P- channel QS na may mga pagkabigo(Erlang problema). Dito namin isaalang-alang ang isa sa mga unang sa oras, "klasikal" problema ng teorya ng queuing; ang problemang ito ay lumitaw mula sa mga praktikal na pangangailangan ng telephony at nalutas sa simula ng ating siglo ng Danish mathematician na si Erlant. Ang gawain ay itinakda tulad ng sumusunod: mayroon P channels (mga linya ng komunikasyon), na tumatanggap ng daloy ng mga application na may intensity λ. Ang daloy ng serbisyo ay may intensity μ (ang kapalit ng average na oras ng serbisyo t tungkol).

Hanapin ang mga huling probabilidad ng mga estado ng QS, pati na rin ang mga katangian ng kahusayan nito:

^ A - absolute throughput, ibig sabihin, ang average na bilang ng mga application na inihatid sa bawat yunit ng oras;

Q- kamag-anak na throughput, ibig sabihin, ang average na bahagi ng mga papasok na kahilingan na inihatid ng system;

^ R otk- ang posibilidad ng pagkabigo, i.e. ang katotohanan na ang aplikasyon ay iiwan ang QS na hindi naihatid;

k - average na bilang ng mga abalang channel.

Solusyon. Mga estado ng system ^S(QS) ay bibigyan ng bilang ayon sa bilang ng mga kahilingan sa system (sa kasong ito, ito ay tumutugma sa bilang ng mga abalang channel):

S 0 — walang mga aplikasyon sa CMO,

S 1 — may isang kahilingan sa QS (isang channel ay abala, ang iba ay libre),

Sk - sa SMO ay k mga aplikasyon ( k abala ang mga channel, libre ang iba),

S n - sa SMO ay P mga aplikasyon (lahat n abala ang mga channel).

Ang graph ng estado ng QS ay tumutugma sa scheme ng kamatayan sa pagpaparami (Larawan 20.1). Markahan natin ang graph na ito - ilagay ang intensity ng mga daloy ng kaganapan malapit sa mga arrow. Mula sa S 0 in S1 ang sistema ay inililipat sa pamamagitan ng daloy ng mga kahilingan na may intensity λ (sa sandaling dumating ang isang kahilingan, ang sistema ay tumalon mula sa S0 sa S1). Ang parehong daloy ng mga kahilingan ay naglilipat ng system mula sa anumang kaliwang estado patungo sa kalapit na kanang estado (tingnan ang itaas na mga arrow sa Fig. 20.1).

Ibaba natin ang intensity ng lower arrows. Hayaan ang sistema sa estado ^S 1 (isang channel ay gumagana). Gumagawa ito ng mga serbisyo ng μ kada yunit ng oras. Ibinaba namin ang arrow S 1 →S 0 intensity μ. Ngayon isipin na ang sistema ay nasa estado S2(Gumagana ang dalawang channel). Para puntahan niya S 1 , ito ay kinakailangan na alinman sa unang channel, o ang pangalawa, tapusin servicing; ang kabuuang intensity ng kanilang mga daloy ng serbisyo ay 2μ; ilagay ito sa kaukulang arrow. Ang kabuuang daloy ng serbisyo na ibinigay ng tatlong channel ay may intensity na 3μ, k mga channel - km. Ibinaba namin ang mga intensidad na ito sa mas mababang mga arrow 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.

Ayon sa formula (19.8) nakukuha natin:

Mga termino ng pagkabulok ang magiging coefficients para sa p 0 sa mga ekspresyon para sa p1

Tandaan na ang mga formula (20.1), (20.2) ay hindi kasama ang mga intensidad na λ at μ nang hiwalay, ngunit bilang ratio lamang λ/μ. Magpakilala

λ/μ = ρ (20.3)

At tatawagin natin ang halaga ng p "ang pinababang intensity ng daloy ng mga aplikasyon." Ang kahulugan nito ay ang average na bilang ng mga kahilingang dumarating para sa average na oras ng serbisyo ng 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 estado ay tinatawag na mga formula ng Erlang, bilang parangal sa nagtatag ng teorya ng pagpila. Karamihan sa iba pang mga formula 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. Batay sa kanila, kakalkulahin namin ang mga katangian ng kahusayan ng QS. Una naming mahanap ^ R otk. - ang posibilidad na ang papasok na kahilingan ay tatanggihan (hindi ihahatid). Para dito kinakailangan na ang lahat P abala ang mga channel, kaya

R otk = R n = . (20.6)

Mula dito nakita namin ang kamag-anak na throughput - ang posibilidad na maihatid ang aplikasyon:

Q = 1 - P bukas = 1 - (20.7)

Nakukuha namin ang ganap na throughput sa pamamagitan ng pagpaparami ng intensity ng daloy ng mga kahilingan λ sa Q:

A = λQ = λ. (20.8)

Ito ay nananatili lamang upang mahanap ang average na bilang ng mga abalang channel k. Ang halagang ito ay matatagpuan "direkta", bilang ang matematikal na inaasahan ng isang discrete random variable na may posibleng mga halaga 0, 1, ..., P at ang mga probabilidad ng mga halagang ito p 0 p 1 , ..., p n:

k = 0 · p 0 + isa · p 1 + 2 · p 2 + ... + n · p n .

Pagpapalit dito ng mga expression (20.5) para sa R k , (k = 0, 1, ..., P) at pagsasagawa ng mga naaangkop na pagbabago, makukuha natin ang tamang formula para sa k. Ngunit mas madaling makuha natin ito (narito, isa sa mga "maliit na trick"!) Sa katunayan, alam natin ang ganap na throughput PERO. Ito ay walang iba kundi ang intensity ng daloy ng mga application na inihatid ng system. Ang bawat may trabahong i .shal bawat yunit ng oras ay nagsisilbi ng average ng |l na mga kahilingan. Kaya ang average na bilang ng mga abalang channel ay

k = A/μ, (20.9)

o, ibinigay (20.8),

k = (20.10)

Hinihikayat namin ang mambabasa na gawin ang halimbawa sa kanilang sarili. Mayroong istasyon ng komunikasyon na may tatlong channel ( n= 3), ang intensity ng daloy ng mga application λ = 1.5 (mga application kada minuto); average na oras ng serbisyo bawat kahilingan t v = 2 (min.), ang lahat ng daloy ng kaganapan (tulad ng sa buong talatang ito) ay ang pinakasimple. Hanapin ang huling mga probabilidad ng estado at mga katangian ng pagganap ng QS: A, Q, P otk, k. Kung sakali, narito ang mga sagot: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, p 3 = 9/26 ≈ 0,346,

PERO≈ 0,981, Q ≈ 0,654, P bukas ≈ 0.346, k ≈ 1,96.

Makikita mula sa mga tugon, sa pamamagitan ng paraan, na ang aming CMO ay higit na na-overload: sa tatlong channel, sa karaniwan, halos dalawa ang abala, at humigit-kumulang 35% ng mga papasok na aplikasyon ay nananatiling hindi naseserbisyuhan. Inaanyayahan namin ang mambabasa, kung siya ay mausisa at hindi tamad, upang malaman: gaano karaming mga channel ang kinakailangan upang masiyahan ang hindi bababa sa 80% ng mga papasok na aplikasyon? At anong bahagi ng mga channel ang magiging idle sa parehong oras?

Mayroon nang ilang pahiwatig ng pag-optimize. Sa katunayan, ang nilalaman ng bawat channel sa bawat yunit ng oras ay nagkakahalaga ng isang tiyak na halaga. Kasabay nito, ang bawat serbisyong aplikasyon ay nagdudulot ng kaunting kita. Pagpaparami ng kita na ito sa average na bilang ng mga aplikasyon PERO, serbisiyo bawat yunit ng oras, makukuha natin ang average na kita mula sa CMO bawat yunit ng oras. Naturally, sa pagtaas ng bilang ng mga channel, lumalaki ang kita na ito, ngunit ang mga gastos na nauugnay sa pagpapanatili ng mga channel ay lumalaki din.

Ano ang hihigit - pagtaas ng kita o gastos? Depende ito sa mga kondisyon ng operasyon, sa "bayad sa serbisyo ng aplikasyon" at sa 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 gayong problema, na iniiwan ang parehong "hindi tamad at mausisa na mambabasa" upang makabuo ng isang halimbawa at lutasin ito. Sa pangkalahatan, ang pag-imbento ng mga problema ay higit pa sa paglutas sa mga itinakda na ng isang tao.

Single-channel na QS na may walang limitasyong pila.

Sa pagsasagawa, ang isang channel na QS na may pila ay karaniwan (isang doktor na naglilingkod sa mga pasyente; isang pay phone na may isang booth; isang computer na tumutupad sa mga order ng user). Sa teorya ng queuing, ang single-channel QS na may queue ay sumasakop din sa isang espesyal na lugar (karamihan sa mga analytical formula na nakuha sa ngayon para sa mga non-Markovian system ay nabibilang sa naturang QS). Samakatuwid, bibigyan namin ng espesyal na pansin ang single-channel na QS na may pila.

Hayaang magkaroon ng isang solong channel na QS na may pila kung saan walang mga paghihigpit na ipinapataw (ni sa haba ng pila, o sa oras ng paghihintay). Ang QS na ito ay tumatanggap ng daloy ng mga kahilingan na may intensity λ ; ang daloy ng serbisyo ay may intensity μ na kabaligtaran sa average na oras ng serbisyo ng kahilingan t tungkol sa.

Kinakailangang hanapin ang mga huling probabilidad ng mga estado ng QS, pati na rin ang mga katangian ng kahusayan nito:

L syst. — average na bilang ng mga application sa system,

W syst. ay ang average na oras ng paninirahan ng isang kahilingan sa system,

^L och- ang average na bilang ng mga application sa queue,

W och — ang karaniwang oras na ginugugol ng isang application sa pila,

P zan — ang posibilidad na ang channel ay abala (ang antas ng pag-load ng channel).

Tulad ng para sa ganap na throughput PERO at kamag-anak Q, pagkatapos ay hindi na kailangang kalkulahin ang mga ito:

dahil sa ang katunayan na ang pila ay walang limitasyon, ang bawat aplikasyon ay ihahatid nang maaga o huli, samakatuwid Isang \u003d λ, para sa parehong dahilan Q= 1.

Solusyon. Ang mga estado ng system, tulad ng dati, ay bibigyan ng bilang ayon sa bilang ng mga aplikasyon sa QS:

S 0 — libre ang channel

S 1 - abala ang channel (nagsisilbi sa kahilingan), walang pila,

S 2 — abala ang channel, isang kahilingan ang nasa pila,

S k - abala ang channel, k - 1 application ang nasa pila,

Sa teoryang, ang bilang ng mga estado ay hindi limitado ng anumang bagay (walang hanggan). Ang graph ng estado ay may form na ipinapakita sa Fig. 20.2. Ito ay isang pamamaraan ng kamatayan at pagpaparami, ngunit may walang katapusang bilang ng mga estado. Sa lahat ng mga arrow, ang daloy ng mga kahilingan na may intensity λ ay naglilipat ng system mula kaliwa pakanan, at mula kanan papuntang kaliwa, ang daloy ng serbisyo na may intensity μ.

Una sa lahat, tanungin natin ang ating sarili, may mga huling probabilidad ba sa kasong ito? Pagkatapos ng lahat, ang bilang ng mga estado ng system ay walang hanggan, at, sa prinsipyo, sa t → ∞ maaaring lumaki ang pila ng walang katiyakan! Oo, totoo: ang mga huling probabilidad para sa naturang QS ay hindi palaging umiiral, ngunit kapag ang system ay hindi na-overload. Mapapatunayan na kung ang ρ ay mahigpit na mas mababa sa isa (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ lumalaki nang walang katapusan.

Ang katotohanang ito ay tila lalo na "hindi maintindihan" para sa ρ = 1. Mukhang walang imposibleng mga kinakailangan para sa system: sa panahon ng serbisyo ng isang kahilingan, sa karaniwan, isang kahilingan ang dumating, at ang lahat ay dapat na maayos, ngunit sa katotohanan ito ay hindi. Para sa ρ = 1, kinakaya ng QS ang daloy ng mga kahilingan lamang kung regular ang daloy na ito, at hindi rin random ang oras ng serbisyo, katumbas ng agwat sa pagitan ng mga kahilingan. Sa ganitong "ideal" na kaso, hindi magkakaroon ng queue sa QS, ang channel ay patuloy na magiging abala at regular na maglalabas ng mga kahilingan sa serbisyo.

Ngunit sa sandaling maging random ang daloy ng mga kahilingan o daloy ng serbisyo, tataas na ang pila nang walang katiyakan. Sa pagsasagawa, hindi lamang ito nangyayari dahil ang "isang walang katapusang bilang ng mga aplikasyon sa pila" ay isang abstraction. Ito ang mga malalaking pagkakamali na maaaring humantong sa pagpapalit ng mga random na variable ng kanilang mga inaasahan sa matematika!

Ngunit bumalik tayo sa aming single-channel na QS na may walang limitasyong pila. Sa mahigpit na pagsasalita, ang mga pormula para sa mga huling probabilidad sa pamamaraan ng kamatayan at pagpaparami ay hinango lamang natin para sa kaso ng isang may hangganang bilang ng mga estado, ngunit hayaan natin ang mga kalayaan - gagamitin natin ang mga ito para sa isang walang katapusang bilang ng mga estado. Kalkulahin natin ang mga huling probabilidad ng mga estado ayon sa mga formula (19.8), (19.7). Sa aming kaso, ang bilang ng mga termino sa formula (19.8) ay magiging walang hanggan. Kumuha kami ng isang expression para sa p 0:

p 0 \u003d -1 \u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)

Ang serye sa formula (20.11) ay isang geometric na pag-unlad. Alam namin na para sa ρ< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... umiiral lamang para sa r<1).

Ngayon ipagpalagay na ang kundisyong ito ay nasiyahan at ρ1 + ρ + ρ 2 + ... + ρ k + ... = ,

p 0 = 1 - p. (20.12)

Mga probabilidad p 1 , p 2 , ..., p k ,... ay matatagpuan sa pamamagitan ng mga formula:

p1 = ρ p 0 , p 2= ρ2 p 0 ,…,p k = ρ p0, ...,

Kung saan, isinasaalang-alang ang (20.12), sa wakas ay nakita natin:

p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ k(1 - p), . . .(20.13)

Tulad ng nakikita mo, ang mga probabilidad p0, p1, ..., p k,... bumuo ng geometric progression na may denominator p. Kakatwa, ang pinakamalaki sa kanila p 0 — ang posibilidad na ang channel ay magiging libre sa lahat. Gaano man ka-load ang system ng queue, kung makakayanan lang nito ang daloy ng mga application (ρ<1), самое вероятное число заявок в системе будет 0.

Hanapin ang average na bilang ng mga application sa QS ^L syst. . Dito kailangan mong mag-isip nang kaunti. Random na halaga Z- bilang ng mga kahilingan sa system — may mga posibleng halaga 0, 1, 2, .... k,... may probabilidad p0, p 1 , p 2 , ..., p k , ... Ang mathematical expectation nito ay

L syst = 0 ? p 0 + 1 ? p 1 + 2 ? p 2 +…+k ? p k +…= (20.14)

(ang kabuuan ay hindi kinukuha mula 0 hanggang ∞, ngunit mula 1 hanggang ∞, dahil ang zero term ay katumbas ng zero).

Pinapalitan namin sa formula (20.14) ang expression para sa p k (20.13):

L syst. =

Ngayon ay kinuha namin ang tanda ng kabuuan ρ (1-ρ):

L syst. = ρ(1-ρ)

Narito muli naming inilalapat ang "maliit na trick": kρ k Ang -1 ay walang iba kundi ang derivative na may kinalaman sa ρ ng expression na ρ k; ibig sabihin,

L syst. = ρ(1-ρ)

Sa pamamagitan ng pagpapalit ng mga operasyon ng pagkita ng kaibhan at pagsusuma, nakukuha namin ang:

L syst. = ρ (1-ρ) (20.15)

Ngunit ang kabuuan sa pormula (20.15) ay walang iba kundi ang kabuuan ng isang walang katapusang pagbaba ng geometric na pag-unlad na may unang termino na ρ at ang denominator na ρ; ang halagang ito

ay katumbas ng , at ang derivative nito ay . Ang pagpapalit ng ekspresyong ito sa (20.15), nakukuha natin:

L syst = . (20.16)

Ngayon, ilapat natin ang formula ng Little (19.12) at hanapin ang average na oras ng paninirahan ng isang aplikasyon sa system:

W syst = (20.17)

Hanapin ang average na bilang ng mga application sa queue L och. Magtatalo kami bilang mga sumusunod: ang bilang ng mga aplikasyon sa pila ay katumbas ng bilang ng mga aplikasyon sa system na binawasan ang bilang ng mga aplikasyon sa ilalim ng serbisyo. Kaya (ayon sa panuntunan ng pagdaragdag ng mga inaasahan sa matematika), ang average na bilang ng mga aplikasyon sa pila L pt ay katumbas ng average na bilang ng mga application sa system L syst minus ang average na bilang ng mga kahilingan sa ilalim ng serbisyo.

Ang bilang ng mga kahilingan sa ilalim ng serbisyo ay maaaring alinman sa zero (kung ang channel ay libre) o isa (kung ito ay abala). Ang pag-asa sa matematika ng naturang random na variable ay katumbas ng posibilidad na abala ang channel (tinukoy namin ito R zan). Obviously, R Ang zan ay katumbas ng isang minus ang posibilidad p 0 na ang channel ay libre:

R zan = 1 - R 0 = p. (20.18)

Samakatuwid, ang average na bilang ng mga kahilingan sa ilalim ng serbisyo ay katumbas ng

^L tungkol sa= ρ, (20.19)

L och = L syst - ρ =

at sa wakas

L pt = (20.20)

Gamit ang formula ni Little (19.13), nakita namin ang average na oras na ginugugol ng application sa pila:

(20.21)

Kaya, ang lahat ng mga katangian ng kahusayan ng QS ay natagpuan.

Imungkahi natin sa mambabasa na lutasin ang isang halimbawa sa kanyang sarili: ang isang solong channel na QS ay isang railway marshalling yard, na tumatanggap ng pinakasimpleng daloy ng mga tren na may intensity na λ = 2 (mga tren kada oras). Serbisyo (disbandment)

Ang komposisyon ay tumatagal ng random (nagpapakita) na oras na may average na halaga t tungkol sa = 20(min.). Sa arrival park ng istasyon, mayroong dalawang riles kung saan ang mga darating na tren ay maaaring maghintay para sa serbisyo; kung ang parehong mga riles ay abala, ang mga tren ay napipilitang maghintay sa mga panlabas na riles.

Kinakailangang hanapin (para sa paglilimita, nakatigil na mode ng pagpapatakbo ng istasyon): average, bilang ng mga tren l sistemang nauugnay sa istasyon, ibig sabihin ng oras W sistema ng pananatili ng tren sa istasyon (sa mga panloob na riles, sa mga panlabas na riles at nasa ilalim ng pagpapanatili), average na numero L pts ng mga tren na naghihintay sa linya para sa disbandment (hindi mahalaga kung aling mga track), average na oras W Ang mga pt ay mananatiling komposisyon sa listahan ng naghihintay. Gayundin, subukang hanapin ang average na bilang ng mga tren na naghihintay na ma-disband sa mga panlabas na riles. L panlabas at ang karaniwang oras ng paghihintay na ito W panlabas (ang huling dalawang dami ay nauugnay sa formula ni Little).

Panghuli, hanapin ang kabuuang pang-araw-araw na multa W, na kailangang bayaran ng istasyon para sa demurrage ng mga tren sa mga panlabas na riles, kung ang istasyon ay magbabayad ng multa ng isang (rubles) para sa isang oras na demurrage ng isang tren. Kung sakali, narito ang mga sagot: L syst. = 2 (komposisyon), W syst. = 1 (oras), L puntos = 4/3 (komposisyon), W pt = 2/3 (oras), L panlabas = 16/27 (komposisyon), W panlabas = 8/27 ≈ 0.297 (oras). Ang average na pang-araw-araw na parusa W para sa paghihintay ng mga tren sa mga panlabas na riles ay nakukuha sa pamamagitan ng pagpaparami ng average na bilang ng mga tren na dumarating sa istasyon bawat araw, ang average na oras ng paghihintay para sa mga tren sa mga panlabas na riles at ang oras-oras na multa a: W ≈ 14.2 a.

muling i-channel ang QS na may walang limitasyong pila.

Ganap na katulad ng problema 2, ngunit medyo mas kumplikado, ang problema ng n-channel QS na may walang limitasyong pila.

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

Mayroong isang pamamaraan ng kamatayan at pagpaparami, ngunit may isang walang katapusang bilang ng mga estado. Sabihin natin nang walang patunay ang natural na kondisyon para sa pagkakaroon ng mga huling probabilidad: ρ/ n n ≥ 1, ang pila ay lumalaki hanggang sa infinity.

Ipagpalagay natin na ang kundisyon ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 magkakaroon ng serye ng mga terminong naglalaman ng mga factorial, kasama ang kabuuan ng isang walang katapusang pagbaba ng geometric na pag-unlad na may denominator ρ/ n. Summing it up, nahanap natin

(20.22)

Ngayon, hanapin natin ang mga katangian ng kahusayan ng QS. Sa mga ito, pinakamadaling mahanap ang average na bilang ng mga channel na inookupahan k= λ/μ, = ρ (ito ay karaniwang totoo para sa anumang QS na may walang limitasyong pila). Hanapin ang average na bilang ng mga application sa system L system at ang average na bilang ng mga application sa queue L och. Sa mga ito, mas madaling kalkulahin ang pangalawa, ayon sa formula

L och =

pagsasagawa ng kaukulang pagbabago ayon sa sample ng problema 2

(na may pagkakaiba-iba ng serye), nakukuha namin:

L och = (20.23)

Pagdaragdag dito ng average na bilang ng mga application na nasa ilalim ng serbisyo (ito rin ang average na bilang ng mga abalang channel) k =ρ, nakukuha namin ang:

L syst = L och + ρ. (20.24)

Paghahati ng mga ekspresyon para sa L och at L syst sa λ , gamit ang formula ni Little, nakukuha namin ang average na oras ng paninirahan ng isang application sa queue at sa system:

(20.25)

Ngayon lutasin natin ang isang kawili-wiling halimbawa. Ang opisina ng tiket sa tren na may dalawang bintana ay isang dalawang channel na QS na may walang limitasyong pila na itinatakda kaagad sa dalawang bintana (kung libre ang isang bintana, kukunin ito ng susunod na pasahero sa linya). Ang takilya ay nagbebenta ng mga tiket sa dalawang punto: A at AT. Ang tindi ng daloy ng mga aplikasyon (mga pasaherong gustong bumili ng tiket) para sa parehong mga punto A at B ay pareho: λ A = λ B = 0.45 (pasahero kada minuto), at sa kabuuan ay bumubuo sila ng pangkalahatang daloy ng mga aplikasyon na may intensity na λ A + λB = 0.9. Ang isang cashier ay gumugugol ng isang average ng dalawang minuto sa paglilingkod sa isang pasahero.

Ipinapakita ng karanasan na naipon ang mga pila sa opisina ng tiket, nagrereklamo ang mga pasahero tungkol sa kabagalan ng serbisyo. PERO at sa SA, lumikha ng dalawang espesyal na opisina ng tiket (isang window sa bawat isa), nagbebenta ng mga tiket ng isa - hanggang sa punto lamang PERO, ang isa - hanggang sa punto lamang AT. Ang pagiging maayos ng panukalang ito ay kontrobersyal - ang ilan ay nangangatuwiran na ang mga pila ay mananatiling pareho. Kinakailangang suriin ang pagiging kapaki-pakinabang ng panukala sa pamamagitan ng pagkalkula. Dahil nagagawa nating kalkulahin ang mga katangian para lamang sa pinakasimpleng QS, ipagpalagay natin na ang lahat ng mga daloy ng kaganapan ay ang pinakasimpleng (hindi ito makakaapekto sa husay na bahagi ng mga konklusyon).

Kung gayon, bumaba tayo sa negosyo. Isaalang-alang ang dalawang opsyon para sa pag-aayos ng mga benta ng tiket - ang umiiral at ang iminungkahing isa.

Pagpipilian I (umiiral). Ang isang dalawang-channel na QS ay tumatanggap ng daloy ng mga aplikasyon na may intensity na λ = 0.9; intensity ng daloy ng pagpapanatili μ = 1/2 = 0.5; ρ = λ/μ = l.8. Dahil ρ/2 = 0.9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0.0525. Ang average, ang bilang ng mga application sa queue ay matatagpuan sa pamamagitan ng formula (20.23): L och ≈ 7.68; ang average na oras na ginugol ng customer sa pila (ayon sa una sa mga formula (20.25)), ay katumbas ng W pts ≈ 8.54 (min.).

Pagpipilian II (iminungkahing). Kinakailangang isaalang-alang ang dalawang single-channel na QS (dalawang dalubhasang bintana); bawat isa ay tumatanggap ng daloy ng mga kahilingan na may intensity λ = 0.45; μ . katumbas pa rin ng 0.5; ρ = λ/μ = 0.9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8.1.

Narito ang isa para sa iyo! Ang haba ng pila, hindi lang nabawasan, nadagdagan pa! Siguro ang average na oras ng paghihintay sa pila ay nabawasan? Tingnan natin. Delya L puntos sa λ = 0.45, nakukuha namin W pts ≈ 18 (minuto).

Iyan ang rasyonalisasyon! Sa halip na bumaba, parehong tumaas ang average na haba ng pila at ang average na oras ng paghihintay dito!

Subukan nating hulaan kung bakit ito nangyari? Pagkatapos ng pag-iisip tungkol dito, dumating tayo sa konklusyon: nangyari ito dahil sa unang variant (two-channel QS) ang average na bahagi ng oras na ang bawat isa sa dalawang cashier ay idle ay mas kaunti: kung hindi siya abala sa paglilingkod sa isang pasahero na bumibili isang tiket sa punto PERO, kaya niyang asikasuhin ang pasaherong bibili ng ticket to the point SA, at vice versa. Sa pangalawang variant, walang ganoong pagpapalitan: ang isang walang tao na cashier ay nakaupo lamang nang walang ginagawa sa...

- Well , OK, ang mambabasa ay handa na sumang-ayon, ang pagtaas ay maaaring ipaliwanag, ngunit bakit ito ay napakahalaga? Mayroon bang maling kalkulasyon dito?

At sasagutin natin ang tanong na ito. Walang mali. Ang katotohanan , na sa aming halimbawa, parehong gumagana ang mga QS sa limitasyon ng kanilang mga kakayahan; kung bahagyang taasan mo ang oras ng serbisyo (i.e., bawasan ang μ), hindi na nila makakayanan ang daloy ng mga pasahero, at ang pila ay magsisimulang lumaki nang walang katiyakan. At ang "dagdag na downtime" ng cashier sa isang kahulugan ay katumbas ng pagbaba sa kanyang produktibidad μ.

Kaya, ang resulta ng mga kalkulasyon, na sa una ay tila kabalintunaan (o kahit na hindi tama), ay lumalabas na tama at maipaliwanag.

Ang ganitong uri ng mga paradoxical na konklusyon, ang dahilan kung saan ay hindi nangangahulugang halata, ay mayaman sa teorya ng pagpila. Ang may-akda mismo ay paulit-ulit na "nagulat" sa mga resulta ng mga kalkulasyon, na kalaunan ay naging tama.

Sa pagmumuni-muni sa huling gawain, ang mambabasa ay maaaring maglagay ng tanong sa ganitong paraan: pagkatapos ng lahat, kung ang takilya ay nagbebenta ng mga tiket sa isang punto lamang, kung gayon, natural, ang oras ng serbisyo ay dapat bumaba, mabuti, hindi sa kalahati, ngunit hindi bababa sa medyo, ngunit naisip namin na ito pa rin ang average ay 2 (min.). Inaanyayahan namin ang isang mapiling mambabasa na sagutin ang tanong: magkano ang dapat bawasan para maging kumikita ang "proposisyon sa rasyonalisasyon"?

Muli, nagkikita kami, bagaman elementarya, ngunit problema pa rin sa pag-optimize. Sa tulong ng mga pansamantalang kalkulasyon, kahit na sa pinakasimpleng, mga modelo ng Markov, posible na linawin ang husay na bahagi ng kababalaghan - kung paano kumikita ang pagkilos, at kung paano ito hindi kumikita. Sa susunod na seksyon, ipapakilala namin ang ilang mga modelong elementarya na hindi Markovian na magpapalawak pa sa aming mga posibilidad.

Matapos maging pamilyar ang mambabasa sa mga pamamaraan para sa pagkalkula ng mga panghuling probabilidad ng estado at mga katangian ng kahusayan para sa pinakasimpleng QS (nakabisado niya ang pamamaraan ng kamatayan at pagpaparami at ang Little formula), maaari siyang mag-alok ng dalawa pang simpleng QS para sa independiyenteng pagsasaalang-alang.

Single-channel na QS na may limitadong pila. Ang problema ay naiiba lamang sa Problema 2 dahil ang bilang ng mga kahilingan sa pila ay limitado (hindi maaaring lumampas sa ilang ibinigay t). Kung may dumating na bagong kahilingan sa sandaling okupado na ang lahat ng lugar sa pila, iniiwan nito ang QS na hindi naihatid (tinanggihan).

Kinakailangang hanapin ang mga huling probabilidad ng mga estado (sa pamamagitan ng paraan, umiiral sila sa problemang ito para sa anumang ρ - pagkatapos ng lahat, ang bilang ng mga estado ay may hangganan), ang posibilidad ng pagkabigo R otk, ganap na bandwidth PERO, ang posibilidad na ang channel ay abala R zan, average na haba ng pila L och, ang average na bilang ng mga aplikasyon sa CMO L syst , average na oras ng paghihintay sa pila W och , average na oras ng paninirahan ng isang aplikasyon sa CMO W syst. Kapag kinakalkula ang mga katangian ng queue, maaari mong gamitin ang parehong pamamaraan na ginamit namin sa Problema 2, na may pagkakaiba na ito ay kinakailangan upang ibuod hindi isang walang katapusang pag-unlad, ngunit isang may hangganan.

Closed loop QS na may isang channel at m mga mapagkukunan ng aplikasyon. Para sa pagiging konkreto, itakda natin ang gawain sa sumusunod na anyo: isang manggagawa ang naglilingkod t mga makina, na ang bawat isa ay nangangailangan ng pagsasaayos (pagwawasto) paminsan-minsan. Ang intensity ng daloy ng demand ng bawat gumaganang makina ay katumbas ng λ . Kung ang makina ay wala sa ayos sa sandaling ang manggagawa ay malaya, agad siyang pumunta sa serbisyo.

Kung wala siya sa ayos sa sandaling abala ang manggagawa, pumipila siya at naghihintay na malaya ang manggagawa. Average na oras ng pag-setup t rev = 1/μ. Ang intensity ng daloy ng mga kahilingan na dumarating sa manggagawa ay depende sa kung gaano karaming mga makina ang gumagana. Kung ito ay gumagana k mga kasangkapan sa makina, ito ay katumbas ng kλ. Hanapin ang mga huling probabilidad ng estado, ang average na bilang ng mga gumaganang makina, at ang posibilidad na magiging abala ang manggagawa.

Tandaan na sa QS na ito, magkakaroon din ng mga huling probabilidad para sa anumang mga halaga ng λ at μ = 1/ t o, dahil ang bilang ng mga estado ng system ay may hangganan.

Ang prosesong stochastic ng Markov na may mga discrete states at tuloy-tuloy na oras na isinasaalang-alang sa nakaraang lecture ay nagaganap sa mga queuing system (QS).

Mga sistema ng pagpila - ito ay mga sistema kung saan ang mga kahilingan sa serbisyo ay natatanggap sa mga random na oras, habang ang mga natanggap na kahilingan ay sineserbisyuhan gamit ang mga channel ng serbisyo na magagamit sa system.

Ang mga halimbawa ng mga sistema ng pagpila ay:

• settlement at cash nodes sa mga bangko, negosyo;
• mga personal na computer na naghahatid ng mga papasok na aplikasyon o mga kinakailangan para sa paglutas ng ilang partikular na problema;
• mga istasyon ng serbisyo ng kotse; gasolinahan;
• mga kumpanya sa pag-audit;
• mga departamento ng inspeksyon sa buwis na kasangkot sa pagtanggap at pagpapatunay ng kasalukuyang pag-uulat ng mga negosyo;
• pagpapalitan ng telepono, atbp.

	Mga buhol	Mga kinakailangan
Ospital	mga order	Mga pasyente
Produksyon
Ang paliparan	Paglabas ng runway Mga puntos sa pagpaparehistro	Mga pasahero

Isaalang-alang ang pamamaraan ng pagpapatakbo ng QS (Larawan 1). Ang sistema ay binubuo ng isang request generator, isang dispatcher at isang service node, isang failure accounting node (terminator, request destroyer). Ang isang service node ay karaniwang maaaring magkaroon ng ilang mga channel ng serbisyo.

kanin. isa

1. Tagabuo ng Application – isang bagay na bumubuo ng mga aplikasyon: isang kalye, isang workshop na may mga naka-install na unit. Ang input ay daloy ng aplikasyon(ang daloy ng mga customer sa tindahan, ang daloy ng mga sirang unit (mga kotse, mga kagamitan sa makina) para sa pag-aayos, ang daloy ng mga bisita sa wardrobe, ang daloy ng mga sasakyan sa mga istasyon ng gasolina, atbp.).
2. Dispatcher – isang tao o device na alam kung ano ang gagawin sa ticket. Isang node na kumokontrol at nagdidirekta ng mga kahilingan sa mga channel ng serbisyo. Dispatcher:

• tumatanggap ng mga aplikasyon;
• bumubuo ng isang pila kung ang lahat ng mga channel ay abala;
• nagtuturo sa kanila sa mga channel ng serbisyo, kung mayroon man;
• tumanggi sa mga aplikasyon (para sa iba't ibang dahilan);
• tumatanggap ng impormasyon mula sa node ng serbisyo tungkol sa mga libreng channel;
• sinusubaybayan ang oras ng system.

1. Lumiko - humiling ng accumulator. Maaaring wala ang pila.
2. Service node ay binubuo ng isang may hangganang bilang ng mga channel ng serbisyo. Ang bawat channel ay may 3 estado: libre, abala, idle. Kung abala ang lahat ng channel, maaari kang makabuo ng diskarte kung kanino ililipat ang application.
3. Pagtanggi mula sa serbisyo ay nangyayari kung abala ang lahat ng channel (maaaring hindi gumana ang ilan sa mga ito).

Bilang karagdagan sa mga pangunahing elementong ito sa QS, nakikilala rin ng ilang mapagkukunan ang mga sumusunod na bahagi:

terminator - tagasira ng mga transaksyon;

bodega - imbakan ng mga mapagkukunan at mga natapos na produkto;

accounting account - para sa pagsasagawa ng mga operasyon ng uri ng "pag-post";

tagapamahala - tagapamahala ng mga mapagkukunan;

Pag-uuri ng CMO

Ang unang dibisyon (sa pamamagitan ng pagkakaroon ng mga pila):

• CMO na may mga pagkabigo;
• CMO na may pila.

AT CMO na may mga pagkabigo ang isang kahilingan na dumarating sa sandaling abala ang lahat ng channel ay tinanggihan, umalis sa QS, at hindi na ihahatid pa.

AT CMO na may pila ang isang application na dumarating sa oras na ang lahat ng mga channel ay abala ay hindi umaalis, ngunit pumila at naghihintay ng pagkakataon na maihatid.

QS na may mga pila ay nahahati sa iba't ibang uri depende sa kung paano nakaayos ang pila - limitado o hindi limitado. Ang mga paghihigpit ay maaaring nauugnay sa parehong haba ng pila at oras ng paghihintay, "disiplina sa serbisyo."

Kaya, halimbawa, ang mga sumusunod na QS ay isinasaalang-alang:

• QS na may naiinip na mga kahilingan (limitado ang haba ng pila at oras ng serbisyo);
• QS na may priyoridad na serbisyo, ibig sabihin, ang ilang mga aplikasyon ay inihahatid nang wala sa oras, atbp.

Maaaring pagsamahin ang mga uri ng paghihigpit sa pila.

Ang isa pang pag-uuri ay naghahati sa CMO ayon sa pinagmulan ng mga aplikasyon. Ang system mismo o ilang panlabas na kapaligiran na umiiral nang hiwalay sa system ay maaaring makabuo ng mga aplikasyon (mga kinakailangan).

Naturally, ang daloy ng mga kahilingan na nabuo ng system mismo ay depende sa system at sa estado nito.

Bilang karagdagan, ang mga SMO ay nahahati sa bukas CMO at sarado SMO.

Sa isang bukas na QS, ang mga katangian ng daloy ng mga aplikasyon ay hindi nakasalalay sa estado ng QS mismo (kung gaano karaming mga channel ang abala). Sa isang saradong QS, umaasa sila. Halimbawa, kung ang isang manggagawa ay nagpapanatili ng isang pangkat ng mga makina na paminsan-minsan ay nangangailangan ng pagsasaayos, kung gayon ang tindi ng daloy ng "mga kinakailangan" mula sa mga makina ay nakasalalay sa kung ilan sa mga ito ang nasa maayos na at naghihintay ng pagsasaayos.

Isang halimbawa ng isang saradong sistema: ang pagbibigay ng suweldo ng isang cashier sa isang negosyo.

Sa bilang ng mga channel, nahahati ang QS sa:

• single-channel;
• multichannel.

Mga katangian ng sistema ng pagpila

Ang mga pangunahing katangian ng isang queuing system ng anumang uri ay:

• ang input stream ng mga papasok na kinakailangan o mga kahilingan sa serbisyo;
• disiplina sa pila;
• mekanismo ng serbisyo.

Stream ng input ng mga kinakailangan

Upang ilarawan ang input stream, kailangan mong itakda isang probabilistikong batas na tumutukoy sa pagkakasunud-sunod ng mga sandali ng pagtanggap ng mga kinakailangan sa serbisyo, at ipahiwatig ang bilang ng mga naturang paghahabol sa bawat regular na resibo. Sa kasong ito, bilang panuntunan, nagpapatakbo sila sa konsepto ng "probabilistic distribution ng mga sandali ng pagtanggap ng mga kinakailangan". Dito maaari kang kumilos tulad ng solong at pangkat na mga kinakailangan (ang bilang ng mga naturang claim sa bawat sunod-sunod na resibo). Sa huling kaso, karaniwang pinag-uusapan natin ang tungkol sa isang sistema ng pagpila na may parallel-group na serbisyo.

A i– oras ng pagdating sa pagitan ng mga kinakailangan – independiyenteng magkaparehong ibinahagi na mga random na variable;

E(A) ay ang mean (MO) na oras ng pagdating;

λ=1/E(A)- ang intensity ng pagtanggap ng mga kinakailangan;

Mga katangian ng input stream:

1. Isang probabilistikong batas na tumutukoy sa pagkakasunud-sunod ng mga sandali ng pagtanggap ng mga kinakailangan sa serbisyo.
2. Ang bilang ng mga kahilingan sa bawat susunod na pagdating para sa mga multicast na daloy.

Disiplina sa pila

Lumiko - isang hanay ng mga kinakailangan na naghihintay na maserbisyuhan.

May pangalan ang pila.

Disiplina sa pila tinutukoy ang prinsipyo ayon sa kung saan ang mga kahilingan na dumarating sa input ng sistema ng serbisyo ay konektado mula sa pila hanggang sa pamamaraan ng serbisyo. Ang pinakakaraniwang ginagamit na mga disiplina sa pila ay tinutukoy ng mga sumusunod na patakaran:

• unang dumating - unang nagsilbi;

first in first out (FIFO)

ang pinakakaraniwang uri ng pila.

Anong istraktura ng data ang angkop para sa paglalarawan ng naturang queue? Ang array ay masama (limitado). Maaari kang gumamit ng istraktura ng LIST.

Ang listahan ay may simula at wakas. Ang listahan ay binubuo ng mga entry. Ang entry ay isang list cell. Dumating ang application sa dulo ng listahan, at pinili para sa serbisyo mula sa simula ng listahan. Ang entry ay binubuo ng isang paglalarawan ng application at isang link (isang index ng kung sino ang nasa likod nito). Bilang karagdagan, kung ang pila ay may limitasyon sa oras, dapat ding tukuyin ang limitasyon sa oras.

Ikaw, bilang mga programmer, ay dapat na makagawa ng mga listahan na may dalawang panig, isang panig.

Listahan ng mga aksyon:

• ipasok sa buntot;
• kumuha mula sa simula;
• alisin sa listahan pagkatapos ng timeout.
• huling dumating, unang nagsilbi LIFO (cartridge clip, dead end sa istasyon ng tren, pumasok sa isang buong kotse).

Isang istraktura na kilala bilang isang STACK. Maaaring ilarawan sa pamamagitan ng isang array o istraktura ng listahan;

• random na pagpili ng mga aplikasyon;
• pagpili ng mga aplikasyon ayon sa priyoridad na pamantayan.

Ang bawat aplikasyon ay nailalarawan, bukod sa iba pang mga bagay, sa pamamagitan ng isang antas ng priyoridad at, sa pagdating, ay inilalagay hindi sa buntot ng pila, ngunit sa dulo ng priority group nito. Ang dispatcher ay nag-uuri ayon sa priyoridad.

Mga katangian ng pila

• limitasyonoras ng paghihintay ang sandali ng paglitaw ng serbisyo (may isang pila na may limitadong oras ng paghihintay para sa serbisyo, na nauugnay sa konsepto ng "tinatanggap na haba ng pila");
• haba ng pila.

Mekanismo ng serbisyo

Mekanismo ng serbisyo ay tinutukoy ng mga katangian ng mismong pamamaraan ng serbisyo at ang istraktura ng sistema ng serbisyo. Kasama sa mga pamamaraan ng pagpapanatili ang:

• bilang ng mga channel ng serbisyo ( N);
• ang tagal ng pamamaraan ng serbisyo (probabilistikong pamamahagi ng oras ng serbisyo ng mga kinakailangan);
• ang bilang ng mga kinakailangan na nasiyahan bilang isang resulta ng pagpapatupad ng bawat naturang pamamaraan (para sa mga aplikasyon ng grupo);
• ang posibilidad ng pagkabigo ng channel ng paghahatid;
• istraktura ng sistema ng serbisyo.

Para sa isang analytical na paglalarawan ng mga katangian ng pamamaraan ng serbisyo, ang konsepto ng "probabilistikong pamamahagi ng oras ng serbisyo ng mga kinakailangan" ay ginagamit.

Si- oras ng serbisyo i ika kinakailangan;

E(S)- average na oras ng serbisyo;

μ=1/E(S)- ang bilis ng mga kinakailangan sa serbisyo.

Dapat tandaan na ang oras para sa pagseserbisyo sa isang aplikasyon ay nakasalalay sa likas na katangian ng aplikasyon mismo o sa mga kinakailangan ng kliyente at sa estado at mga kakayahan ng sistema ng paglilingkod. Sa ilang mga kaso kinakailangan din na isaalang-alang probabilidad ng pagkabigo ng channel ng serbisyo pagkatapos ng isang tiyak na limitadong agwat ng oras. Ang katangiang ito ay maaaring imodelo bilang isang stream ng mga pagkabigo na pumapasok sa QS at may priyoridad sa lahat ng iba pang kahilingan.

Salik sa paggamit ng QS

Nμ – rate ng serbisyo sa system kapag abala ang lahat ng service device.

ρ=λ/( Nμ) ay tinatawag Salik sa paggamit ng QS , ay nagpapakita kung gaano karaming mga mapagkukunan ng system ang ginagamit.

Istraktura ng sistema ng serbisyo

Ang istraktura ng sistema ng serbisyo ay tinutukoy ng bilang at magkaparehong pag-aayos ng mga channel ng serbisyo (mga mekanismo, mga aparato, atbp.). Una sa lahat, dapat bigyang-diin na ang isang sistema ng serbisyo ay maaaring hindi isang channel ng serbisyo, ngunit marami; ang isang sistema ng ganitong uri ay kayang maghatid ng ilang mga kinakailangan nang sabay-sabay. Sa kasong ito, ang lahat ng mga channel ng serbisyo ay nag-aalok ng parehong mga serbisyo, at, samakatuwid, maaari itong maitalo na mayroon parallel service .

Halimbawa. Mga cash register sa tindahan.

Ang sistema ng serbisyo ay maaaring binubuo ng ilang iba't ibang uri ng mga channel ng serbisyo kung saan dapat pumasa ang bawat kinakailangang serbisyo, ibig sabihin, sa sistema ng serbisyo ang mga pamamaraan ng paglilingkod sa mga kinakailangan ay ipinatupad nang sunud-sunod . Tinutukoy ng mekanismo ng serbisyo ang mga katangian ng papalabas (naihatid) na stream ng mga kahilingan.

Halimbawa. Komisyong Medikal.

Pinagsamang Serbisyo - pagseserbisyo ng mga deposito sa savings bank: una ang controller, pagkatapos ay ang cashier. Bilang isang patakaran, 2 controllers bawat cashier.

Kaya, ang functionality ng anumang queuing system ay tinutukoy ng mga sumusunod na pangunahing salik :

• probabilistikong pamamahagi ng mga sandali ng pagtanggap ng mga kahilingan sa serbisyo (single o grupo);
• mga kinakailangan mapagkukunan kapasidad;
• probabilistikong pamamahagi ng oras ng tagal ng serbisyo;
• configuration ng system ng serbisyo (parallel, serial o parallel-serial service);
• ang bilang at pagganap ng mga channel ng paghahatid;
• disiplina sa pila.

Ang pangunahing pamantayan para sa pagiging epektibo ng paggana ng QS

Bilang ang pangunahing pamantayan para sa pagiging epektibo ng paggana ng mga sistema ng pagpila Depende sa uri ng problemang nilulutas, maaaring mayroong:

• ang posibilidad ng agarang serbisyo ng natanggap na aplikasyon (P serbisyo =K obs /K post);
• ang posibilidad ng pagtanggi sa serbisyo ng natanggap na aplikasyon (P otk =K otk /K post);

Malinaw na R obl + P otk =1.

Mga daloy, pagkaantala, serbisyo. Pollacek–Khinchin formula

Pagkaantala – isa sa mga pamantayan sa serbisyo ng QS, ang oras na ginugol ng kahilingan sa pag-asam ng serbisyo.

D i– pagkaantala sa queue ng kahilingan i;

W i \u003d D i + S i– oras na ginugol sa sistema ng pangangailangan i.

(na may posibilidad na 1) ay ang itinatag na average na pagkaantala ng isang kahilingan sa pila;

(na may probabilidad 1) ay ang steady-state na average na oras na ginugugol ng kinakailangan sa QS (paghihintay).

Q(t) - ang bilang ng mga kahilingan sa pila sa isang pagkakataon t;

L(t)– bilang ng mga customer sa system sa isang pagkakataon t(Q(t) kasama ang bilang ng mga kinakailangan na nasa serbisyo sa panahong iyon t.

Pagkatapos ay mga exponents (kung mayroon man)

(na may probabilidad 1) ay ang steady-state time-average na bilang ng mga kahilingan sa queue;

(na may probabilidad 1) ay ang steady-state na time-average na bilang ng mga kahilingan sa system.

Tandaan na ang ρ<1 – обязательное условие существования d, w, Q at L sa sistema ng pagpila.

Kung matatandaan natin na ρ= λ/( Nμ), pagkatapos ay malinaw na kung ang intensity ng pagtanggap ng mga kahilingan ay mas malaki kaysa sa Nμ, pagkatapos ay ρ>1, at natural na ang system ay hindi makayanan ang ganoong daloy ng mga aplikasyon, at samakatuwid, ang isa ay hindi maaaring magsalita ng d, w, Q at L.

Ang pinaka-pangkalahatan at kinakailangang mga resulta para sa mga sistema ng pagpila ay kinabibilangan ng mga equation ng konserbasyon

Dapat tandaan na ang mga pamantayan sa itaas para sa pagsusuri ng pagganap ng system ay maaaring analytically kalkulahin para sa queuing system M/M/N(N>1), ibig sabihin, mga system na may Markov na daloy ng mga customer at serbisyo. Para sa M/G/ l para sa anumang pamamahagi G at para sa ilang iba pang mga sistema. Sa pangkalahatan, ang distribusyon ng oras sa pagitan ng mga pagdating, ang distribusyon ng oras ng serbisyo, o pareho ay dapat na exponential (o isang uri ng exponential Erlang distribution ng kth order) para maging posible ang isang analytical na solusyon.

Bilang karagdagan, maaari mo ring pag-usapan ang mga katangian tulad ng:

• absolute throughput ng system – А=Р service *λ;
• relatibong throughput ng system -

Isa pang kawili-wiling (at naglalarawan) na halimbawa ng isang analytical na solusyon – pagkalkula ng steady-state average queue delay para sa isang queuing system M/G/ 1 ayon sa formula:

.

Sa Russia, ang formula na ito ay kilala bilang ang Pollacek formula. – Khinchin, sa ibang bansa ang formula na ito ay nauugnay sa pangalan ni Ross.

Kaya, kung E(S) ay may mas malaking halaga, pagkatapos ay ang labis na karga (sinusukat sa kasong ito bilang d) ay magiging mas malaki; na dapat asahan. Ang formula ay nagpapakita rin ng isang hindi gaanong halatang katotohanan: tumataas din ang kasikipan kapag tumataas ang pagkakaiba-iba sa pamamahagi ng oras ng serbisyo, kahit na ang average na oras ng serbisyo ay nananatiling pareho. Intuitively, ito ay maaaring ipaliwanag tulad ng sumusunod: ang pagkakaiba-iba ng service time random variable ay maaaring magkaroon ng malaking halaga (dahil ito ay dapat na positibo), ibig sabihin, ang tanging service device ay magiging abala sa mahabang panahon, na hahantong sa pagtaas sa pila.

Ang paksa ng teorya ng pagpila ay ang pagtatatag ng ugnayan sa pagitan ng mga salik na tumutukoy sa functionality ng queuing system, at ang kahusayan ng paggana nito. Sa karamihan ng mga kaso, ang lahat ng mga parameter na naglalarawan ng mga sistema ng pagpila ay mga random na variable o function, kaya ang mga system na ito ay tinutukoy bilang mga stochastic system.

Ang random na likas na katangian ng daloy ng mga aplikasyon (mga kinakailangan), pati na rin, sa pangkalahatang kaso, ang tagal ng serbisyo ay humahantong sa katotohanan na ang isang random na proseso ay nangyayari sa sistema ng pagpila. Sa pamamagitan ng likas na katangian ng random na proseso ang nagaganap sa isang queuing system (QS) ay nakikilala Markov at non-Markov system . Sa mga sistema ng Markov, ang papasok na daloy ng mga kahilingan at ang papalabas na daloy ng mga serbisyong kahilingan (claims) ay Poisson. Ang mga daloy ng Poisson ay nagpapadali sa paglalarawan at pagbuo ng isang mathematical na modelo ng isang queuing system. Ang mga modelong ito ay may medyo simpleng solusyon, kaya karamihan sa mga kilalang aplikasyon ng teorya ng queuing ay gumagamit ng Markov scheme. Sa kaso ng mga di-Markovian na proseso, ang mga problema sa pag-aaral ng mga sistema ng pagpila ay nagiging mas kumplikado at nangangailangan ng paggamit ng istatistikal na pagmomodelo, mga pamamaraang numero gamit ang isang computer.