Systémy hromadné obsluhy s omezenou kapacitou
1. Systém M/M/n/m/FIFO
Vstupní proud zákazníků je Poissonův proces s parametrem , doba obsluhy se
řídí rozložením  Ex , v systému je n linek obsluhy, kapacita systému je
omezená (je rovna m) a frontový režim je „první vstupuje, první je obsloužen“.
Označme


 ,
n

 . Systém se může stabilizovat vždy.
Stacionární rozložení:











m,1,njproa
n!
n
n,1,2,jproa
!j
a
0
j
n
0
j
j


, kde
 

 


 1n
0j
m
nj
j
nj0
!n
n
!j
1
a .
Charakteristiky stabilizovaného systému:
Pravděpodobnost, že přicházející zákazník bude odmítnut: 0
m
n
Z a
!n
n
P  .
Pravděpodobnost, že přicházející zákazník bude čekat ve frontě:
 










1pronma
1pro
1
1
a
P
n
nm
n
Q .
Střední hodnota počtu přijatých zákazníků za jednotku času:  ZP P1 .
Střední hodnota počtu odmítnutých zákazníků za jednotku času: ZZ P .
Střední hodnota počtu zákazníků ve frontě:    

m
1nj
nQ anjNE .
Střední hodnota počtu obsluhovaných zákazníků:    ZS P1NE  .
Využití systému:  ZP1 .
Ostatní charakteristiky dostaneme pomocí Littleova vzorce.
function[a,PZ,PQ,lambdaP,lambdaZ,kappa,ENS,ENQ,EN,EWS,EWQ,EW]=odmitani(lambda,mi,n,m)
% [a,PZ,PQ,lambdaP,lambdaZ,kappa,ENS,ENQ,EN,EWS,EWQ,EW]=odmitani(lambda,mi,n,m)
% Vypočítá stacionární rozložení, využití a charakteristiky SHO 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 ........ pst, že příchozí zákazník bude odmítnut
% PQ ........ pst, že příchozí zákazník bude čekat ve frontě
% lambdaP ... střední hodnota počtu přijatých zákazníků za jednotku času
% lambdaZ ... střední hodnota počtu odmítnutých zákazníků za jednotku času
% ENS ....... střední hodnota počtu obsluhovaných zákazníků
% ENQ ....... střední hodnota počtu zákazníků ve frontě
% EN ........ střední hodnota počtu zákazníků v systému
% EWS ....... střední hodnota doby, kterou zákazník stráví obsluhou
% EWQ ....... střední hodnota doby, kterou zákazník stráví ve frontě
% EW ........ střední hodnota doby, kterou zákazník stráví v systému
beta=lambda/mi;
ro=beta/n;
a(1)=inv(sum(beta.^(0:n-1)./factorial(0:n-1))+n^n/factorial(n)*sum(ro.^(n:m)));
a(2:n+1)=(beta.^(1:n)./factorial(1:n))*a(1);
a(n+2:m+1)=(n^n/factorial(n))*ro.^(n+1:m)*a(1);
PZ=a(m+1);
if ro==1
PQ=a(n+1)*(m-n);
else
PQ=a(n+1)*(1-ro^(m-n))/(1-ro);
end;
lambdaP=lambda*(1-PZ);
lambdaZ=lambda*PZ;
kappa=ro*(1-PZ);
ENS=beta*(1-PZ);
ENQ=sum(((n+1:m)-n).*a(n+2:m+1));
EN=ENQ+ENS;
EW=EN/lambda;
EWS=ENS/lambda;
EWQ=ENQ/lambda;
Příklad 1.: V autoservisu jsou 3 mycí rampy a jeden pracovník, jemuž mytí auta
trvá v průměru 12 min. Za 1 h přijedou průměrně 3 auta. Jsou-li však
v okamžiku příjezdu auta všechny rampy obsazeny, auto nečeká a vrací se
později.
a) Jaká je pravděpodobnost, že v autoservisu budou 0, 1, 2, 3 auta?
b) Vypočtěte střední hodnotu počtu zákazníků v autoservisu a ve frontě.
c) Vypočtěte střední hodnotu doby čekání ve frontě.
d) Jaká je pravděpodobnost, že bude volná aspoň jedna rampa?
e) Vypočtěte využití systému.
Řešení: Jde o systém M/M/n/m/FIFO, kde n = 1, m = 3.
5
3
,
5
3
,5,3 
ad a)
272
27
a,
272
45
a,
272
75
a,
272
125
a 3210 
ad b)    
272
99
NE,
272
246
NE Q 
ad c)   s18min7
272
33
WE Q 
ad d)
272
245
a1 3 
ad e) 54,0
272
147

Úlohy řešte pomocí funkce odmitani.m.
Návod na řešení pomocí MATLABu:
lambda=3;mi=5;n=1;m=3;
[a,PZ,PQ,lambdaP,lambdaZ,kappa,ENS,ENQ,EN,EWS,EWQ,EW]=odmitani(lambda,mi,n,m)
Příklad 2.: Na parkoviště s maximální kapacitou 40 míst přijíždí v období
ustáleného provozu průměrně 20 aut za 1 h. Střední hodnota doby pobytu auta
na parkovišti je 2,5 h. Za předpokladu, že příjezdy aut na parkoviště tvoří
Poissonův proces a doba pobytu na parkovišti se řídí exponenciálním
rozložením, vyřešte následující úlohy:
a) Na kolik procent je parkoviště využíváno?
b) Jaký je průměrný počet volných parkovacích míst?
c) Jaký je průměrný počet odmítnutých vozidel za 1 h provozu parkoviště?
Úlohy řešte pomocí funkce odmitani.m.
Výsledek:
Ad a) Parkoviště je využito na 93,8 %.
Ad b) V průměru jsou volná dvě parkovací místa.
Ad c) Za hodinu provozu parkoviště je v průměru odmítnuto 5 aut.
2. Uzavřený systém M/M/n/m/FIFO
V systému je 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.
Doba pobytu každého zákazníka mimo systém se řídí rozložením  Ex , doba
obsluhy každé linky se řídí rozložením  Ex .
Označme


 ,
n

 .
Stacionární rozložení:
 















m,,2n,1njproa
!jm!n
!mn
n,,2,1jproa
j
m
a
0
n
0
j
j


, kde 

m
1j
j0 a1a
Pravděpodobnost, že přicházející zákazník bude čekat ve frontě:
 


1!n
aP
n
0Q
Charakteristiky stabilizovaného systému:
Střední hodnota počtu zákazníků v systému:   

m
0j
jjaNE .
Střední hodnota počtu obsluhovaných zákazníků:    



m
nj
j
1n
0j
jS anjaNE .
Střední hodnota počtu zákazníků mimo systém:    NEmNE R  .
Střední hodnota počtu zkazníiů přicházejících za jednotku času (intenzita
vstupního proudu):  RR NE .
Využití systému:  RNE .
Ostatní charakteristiky dostaneme pomocí Littleova vzorce.
function[a,ENS,ENR,EN,lambdaR,kappa]=uzavreny(lambda,mi,n,m);
% [a,ENS,ENR,EN,lambdaR,kappa]=uzavreny(lambda,mi,n,m)
%
% Vypočítá stacionární rozložení, využití a charakteristiky uzavřeného systému
% hromadné obsluhy s omezenou kapacitou M|M|n|m|FIFO.
%
% 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
% (intenzita vstupního proudu zákazníků)
% kappa ..... využití systému
beta=lambda/mi;
ro=beta/n;
for k=2:m+1
if k<=n+1
x(k)=nchoosek(m,k-1)*beta^(k-1);
else
x(k)=n^n/factorial(n)*factorial(m)/factorial(m-k+1)*ro^(k-1);
end;
end;
a(1)=1/(1+sum(x));
for k=2:m+1
a(k)=x(k)*a(1);
end;
ENS=sum((0:n-1).*a(1:n))+n*sum(a(n+1:m+1));
EN=sum((0:m).*a);
ENR=m-EN;
lambdaR=lambda*ENR;
kappa=ro*ENR;
Příklad 3.: Skupinu pěti stejných strojů má na starosti jeden údržbář. Doba
bezporuchového provozu stroje má exponenciální rozložení se střední hodnotou
1/2 směny a doba opravy má rovněž exponenciální rozložení se střední
hodnotou 1/20 směny.
a) Jaká je pravděpodobnost, že všechny stroje pracují?
b) Jaká je pravděpodobnost, že budou současně vyřazeny aspoň dva stroje?
Řešení: Jde o uzavřený systém M/M/n/m/FIFO, kde n = 1, m = 5.
10
1
,
10
1
,20,2 
a1 = 0,5a0, a2 = 0,2a0, a3 = 0,06a0, a4 = 0,012a0, a5 = 0,0012a0,
a0(1 + 0,5 + 0,2 + 0,06 + 0,012 + 0,0012) = 1, tedy a0 = 0,564
ad a) P(N = 0) = a0 = 0,564
ad b) P(N ≥ 2) = a2 + a3 + a4 + a5 = 0,154
Úlohy řešte pomocí funkce uzavreny.m.
Návod na řešení pomocí MATLABu:
lambda=2;mi=20;n=1;m=5;
function[a,ENS,ENR,EN,lambdaR,kappa]=uzavreny(lambda,mi,n,m);
Příklad 4.: V uzavřeném systému M/M/n/m/FIFO, kde n = 1, m = 2, 2,3 
vypočtěte stacionární rozložení a základní charakteristiky systému.
Úlohy řešte pomocí funkce uzavreny.m.
Výsledek:
Stacionární rozložení: 






17
9
,
17
6
,
17
2
a
Střední hodnota počtu zákazníků v systému je 1,41.
Střední hodnota počtu obsluhovaných zákazníků je 0,88.
Střední hodnota počtu zákazníků ve frontě je 0,53.
Střední hodnota počtu zákazníků mimo systém je 0,59.
Intenzita vstupního proudu zákazníků je 1,76.
Systém je využit na 88 %.
Optimalizace systému M/M/1/∞/FIFO
Nechť ve stabilizovaném systému M/M/1/∞/FIFO jsou známy tyto
náklady:
c1 … náklady na obsluhu jednoho požadavku,
c2 … náklady na údržbu prázdného systému.
Předpokládáme, že intenzita vstupního proudu zákazníku je λ. Cílem
je najít takovou intenzitu obsluhy μ, aby celkové náklady na provoz
systému údržbu prázdného systému byly minimální.
Zavedeme funkci nákladů a ztrát:
 


 21 ccF . Hledáme minimum této funkce vzhledem k μ.
Funkci derivujeme podle μ a derivaci položíme rovnu 0. Zjistíme, že
minima bude dosaženo pro 
1
2
c
c
.
function[mi,F]=opt_neomezeny_1(lambda,c1,c2);
% [mi,F]=opt_neomezeny_1(lambda,c1,c2)
%
% Vypočítá optimální intenzitu obsluhy a hodnotu funkce nákladů
% a ztrát (při této intenzitě) systému hromadné obsluhy M|M|1|Inf|FIFO.
%
% Vstupní parametry:
% lambda .... parametr vstupního proudu
% c1 ........ náklady na obsluhu jednoho požadavku
% c2 ........ náklady na údržbu prázdného systému za časovou jednotku
%
% Výstupní parametry:
% mi ........ optimální intenzita obsluhy
% F ......... hodnota funkce nákladů a ztrát při optimální intenzitě
% obsluhy (minimální celkové průměrné náklady na provoz systému
% a údržbu prázdného systému)
mi=lambda+sqrt(c2*lambda/c1);
ro=lambda/mi;
if ro<1
F=c1*mi+c2*lambda/(mi-lambda);
else
error('Systém se nemůže stabilizovat. Intenzita provozu je větší než 1.')
end;
Příklad 5.: Sledujeme činnost výdejny nářadí ve strojírenském závodě. Náklady
na obsluhu jednoho požadavku činí 2 Kč, ztráty z prostojů jsou 10 Kč/h.
Průměrně má výdejna 8 požadavků za 1 h. Najděte:
a) optimální intenzitu obsluhy,
b) hodnotu funkce nákladů a ztrát při této optimální intenzitě obsluhy.
Řešení: λ = 8, c1 = 2, c2 = 10
Ad a) 32,144088
2
10
8
c
c
1
2

Výdejna musí obsloužit průměrně 14,32 požadavku z 1 h provozu, tj. jeden
požadavek musí být odbaven v průměru za 0,0698 h = 4,188 min = 4 min 11 s.
Ad b)   30,41
832,14
8
1032,142ccF 21 





Celkové náklady a ztráty za 1 h provozu výdejny nářadí činí 41,30 Kč.
Návod na řešení pomocí MATLABu:
lambda=8;c1=2;c2=10;
[mi,F]=opt_neomezeny_1(lambda,c1,c2);
Příklad 6.: V dílně dochází v průměru ke třem poruchám strojů za hodinu.
Prostojové náklady stroje jsou 1000 Kč za hodinu. Můžeme volit mezi
průměrným opravářem, který opravuje čtyři stroje za hodinu a stojí i s režií 500
Kč za hodinu a zkušeným opravářem, který opravuje pět strojů za hodinu a stojí
i s režií 650 Kč za hodinu. Kterého z nich je výhodnější přijmout?
Návod: Rozhodněte podle funkce nákladů a ztrát.
Výsledek: Pro průměrného opraváře nabývá funkce nákladů a ztrát hodnoty
5 000 Kč, pro zkušeného pak 4 750, je tedy výhodnější přijmout zkušeného
opraváře.
Optimalizace systému M/M/n/∞/FIFO
Nechť ve stabilizovaném systému M/M/n/∞/FIFO jsou známy tyto
náklady:
k1 … náklady na čekajícíh zákazníka,
k2 … náklady na nevyužitou linku obsluhy.
Předpokládáme, že intenzita vstupního proudu zákazníku je λ,
intenzita obsluhy je μ. Cílem je najít takový počet linek obsluhy, při
němž jsou průměrné celkové náklady minimální.
Zavedeme tzv. kriteriální funkci:
      S2Q1 NEnkNEknC  .
Víme, že  
 2nQQ
1
a
1
PNE





 a    nNE S .
Po dosazení do kriteriální funkce dostaneme:
 
 
 


 1nk
1
a
knC 22
n
1 .
Systém se může stabilizovat, když



n
1 , tedy


n . Hledáme n*
tak, aby
   









 Nn,n;nCminnC *
.
function[C]=opt_neomezeny_n(n,lambda,mi,k1,k2);
% [C]=opt_neomezeny_n(n,lambda,mi,k1,k2)
%
% Vypočítá hodnotu kriteriální funkce v systému hromadné
% obsluhy M|M|n|Inf|FIFO.
%
% Vstupní parametry:
% n ......... počet linek obsluhy
% lambda .... parametr vstupního proudu
% mi ........ parametr obsluhy
% k1 ........ náklady na čekajícího zákazníka
% k2 ........ náklady na nevyužitou linku obsluhy
%
% Výstupní parametry:
% C ......... hodnota kriteriální funkce pro n linek obsluhy
% (celkové průměrné náklady na provoz systému)
beta=lambda/mi;
ro=beta/n;
if ro<1
a0=inv(sum(beta.^(0:n-1)./factorial(0:n-1))+n*beta^n/factorial(n)/(n-beta));
an=beta^n*a0/factorial(n);
C=k1*an*ro/(1-ro)^2+k2*(n-n*ro);
else
error('Systém se nemůže stabilizovat. Intenzita provozu je větší než 1.')
end;
Příklad 7.: Začínající softwarová firma může očekávat 4 objednávky za měsíc.
Charakter objednávek je takový, že programátor je schopen vyřešit za měsíc
průměrně dvě objednávky. Měsíční náklady na provizorní řešení, kdy zákazník
čeká na konečné řešení, jsou 50 000 Kč. Nemá-li programátor práci, dostává
základní plat 10 000 Kč z rezervního fondu firmy. V případě, že programátor má
objednávku, je základní plat plus výkonnostní příplatek zcela pokryt z ceny
objednávky. Při jakém počtu programátorů budou průměrné náklady firmy
minimální?
Řešení: λ = 4, μ=2, k1=50000, k2=10000,
n
2
n
,2 




 . Aby se systém
mohl stabilizovat, musí ve firmě pracovat aspoň tři programátoři.
Výsledky shrneme do tabulky:
n ρ an C(n)
3 2/3 4/27 54 444,44 Kč
4 1/2 2/23 28 695,65 Kč
5 2/5 12/335 31 990, 05 Kč
6 1/3 4/333 40 450,45 Kč
Vidíme, že optimální počet programátorů je roven 4.
Návod na řešení pomocí MATLABu:
lambda=4;mi=2;k1=50000;k2=10000;n=3;
Příklad 8.: V nově otevřené pobočce České spořitelny bylo rozhodnuto
rezervovat pro operace se sporožirovým účtem 3 přepážky. Klienti pro tyto
operace, kteří do pobočky přicházejí, se řadí do jedné fronty a po uvolnění
libovolné z přepážek mohou být obsluhováni. Po otevření pobočky bylo
zjištěno, že klienti přicházejí s průměrnou intenzitou 68 osob za 1 h s tím, že
intervaly mezi jejich příchody mají exponenciální rozložení. Doba nutná pro
odbavení klienta je náhodná veličina s exponenciálním rozložením se střední
hodnotou 2 min 24 s. Za předpokladu, že náklady na pobyt klienta v pobočce po
dobu 1 h jsou 120 Kč a náklady na provoz jedné přepážky za 1 h jsou 300 Kč,
najděte optimální počet přepážek.
Výsledek: Optimální jsou 4 přepážky.