Giáo trình mô hình hóa - Chương 5

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

200
lượt xem 48
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình mô hình hóa - Chương 5

55 Gi¸o tr×nh M« h×nh ho¸ 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ô A S Kh¸ch hµng Kªnh phôc vô Kh¸ch hµng rêi Kh¸ch hµng Kh¸ch hµng khái hÖ thèng ®−îc phôc vô trong hµng ®îi H×nh 5.1- 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 Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
56 Gi¸o tr×nh M« h×nh ho¸ 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. t 0 H×nh 5.2. Dßng sù kiÖn gi¸n ®o¹n 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Ò Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
57 Gi¸o tr×nh M« h×nh ho¸ 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 A2 A1 Ai A3 Ai+1 hiÖn t t2 ti+1 t1 ti t3 - A1, A2,... Ai: kho¶ng thêi gian gi÷a c¸c kh¸ch hµng. H×nh 5.3. Dßng 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è 1 λ= = const MA 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 Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
58 Gi¸o tr×nh M« h×nh ho¸ 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ô. 1 μ= Gäi S1, S2,... lµ thêi gian phôc vô. VËy: Ms 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 μ λ ρ= §èi víi hÖ M/M/S Sμ Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
59 Gi¸o tr×nh M« h×nh ho¸ 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. Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
60 Gi¸o tr×nh M« h×nh ho¸ + Thêi gian phôc vô ng¾n ®−îc phôc vô tr−íc (Shortest job first). VÝ dô trªn nót giao th«ng xe nhá gän di chuyÓn nhanh ®−îc −u tiªn ®i tr−íc so víi xe to cång kÒnh di chuyÓn chËm ph¶i ®i sau. Bµi to¸n cã thêi gian ng¾n ®−îc m¸y tÝnh chän ®Ó gi¶i tr−íc. 5.8- Thêi gian xÕp hµng vµ chiÒu dµi hµng ®îi Gäi: Di- Thêi gian xÕp hµng cña kh¸ch hµng thø i; Si- Thêi gian phôc vô kh¸ch hµng thø i; VËy: Wi = Di + Si –Thêi gian chê ®îi trong hÖ thèng cña kh¸ch hµng thø i. Q(t)- Sè kh¸ch hµng trong hµng ®îi t¹i thêi ®iÓm t. L(t)- Sè kh¸ch hµng cã trong hÖ thèng t¹i thêi ®iÓm t; L(t) = Q(t) + sè kh¸ch hµng ®ang ®−îc phôc vô. Chóng ta cã thÓ chøng minh ®−îc c¸c quan hÖ sau ®©y [1]: n ∑D i Thêi gian xÕp hµng trung b×nh: d = lim i =1 (5.1) n n →∞ n ∑W i Thêi gian chê ®îi trung b×nh trong hÖ thèng: w = lim i =1 (5.2) n n →∞ TrÞ sè trung b×nh kh¸ch hµng cã trong hµng ®îi, hay cßn gäi lµ chiÒu dµi trung b×nh cña hµng ®îi: Q = λd (5.3) Trong ®ã: λ: C−êng ®é dßng kh¸ch hµng d: Thêi gian xÕp hµng trung b×nh TrÞ sè trung b×nh kh¸ch hµng cã trong hÖ thèng L = λω (5.4) Trong ®ã: ω- Thêi gian chê ®îi trung b×nh cña kh¸ch hµng trong hÖ thèng. 5.9- N¨ng lùc phôc vô vµ x¸c suÊt mÊt kh¸ch hµng cña hÖ thèng XÐt hÖ thèng hµng ®îi M/M/1 sè vÞ trÞ trong hµng ®îi h÷u h¹n vµ b»ng n. Trong tr−êng hîp nµy khi kh¸ch hµng ®Õn hÖ thèng mµ tÊt c¶ vÞ trÝ trong hµng ®îi ®Òu bÞ chiÕm chç th× kh¸ch hµng sÏ rêi bá hÖ thèng. Ta nãi hÖ thèng mÊt kh¸ch hµng. C−êng ®é dßng kh¸ch hµng lµ λ. C−êng ®é dßng phôc vô lµ μ. Tr¹ng th¸i cña hÖ thèng lµ U. H×nh 5.4 m« t¶ tr¹ng th¸i cña hÖ thèng nªu trªn. λ U0 U1 U2 Ui Un+1 ….. ….. μ H×nh 5.4. Tr¹ng th¸i hÖ thèng hµng ®îi M/M/1 Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
61 Gi¸o tr×nh M« h×nh ho¸ Chóng ta ®¸nh sè tr¹ng th¸i hÖ thèng theo sè l−îng kh¸ch hµng cã trong hÖ thèng (®−îc phôc vô vµ ®ang ®îi). + U0 - §iÓm phôc vô rçi (kh«ng cã kh¸ch hµng) + U1 - §iÓm phôc vô bËn (mét kh¸ch hµng ®ang ®−îc phôc vô), kh«ng cã kh¸ch hµng ®îi + U2 - §iÓm phôc vô bËn, mét kh¸ch hµng ®îi + Ui - §iÓm phôc vô bËn, (i-1) kh¸ch hµng ®îi + Un+1 - §iÓm phôc vô bËn, n kh¸ch hµng ®îi p0, p1, p2... pn+1 - lµ x¸c suÊt ®Ó hÖ thèng ë tr¹ng th¸i U0, U1, U2,... Un+1 Tõ h×nh 5.4 ta cã thÓ viÕt: λ = μp1 ⎫ λp1 = μp 2 ⎪ ⎪ ⎬ (5.5) ..... ⎪ λpi −1 = μpi ⎪ ⎭ Tõ ®ã ta cã c¸c quan hÖ sau: λ ⎫ p1 = p ⎪ μ0 ⎪ ⎪ 2 ⎛λ⎞ p2 = ⎜ ⎟ p0 ⎪ ⎪ ⎝μ⎠ ⎬ (5.6) ⎪ .... ⎪ ⎪ n +1 ⎛λ⎞ pn +1 = ⎜ ⎟ p0 ⎪ ⎝μ⎠ ⎪ ⎭ Chó ý r»ng tæng x¸c suÊt c¸c tr¹ng th¸i cña hÖ thèng (trõ tr¹ng th¸i U0 lµ tr¹ng th¸i kh«ng cã kh¸ch hµng) lu«n lu«n b»ng 1, ta cã: p1 + p2 + p3 + pn+1 = 1 DÏ dµng t×m ®−îc x¸c suÊt p0 lµ x¸c suÊt hÖ thèng rçi, kh«ng cã kh¸ch hµng 1 p0 = (5.7) n +1 2 λ ⎛λ⎞ ⎛λ⎞ 1 + + ⎜ ⎟ + ... + ⎜ ⎟ μ ⎝μ⎠ ⎝μ⎠ MÉu sè cña (5.7) lµ mét cÊp sè nh©n cã c«ng béi λ/μ, do ®ã cã thÓ viÕt 1 p0 = (5.8) ⎡ ⎛ λ ⎞n +2 ⎤ ⎛ λ ⎞ ⎢1 − ⎜ ⎟ ⎥ ⎜1 − ⎟ ⎢ ⎝ μ ⎠ ⎥⎝ μ ⎠ ⎣ ⎦ Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
62 Gi¸o tr×nh M« h×nh ho¸ 1− λ μ p0 = (5.9) ( μ) n+2 1− λ Chó ý r»ng x¸c suÊt pn+1 lµ x¸c suÊt x¶y ra tr¹ng tr¸i tÊt c¶ n vÞ trÝ trong hµng ®îi ®Òu cã kh¸ch hµng ®øng ®îi. Lóc nµy cã kh¸ch hµng míi ®Õn th× sÏ rêi bá hÖ thèng. VËy x¸c suÊt ®Ó hÖ thèng bÞ mÊt kh¸ch hµng p0 sÏ lµ: p0 = pn+1 Thay (5.9) vµo (5.6), ta cã thÓ viÕt 1− λ ( μ) ( μ) n +1 n +1 μ p 0 = p n +1 = λ p0 = λ (5.10) ( μ) n +2 1− λ Tr¹ng th¸i ng−îc víi tr¹ng th¸i mÊt kh¸ch hµng chÝnh lµ tr¹ng th¸i phôc vô. V× vËy kh¶ n¨ng phôc vô t−¬ng ®èi cña hÖ thèng ®−îc ®¸nh gi¸ b»ng x¸c suÊt 1− λ ( μ) n +1 μ p1 = 1 − p 0 = 1 − λ (5.11) ( μ) n+2 1− λ Kh¶ n¨ng phôc vô tuyÖt ®èi ®−îc ®¸nh gi¸ b»ng c«ng thøc sau: A = λ.p1 (5.12) Gi¸ trÞ A lµ sè kh¸ch hµng ®−îc phôc vô trªn mét ®¬n vÞ thêi gian Chóng ta còng cã thÓ chøng minh ®−îc r»ng gi¸ trÞ trung b×nh sè kh¸ch hµng cã trong hµng ®îi Q lµ () () () ⎡ ⎞⎤ 2 n ⎛ λ 1− λ ⎜ n + 1 − n λ μ ⎟⎥ ⎢ μ⎣ μ⎝ ⎠⎦ Q= (5.13) () () ⎡ ⎤⎡ n +2 λ⎤ λ ⎢1 − μ ⎥ ⎢1 − μ ⎥ ⎣ ⎦ ⎣ ⎦ Theo (5.13) thêi gian xÕp hµng chê ®îi trung b×nh d Q d= (5.14) λ Thêi gian trung b×nh cña kh¸ch hµng ë trong hÖ thèng ω = thêi gian xÕp hµng trung b×nh d + thêi gian trung b×nh phôc vô ts. Thêi gian trung b×nh phôc vô ts b»ng thêi gian phôcvô mét kh¸ch hµng 1/μ nh©n víi kh¶ n¨ng phôc vô cña hÖ thèng P1, tøc: 1 ts = P1 (5.15) μ Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
63 Gi¸o tr×nh M« h×nh ho¸ VËy ta cã: ω = d + ts (5.16) Thay (5.14) vµ (5.15) vµo (5.16) ta cã: Q P1 ω= + (5.17) λμ Sè kh¸ch hµng n»m trong hÖ thèng L b»ng sè kh¸ch hµng n»m trong hµng ®îi Q céng víi sè kh¸ch hµng trung b×nh ®ang ®−îc phôc vô ls ls = λ.ts Ta cã: Thay (5.15) vµo biÓu thøc trªn ta ®−îc λ ls = P1 (5.18) μ VËy sè kh¸ch hµng trung b×nh n»m trong hÖ thèng lµ: λ L = Q+ P1 (5.19) μ BiÓu thøc (5.19) chÝnh lµ ta thay (5.17) vµo (5.4) VÝ dô: Mét tr¹m söa ch÷a «t« cã mét ®iÓm söa ch÷a. B·i ®ç xe chê phôc vô chøa ®−îc 3 xe , tøc n = 3. C−êng ®é dßng xe ®Õn söa ch÷a λ = 1 phót Thêi gian söa ch÷a 1 xe «t« lµ: 1,25/phót H·y x¸c ®Þnh: - X¸c suÊt tr¹m mÊt kh¸ch hµng: p0 - Kh¶ n¨ng phôc vô t−¬ng ®èi vµ tuyÖt ®èi: P1 vµ A - TrÞ sè trung b×nh sè «t« chê phôc vô: Q - TrÞ sè trung b×nh sè «t« cã trong tr¹m (t¹i mét thêi ®iÓm): L - Thêi gian trung b×nh «t« chê trong hµng: d - Thêi gian trung b×nh «t« cã mÆt t¹i tr¹m söa ch÷a: ω Gi¶i: Tr¹m söa ch÷a «t« nªu trªn cã thÓ ®−îc m« t¶ b»ng m« h×nh M/M/1 víi ®é dµi hµng ®îi lµ n = 3 C−êng ®é dßng phôc vô: μ = 1/1,25 = 0,8 Theo (5.10) tÝnh ®−îc x¸c suÊt tr¹m mÊt kh¸ch hµng p0, tøc nÕu ®· cã 3 xe ®ang chê söa ch÷a th× xe tiÕp theo sÏ ®i qua mµ kh«ng vµo tr¹m ®Ó söa ch÷a n÷a. Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
64 Gi¸o tr×nh M« h×nh ho¸ 1− λ ( μ) ( μ) n +1 n +1 μ p 0 = p n +1 = λ .p 0 = λ ( μ) n+2 1− λ 1− 1 ( 0,8) 1 − 4 0,8 p0 = 1 = 0, 297 ( 0,8) 5 1 - Theo (5.11) tÝnh ®−îc kh¶ n¨ng phôc vô t−¬ng ®èi p1 = 1 – p0 = 0,703 - Theo (5.13) tÝnh ®−îc trÞ sè trung b×nh sè «t« chê phôc vô (xÕp hµng): Q () () () ⎡ ⎞⎤ 2 n ⎛ λ 1− λ ⎜ n + 1 − n λ μ ⎟⎥ ⎢ μ⎣ μ⎝ ⎠⎦ Q= () () ⎡ ⎤⎡ n +2 λ⎤ λ ⎢1 − μ ⎥ ⎢1 − μ ⎥ ⎣ ⎦ ⎣ ⎦ ( ) ( ) ( ( 10,8))⎤⎥⎦ = 1,56 ⎡2 n 1 1− 1 3 +1− 3 0,8 ⎢ 0,8 ⎣ Q= ( ) ( )⎥⎦⎤ ⎡ ⎤⎡ 5 1− 1 1− 1 ⎢ 0,8 ⎥ ⎢ 0,8 ⎣ ⎣ ⎦ -Theo (5.19) tÝnh ®−îc trÞ sè trung b×nh sè «t« cã mÆt trong tr¹m söa ch÷a L: λ 1 L =Q+ P1 = 1,56 + 0, 703 = 2, 44 μ 0,8 - Theo (5.14) tÝnh ®−îc thêi gian trung b×nh «t« chê trong hµng d: Q 1,56 d= = = 1,56 (phót) λ 1 - Theo (5.17) tÝnh ®−îc thêi gian trung b×nh «t« cã mÆt ë tr¹m söa ch÷a ω:− Q P1 1,56 0, 703 ω= += + = 2, 44 (phót) λμ 1 0,8 5.10- HÖ thèng hµng ®îi M/M/1 cã ®é dµi hµng ®îi kh«ng h¹n chÕ (n → ∞) Sau ®©y xÐt c¸c ®Æc tÝnh cña hÖ thèng khi n → ∞, luËt xÕp hµng FIFO. + Kh¶ n¨ng phôc vô P1 Khi n → ∞ biÓu thøc (5.11) tiÕn tíi P1 = 1, ®iÒu nµy cã thÓ ®−îc gi¶i thÝch lµ nÕu luËt xÕp hµng lµ FIFO vµ ®é dµi hµng ®îi kh«ng h¹n chÕ th× tÊt c¶ c¸c kh¸ch hµng ®Òu ®−îc phôc vô cho nªn kh¶ n¨ng phôc vô P1 = 1, tøc 100% kh¸ch hµng ®Õn hÖ thèng ®Òu ®−îc phôc vô. + X¸c xuÊt mÊt kh¸ch hµng cña hÖ thèng P0 = 0 Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
65 Gi¸o tr×nh M« h×nh ho¸ + §é dµi trung b×nh cña hµng ®îi (5.13) khi n → ∞ lµ: ( μ) 2 λ Q= 1− ( λ ) (5.20) μ + TrÞ sè trung b×nh sè kh¸ch hµng cã mÆt trong hÖ thèng, (5.19) khi n → ∞ ( λ μ) L= 1− ( λ ) (5.21) μ + TrÞ sè trung b×nh thêi gian kh¸ch hµng chê trong hµng ®îi, (5.14) khi n → ∞ () 2 λ μ 1 d= ( μ) (5.22) λ 1− λ + TrÞ sè trung b×nh thêi gian kh¸ch hµng cã mÆt trong hÖ thèng, (5.17) khi n → ∞ ( μ) + 1 2 λ ω= λ ⎛1 − ( λ ) ⎞ μ (5.23) ⎜ μ⎟ ⎝ ⎠ C¸c hÖ thèng hµng ®îi ®−îc xem xÐt ë trªn ®Òu gi¶ thiÕt r»ng thêi gian chê ®îi trong hµng ®îi lµ kh«ng h¹n chÕ. Trong thùc tÕ cã nh÷ng hÖ thèng mµ thêi gian chê ®îi bÞ h¹n chÕ d ≤ D0. Trong ®ã D0 lµ thêi gian cho phÐp ®îi trong hµng ®îi. Trong tr−êng hîp nµy tuy chiÒu dµi hµng ®îi kh«ng h¹n chÕ, nh−ng hÖ thèng vÉn cã kh¶ n¨ng mÊt kh¸ch hµng nÕu thêi gian trung gian chê ®îi d > D0. VÝ dô: - C¸c kh¸ch hµng cña mét tr¹m b¸n x¨ng nÕu ph¶i xÕp hµng l©u sÏ bá ®i sang tr¹m kh¸c. - TrËn ®Þa ph¸o phßng kh«ng (kªnh phôc vô) ph¶i ph¶n øng kÞp thêi trong mét qu·ng thêi gian nhÊt ®Þnh (thêi gian phôc vô) nÕu kh«ng m¸y bay ®èi ph−¬ng (kh¸ch hµng) sÏ rêi bá trËn ®Þa ph¸o. - C¸c kh¸ch hµng vµo cöa hµng ¨n nhanh nÕu ph¶i chê ®îi l©u sÏ bá ®i sang cña hµng kh¸c. 5.11- VÝ dô minh ho¹ vÒ hÖ thèng hµng ®îi M« pháng tr¹m söa ch÷a «t« (Xem vÝ dô ë môc 5.9) 1. M« t¶ ®èi t−îng m« pháng Mét tr¹m söa ch÷a «t« cã mét ®iÓm söa ch÷a (phôc vô). B·i ®ç xe phôc vô chøa ®−îc 3 xe, tøc n = 3. Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
66 Gi¸o tr×nh M« h×nh ho¸ C−êng ®é dßng xe ®Õn söa ch÷a, λ = 1/phót. Thêi gian trung b×nh ®Ó söa ch÷a mét xe «t« lµ 1,25 phót. H·y m« pháng ho¹t ®éng cña tr¹m trong qu·ng thêi gian T = 240 phót, ®Ó x¸c ®Þnh c¸c chØ tiªu sau ®©y: - Sè xe ®Õn tr¹m söa ch÷a - Sè xe ®−îc phôc vô (®−îc söa ch÷a) - Sè xe ph¶i rêi bá tr¹m v× kh«ng cã chç ®Ó xÕp hµng chê ®Õn l−ît söa ch÷a - X¸c suÊt mÊt kh¸ch hµng P0 - Kh¶ n¨ng phôc vô t−¬ng ®èi P1 - Sè xe trung b×nh trong hµng ®îi Q - Thêi gian ®îi trung b×nh d - Thêi gian trung b×nh xe cã mÆt t¹i tr¹m (thêi gian xÕp hµng + thêi gian phôc vô) - Rót ra c¸c kiÕn nghÞ cÇn thiÕt NhiÖm vô m« pháng trªn ®©y ®· ®−îc tr×nh bµy ë vÝ dô trong môc 5.9 ë vÝ dô nµy ®· dïng c¸c biÓu thøc gi¶i tÝch ®Ó gi¶i bµi to¸n. ë ®©y chóng ta dïng ph−¬ng ph¸p m« pháng ®Ó gi¶i quyÕt cïng bµi to¸n nªu trªn nh»m so s¸nh gi÷a hai ph−¬ng ph¸p. 2. C¸c ®iÒu kiÖn ®Çu - Dßng xe «t« ®Õn tr¹m söa ch÷a ®−îc coi lµ dßng tèi gi¶n, cã c−êng ®é λ = 1 xe/phót. Nh− vËy kho¶ng c¸ch gi÷a c¸c xe ®Õn tr¹m cã ph©n bè mò cã th«ng sè lµ λ. - Tr¹m cã ba chç ®Ó xe xÕp hµng chê phôc vô, n = 3. VËy ®é dµi hµng ®îi bÞ h¹n chÕ bëi n = 3, nh−ng thêi gian ®îi kh«ng bÞ h¹n chÕ. - Thêi gian söa ch÷a trung b×nh b»ng 1,25 phót. VËy c−êng ®é dßng söa ch÷a b»ng μ = 1/1,25 = 0,8 1/phót. - Thêi gian söa ch÷a lµ ®¹i l−îng ngÉu nhiªn tu©n theo luËt ph©n bè mò cã th«ng sè lµ μ. - §iÒu kiÖn khëi ®éng m« pháng: t¹i t = 0 hÖ thèng rçng, tøc kh«ng cã xe trong ®iÓm söa ch÷a vµ còng kh«ng cã xe trong hµng ®îi. - §iÒu kiÖn ngõng m« pháng lµ thêi gian m« pháng Tmp = 240 phót N Tmp = ∑ t k k =1 tk: kho¶ng thêi gian gi÷a xe thø (k-1) vµ xe thø (k), cã nghÜa lµ thêi gian m« pháng ®−îc t¨ng lªn sau mçi lÇn x¶y ra mét sù kiÖn míi lµ cã mét xe ®Õn tr¹m söa ch÷a. 3. C¸c ký hiÖu trong ch−¬ng tr×nh m« pháng Ak : sè thø tù cña c¸c xe ®Õn tr¹m söa ch÷a Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
67 Gi¸o tr×nh M« h×nh ho¸ tk : kho¶ng thêi gian gi÷a xe thø (k-1) vµ xe thø (k), (phót) S1 : sè xe ®−îc phôc vô Q : sè xe cã mÆt trong hµng ®îi t¹i c¸c b−íc m« pháng Q1 : sè xe ®· xÕp hµng trong hµng ®îi M : sè xe ph¶i rêi bá tr¹m tøc sè kh¸ch hµng mµ tr¹m bÞ mÊt v× kh«ng ®ñ chç xÕp hµng chê phôc vô. TiÕp theo lµ ch−¬ng tr×nh m« pháng tr¹m söa ch÷a «t« M/M/1 viÕt b»ng ng«n ng÷ Pascal. 4.Ch−¬ng tr×nh m« pháng Pascal program MO_PHONG_TRAM_SUA_CHUA_OTO uses ctr; var k, q, q1, m, a1, s1, qtb, d, i: integer; u, n, a, s, stb, ai, si, ld, mu, t, td, ts, tw: real; f: text; PROCEDURE Print (l: integer; var f: text); BEGIN IF l = 0 THEN BEGIN Clrscr; Gotoxy(1,2); write(f,‘Ak’); gotoxy(17,2); Write(f,‘Tk’); gotoxy(30,2); write(f,‘S1’); gotoxy(42,2); write(f,‘Q’); gotoxy(54,2); write(f,‘Q1’); gotoxy(66,2); write(f,‘M’); writeln(f,”); END; IF L=1 THEN BEGIN gotoxy(1,3+i); write(f,‘ ’,a1:3); gotoxy(15,3+i); write(f,‘ ’,a:8:4); gotoxy(30,3+i); write(f,‘ ’,s1:2); gotoxy(42,3+i); write(f,‘ ’,q:1); gotoxy(54,3+i); write(f,‘ ’,q1:3); gotoxy(66,3+i); write(f,‘ ’,m:3); writeln(f,’ ‘); Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
68 Gi¸o tr×nh M« h×nh ho¸ END; RTOCEDURE Print_to_screen; BEGIN i:=i+1; Print(1,f); IF(k MOD 20=0) AND (k0) THEN BEGIN I:=0; END; PROCEDURE Initial; BEGIN Clrscr; q:=0; q1:=0; m:=0; a1:=0; s1:=0; d1:=0; qtb:=0; s:=0; stb:=0; a:=0; * NhËn xÐt: KÕt qu¶ m« pháng gÇn gièng víi kÕt qu¶ cña ph−¬ng ph¸p gi¶i tÝch cho ë vÝ dô trong môc 5.9. ¦u ®iÓm cña ph−¬ng ph¸p m« pháng lµ cã thÓ quan s¸t tr¹ng th¸i hÖ thèng qua tõng b−íc m« pháng, tõ ®ã cã thÓ ®−a ra c¸c nhËn xÐt vµ biÖn ph¸p ®Ó c¶i tiÕn hÖ thèng. Trong khi ®ã ph−¬ng ph¸p gi¶i tÝch chØ cho kÕt qu¶ tæng qu¸t cuèi cïng mµ th«i. 5.12- C©u hái vµ bµi tËp 1. HÖ thèng M/M/1 Tr¹m «t« buýt Hµnh kh¸ch ®Õn tr¹m «t« buýt víi c−êng ®é λ = 3 hµnh kh¸ch/phót vµ xÕp hµng ®Ó chê lªn xe. VÞ trÝ dµnh ®Ó xÕp hµng kh«ng (hoÆc cã) bÞ h¹n chÕ. Cø sau 5 phót cã mét «t« buýt ®Õn tr¹m. Mçi chuyÕn «t« buýt chë ®−îc 50 kh¸ch hµng. H·y m« pháng tr¹m xe buýt sau 1 giê ho¹t ®éng. TÝnh trÞ sè trung b×nh kh¸ch hµng ph¶i chê trong hµng ®îi. 2.HÖ thèng M/M/1 C¶ng biÓn Tµu biÓn ®i ®Õn c¶ng víi kho¶ng c¸ch lµ qu·ng thêi gian ngÉu nhiªn cã ph©n bè mò expo(λ). Gi¸ trÞ trung b×nh cña kho¶ng thêi gian gi÷a c¸c tµu biÓn lµ 1,25 ngµy - do ®ã suy ra λ = 1/1,25 = 0,8. C¶ng cã mét cÇn trôc ®Ó bèc dì hµng ho¸. Khi ®Õn c¶ng, nÕu cÇn trôc ®ang bËn th× tµu biÓn sÏ xÕp hµng theo luËt FIFO. Thêi gian bèc dì hµng (thêi gian phôc vô) cña cÇn trôc phô thuéc vµo sè l−îng hµng ho¸ cña tµu biÓn. Thêi gian bèc dì hµng trung b×nh cho mét tµu lµ 1,5 ngµy. VËy thêi gian phôc vô cã ph©n bè mò expo(μ) víi μ = 1/1,5 = 0,66. H·y m« pháng ho¹t ®éng cña c¶ng vµ x¸c ®Þnh xem liÖu cã cÇn thªm cÇn trôc thø hai ®Ó tµu biÓn kh«ng ph¶i xÕp hµng chê qu¸ mét ngµy. Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
69 Gi¸o tr×nh M« h×nh ho¸ 3.HÖ thèng M/M/5 Siªu thÞ Kh¸ch hµng ®Õn siªu thÞ sÏ lÇn l−ît thùc hiÖn c¸c ®éng t¸c sau: LÊy giá ®ùng hµng. Chän hµng trªn c¸c quÇy. TÝnh tiÒn. Rêi khái siªu thÞ. Dßng kh¸ch hµng ®Õn siªu thÞ lµ mét dßng tèi gi¶n cã c−êng ®é λ kh¸ch hµng/phót. Gi¶ thiÕt sè giá dùng hµng kh«ng bÞ h¹n chÕ nªn kh¸ch hµng ®Õn siªu thÞ lµ lËp tøc vµo siªu thÞ chän hµng kh«ng ph¶i xÕp hµng. Sè hµng ®−îc chän mua xÕp vµo c¸c giá lµ sè ngÉu nhiªn phô thuéc vµo tõng ý thÝch cña kh¸ch hµng. Sau khi chän xong hµng, kh¸ch sÏ ®Õn mét trong n¨m quÇy kiÓm hµng vµ tÝnh tiÒn (siªu thÞ cã 5 kªnh phôc vô). NÕu quÇy bËn kh¸ch hµng sÏ xÕp hµng theo luËt FIFO vµ chê ®îi cho ®Õn khi ®−îc phôc vô míi th«i, tøc thêi gian chê kh«ng h¹n chÕ. Thêi gian phôc vô cho mét kh¸ch hµng lµ ®¹i l−îng ngÉu nhiªn phô thuéc vµo sè l−îng vµ ®é phøc t¹p kiÓm ho¸ cña nh÷ng hµng ho¸ kh¸ch ®· chän. Thêi gian phôc vô cã ph©n bè mò, c−êng ®é phôc vô lµ μ kh¸ch hµng/phót. Sau khi ®−îc phôc vô xong kh¸ch hµng sÏ rêi khái siªu thÞ. H·y m« pháng ho¹t ®éng cña siªu thÞ sau 4 giê lµm viÖc. X¸c ®Þnh trÞ sè trung b×nh kh¸ch hµng xÕp hµng trong hµng ®îi chê tÝnh tiÒn. LiÖu siªu thÞ cã cÇn ph¶i më thªm quÇy kiÓm hµng n÷a kh«ng? 4. HÖ thèng M/M/10 Tr¹m ®iÖn tho¹i Mét tr¹m ®iÖn tho¹i gåm cã 10 kªnh liªn l¹c. Sè kh¸ch hµng gäi ®iÖn tho¹i lµ mét ®¹i l−îng ngÉu nhiªn, ®éc lËp; v× vËy kho¶ng c¸c gi÷a c¸c kh¸ch hµng tu©n theo ph©n bè mò. Khi kh¸ch hµng gäi ®Õn nÕu cßn kªnh rçi lËp tøc ®−îc phôc vô- tøc ®−îc nèi th«ng m¹ch ®Ó thùc hiÖn ®µm tho¹i. NÕu c¶ 10 kªnh ®Òu bËn kh¸ch hµng ph¶i xÕp hµng chê ®Õn l−ît theo luËt FIFO. Thêi gian ®µm tho¹i cña kh¸ch hµng -tøc thêi gian phôc vô- lµ mét ®¹i l−îng ngÉu nhiªn tu©n theo luËt ph©n bè mò. VÊn ®Ò ®Æt ra ë ®©y lµ ph¶i x¸c ®Þnh sè kªnh phôc vô b»ng bao nhiªu ®Ó thêi gian chê ®îi cña kh¸ch hµng kh«ng v−ît qu¸ gi¸ trÞ cho phÐp. 5. HÖ thèng M/M/2 Tr¹m söa ch÷a «t« Bµn kiÓm tra Mét tr¹m söa ch÷a «t« 0,7 cña thµnh phè gåm cã (xem h×nh 5.5) QuÇy söa ch÷a Hµng ®îi 1 0,3 - Mét bµn kiÓm tra - Hai quÇy söa ch÷a «t« lµm viÖc song song. Hµng ®îi 2 Kho¶ng c¸ch gi÷a c¸c H×nh 5.5. Tr¹m söa ch÷a «t« «t« ®Õn tr¹m söa ch÷a tu©n theo luËt ph©n bè mò víi gi¸ trÞ trung b×nh b»ng 2 giê. Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
70 Gi¸o tr×nh M« h×nh ho¸ Thêi gian kiÓm tra tu©n theo luËt ph©n bè ®Òu gi÷a 15 phót ®Õn 1,05 giê. ¤t« xÕp hµng tr−íc bµn kiÓm tra theo luËt FIFO. Qua kiÓm tra cã 70% «t« kh«ng ph¶i söa ch÷a vµ lËp tøc rêi khái tr¹m. Cã 30% «t« ph¶i ®−a ®i söa ch÷a, ®Õn xÕp hµng tr−íc 2 quÇy söa ch÷a lµm viÖc song song. LuËt xÕp hµng vµo quÇy söa ch÷a lµ FIFO. Thêi gian söa ch÷a «t« tu©n theo luËt ph©n bè ®Òu gi÷a 2,1 giê vµ 4,5 giê. H·y m« pháng tr¹m lµm viÖc trong 160 giê vµ tÝnh: - Thêi gian ®îi trung b×nh trong mçi hµng ®îi - ChiÒu dµi hµng ®îi trung b×nh cña mçi hµng ®îi - HiÖu suÊt sö dông cña bµn kiÓm tra - HiÖu suÊt sö dông cña quÇy söa ch÷a - NÕu gi¸ trÞ trung b×nh cña kho¶ng c¸ch gi÷a c¸c «t« ®Õn tr¹m söa ch÷a gi¶m xuèng cßn 30 phót. §iÒu g× sÏ x¶y ra? 6. HÖ thèng M/M/1 Ph©n x−ëng gia c«ng c¬ khÝ Mét ph©n x−ëng cã mét c«ng ®o¹n gia c«ng c¬ khÝ vµ mét bµn kiÓm tra nh− ë h×nh 5.6. Bµn kiÓm tra Hµng ®îi 1 Hµng ®îi 2 0,9 tèt C«ng ®o¹n gia c«ng c¬ khÝ H×nh 5.6. Ph©n x−ëng gia c«ng c¬ khÝ C¸c chi tiÕt m¸y ®−a ®Õn c«ng ®o¹n gia c«ng c¬ khÝ cã kho¶ng c¸ch tu©n theo luËt ph©n bè mò vµ cã gi¸ trÞ trung b×nh b»ng 1 phót. Thêi gian gia c«ng c¬ khÝ chi tiÕt tu©n theo luËt ph©n bè ®Òu n»m trong kho¶ng 0,65 ®Õn 0,7 phót. Thêi gian kiÓm tra s¶n phÈm theo luËt ph©n bè ®Òu n»m trong kho¶ng 0,75 ®Õn 0,8 phót. Cã 90% s¶n phÈm ®¹t lo¹i tèt ®−îc ®−a ®i ®ãng gãi, cßn 10% s¶n ph¶m lµ lo¹i xÊu sÏ ®−îc ®−a trë vÒ gia c«ng l¹i. Gi¶ thiÕt r»ng sè chê ®îi cña hai hµng ®îi lµ kh«ng h¹n chÕ H·y m« pháng hÖ thèng lµm viÖc trong qu·ng thêi gian 240 phót vµ tÝnh: - Thêi gian ®îi trung b×nh trong c¸c hµng ®îi - ChiÒu dµi hµng ®îi trung b×nh cña c¸c hµng ®îi - Sè s¶n phÈm ph¶i gia c«ng l¹i. 7. HÖ thèng M/M/3 HÖ thèng xö lý tin Mét hÖ thèng xö lý th«ng tin bao gåm mét kªnh truyÒn tin, mét bé ®Öm (buffer) vµ ba m¸y tÝnh (xem h×nh 5.7) TÝn hiÖu tõ c¶m biÕn ®i vµo kªnh truyÒn tin víi kho¶ng c¸ch trung b×nh lµ 5 μs. Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn
71 Gi¸o tr×nh M« h×nh ho¸ T¹i bé ®Öm c¸c tÝn hiÖu ®−îc xö lý s¬ bé víi thêi gian 10 μs cho mét tÝn hiÖu. Sau ®ã tÝn hiÖu ®−îc ®−a vµo xö lý ë mét trong ba m¸y tÝnh. Thêi gian m¸y tÝnh xö lý Bé ®Öm C¶m biÕn Kªnh truyÒn mét tÝn hiÖu mÊt 33 μs. H·y m« pháng qu¸ tr×nh xö lý th«ng tin khi cã 500 tÝn hiÖu tõ c¶m biÕn H×nh 5.7. HÖ thèng xö lý th«ng tin ®−a tíi vµ tÝnh: - Thêi gian trung b×nh tÝn hiÖu ph¶i chê trong bé ®Öm tr−íc khi ®−îc ®−a vµo m¸y tÝnh ®Ó xö lý. - ChiÒu dµi trung b×nh hµng ®îi cña c¸c tÝn hiÖu trong bé ®Öm. - X¸c suÊt bé ®Öm bÞ trµn, biÕt r»ng dung l−îng cña bé ®Öm lµ 30 tÝn hiÖu. §iÒu g× sÏ x¶y ra khi t¨ng tèc ®é xö lý tÝn hiÖu cña c¸c m¸y tÝnh lªn 25 microsec/tÝn hiÖu. Bé m«n Tù ®éng ho¸ http://www.ebook.edu.vn Khoa §iÖn