Gi¸o tr×nh M« h×nh ho¸
Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
55
Ch−¬ng 5- M« pháng hÖ thèng hμng ®îi
5.1- Kh¸i niÖm chung vÒ hÖ thèng hµng ®îi (Queueing System)
HÖ thèng hµng ®îi lµ hÖ thèng cã c¸c bé phËn phôc vô (Services) vµ c¸c kh¸ch hµng ®i
®Õn hÖ thèng (Arriving Customers) ®Ó ®−îc phôc vô. NÕu khi kh¸ch hµng ®Õn mµ c¸c bé phËn
phôc vô ®Òu bÞ bËn th× kh¸ch hµng sÏ xÕp hµng ®Ó ®îi ®−îc phôc vô. ChÝnh v× vËy hÖ thèng
nµy cã tªn gäi lµ hÖ thèng hµng ®îi. Lý thuyÕt to¸n häc ®Ó kh¶o s¸t c¸c hÖ hµng ®îi ®−îc gäi
lµ lý thuyÕt phôc vô ®¸m ®«ng (c¸c kh¸ch hµng ®−îc coi lµ mét ®¸m ®«ng ®−îc phôc vô).
Trong hÖ hµng ®îi kh¸ch hµng lµ sù kiÖn gi¸n ®o¹n x¶y ra t¹i c¸c thêi ®iÓm ngÉu nhiªn, v× vËy
hÖ hµng ®îi thuéc lo¹i hÖ c¸c sù kiÖn gi¸n ®o¹n.
5.2- C¸c thµnh phÇn chÝnh cña hÖ thèng hµng ®îi
H×nh 5.1 tr×nh bµy hÖ thèng hµng ®îi mét kªnh phôc vô
Trong thùc tÕ cã rÊt nhiÒu hÖ thèng cã thÓ ®−îc xem lµ hÖ thèng hµng ®îi. M« pháng hÖ
thèng hµng ®îi nh»m ®¸nh gi¸ n¨ng lùc lµm viÖc cña hÖ thèng, kh¶ n¨ng mÊt kh¸ch hµng do
ph¶i chê ®îi l©u hoÆc kh«ng cßn chç ®Ó xÕp hµng ®îi ®Õn l−ît ®−îc phôc vô. Trªn c¬ së nh÷ng
ph©n tÝch nh− vËy, ng−êi ta thiÕt kÕ hÖ thèng, chän sè kªnh phôc vô, n¨ng suÊt phôc vô, kÝch
th−íc hµng ®îi v.v.. nh»m ®¹t ®−îc hiÖu qu¶ tèi −u. B¶ng 5.1 tr×nh bµy mét sè hÖ thèng hµng
®îi
B¶ng 5.1
HÖ thèng Kªnh phôc vô Kh¸ch hµng
Ng©n hµng Nh©n viªn ng©n hµng Kh¸ch hµng
BÖnh viÖn B¸c sü, y t¸ BÖnh nh©n
HÖ thèng m¸y tÝnh CPU, thiÕt bÞ vµo ra D÷ liÖu
D©y chuyÒn s¶n xuÊt C«ng nh©n, m¸y mãc S¶n phÈm
C¶ng hµng kh«ng §−êng b¨ng, tr¹m kiÓm so¸t M¸y bay, hµnh kh¸ch
HÖ thèng liªn l¹c §−êng d©y, nh©n viªn Kh¸ch hµng
Siªu thÞ QuÇy hµng, quÇy tr¶ tiÒn Kh¸ch hµng
HÖ thèng hµng ®îi cã ba bé phËn chÝnh lµ:
1). Dßng kh¸ch hµng (Arriving Customers, Arrival Patterns): lµ c¸c phÇn tö, c¸c sù kiÖn
®i ®Õn hÖ thèng ®Ó ®−îc phôc vô - ®−îc gäi chung lµ kh¸ch hµng. §Æc tr−ng cho dßng kh¸ch
S
A
Kh¸ch hµn
g
Kh¸ch hµng
trong hµng ®îi
Kh¸ch hµng
®−îc phôc vô Kªnh
p
hôc vô Kh¸ch hµn
g
rêi
khái hÖ thèng
H
×nh 5.1- HÖ thèng hµng ®îi mét kªnh phôc vô
Gi¸o tr×nh M« h×nh ho¸
Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
56
hµng lµ c−êng ®é dßng kh¸ch hµng
λ
1/®¬n vÞ thêi gian. Dßng kh¸ch hµng lµ mét dßng c¸c sù
kiÖn gi¸n ®o¹n, ngÉu nhiªn, do ®ã kho¶ng c¸ch thêi gian gi÷a c¸c kh¸ch hµng còng lµ mét ®¹i
l−îng ngÉu nhiªn.
2). Kªnh phôc vô (Server): lµ c¸c bé phËn ®Ó phôc vô kh¸ch hµng, thùc hiÖn c¸c yªu cÇu
cña kh¸ch hµng. Thêi gian phôc vô (Service Time) vµ kho¶ng thêi gian gi÷a c¸c lÇn phôc vô lµ
nh÷ng biÕn ngÉu nhiªn. Tuú theo hÖ thèng cã mét hay nhiÒu ®iÓm phôc vô mµ ng−êi ta gäi lµ
hÖ thèng mét hoÆc nhiÒu kªnh phôc vô. §Æc tr−ng cho kªnh phôc vô lµ dßng phôc vô víi
c−êng ®é phôc vô lµ
μ
1/®¬n vÞ thêi gian. C−êng ®é phôc vô lµ sè kh¸ch hµng ®−îc phôc vô
xong trªn mét ®¬n vÞ thêi gian.
3). Hµng ®îi (Queue): lµ sè kh¸ch hµng chê ®Õn l−ît phôc vô. Tuú theo sè kh¸ch hµng
®Õn nhiÒu hay Ýt (c−êng ®é λ lín hay bÐ), kh¶ n¨ng phôc vô (sè kªnh phôc vô, thêi gian phôc
vô) mµ sè kh¸ch hµng ph¶i ®îi trong hµng ®îi nhiÒu hay Ýt. V× vËy ®é dµi cña hµng ®îi còng lµ
mét biÕn ngÉu nhiªn.
§Æc tr−ng cho hµng ®îi cã:
- ChiÒu dµi hµng ®îi: lµ sè kh¸ch hµng cã trong hµng ®îi ®ang chê ®Ó ®−îc phôc vô.
- Thêi gian ®îi: lµ kho¶ng thêi gian tõ khi kh¸ch hµng ®Õn hÖ thèng ®Õn khi b¾t ®Çu
®−îc phôc vô. Thêi gian ®îi cã thÓ ®−îc h¹n chÕ hoÆc kh«ng h¹n chÕ.
- LuËt xÕp hµng: lµ ph−¬ng thøc chän kh¸ch hµng trong hµng ®îi. Th«ng th−êng cã c¸c
luËt xÕp hµng nh− ®Õn tr−íc ®−îc phôc vô tr−íc, ®Õn sau ®−îc phôc vô tr−íc, ngÉu nhiªn, −u
tiªn... NÕu hÖ thèng cã nhiÒu kªnh phôc vô th× ph¶i cã luËt ph©n chia kh¸ch hµng gi÷a c¸c
kªnh phôc vô.
5.3- Dßng kh¸ch hµng (Customer)
Dßng kh¸ch hµng lµ mét trong nh÷ng bé phËn quan träng nhÊt cña hÖ thèng hµng ®îi.
Mét sè vÝ dô sau ®©y lµ c¸c dßng kh¸ch hµng:
- Dßng c¸c cuéc gäi cña mét tr¹m ®iÖn tho¹i.
- Dßng c¸c thiÕt bÞ ®iÖn gia dông (bµn lµ, tivi, radio, m¸y giÆt, nåi c¬m ®iÖn v.v.) nèi vµo
m¹ng ®iÖn cung cÊp.
- Dßng c¸c h− háng x¶y ra trong hÖ thèng m¸y tÝnh, hÖ thèng ®iÒu khiÓn.
- Dßng ®¹n ph¸o b¾n c¸c môc tiªu di ®éng.
- Dßng bÖnh nh©n ®Õn kh¸m bÖnh, kh¸ch hµng vµo nhµ hµng, siªu thÞ v.v..
Nh÷ng dßng nh− vËy ®−îc gäi lµ dßng sù kiÖn ngÉu nhiªn cã tr¹ng th¸i gi¸n ®o¹n x¶y ra
kÕ tiÕp nhau trong thêi gian liªn tôc, xem h×nh 5.2.
Trªn h×nh 5.2 chóng ta cã thÓ lÊy ®iÓm gèc thêi gian 0t ë bÊt kú ®iÓm nµo trªn trôc thêi
gian. C¸c dßng kh¸ch hµng mµ chóng ta xem xÐt trong ch−¬ng nµy th−êng cã thÓ ®−îc quy vÒ
t
H
×nh
5
.2. Dßng sù kiÖn gi¸n ®o¹n
0
Gi¸o tr×nh M« h×nh ho¸
Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
57
dßng sù kiÖn tèi gi¶n. Mét dßng tèi gi¶n cã ba tÝnh chÊt c¬ b¶n sau: dõng, kh«ng hËu qu¶ vµ
to¹ ®é.
- Dßng dõng lµ dßng mµ x¸c suÊt x¶y ra mét sè sù kiÖn nµo ®ã chØ phô thuéc vµo qu·ng
thêi gian t (xem h×nh 5.2) chø kh«ng phô thuéc vµo vÞ trÝ cña qu·ng thêi gian t trªn trôc thêi
gian. Cã nghÜa lµ trªn dßng dõng x¸c suÊt x¶y ra sù kiÖn lµ nh− nhau trªn suèt trôc thêi gian.
- Dßng kh«ng hËu qu¶ lµ dßng mµ sè sù kiÖn x¶y ra ®éc lËp nhau, cã nghÜa lµ sù kiÖn
x¶y ra t¹i thêi ®iÓm t1 kh«ng kÐo theo sù kiÖn x¶y ra t¹i thêi ®iÓm t2 vµ ng−îc l¹i.
- Dßng to¹ ®é lµ dßng c¸c sù kiÖn chØ x¶y ra t¹i mét to¹ ®é nhÊt ®Þnh. Cã nghÜa lµ t¹i
mét thêi ®iÓm chØ cã mét sù kiÖn x¶y ra, x¸c suÊt ®Ó cã hai hay nhiÒu sù kiÖn x¶y ra cïng mét
lóc lµ rÊt nhá cã thÓ bá qua.
Chó ý r»ng nÕu sù kiÖn x¶y ra kh«ng ph¶i lµ ngÉu nhiªn mµ theo mét quy luËt nµo ®ã, vÝ
dô ®Òu ®Æn c¸ch mét kho¶ng thêi gian T, nh÷ng dßng nh− vËy lµ dßng cã hËu qu¶. Ng−êi ta
chøng minh ®−îc r»ng tæng mét sè ®ñ lín dßng (dõng, to¹ ®é) cã hËu qu¶ h¹n chÕ sÏ cho mét
dßng tèi gi¶n (dõng, kh«ng hËu qu¶, to¹ ®é). Mét dßng dõng hoÆc kh«ng dõng, nh−ng kh«ng
hËu qu¶ vµ to¹ ®é ®−îc gäi lµ dßng Poisson. Trong dßng Poisson c−êng ®é sù kiÖn λ (sè sù
kiÖn x¶y ra trªn mét ®¬n vÞ thêi gian) phô thuéc vµo thêi gian, tøc λ = λ(t).
NÕu λ = const th× dßng Poisson lµ dõng vµ lóc nµy trë thµnh dßng tèi gi¶n.
Dßng tèi gi¶n cã vai trß quan träng trong viÖc kh¶o s¸t c¸c dßng kh¸ch hµng v× c¸c tÝnh
to¸n dùa trªn dßng tèi gi¶n sÏ ®¬n gi¶n vµ thuËn lîi.
XÐt mét dßng kh¸ch hµng lµ mét dßng tèi gi¶n (h×nh 5.3), trong ®ã:
- t1, t2, ... ti: thêi ®iÓm c¸c kh¸ch hµng xuÊt
hiÖn
- A1, A2,... Ai: kho¶ng thêi gian gi÷a c¸c
kh¸ch hµng.
Do dßng kh¸ch hµng lµ dßng tèi gi¶n nªn c−êng ®é kh¸ch hµng (sè kh¸ch hµng trung
b×nh trªn mét ®¬n vÞ thêi gian) lµ h»ng sè
A
1const
M
λ= =
Trong ®ã: MA - kú väng to¸n cña ®¹i l−îng ngÉu nhiªn A1, A2,... Ai
Ng−êi ta chøng minh ®−îc nÕu dßng kh¸ch hµng lµ mét dßng tèi gi¶n th× kho¶ng c¸ch
gi÷a c¸c kh¸ch hµng Ai sÏ lµ biÕn ngÉu nhiªn theo quy luËt ph©n bè mò - expo(
λ
).
Nh− vËy theo dßng kh¸ch hµng lµ dßng tèi gi¶n, thêi gian gi÷a c¸c kh¸ch hµng tu©n theo
luËt ph©n bè mò, gi¸ trÞ trung b×nh cña nã b»ng 1/λ, trong ®ã λ - c−êng ®é cña dßng kh¸ch
hµng.
Nh− ®· tr×nh bµy trªn h×nh 5.3, t¹i c¸c thêi ®iÓm t1, t2,... ti kh¸ch hµng xuÊt hiÖn lµm cho
tr¹ng th¸i cña hÖ thèng thay ®æi. V× dßng kh¸ch hµng lµ dßng tèi gi¶n nªn c¸c thêi ®iÓm t1,
t2,... ti xuÊt hiÖn hoµn toµn ngÉu nhiªn kh«ng phô thuéc lÉn nhau, tõ ®ã suy ra qu¸ tr×nh
t1t2t3 ti ti+1
A1A2A3 Ai Ai+1
t
H
×nh
5
.3. Dßng kh¸ch hµn
g
Gi¸o tr×nh M« h×nh ho¸
Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
58
chuyÓn tr¹ng th¸i trong hÖ thèng còng lµ ngÉu nhiªn kh«ng phô thuéc vµo c¸c tr¹ng th¸i trong
qu¸ khø. NÕu nh− nguyªn t¾c xÕp hµng lµ FIFO th× chuçi tr¹ng th¸i cña hÖ thèng nh− trªn
®−îc gäi lµ chuçi Markov. ChÝnh v× vËy ng−êi ta dïng ký hiÖu M ®Ó chØ ph©n bè mò cña c¸c
kho¶ng thêi gian gi÷a c¸c kh¸ch hµng.
5.4- Kªnh phôc vô (Server)
Mét hÖ thèng cã thÓ cã mét hoÆc nhiÒu kªnh phôc vô. Tuú tÝnh chÊt cña kh¸ch hµng mµ
thêi gian phôc vô kh¸c nhau. Sau ®©y lµ mét vÝ dô vÒ thêi gian phôc vô
- Thêi l−îng cña c¸c cuéc gäi ë tr¹m ®iÖn tho¹i
- Thêi gian gia c«ng c¸c chi tiÕt trªn m¸y
- Thêi gian kh¸m bÖnh, ®iÒu trÞ cho bÖnh nh©n
- Thêi gian tÝnh tiÒn cho mét kh¸ch hµng ë siªu thÞ
Thêi gian phôc vô lµ mét ®¹i l−îng ngÉu nhiªn. Sau khi kh¸ch hµng ®−îc phôc vô xong
th× sÏ rêi khái hÖ thèng vµ kªnh phôc vô nhËn ngay kh¸ch hµng míi ®Ó phôc vô nÕu trong
hµng ®îi ®ang cã kh¸ch hµng. Nh− vËy sè c¸c kh¸ch hµng ®−îc phôc vô t¹o thµnh dßng phôc
vô. Trong tr−êng hîp thêi gian phôc vô cã ph©n bè mò expo(
μ
), trong ®ã: μ -c−êng ®é dßng
phôc vô- lµ sè kh¸ch hµng ®−îc phôc vô trªn mét ®¬n vÞ thêi gian - th× dßng phôc vô t¹o thµnh
mét dßng tèi gi¶n vµ chuçi tr¹ng th¸i phôc vô lµ mét chuçi Markov vµ ng−êi ta dïng ký hiÖu
M ®Ó chØ ph©n bè mò cña thêi gian phôc vô.
Gäi S1, S2,... lµ thêi gian phôc vô. VËy:
s
1
M
μ=
Trong ®ã Ms lµ kú väng to¸n cña thêi gian phôc vô.
Ng−êi ta th−êng dïng c¸c ký hiÖu sau ®©y ®Ó chØ c¸c hÖ thèng hµng ®îi kh¸c nhau
- M/M/1 - HÖ thèng hµng ®îi cã 1 kªnh phôc vô, dßng kh¸ch hµng vµ phôc vô lµ dßng
tèi gi¶n.
- M/M/S - HÖ thèng hµng ®îi cã S kªnh phôc vô, dßng kh¸ch hµng vµ phôc vô lµ dßng
tèi gi¶n
- GI/G/S - HÖ thèng hµng ®îi cã S kªnh phôc vô, dßng kh¸ch hµng lµ dßng sù kiÖn ngÉu
nhiªn ®éc lËp (GI: General independent) vµ dßng phôc vô cã ph©n bè bÊt kú (G:General)
Trong hÖ thèng hµng ®îi ng−êi ta th−êng ®¸nh gi¸ kh¶ n¨ng cña hÖ thèng b»ng hÖ sè sö
dông (Utilization factor):
λ
ρ=μ §èi víi hÖ M/M/1
S
λ
ρ= μ §èi víi hÖ M/M/S
Gi¸o tr×nh M« h×nh ho¸
Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
59
5.5- ChiÒu dµi hµng ®îi
ChiÒu dµi hµng ®îi lµ sè kh¸ch hµng ®øng ®îi ®Ó ®−îc phôc vô. NÕu sè vÞ trÝ ®Ó ®øng
®îi kh«ng h¹n chÕ th× chiÒu dµi hµng ®îi cã thÓ dµi bÊt kú. Ng−îc l¹i nÕu sè vÞ trÝ ®Ó ®øng ®îi
bÞ h¹n chÕ th× chiÒu dµi hµng ®îi kh«ng v−ît qu¸ sè ®· cho tr−íc. Trong tr−êng hîp nÕu kh¸ch
hµng ®Õn ®óng vµo lóc chiÒu dµi hµng ®îi ®· ®Çy th× ph¶i rêi bá hÖ thèng vµ hÖ thèng sÏ bÞ
mÊt kh¸ch hµng. ChiÒu dµi hµng ®îi lµ mét ®¹i l−îng ngÉu nhiªn phô thuéc vµo c−êng ®é
dßng kh¸ch hµng vµ dßng phôc vô.
5.6- Thêi gian xÕp hµng
Thêi gian xÕp hµng lµ qu·ng thêi gian kh¸ch hµng ®øng ®îi trong hµng ®îi chê ®Õn l−ît
phôc vô. Cã lo¹i kh¸ch hµng cã thÓ ®îi bao l©u còng ®−îc, ng−îc l¹i cã lo¹i kh¸ch hµng chØ cã
thÓ ®îi trong kho¶ng thêi gian nhÊt ®Þnh, hÕt thêi gian ®ã kh¸ch hµng sÏ rêi bá hÖ thèng, mÆc
dÇu vÉn cßn chç ®Ó ®øng ®îi. Trong tr−êng hîp nµy hÖ thèng sÏ mÊt kh¸ch hµng. §Ó gi¶m kh¶
n¨ng mÊt kh¸ch hµng hÖ thèng ph¶i t¨ng c−êng ®é phôc vô hoÆc t¨ng sè kªnh phôc vô.
5.7- LuËt xÕp hµng
LuËt xÕp hµng lµ luËt lùa chän kh¸ch hµng ®Ó phôc vô. Trong hÖ thèng hµng ®îi cã mét
kªnh phôc vô th−êng cã c¸c luËt xÕp hµng sau ®©y:
- FIFO (First In First Out) - kh¸ch hµng ®Õn tr−íc ®−îc phôc vô tr−íc, kh¸ch hµng ®Õn
sau ®−îc phôc vô sau. LuËt FIFO th−êng ®−îc dïng ë nh÷ng n¬i nh−:
+ XÕp hµng tr−íc quÇy tÝnh tiÒn cña siªu thÞ.
+ XÕp hµng vµo c¬ së dÞch vô, ph−¬ng tiÖn vËn t¶i.
+ C¸c thiÕt bÞ xÕp hµng trªn b¨ng chuyÒn chê ®Õn l−ît ®−îc l¾p r¸p.
- LIFO (Last In First Out) - kh¸ch hµng ®Õn sau ®−îc phôc vô tr−íc. LuËt LIFO th−êng
®−îc dïng ë nh÷ng n¬i sau:
+ Ra khái buång thang m¸y: ng−êi vµo sau cïng sÏ ra tr−íc tiªn.
+ §äc d÷ liÖu trªn b¨ng tõ: d÷ liÖu ghi sau sÏ ®−îc ®äc tr−íc.
+ Hµng ho¸ ®−îc xÕp vµo thïng chøa: hµng xÕp sau cïng (phÝa trªn cïng cña thïng
chøa) sÏ ®−îc lÊy ra tr−íc v.v..
- NgÉu nhiªn: C¸c kh¸ch hµng ®Òu cã ®é −u tiªn nh− nhau vµ ®−îc phôc vô mét c¸ch
ngÉu nhiªn. LuËt nµy th−êng thÊy ë c¸c tr−êng hîp sau:
+ LÊy linh kiÖn ®iÖn tö trong « ra ®Ó l¾p r¸p.
- ¦u tiªn: Mét sè kh¸ch hµng cã mét sè ®Æc tÝnh nhÊt ®Þnh sÏ ®−îc phôc vô tr−íc. LuËt
nµy th−êng thÊy trong c¸c tr−êng hîp nh−:
+ Phô n÷, trÎ em vµ ng−êi tµn tËt ®−îc −u tiªn phôc vô tr−íc.
+ LuËt FIFO, luËt LIFO còng lµ mét tr−êng hîp ®Æc biÖt víi dÊu hiÖu −u tiªn lµ tr−íc
hoÆc ®Õn sau.