8. Systémy hromadné obsluhy s omezenou kapacitou 8.1. Systém M/M/l/1 Vstupní proud zákazníků je Poissonův proces s parametrem X, doba obsluhy se řídí exponenciálním rozložením s parametrem ji, v systému je 1 linka obsluhy, kapacita systému je 1 (zákazník nemůže čekat ve frontě a přijde-li k obsazenému systému, vůbec nečeká a odchází). Počet zákazníků v systému v čase t lze modelovat HMR se spojitým časem {Xt;teT} f-l X ^ s množinou stavů J = {0, 1} a maticí přechodu Q = Stacionární rozložení dostaneme ve tvaru: a = X ^ V X + ji X + ji J Význam složek stacionárního rozložení: a0 - [i a, = X + [i X X + \x pravděpodobnost, že v systému není žádný zákazník pravděpodobnost, že v systému je právě 1 zákazník = pravděpodobnost, že přicházející zákazník bude odmítnut = Pz Charakteristiky systému: Střední hodnota počtu přijatých zákazníků za jednotku času: Ap - Xzio Střední hodnota počtu odmítnutých zákazníků za jednotku času: Xz = Aai _ X Využití systému: K - Pao - — ao Střední hodnota počtu zákazníků v systému: E(N) = 0 • a0 +1 • ax = ax = ^ T7/wx_e(n)_ 1 Střední hodnota doby strávené v systému: byw) - —^— - ^ 8.2. Příklad: Je známo, že počet příchozích hovorů na jistou telefonní linku se řídí Poissonovým rozložením, přičemž v průměru přichází 1 hovor za 1 h. Dále je známo, že doba trvání hovoru se řídí exponenciálním rozložením a hovor trvá v průměru 20 minut. Jestliže je linka obsazená, nový volající okamžitě zavěsí. Vypočtěte, jaké procento lidí se nedovolalo. Řešení: Za časovou jednotku zvolíme 1 h. Pak^ = 1, (-i = 3 5 P 3< systém se může stabilizovat. X 1 ^cq/ ai = = 4 = 25 /o. Nedovolá se 25 % lidí. 8.3. Systém M/M/l/m/FIFO Vstupní proud zákazníků je Poissonův proces s parametrem X, doba obsluhy se řídí exponenciálním rozložením s parametrem ji, v systému je 1 linka obsluhy, systém má kapacitu m a frontový režim je FIFO. Je-li systém obsazen, další zákazníci odcházejí bez obsloužení. Ve frontě může být nejvýše m - 1 zákazníků. Počet zákazníků, kteří jsou v systému v okamžiku t, je náhodná veličina Xt a stochastický proces {Xt;teT} je HMR se spojitým časem, množinou stavů J = {0, 1, m}, vektorem počátečních pravděpodobností p(0) = (1, 0, 0, 0) a maticí intenzit přechodu Í-X X 0 0 . . 0 0 ^ - (X + ji) X 0 . . 0 0 Q = 0 -(X + \x) X . . 0 0 v0 0 0 0 . • n Označme P ~ Odvodíme stacionární rozložení tohoto systému. Vyřešíme systém rovnic aQ = 0 s normalizační podmínkou 5>i = i j=o a zjistíme, že j 1 ao _-~ Hodnotu a0 odvodíme z normalizační podmínky: a- = Í-T a0 -PJao,i = l ? ? • • • ? m. 1 m j=i j=o •v j . Rada ve jmenovateli je m konečná a její součet je j 1-p m+1 1-p pro p ^ 1 í-p m + 1 pro p = 1 tedy a0=< 1-P* 1 m + 1 -propal pro p = 1 Charakteristiky systému m Stř. hodnota počtu zákazníků v systému: E^~ §^aj p[l-(m + l)pm + mpm+1] (l-p)(l-pm+1) pro p 1 m lyProp = l m Stř. hodnota počtu zákazníků ve frontě: e(nq)= IIG-'K = E(N)-(1"ao) = e(n)-^^ propal 1-P e(n) m m +1 pro p = 1 Stř. hodnota počtu obsloužených zákazníků: ap = a(l-am), Pm(!-P) 1 - pm+* Pr° P 1 1 pro p = 1 .m +1 Stř. hodnota doby strávené v systém 3mu: e(w) = 4^ ve frontě: e(wq) = ^^ ap ap Pravdčp., že zákazník nebude obsloužen (tj. v systému je již m požadavků): am = a^1 Pravdčp., že zákazník bude obsloužen: 1 - am 8.4. Příklad: Během osmihodinové směny dojde v průměru ke 12 poruchám strojů. Oprava trvá v průměru půl hodiny. Pokud je opravář obsazen, ve frontě na opravu mohou čekat maximálně tři stroje. Stanovte základní charakteristiky systému. Řešení: Jde o systém M/M/1/4/FIFO. Za časovou jednotku volíme 1 h. A, = —= l,5,*i = —= 2,p = - = —= 0,75,m = 4 8 0,5 n 2 a = 1_P = 1-0,75 =0327.». Pravděpodobnost, že opravář je volný: 0 i _ pm+1 1 - 0 755 ' Pravděpodobnost, že stroj nebude opraven v důsledku omezené kapacity systému: a4 = a0p4 = 0,1037 Stř. hodnota počtu opravených strojů: ^P = ^(l - am) = l,5(l - 0,1037) = 1,3444 Stř. hodnota počtu strojů v systému: e(n) = = = ^ Stř. hodnota počtu strojů ve frontě: e(nq) = e(n)- p(l_~lJ = 1,4443- ^"^ľ ^ = 0>7721 / x lín) 14443 Stř. hodnota doby strávené v systému: E(w) = -y^ = = ^0743h =lh 4mm 30s eit^ ) 0 7721 Stř. hodnota doby strávené ve frontě: e(wq) = -y2- = = °>5743h = 34mm 30s 8.5. Otevřený systém M/M/n/m/FIFO Kapacita systému s n linkami je omezená, je rovna m, m > n. Zákazník, který přijde k plně obsazenému systému je odmítnut. Ve frontě tedy může být nejvýše m - n > 0 zákazníků. Počet zákazníků, kteří jsou v systému v okamžiku t, je náhodná veličina Xt a stochastický proces {Xt;teT} je HMR se spojitým časem, množinou stavů J = {0, 1, ..., m}, vektorem počátečních pravděpodobností p(0) = (1, 0, 0, ..., 0) a maticí intenzit přechodu /-A A 0 .. 0 0 0 .. 0 0 \ -(A< + A) A .. 0 0 0 .. 0 0 0 -(2/A + A) . 0 0 0 .. 0 0 Q = . . . ... ... ..... . . . ... ..... . . . 0 0 0 .. nfi —(nu + A) A . 0 0 0 0 0 0 71/:/ -(/i/i + A) . 0 0 _ \0 0 0 0 0 0 -nfij kde X > 0 je intenzita vstupního proudu a u. > 0 je intenzita obsluhy. Je-li v systému víc zákazníků než linek obsluhy (j > n, j < m), jsou intenzity obsluhy stejné jako pro j = n. Přechodový diagram: -(M+A) -(2M+A) -j = i j=o aj=< J ■a0 pro j = 1,2,...,n n11 : . , , kde ao pJa0 pro j = n + l,...,m a n — n X^+-rXp Stacionární rozložení existuje vždy. Charakteristiky stabilizovaného systému: n Pravděpodobnost, že přicházející zákazník bude odmítnut: = am - n m n!Pa»- Pravděpodobnost, že přicházející zákazník bude čekat ve frontě: PQ = < an propal 1-p an(m-n)prop = 1 Střední hodnota počtu přijatých zákazníků za jednotku času: ^P = A,(l "Pz). Střední hodnota počtu odmítnutých zákazníků za jednotku času: Xz = XPZ. m Střední hodnota počtu zákazníků ve frontě: ^ v^Q / SO- n)a j=n+l j. Střední hodnota počtu obsluhovaných zákazníků: E(NS) = (3(l - Pz). Využití systému: k = p(l - Pz). Ostatní charakteristiky dostaneme pomocí Littleova vzorce. 8.6. Příklad: Na jistém oddělení nemocnice jsou na dvou operačních sálech nepřetržitě prováděny urgentní operace. Na každém sále se v průměru operují 4 pacienti za den a na oddělení přichází v průměru 7 pacientů za den. Přitom z organizačních důvodů bylo stanoveno, že na pořadníku může být maximálně 10 pacientů, ostatní jsou odesíláni jinam. Určete základní charakteristiky tohoto systému hromadné obsluhy. Řešení: Za časovou jednotku volíme 1 den. _(3_7 Jde o systémM/M/n/m/FIFO, kden = 2, m=10 + 2=12, X = 7, |i = 4, P"77"7,P"~"Ř. Pravděpodobnost, že systém je prázdný: í n-l Q) m Y* ( 1 (l\ ^2 12 Y1 a0 - n-l OJ „n m \ 1 V u v ~ J! n! J=n J ®2 V - j! 2! J=2 = 0,0821 J Pravděpodobnost, že pacient bude odeslán jinam: Pz = am = n n! Pma0 = 2V7^12 2! v8y 0,0821 = 0,0331 Pravděpodobnost, že pacient bude čekat: PQ=ani^ = a2l^ = ^a0i# = ^0,082ll^ = 0,7411 Q n 1-p 2 1-p 2! 0 l-{ 2 1-| Střední hodnota počtu čekajících pacientů: . . m 12 12 12 e(nq)= SO " nK = SO - 2K = SO - 2)2(1^0 = SO - 2)2(1)0,0821 = 2,8729 j=n+l j=3 j=3 j=3 Pravděpodobnost, že oba sály budou obsazeny: P(N>2) = l-a0 -ax =l-a0 -(3a0 = 1-0,0821-{0,0821 = 0,7742 Využití systému: k = p(l - Pz) = }(l - 0,0331) = 0,8461 Střední hodnota počtu operovaných pacientů: E(NS) = p(l - Pz) = j(l - 0,0331) = 1,6921 Střední hodnota počtu pacientů v systému: E(N) = E(NS) + E(Nq) = 1,6921 + 2,8729 = 4,5651 Střední hodnota pročekané doby: / x EÍN0) EÍN0) 2,8729 EW0= —= / Q\= 9 = 0,4245dne = 10hllmin v Q/ ^P A,(l-Pz) 6,7683 cYw A- E(Ns)_ !'6921 Střední hodnota doby operace: bv Ws) ~ ~ 67683 " ~ Střední hodnota doby strávené v systému: E(W) = E(WS) + E(WQ) = 0,25 + 0,4245 = 0,6745 dne = 16 h 11 min Charakteristiky stabilizovaného systému M/M/n/m/FIFO počítá funkce odmitani.m % [a,PZ,PQ,lambdaP,lambdaZ,kappa,ENS,ENQ,EN,EWS,EWQ,EW]=odmitani(lambda,mi,n,m) % Vypočíta stacionární rozloženi, využiti a charakteristiky systému % hromadne obsluhy s omezenou kapacitou M|M|n|m|FIFO s odmítáním. % Vstupní parametry: % lambda .... parametr vstupního proudu % mi........parametr obsluhy % n.........počet linek obsluhy % m.........kapacita systému % Výstupní parametry: % a.........stacionární rozložení % PZ........pravděpodobnost, ze příchozí zákazník bude odmítnut % PQ........pravděpodobnost, ze příchozí zákazník bude cekat ve fronte % lambdaP ... strední hodnota poctu prijatých zákazníku za jednotku casu % lambdaZ ... strední hodnota poctu odmítnutých zákazníku za jednotku casu % ENS.......strední hodnota poctu obsluhovaných zákazníku % ENQ.......strední hodnota poctu zákazníku ve fronte % EN........strední hodnota poctu zákazníku v systému % EWS.......strední hodnota doby, kterou zákazník stráví obsluhou % EWQ.......strední hodnota doby, kterou zákazník stráví ve fronte % EW........strední hodnota doby, kterou zákazník strávi v systému 8.7. Příklad: Je známo, že systém M/M/2/5/FIFO je využíván na 68,62 %. a) Kolik procent přicházejících zákazníků bude odmítnuto? b) Zjistěte střední hodnotu počtu čekajících zákazníků. X Řešení: n = 2, m = 5, p = ^,P = ^ = |,k = p(l-Pz)= 0,6862 22 5 5 I5/ = as = — P a0 = 2p a0 = 2—a0 = 2! 2' p; 16 a o, tedy K = P(1-Pz)=| 5 A l--^a 16 o V = 0,6862 ^n-l OJ a0 - V v p n V J J=o j! n! J=n m A l 1 pj y Vj=° J! j=2 w dosadíme do vzorce pro k a dostaneme rovnici v1 / v ! O p' p' p' p 1 + B + —+ — + — + — 2 4 8 16 J 5 V1 Nyní a0 p 2 1- 16 V ! o p' p' p' p' 1 + B + —+ — + — + — 2 4 8 16; = 0,6862 K jejímu řešení použijeme symbolický toolbox systému MATLAB: syms x; solve(0.5*x*(l-(0.0625*xA5/(l+x+0.5*xA2+0.25*xA3+0.125*xA4+0.0625*xA5)))-0.6862) Zjistíme, že p = 1,5 a dále a0 = 0,1793. V úkolu (a) počítáme pravděpodobnost odmítnutí zákazníka, tedy P7 = a, = — p5a0 = 2p5a0 = 2^a0 = = — • OJ 793 = 0,0851 2! T 16 16 Vidíme, že bude odmítnuto 8,5 % přicházejících zákazníků. V úkolu (b) počítáme střední hodnotu počtu čekajících zákazníků, tj. m 3 e(nq) = Z0"n)aj =Z0_2)aj = a3+2a4+3a< j=n+l j=3 n & =—-pJa0 proj = n + l: n! a3 = 2p a0 = 2 ra\4 a4 = 2p4a0 = 2 a5 = 2p5a0 = 2 p p v2y m a0 = 2 a0 = 2 0,1793 = 0,1513 a0 = 2 v2y 1,5 0,1793 = 0,1135 0,1793 = 0,0851 v z y Po dosazení do vzorce pro E(Nq) máme: E(NQ ) = 0,1513 + 2 • 0,1135 + 3 • 0,0851 Znamená to, že v průměru čeká ve frontě 0,6336 zákazníků. 8.8. Uzavřený (cyklický) systém M/M/n/m/FIFO V tomto systému cirkuluje m zákazníků, přičemž mohou čekat v omezené frontě délky m-n > 0. Zákazníci po ukončení obsluhy opouštějí systém, ale později se do něj vracejí s novým požadavkem. Ilustrace: n linek obsluhy vstupní proud fronta výstupní proud Doba pobytu každého zákazníka mimo systém má rozložení Ex(k), doba obsluhy u každé z n linek obsluhy se řídí rozložením Ex(ji). Systém, lze modelovat pomocí procesu vzniku a zániku {Xt;teT} s množinou stavu J = {0, 1, ...,m}, kde stavy interpretujeme takto: 0 ... systém je prázdný 1 ... v systému je 1 obsluhovaný zákazník, ostatních m - 1 je mimo systém n ... v systému je n obsluhovaných zákazníků, ostatních m - n je mimo systém n+1 ... n obsluhovaných, 1 ve frontě, m - n -1 mimo systém m ... n obsluhovaných, m - n ve frontě Vektor počátečních pravděpodobností je p(0) = (1,0, ..., 0) a matice přechodu má tvar Q — -77? A 777 A 0 0 0 0 \ /' -(M + (m-l)A) . .. 0 0 0 0 0 2/j .. 0 0 0 0 0 0 n\x —(nfjL + (???. — n)\) (m — n)X 0 0 0 .. 0 — (nf-t + (77? — n — 1)A) (J V 0 0 0 0 0 -np) kde X > 0 je intenzita vstupního proudu a [i > 0 je intenzita obsluhy. Přechodový diagram: mA (m-1)A (m-2)A (m-n-M)A (m-n)A {m-n-1)A a -mA -(p+(m-1)A) -(2M+(m-2)A) -(np+(m-n)A) -(np+(m-r>-1)A) ""M Stacionární rozložení: Označme P ^ a P n . Obvyklým způsobem (tj. řešením systému aQ = 0, iLaJ ) odvodíme, že stacionární rozložení je: . pJa0pro j = l,2,...,n U J n11 m! i . ,kde ao =1_Zaj. —r-7-ä:P a0pro j = n + l,...,m h n! (m-jj! Stacionárni rozložení existuje vždy. Charakteristiky systému: m Střední hodnot počtu zákazníků v systému: j=o n-1 m Střední hodnota počtu obsluhovaných zákazníků: E(NS) X Jaj + nX aj. j=0 j=n Střední hodnota počtu zákazníků mimo systém: E(NR)=m-E(N). Střední hodnota počtu zákazníků přicházejících z jednotku času: XR=XE(NR) Využití systému: k = PE(NR). Další charakteristiky lze získat z Littleova vzorce. 8.9. Příklad: Ve firmě jsou k dispozici 2 kopírky pro 5 zaměstnanců, přičemž každý z nich přichází kopírovat v průměru jednou za 40 minut. Průměrná doba kopírování je 4 minuty. Předpokládáme, že vstupní proud je Poissonův proces a doba kopírování se řídí exponenciálním rozložením. a) Jaká je pravděpodobnost, že kopírky nebudou využity? b) Jaká je pravděpodobnost, že zaměstnanec, který přichází ke kopírkám, bude muset čekat? cj Jaká je střední hodnota délky fronty? Řešení: Za časovou jednotku volíme 1 min. n = 2, m = 5, . 1 1X1 (3 1 X = —,ji = -,p = — = — 40 4 n 10 P 20 • Vypočteme stacionární rozložení aj=< U J n* (3Ja0 proj = l,2,...,n m! m n! (m-j) i . , ,kde ao-1"!^ pJa0 pro j = n + l,...,m j=i 1 10 2 (5\ i ^ ^0 ~ ^0 ^2 v2y vlOy a, a4=2- 5ir i ^4 V 20y í A V a0 = 240 V 20y a, a, = 2— 5 0! 10 5! ŕ 1 ^ a. = 2— 2! ^ 1 A3 V 20y a0 = 240 V 20y 1 a0 =120 ŕ 1 A5 V 20y V 20y 5 a, a0 a0 = 1-Va-= 0,6186 j=i Ad a) Pravděpodobnost, že kopírky nebudou využity, je a0 = 0,6186. Ad b) pravděpodobnost, že zaměstnanec, který přichází ke kopírkám, bude muset čekat, je P(N > 2) = 1 - P(N < l) = 1 - a0 - a1 = 1 - 0,6186 - 0,3093 = 0,0721 Ad c) Střední hodnota délky fronty: E(Nq) = E(N) - E(NS), přičemž m n-1 m E(n)= £ja, = 0,4648 > E(ns) = Xja, + i& = 0,4535^ tedy e(n } = 00113 j=0 j=0 j=n Charakteristiky uzavřeného systému M/M/n/m/FIFO počítá funkce uzavřeny.m. Syntaxe: [a,ENS,ENR,EN,lambdaR,kappa]=uzavreny(lambda,mi,n,m) Vstupní parametry: lambda .... parametr vstupního proudu mi........parametr obsluhy n.........počet linek obsluhy m.........kapacita systému Výstupní parametry: a.........stacionární rozložení ENS.......střední hodnota počtu obsluhovaných zákazníků ENR.......střední hodnota počtu zákazníků mimo systém EN........střední hodnota počtu zákazníků v systému lambdaR ... střední hodnota počtu zákazníků přicházejících za jednotku času kappa.....využití systému