9. Optimalizace v systémech hromadné obsluhy
Cíl: před linkami obsluhy se nemají vytvářet příliš dlouhé fronty a současně linky obsluhy mají
být dostatečně využity.
Je-li malá intenzita obsluhy, tvoří se dlouhá fronta a klesá zisk.
Je-li naopak velká intenzita obsluhy, jsou linky obsluhy po určitou dobu nevyužity a stoupají
náklady.
Potřebujeme tedy v systému s jednou linkou obsluhy zajistit optimální intenzitu obsluhy a
v systému s více linkami optimální počet linek obsluhy tak, aby při minimálních nákladech bylo
dosaženo maximálního zisku.
9.1. Optimalizace systému M/M/1/∞/FIFO
Vstupní proud zákazníků je Poissonův proces s parametrem λ, doba obsluhy se řídí
exponenciálním rozložením.
Ve stabilizovaném systému známe:
náklady c1 na obsluhu jednoho požadavku;
náklady c2 na údržbu prázdného systému za jednotku času.
Ve většině případů je intenzita vstupního proudu λ dána, můžeme tedy ovlivnit pouze intenzitu
obsluhy µ.
Hledáme intenzitu obsluhy µ tak, aby funkce nákladů a ztrát
( ) ( )
λ−µ
λ
+µ=+µ=µ 2121 ccNEccF
nabývala svého minima.
Funkci ( )µF derivujeme podle µ a derivaci položíme rovnu 0:
( )
( )
λ±λ=µ⇒=
λ−µ
λ
−=
µ
µ
1
2
221
c
c
0cc
d
dF
Vzhledem k tomu, že systém musí být schopen se stabilizovat (tj. µ<λ ), je minima dosaženo
pro λ+λ=µ
1
2
c
c
. (Jedná se skutečně o minimum, což lze ověřit pomocí 2. derivace:
( )
( )
0
2
c
d
Fd
322
2
>
λ−µ
λ
=
µ
µ
.)
9.2. Příklad: Na malou poštu s jednou přepážkou přichází v období ustáleného provozu
průměrně 18 klientů za 1 h. Náklady na obsluhu jednoho klienta činí 20 Kč a prostojové náklady
na přepážku jsou 40 Kč/h. Stanovte optimální dobu obsluhy jednoho klienta a vyčíslete funkci
nákladů a ztrát pro optimální intenzitu obsluhy.
Řešení: λ = 18, c1 = 20, c2 = 40
2461818
20
40
18
c
c
1
2
=+=⋅+=λ+λ=µ zákazníků za 1 h
s30min2h
24
11
==
µ
( ) Kč600
1824
18
40242024F =
−
⋅+⋅=
Optimální doba obsluhy zákazníka je 2 minuty 30 sekund. Pro tuto optimální dobu obsluhy činí
hodnota funkce nákladů a ztrát 600 Kč.
9.3. Poznámka: Uvedeme ještě jiný přístup k optimalizační úloze. Vedle nákladů c1 a c2
budeme uvažovat ještě náklady c3, což jsou náklady orientované na udržení zákazníka za
jednotku času. Budeme hledat takovou intenzitu provozu µ
λ
=ρ , při níž jsou celkové průměrné
náklady minimální.
Zavedeme kriteriální funkci
( ) ( )
ρ−
ρ
+ρ−+ρ=ρ
1
c1ccC 321
Hledáme minimum kriteriální funkce vzhledem k ρ:
( )
( ) 12
3
2321
cc
c
10
1
1
ccc
d
dC
−
±=ρ⇒=
ρ−
+−=
ρ
ρ
Případ
12
3
cc
c
1
−
+=ρ nevyhovuje, protože ve stabilizovaném systému 1<ρ . Tedy optimální
intenzita provozu je
12
3
cc
c
1
−
−=ρ , přičemž 1
cc
c
0
12
3
<
−
< .
Pomocí 2. derivace kriteriální funkce ověříme, že jde skutečně o minimum:
( )
( )
0
1
2
c
d
Cd
332
2
>
ρ−
=
ρ
ρ
pro
12
3
cc
c
1
−
−=ρ .
9.4. Příklad: Malá stavební firma s jedním zaměstnancem očekává v příštím měsíci tyto
náklady: penalizace úvěrující bankou za nečinnost je 150 000 Kč, náklady na plat zaměstnance
jsou 50 000 Kč a náklady na reklamu 10 000 Kč. Za jakých podmínek může mít firma minimální
náklady?
Řešení:
c1 = 50 000, c2 = 150 000, c3 = 10 000
683,0
10
1
1
50000150000
10000
1
cc
c
1
12
3
=−=
−
−=
−
−=ρ .
Minimální náklady při této intenzitě provozu činí
( ) ( ) ( ) 103246
683,01
683,0
10000683,01150000683,050000
1
c1ccC 321 =
−
⋅+−⋅+⋅=
ρ−
ρ
+ρ−+ρ=ρ Kč.
Intenzita obsluhy tedy musí být λ=
λ
=µ 464,1
683,0
.
Znamená to, že intenzita obsluhy musí být takřka 1,5 x vyšší než intenzita vstupu.
9.5. Příklad: Sledujeme činnost výdejny nářadí ve strojírenském závodě. Náklady na obsluhu
jednoho požadavku činí 20 Kč, ztráty z prostojů jsou 100 Kč/h. V průměru má výdejna 8
požadavků za 1 h.
Uvažujeme následující 4 varianty činnosti výdejny:
varianta I: neomezená kapacita systému, optimální intenzita obsluhy;
varianta II: ve frontě mohou být maximálně 2 požadavky, optimální intenzita obsluhy;
varianta III: ve výdejně jsou 2 okénka, systém má neomezenou kapacitu, intenzita obsluhy je
poloviční než vypočtená optimální;
varianta IV: ve výdejně jsou 2 okénka, ve frontě mohou být maximálně 2 požadavky, intenzita
obsluhy je poloviční než vypočtená optimální.
Pro každou z těchto variant vypočtěte:
- pravděpodobnost, že systém je prázdný;
- využití systému;
- E(N), E(NQ), E(NS);
- E(W), E(WQ), E(WS);
- pravděpodobnost odmítnutí požadavku;
- celkové náklady a ztráty za 1 h provozu.
Řešení:
100c,20c,8 21 ===λ , 32,1410288
20
100
8
c
c
1
2
=+=⋅+=λ+λ=µ požadavků za 1 h
Varianta I: Jde o systém M/M/1/∞/FIFO, λ = 8, µ = 14,32
Použijeme funkci neomezeny_1.m
a0 = 0,4415
κ = 55,85 %
E(N) = 1,2649
E(NQ) = 0,7064
E(NS) = 0,5585
E(W) = 0,1581 h = 9 min 29 s
E(WQ) = 0,0883 h = 5 min 18 s
E(WS) = 0,0698 h = 4 min 11 s
PZ = 0
F(µ) = c1µ + c2 E(N) = 20(8 + 2√10) + 100.1,2649 = 412,98 Kč
Varianta II: Jde o systém M/M/1/3/FIFO, λ = 8, µ = 8 + 2√10, n = 1, m = 3
Použijeme funkci odmitani.m
a0 = 0,4891
κ = 51,09 %
E(N) = 0,8338
E(NQ) = 0,3229
E(NS) = 0,5109
E(W) = 0,11139 h = 6 min 50 s
E(WQ) = 0,0441 h = 2 min 39 s
E(WS) = 0,0698 h = 4 min 11 s
PZ = 0,0852
F(µ) = c1µ + c2 E(N) = 20(8 + 2√10) + 100.0,8338 = 369,87 Kč
Varianta III: Jde o systém M/M/2/∞/FIFO, λ = 8, µ = (8 + 2√10)/2, n = 2
Použijeme funkci neomezeny_n.m
a0 = 0,2833
κ = 55,85 %
E(N) = 1,6233
E(NQ) = 0,5063
E(NS) = 1,1170
E(W) = 0,2029 h = 12 min 10 s
E(WQ) = 0,0633 h = 3 min 48 s
E(WS) = 0,1396 h = 8 min 22 s
PZ = 0
F(µ) = c1µ + c2 E(N) = 10(8 + 2√10) + 100.1,6233 = 305,58 Kč
Varianta IV: Jde o systém M/M/2/4/FIFO, λ = 8, µ = (8 + 2√10)/2, n = 2, m = 4
Použijeme funkci odmitani.m
a0 = 0,3045
κ = 52,54 %
E(N) = 1,2754
E(NQ) = 0,2246
E(NS) = 1,0508
E(W) = 0,1555 h = 9 min 20 s
E(WQ) = 0,0159 h = 57 s
E(WS) = 0,1396 h = 8 min 23 s
PZ = 0,0593
F(µ) = c1µ + c2 E(N) = 10(8 + 2√10) + 100.1,2754 = 270,79 Kč
Shrnutí výsledků:
typ a0 κ E(N) E(NQ) E(NS) E(W) E(WQ) E(WS) PZ F(µ)
I 0,4415 55,85 % 1,2649 0,7064 0,5585 9 min 29 s 5 min 18 s 4 min 11 s 0 413 Kč
II 0,4891 51,09 % 0,8338 0,3229 0,5109 6 min 50 s 2 min 39 s 4 min 11 s 8,52 % 370 Kč
III 0,2833 55,85 % 1,6233 0,5063 1,1170 12 min 10 s 3 min 48 s 8 min 22 s 0 306 Kč
IV 0,3045 52,54 % 1,2754 0,2246 1,0508 9 min 20 s 0 min 57 s 8 min 23 s 5,93 % 271 Kč
9.6. Optimalizace systému M/M/n/∞/FIFO
Vstupní proud zákazníků je Poissonův proces s parametrem λ, doba obsluhy se řídí
exponenciálním rozložením s parametrem µ. Známe:
c1 … náklady na čekajícího zákazníka za jednotku času,
c2 … náklady na nevyužitou linku obsluhy za jednotku času.
Cílem je najít takový počet linek obsluhy, při němž jsou průměrné celkové náklady minimální.
Zavedeme kriteriální funkci ( ) ( ) ( )[ ]S2Q1 NEncNEcnC −+= .
První sčítanec vyjadřuje průměrné náklady na čekajícího zákazníka. Ty jsou úměrné střední
hodnotě počtu zákazníků ve frontě.
Druhý sčítanec vyjadřuje průměrné náklady na nevyužití linky obsluhy. Ty jsou úměrné střední
hodnotě počtu nevyužitých linek.
Přitom ( )
ρ−
ρ
=
1
PNE QQ , ( ) ρ−
=
ρ−
β
=
1
a
1!n
aP n
n
0Q , µ
λ
=β , n
β
=ρ , ( )
1
1n
0j
nj
0
n!n
n
!j
a
−
−
=






β−
β
+
β
= ∑ , ( ) ρ= nNE S .
Po dosazení do kriteriální funkce dostaneme:
( )
( )
( )ρ−+
ρ−
ρ
= nnc
1
a
cnC 22
n
1
Systém se může stabilizovat, když µ
λ
=
β
=ρ>
nn
1 , tedy µ
λ
>n . Hledáme n*
tak, že
( ) ( )






∈
µ
λ
>= Nn,n;nCminnC *
.
9.7. Příklad: Začínající softwarová firma může očekávat 4 objednávky za měsíc. Charakter
objednávky 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 rezervního fondu firmy základní plat 10 000 Kč.
V případě, že programátor má objednávku, je jeho 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é měsíční náklady
stabilizované firmy minimální?
Řešení:
n
2
n
,2,10000c,50000c2,,4 21 =
β
=ρ=
µ
λ
=β===µ=λ , ( )
( )
( )ρ−+
ρ−
ρ
= nnc
1
a
cnC 22
n
1 ,
0
n
n a
!n
a
β
= , ( ) ( )
1
1n
0j
nj
1
1n
0j
nj
0
n!n
2n
!j
2
n!n
n
!j
a
−
−
=
−
−
=






β−
+=





β−
β
+
β
= ∑∑
Z podmínky stability plyne, že minimální počet programátorů je 3.
n = 3: 3
2
=ρ , 9
1
6
83
221a
1
0 =




 ⋅
+++=
−
, 27
4
9
1
6
8
a
!3
a 0
3
3 =⋅=
β
=
( )
( ) 9
8
27
24
27
4
1
aNE
9
1
3
2
23Q ==⋅=
ρ−
ρ
= , ( ) 2
3
2
3nNE S =⋅=ρ=
( ) ( ) 4,544442310000
9
8
500003C =−+= Kč
n = 4: 2
1
=ρ , 23
3
224
164
3
4
221a
1
0 =





⋅
⋅
++++=
−
, 23
2
23
3
24
16
a
!4
a 0
4
4 =⋅=
β
=
( )
( ) 23
4
23
2
1
aNE
4
1
2
1
24Q =⋅=
ρ−
ρ
= , ( ) 2
2
1
4nNE S =⋅=ρ=
( ) ( ) 65,286952410000
23
4
500004C =−+= Kč
n = 5: 5
2
=ρ , 67
9
3120
325
3
2
3
4
221a
1
0 =





⋅
⋅
+++++=
−
, 335
12
67
9
120
32
a
!5
a 0
5
5 =⋅=
β
=
( )
( ) 201
8
335
12
1
aNE
25
9
5
2
25Q =⋅=
ρ−
ρ
= , ( ) 2
5
2
5nNE S =⋅=ρ=
( ) ( ) 05,319902510000
201
8
500005C =−+= Kč
n = 6: 3
1
=ρ , 37
5
15
2
15
4
3
2
3
4
221a
1
0 =





++++++=
−
, 333
4
37
5
720
64
a
!6
a 0
6
6 =⋅=
β
=
( )
( ) 111
1
333
4
1
aNE
9
4
3
1
26Q =⋅=
ρ−
ρ
= , ( ) 2
3
1
6nNE S =⋅=ρ=
( ) ( ) 45,404502610000
111
1
500006C =−+= Kč
Shrnutí výsledků:
n ρ an C(n)
3 6,0
3
2
= 1481,0
27
4
=
54 444,44 Kč
4 5,0
2
1
= 0870,0
23
2
=
28 695,65 Kč
5 4,0
5
2
= 0358,0
335
12
=
31 990,05 Kč
6 3,0
3
1
= 0120,0
333
4
=
40 450,45 Kč
Vidíme, že optimální počet programátorů je 4.