Luận án Một số dạng hàng đợi và các nguyên lý xử lý

trong mạng hàng đợi từ đơn giản đến phức tạp vì vậy mục này bày kết quả nghiên cứu dòng job luân chuyển trong mạng hàng đợi Γ được chập bởi hai mạng thành phần (mục 2.2.2.1) và kết quả nghiên cứu dòng job luân chuyển trong mạng hàng đợi Γ được chập bởi 2J mạng thành phần (mục 2.2.2.2), trong đó ( )J J + là số nút mạng. Từ định nghĩa 2.1 về mạng thành phần khi đó: - Với mọi nút i được mạng thành phần ( ),h l L sử dụng tại thời điểm t ta có: ( ) ( ) ( ) ( ) ( ) ( , ) i,j 0 ( , ) i,0 ( , ) 0,i ( , ) ( , ) i,j j,i 1 0 0 0 1, J h l j h l h l h l h l p t p t n u i l p t n u i h p t p t j J v j i =  =   =   =    =  =   Õ Õ µ . (2.86) - Với mọi nút i không được mạng thành phần ( ),h l L sử dụng tại thời điểm t ta có: ( )( , ), 0 0 J h l i j j p t = = . (2.87) 67 2.2.2.1. Xác định dòng job trong mạng hàng đợi Γ được chập bởi hai mạng thành phần Xét mạng hàng đợi Γ là chập của 2 mạng thành phần ( )1 1,i j và ( )2 2,i j . Vì ( )( , ), k k i j i jA t ( 1,2k = ) là biến cố job chuyển từ nút i sang nút j trong mạng thành phần ( ),k ki j tại thời điểm t và ( ),i jA t là biến cố job chuyển từ nút i sang nút j trong mạng hàng đợi Γ tại thời điểm t . Khi đó ta có: ( ) ( ) ( )1 1 2 2( , ) ( , ), , , i j i j i j i j i jA t A t A t= . (2.88) Từ giả thiết 2.2 khi đó hai mạng thành phần ( )1 1,i j và ( )2 2,i j hoạt động độc lập với nhau. Vì vậy ta có: ( ) ( ) ( ) ( ) ( )1 1 2 2 1 1 2 2( , ) ( , ) ( , ) ( , ), , , , , i j i j i j i j i j i j i j i j i jA t A t A t A t A t       = + −        ( ) ( ) ( ) ( )1 1 2 2 1 1 2 2( , ) ( , ) ( , ) ( , ), , , , i j i j i j i j i j i j i j i jA t A t A t A t       = + −        . (2.89) Từ các ký hiệu ( ) ( )1 1 2 2( , ) ( , ), ,, i j i j i j i jp t p t và ( ),i jp t ta có: ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 2 2 2 2 ( , ) ( , ) , , ( , ) ( , ) , , , , i j i j i j i j i j i j i j i j i j i j p t A t p t A t p t A t   =     =     =   . (2.90) Vì vậy ta có: ( ) ( ) ( ) ( ) ( )1 1 2 2 1 1 2 2( , ) ( , ) ( , ) ( , ), , , , , i j i j i j i j i j i j i j i j i jp t p t p t p t p t= + − . (2.91) Từ giả thiết 2.2 và công thức (2.91) ta thấy nếu mạng hàng đợi Γ là chập của hai mạng thành phần và biết xác suất job luân chuyển giữa các nút trong hai mạng thành phần thì sẽ xác định được xác suất job luân chuyển giữa các nút trong mạng hàng đợi Γ. 2.2.2.2. Xác định dòng job trong mạng hàng đợi Γ được chập bởi J2 mạng thành phần Vì mạng hàng đợi có J nút nên mạng hàng đợi Γ được chập bởi 2J mạng thành phần. Vì vậy ta có: 68 ( ) ( )( , ), , ( , ) k l i j i j k l L A t A t  = . (2.92) Từ giả thiết 2.2 khi đó các mạng thành phần hoạt động độc lập với nhau nghĩa là các biến cố ( ) ( )( )( , ), ,k li jA t k l L độc lập với nhau. Nên ta có: ( ) ( )( , ), , ( , ) k l i j i j k l L A t A t      =      ( )( , ), ( , ) 1 k li j k l L A t    = −     ( )( , ), ( , ) 1 k li j k l L A t    = −     ( )( , ), ( , ) 1 k li j k l L A t    = −      ( )( )( )( , ), ( , ) 1 1 k li j k l L A t  = − − . ( )( )( , ), ( , ) 1 1 k li j k l L p t  = − − . Vì vậy ta có: ( ) ( )( )( , ), , ( , ) 1 1 k li j i j k l L p t p t  = − − . (2.93) Từ giả thiết 2.2 và công thức (2.93) ta thấy nếu biết xác suất job luân chuyển giữa các nút trong tất cả các mạng thành phần thì sẽ xác định được xác suất job luân chuyển giữa các nút trong mạng hàng đợi. 2.3. Về một mô hình mạng hàng đợi cụ thể Trong mục này luận án trình bày về dòng job luân chuyển trong mạng hàng đợi có 5 nút mạng. Áp dụng các kết quả của mục 2.2.1 trong chương 2 để tính toán lưu lượng dòng job luân chuyển trong mạng hàng đợi tại các bước. 69 2.3.1. Tập các mạng thành phần Vì có 5 nút mạng nên mạng hàng đợi là chập của 25 mạng thành phần. Để dễ cho việc trình bày, chúng ta thực hiện chỉ số hóa các mạng thành phần lần lượt từ 1 đến 25 theo bảng sau: Bảng 2.1. Chỉ số hóa các mạng thành phần Chỉ số hóa mạng thành phần Mạng thành phần tương ứng 1 (1,1) 2 (1,2) 3 (1,3) 4 (1,4) 5 (1,5) 6 (2,1) 7 (2,2) 8 (2,3) 9 (2,4) 10 (2,5) 11 (3,1) 12 (3,2) 13 (3,3) 14 (3,4) 15 (3,5) 16 (4,1) 17 (4,2) 18 (4,3) 19 (4,4) 20 (4,5) 21 (5,1) 22 (5,2) 23 (5,3) 70 Chỉ số hóa mạng thành phần Mạng thành phần tương ứng 24 (5,4) 25 (5,5) Khi đó ta có: - Tập các mạng thành phần chứa nút 1 là:  1 1,2,3,4,5,6,8,9,10,11,12,14,15,16,17,18, 20,21,22,23,24L = - Tập các mạng thành phần chứa nút 2 là:  2 2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18, 20,21,22,23,24L = - Tập các mạng thành phần chứa nút 3 là:  3 2,3,4,5,6,8,9,10,11,12,13,14,15,16,17,18,20,21,22,23,24L = - Tập các mạng thành phần chứa nút 4 là:  4 2,3,4,5,6,8,9,10,11,12,14,15,16,17,18,19,20,21,22,23,24L = - Tập các mạng thành phần chứa nút 5 là:  5 2,3,4,5,6,8,9,10,11,12,14,15,16,17,18,20,21,22,23,24,25L = Tại bước 0, giả thiết lưu dòng job tại các nút của mạng hàng đợi là: ( )(0) (0) 1,5 i c i i c L b b i →   =   = . (2.94) 2.3.2. Dòng job luân chuyển trong mạng hàng đợi tại bước n (n≥1) a. Lưu lượng dòng job từ ngoài mạng vào các nút của mạng tại bước n ( )1 2 3 4 51 1 1 1 1 1( ) 0, ( ), ( ), ( ), ( ), ( ),0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0v n v n v n v n v n v n= ( )6 7 8 9 102 2 2 2 2 2( ) 0,0,0,0,0, ( ), ( ), ( ), ( ), ( ),0,0,0,0,0,0,0,0,0,0,0,0v n v n v n v n v n v n= ( )11 12 13 14 153 3 3 3 3 3( ) 0,0,0,0,0,0,0,0,0, ( ), ( ), ( ), ( ), ( ),0,0,0,0,0,0,0,0v n v n v n v n v n v n= ( )16 17 18 19 204 4 4 4 4 4( ) 0,0,0,0,0,0,0,0,0,0,0,0,0, ( ), ( ), ( ), ( ), ( ),0,0,0,0v n v n v n v n v n v n= ( )21 22 23 24 255 5 5 5 5 5( ) 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, ( ), ( ), ( ), ( ), ( )v n v n v n v n v n v n= 71 b. Lưu lượng dòng job đến các nút của mạng hàng đợi tại bước n - Lưu lượng dòng job đến nút 1:     5 1 1 ,1 2: 5 1 ,1 1 2: ( ) ( ) ( 1) ( 1) 1,2,3,4,5 ( ) ( 1) ( 1) \ 1,2,3,4,5 j j c c c c j j j c L c c c j j j c L a n v n b n p n c a n b n p n c L =  =   = + − −      = − −       víi víi . (2.95) - Lưu lượng dòng job đến nút 2:     5 2 2 ,2 1; 2: 5 2 ,2 2 1; 2: ( ) ( ) ( 1) ( 1) 6,7,8,9,10 ( ) ( 1) ( 1) \ 6,7,8,9,10 j j c c c c j j j j c L c c c j j j j c L a n v n b n p n c a n b n p n c L =   =    = + − −      = − −       víi víi . (2.96) - Lưu lượng dòng job đến nút 3:     5 3 3 ,3 1; 3: 5 3 ,3 3 1; 3: ( ) ( ) ( 1) ( 1) 11,12,13,14,15 ( ) ( 1) ( 1) \ 11,12,13,14,15 j j c c c c j j j j c L c c c j j j j c L a n v n b n p n c a n b n p n c L =   =    = + − −      = − −       víi víi . (2.97) - Lưu lượng dòng job đến nút 4:     5 4 4 ,4 1; 4: 5 4 ,4 4 1; 4: ( ) ( ) ( 1) ( 1) 16,17,18,19,20 ( ) ( 1) ( 1) \ 16,17,18,19,20 j j c c c c j j j j c L c c c j j j j c L a n v n b n p n c a n b n p n c L =   =    = + − −      = − −       víi víi . (2.98) - Lưu lượng dòng job đến nút 5:     4 5 5 ,5 1: 4 5 ,5 5 1: ( ) ( ) ( 1) ( 1) 21,22,23,24,25 ( ) ( 1) ( 1) \ 21,22,23,24,25 j j c c c c j j j c L c c c j j j c L a n v n b n p n c a n b n p n c L =  =   = + − −      = − −       víi víi . (2.99) c. Lưu lượng dòng job luân chuyển giữa các mạng thành phần tại bước n Job sau khi đến các nút của mạng hàng đợi thì job sẽ luân chuyển giữa các mạng thành phần. Vì vậy ta có lưu lượng dòng job luân chuyển giữa các mạng thành phần tại nút ( )1,5i i = là: 72 ,( ) ( ) ( ) 1,5 i c d d c i i i i d L r n a n S n c L i   =      =  víi . (2.100) d. Lưu lượng dòng job tại các nút của mạng hàng đợi tại bước n ,( ) ( ) ( 1) ( 1) 1,5 c c c c i i i i i ib n r n b n p n c L i  = + − −    = víi . (2.101) e. Lưu lượng dòng job ra khỏi mạng hàng đợi tại bước n - Lưu lượng dòng job ra ngoài mạng tại nút 1:   1 1 1 1 1,0 1,6,11,16,21 ( ) ( ) ( ) ( 1) ( 1)c c c c c d n a n s n b n p n  = + − − . (2.102) - Lưu lượng dòng job ra ngoài mạng tại nút 2:   2 2 2 2 2,0 2,7,12,17,22 ( ) ( ) ( ) ( 1) ( 1)c c c c c d n a n s n b n p n  = + − − . (2.103) - Lưu lượng dòng job ra ngoài mạng tại nút 3:   3 3 3 3 3,0 3,8,13,18,23 ( ) ( ) ( ) ( 1) ( 1)c c c c c d n a n s n b n p n  = + − − . (2.104) - Lưu lượng dòng job ra ngoài mạng tại nút 4:   4 4 4 4 4,0 4,9,14,19,24 ( ) ( ) ( ) ( 1) ( 1)c c c c c d n a n s n b n p n  = + − − . (2.105) - Lưu lượng dòng job ra ngoài mạng tại nút 5:   5 5 5 5 5,0 5,10,15,20,25 ( ) ( ) ( ) ( 1) ( 1)c c c c c d n a n s n b n p n  = + − − . (2.106) Như vậy với mạng thành phần có 5 nút, luận án đã thực hiện tính toán lưu lượng dòng job luân chuyển giữa các mạng thành phần tại mỗi nút và lưu lượng dòng job tại mỗi nút ở các bước qua đó thấy được quá trình luân chuyển dòng job trong mạng hàng đợi. 2.4. Xây dựng chương trình tính toán lưu lượng dòng job luân chuyển trong mạng hàng đợi Hiện nay có nhiều công cụ dùng để mô phỏng hoạt động của mạng hàng đợi như JMT, GPSS, Petri NetsTuy nhiên vì thuật toán phân rã và tổng hợp 73 mạng là thuật toán mới, chưa từng được công bố trên thế giới nên các công cụ nói trên không thể tính toán lưu lượng dòng job trong mạng hàng đợi theo thuật toán phân rã và tổng hợp mạng. Vì vậy luận án đã tiến hành thiết kế và xây dựng chương trình tính toán lưu lượng dòng job trong mạng hàng đợi theo thuật toán phân rã và tổng hợp mạng. Trong thuật toán phân rã và tổng hợp mạng, ma trận xác suất định tuyến của các mạng thành phần và ma trận xác suất chuyển job tại nút giữa các mạng thành phần là các ma trận phụ thuộc vào lưu lượng dòng job trong mạng hàng đợi và phải áp dụng các công cụ toán học khác để nghiên cứu (chẳng hạn như: lý thuyết đồ thị ngẫu nhiên; bài toán vận tải) vì vậy với mục đích tính toán lưu lượng dòng job trong mạng, luận án giới hạn phạm vi tính toán theo bài toán sau đây: 2.4.1. Nêu bài toán Mạng hàng đợi có J nút. Tại bước ( )0,1,2,...n n = giả thiết đã biết ma trận xác suất định tuyến của các mạng thành phần ( ( ), , 0,( ) ( ) c c i j i j J P n p n c L =  =   ) và ma trận xác suất chuyển job tại nút mạng giữa các mạng thành phần ( ( ) , 0, 0 0 ( ) 1, ( ) ( ) i i i i j J S n i J s n S n =   = =    ). Tính lưu lượng dòng job luân chuyển trong mạng hàng đợi. 2.4.2. Thuật toán xử lý a. Dữ liệu đầu vào - Số nút mạng: J . - Số bước thực hiện thuật toán: n . - Ma trận xác suất định tuyến của các mạng thành phần tại các bước: ( ), , 0,( ) ( ) , 0, c c i j i j J P k p k c L k n =  =  =  . 74 - Ma trận xác suất chuyển job tại nút mạng giữa các mạng thành phần tại các bước: ( ) 0 0 ( ) 1, ; 1, ( ) ( ) i i i S k i J k n s k S k   = = =    . - Lưu dòng job tại các nút của mạng hàng đợi tại bước 0: ( ) ( )(0) (0) 1, i c i i c L b b i J →  = = . - Lưu lượng dòng job vào trong mạng tại các bước: ( )   ( )( ) ( ) 1, ; 1, i c i i c L v k v k i J k n   = = = . b. Dữ liệu đầu ra - Lưu lượng dòng job tại các nút của mạng hàng đợi tại bước n : ( ) ( )( ) ( ) 1, i c i i c L b n b n i J →  = = . - Lưu lượng dòng job ra khỏi mạng hàng đợi tại bước n : ( )( ) 1,id n i J= . 75 2.4.3. Sơ đồ khối thuật toán tổng hợp mạng hàng đợi Bắt đầu i≤ J k= k+1, i= 1 i:=i+1 Kết thúc Đúng Sai k≤ n Đúng Sai   , 1: : ( ) ( ) ( 1) ( 1) i i J c c c i i j j i j j i c L c L a k v k b k p k =       = + − −     ( ) ( ) 0 0 ( ) ( ) i i i i r k a k s k S k =       ( ),( ) ( ) ( 1) ( 1) i c c c i i i i i c L b k r k b k p k  = + − − ,0( ) ( ) ( ) ( 1) ( 1) i c c c c i i i i i c L d k a k s k b k p k  = + − − k=1,i=1 Nhập , , ( ), ( ), ( ), (0)c i iiJ n P k S k v k b ( )1, ; 1, ; ; , 1i J k n c L n J= =   ( ), ( ), ( ), ( ) 1,i i i iv n a n b n d n v i J=íi Hình 2.3. Sơ đồ khối thuật toán tổng hợp mạng hàng đợi 76 2.4.4. Bộ số liệu thử nghiệm - Số nút mạng: 5. - Số bước thực hiện thuật toán: 1.500n = . - Lưu dòng job tại các nút của mạng hàng đợi tại bước 0: ( )(0) 0 1,ib i J → = = . - Lưu lượng dòng job vào trong mạng tại các bước ( 1, )k k n= : ( )1( ) 0,1.5,2.7,3.3,4.5,5.8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0v k = . ( )2( ) 0,0,0,0,0,1.9,2.2,3.5,4.7,5.3,0,0,0,0,0,0,0,0,0,0,0,0v k = . ( )3( ) 0,0,0,0,0,0,0,0,0,1.4,2.8,3.2,4.2,5.3,0,0,0,0,0,0,0,0v k = . ( )4( ) 0,0,0,0,0,0,0,0,0,0,0,0,0,1.3,2.5,3.7,4.2,5.6,0,0,0,0v k = . ( )5( ) 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1.6, 2.2,5.8,4.9,5.25v k = . - Ma trận xác suất định tuyến của các mạng thành phần tại các bước và ma trận xác suất chuyển job tại nút mạng giữa các mạng thành phần tại các bước được trình bày chi tiết trong phụ luc 1. 2.4.5. Kết quả tính toán lưu lượng dòng job luân chuyển trong mạng Với bộ số liệu đã nêu trong mục 2.4.4. Tiến hành chạy chương trình với số bước 1.500n = thu được kết quả như sau: - Lưu lượng dòng job luân chuyển trong mạng hàng đợi tổng quát: Bảng 2.2. Lưu lượng dòng job luân chuyển trong mạng hàng đợi tổng quát Lưu lượng dòng job Từ bên ngoài vào mạng hàng đợi Có trong mạng hàng đợi Ra ngoài mạng hàng đợi Tại bước 1500 89,35 799,115494 89,35 Sau 1500 bước 134.025 799,115494 133.225,8845 77 Biểu đồ sau đây thể hiện lưu lượng dòng job trong mạng hàng đợi (màu xanh) và lưu lượng dòng job ra khỏi mạng hàng đợi (màu vàng) sau một bước tại nút 1: - Lưu lượng dòng job luân chuyển trong các mạng thành phần: Bảng 2.3. Lưu lượng dòng job luân chuyển trong các mạng thành phần Mạng thành phần Tổng lưu lượng dòng job tính đến bước 1500 Từ bên ngoài vào mạng thành phần Có trong mạng thành phần Ra ngoài mạng hàng đợi (1,1) 2.250 12,60788243 4.204,216834 (1,2) 4.050 39,32932462 4.918,873057 (1,3) 4.950 20,04985551 3.665,164656 (1,4) 6.750 45,09474056 4.470,76899 (1,5) 8.700 51,40397691 5.502,54999 (2,1) 2.850 41,63193436 5.614,689284 Hình 2.4. Biểu đồ lưu lượng dòng job trong mạng hàng đợi và ra khỏi mạng hàng đợi sau một bước tại nút 1 L ư u l ư ợ n g Bước 78 Mạng thành phần Tổng lưu lượng dòng job tính đến bước 1500 Từ bên ngoài vào mạng thành phần Có trong mạng thành phần Ra ngoài mạng hàng đợi (2,2) 3.300 5,967150959 4.339,278958 (2,3) 5.250 44,98279315 5.774,393877 (2,4) 7.050 39,86766125 5.929,163096 (2,5) 7.950 35,87407459 6.011,511306 (3,1) 2.100 51,95698861 6.267,406607 (3,2) 4.200 38,8168795 6.067,934758 (3,3) 4.800 7,148387262 4.213,355119 (3,4) 6.300 41,45385828 4.631,618297 (3,5) 7.950 33,61839739 4.620,376289 (4,1) 1.950 34,29333859 5.653,08939 (4,2) 3.750 36,85635209 6.515,458617 (4,3) 5.550 38,21677766 4.852,732452 (4,4) 6.300 9,309737897 5.488,804566 (4,5) 8.400 30,57041979 6.221,182505 (5,1) 2.400 32,09715109 6.753,666188 (5,2) 3.300 28,80401188 5.560,034767 (5,3) 8.700 28,20682512 3.666,221298 (5,4) 7.350 41,59328902 5.910,204863 (5,5) 7.875 9,363685463 6.373,18874 Biểu đồ sau đây thể hiện lưu lượng dòng job trong mạng thành phần (1,1) (màu xanh) và lưu lượng dòng job ra khỏi mạng (1,1) (màu vàng) sau một bước: 79 - Lưu lượng dòng job luân chuyển giữa các mạng thành phần tại các nút: Bảng 2.4. Lưu lượng dòng job luân chuyển giữa các mạng thành phần tại các nút Mạng thành phần Tổng lưu lượng dòng job tính đến bước 1500 Từ bên ngoài vào mạng thành phần Có trong mạng thành phần Ra ngoài mạng hàng đợi Nút 1 (1,1) 2.250 12,6078824 4.204,216834 (1,2) 4.050 12,407703 (1,3) 4.950 3,15734618 (1,4) 6.750 10,6609307 (1,5) 8.700 9,8739859 (2,1) 8,65957368 5.614,689284 (2,3) 6,48519063 (2,4) 5,67447901 (2,5) 6,25160373 Hình 2.5. Biểu đồ lưu lượng dòng job trong mạng thành phần (1,1) và ra khỏi mạng (1,1) sau một bước Bước L ư u l ư ợ n g 80 Mạng thành phần Tổng lưu lượng dòng job tính đến bước 1500 Từ bên ngoài vào mạng thành phần Có trong mạng thành phần Ra ngoài mạng hàng đợi (3,1) 9,22584822 6.267,406607 (3,2) 6,81480403 (3,4) 9,17638423 (3,5) 5,08560445 (4,1) 5,98656283 5.653,08939 (4,2) 4,30938669 (4,3) 5,33192285 (4,5) 4,2972263 (5,1) 8,64964888 6.753,666188 (5,2) 7,03464674 (5,3) 7,31697042 (5,4) 16,05569271 Nút 2 (1,2) 8,312752395 4.918,873057 (1,3) 4,556103139 (1,4) 9,376190115 (1,5) 10,00801823 (2,1) 2.850 9,044423941 (2,2) 3.300 5,967150959 4.339,278958 (2,3) 5.250 10,53417699 (2,4) 7.050 8,70868267 (2,5) 7.950 7,503558952 (3,1) 7,537575982 (3,2) 7,286224608 6.067,934758 (3,4) 5,653904919 81 Mạng thành phần Tổng lưu lượng dòng job tính đến bước 1500 Từ bên ngoài vào mạng thành phần Có trong mạng thành phần Ra ngoài mạng hàng đợi (3,5) 9,804807256 (4,1) 9,097181938 (4,2) 6,71377333 6.515,458617 (4,3) 7,155951065 (4,5) 6,900015205 (5,1) 6,374487996 (5,2) 5,462287653 5.560,034767 (5,3) 4,832680536 (5,4) 5,002912893 Nút 3 (1,2) 4,933298593 (1,3) 5,094873497 3.665,164656 (1,4) 11,3756514 (1,5) 8,311562919 (2,1) 8,892507727 (2,3) 9,627828234 5.774,393877 (2,4) 9,371540606 (2,5) 3,723252313 (3,1) 2.100 5,263648445 (3,2) 4.200 8,882100008 (3,3) 4.800 7,148387262 4.213,355119 (3,4) 6.300 9,050230799 (3,5) 7.950 6,381831605 (4,1) 7,091199965 (4,2) 6,44760602 82 Mạng thành phần Tổng lưu lượng dòng job tính đến bước 1500 Từ bên ngoài vào mạng thành phần Có trong mạng thành phần Ra ngoài mạng hàng đợi (4,3) 6,298365987 4.852,732452 (4,5) 5,2664368 (5,1) 4,32883815 (5,2) 5,146849172 (5,3) 4,421896941 3.666,221298 (5,4) 4,089362451 Nút 4 (1,2) 7,299294036 (1,3) 3,627894482 (1,4) 6,076148758 4.470,76899 (1,5) 13,42538881 (2,1) 8,490673139 (2,3) 5,470647296 (2,4) 8,051616584 5.929,163096 (2,5) 9,295045421 (3,1) 9,582462073 (3,2) 5,441039112 (3,4) 10,418975 4.631,618297 (3,5) 6,250341305 (4,1) 1.950 5,522766871 (4,2) 3.750 11,58246207 (4,3) 5.550 3,802313048 (4,4) 6.300 9,309737897 5.488,804566 (4,5) 8.400 5,24028262 (5,1) 6,288871828 83 Mạng thành phần Tổng lưu lượng dòng job tính đến bước 1500 Từ bên ngoài vào mạng thành phần Có trong mạng thành phần Ra ngoài mạng hàng đợi (5,2) 6,692852558 (5,3) 3,358128843 (5,4) 9,703626444 5.910,204863 Nút 5 (1,2) 6,376276568 (1,3) 3,613638219 (1,4) 7,605819561 (1,5) 9,78502105 5.502,54999 (2,1) 6,544755868 (2,3) 12,86495001 (2,4) 8,061342376 (2,5) 9,100614174 6.011,511306 (3,1) 20,34745389 (3,2) 10,39271175 (3,4) 7,154363322 (3,5) 6,09581278 4.620,376289 (4,1) 6,59562699 (4,2) 7,803123979 (4,3) 15,62822471 (4,5) 8,866458856 6.221,182505 (5,1) 2.400 6,455304242 (5,2) 3.300 4,467375763 (5,3) 8.700 8,277148371 (5,4) 7.350 6,74169452 (5,5) 7.875 9,363685463 6.373,18874 84 Biểu đồ sau đây thể hiện lưu lượng dòng job có trong mạng thành phần (1,1) (màu xanh) và lưu lượng dòng job ra khỏi mạng (1,1) (màu vàng) sau một bước tại nút 1: Chi tiết về thiết kế và xây dựng chương trình tính toán lưu lượng dòng job luân chuyển trong mạng hàng được trình bày tại phụ lục 2. Kết luận chương 2 Chương 2 đã nghiên cứu, đề xuất kỹ thuật phân rã và tổng hợp mạng hàng đợi, trong đó kỹ thuật phân rã nhằm phân tách một mạng bất kỳ thành các mạng thành phần có hướng đơn giản hơn và kỹ thuật tổng hợp cho phép “chập” các mạng thành phần có hướng lại với nhau thành một mạng hàng đợi tổng quát. Kỹ thuật tổng hợp mạng được thực hiện đối với hai trường hợp: trường hợp thứ nhất là tổng hợp các mạng thành phần hoạt động không độc lập với nhau và có sự luân chuyển job từ mạng thành phần này sang mạng thành phần khác tại các nút mạng hàng đợi; trường hợp thứ hai là tổng hợp các mạng Hình 2.6. Biểu đồ lưu lượng dòng job có trong mạng thành phần (1,1) và ra khỏi mạng (1,1) sau một bước tại nút 1 Bước L ư u l ư ợ n g 85 thành phần hoạt động độc lập với nhau, không có sự luân chuyển job từ mạng thành phần này sang mạng thành phần khác. Với kỹ thuật phân rã và tổng hợp mạng khi đó một mạng có J nút bất kỳ luôn luôn được phân rã thành 2J mạng thành phần có hướng (theo định nghĩa 2.1) và mọi mạng hàng đợi bất kỳ có J nút luôn luôn có thể biểu diễn là chập của 2J mạng thành phần có hướng (theo định nghĩa 2.1) với các lưu lượng của dòng job tại bước n được tính theo các công thức (2.79), (2.80), (2.83), (2.85). Với một mô hình mạng hàng đợi cụ thể, luận án đã thể hiện kỹ thuật tổng hợp mạng dưới dạng sơ đồ khối và tiến hành xây dựng chương trình tính toán lưu lượng dòng job luân chuyển trong các mạng hàng đợi này. Kỹ thuật phân rã và tổng hợp mạng cho phép chúng ta nghiên cứu mạng hàng đợi tùy ý với các luồng job đa chiều được xem như là mạng “chập” (“chồng chất”) của các mạng thành phần có hướng và từ cơ sở đó dẫn bài toán nghiên cứu mạng hàng đợi tùy ý về xét bài toán trên các mạng thành phần có hướng đơn giản hơn. Nội dung của chương 2 sử dụng các kết quả đã được công bố trong hai bài báo [2], [3] thuộc danh mục các công trình đã công bố. 86 CHƯƠNG 3 ĐÁNH GIÁ QUÁ TRÌNH TRẠNG THÁI CỦA MẠNG HÀNG ĐỢI DẠNG TỔNG QUÁT Đối với mạng hàng đợi, để xác định được các đặc trưng của mạng hàng đợi như phân phối suất của trạng thái tại các nút mạng và mạng; thông lượng của mạng, xác suất tắc nghẽn của mạng. thì một trong những lớp bài toán vừa có ý nghĩa khoa học vừa có ý nghĩa thực tiễn đã và đang được nhiều tác giả trên thế giới quan tâm là lớp bài toán nghiên cứu quá trình trạng thái của các nút mạng và của mạng hàng đợi. Trong đó các tác giả Hong Chen, David D. Yao ([28]); M. A. M. Ferreira ([39], [40]); Martin Anokye, A. R. Abdul- Aziz, Kwame Annin, Francis T. Oduro ([41]); M Gannon, E Pechersky, Y Suhov, A Yambartsev ([42]); Villy B. Iversen, King - Tim Ko ([53]); Yang Woo Shin, Dug Hee Moon ([54]) đã nghiên cứu về mạng hàng đợi (đơn lớp hoặc đa lớp) có đặc điểm chính như dòng job vào mạng hàng đợi là dòng Poisson, thời gian phục vụ job là biến ngẫu nhiên có phân phối mũ. Các tác giả B. Filipowicz, J. Kwiecien ([14]); Gunter Belch, Stefan Greiner, Hermann de Meer, Kishor S. Trivedi ([20]) sử dụng phương pháp xấp xỉ để nghiên cứu về mạng hàng đợi có các nút mạng là các hàng đợi G/G/1. Kết quả nghiên cứu của các tác giả này liên quan đến quá trình trạng thái tại các nút mạng, quá trình trạng thái của mạng hàng đợi, cường độ (hoặc ma trận xác suất) chuyển trạng thái và các đặc trưng khác của mạng hàng đợi. Trong chương 3, luận án nghiên cứu về mạng hàng đợi có đặc điểm tổng quát hơn, đó là dòng job vào mạng là dòng tổng quát với phân phối bất kỳ và thời gian phục vụ job tại các nút mạng là biến ngẫu nhiên có phân phối bất kỳ. Cụ thể, mạng hàng đợi được nghiên cứu trong chương 3 của luận án thỏa mãn giả thiết như sau: 87 Giả thiết 3.1. Mạng hàng đợi có J nút ( J + ); mỗi nút có một trạm phục vụ; dòng job từ bên ngoài vào mạng hàng đợi là dòng tổng quát với phân phối bất kỳ; thời gian phục vụ job tại mỗi nút của mạng hàng đợi là biến ngẫu nhiên có phân phối bất kỳ và độc lập với nút khác; job sau khi được phục vụ xong tại nút i , job sẽ đến nút j để được phục vụ tiếp hoặc job ra ngoài mạng hàng đợi nếu job đã được phục vụ xong hoàn toàn (về mặt nguyên tắc job có thể quay trở lại nút i để được phục vụ tiếp); dòng job từ ngoài vào mạng độc lập với trạng thái của mạng; các dòng job luân chuyển giữa các nút độc lập với nhau và độc lập với trạng thái của nút đến. Với giả thiết 3.1 khi đó dòng job luân chuyển trong mạng hàng đợi được thể hiện bởi sơ đồ 3.1, trong đó nút 0 (nút hình thức) được bổ sung vào nhằm mô tả dòng job từ ngoài vào mạng và dòng job từ trong mạng ra ngoài, với cấu trúc có thêm nút 0 thì job từ ngoài vào mạng là job từ nút 0 vào các nút khác trong mạng và job từ trong mạng ra khỏi mạng là job từ các nút khác chuyển tới nút 0. Nội dung chính của chương 3 trình bày một số kết quả nghiên cứu trạng thái của mạng hàng đợi tổng quát dạng G/G/J ( J + ). Cụ thể, nếu gọi 0 0 Hình 3.1. Mô hình mạng hàng đợi dạng tổng quát G/G/J 1 2 J 88 ( ) ( 1, ) j X t j J= là trạng thái nút j tại thời điểm t ( ( ) j X t là số job có trong nút j tại thời điểm t ), trạng thái mạng hàng đợi là véc tơ ( )1( ) ( ), ..., ( )JX t X t X t= ; các kết quả nghiên cứu thu được tập trung về các tính chất của các quá trình ( ) j X t đồng thời cũng đưa ra các kết quả về tính chất của quá trình nhiều chiều ( )X t trong bối cảnh dòng vào tổng quát. Bên cạnh đó, trong chương 3, luận án cũng trình bày các tính c