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

ạng thành phần Giả thiết 2.1. Biết dòng job luân chuyển trong các mạng thành phần. Trong mạng chập của các mạng thành phần, các mạng thành phần hoạt động không độc lập với nhau và biết cơ chế luân chuyển job giữa các mạng thành phần (cơ chế luân chuyển này còn được gọi là cơ chế chuyển pha trong mạng hàng đợi). Định nghĩa 2.2. Quá trình luân chuyển job trong mạng chập được phân chia thành các bước và được định nghĩa như sau: 7 Xét quá trình lưu chuyển dòng job trong mạng hàng đợi. Ký hiệu ( )ij t là lượng job chuyển từ nút i sang nút j tại thời điểm t ( , 0,i j J= ). Trong đó ( )0j t là lượng job từ bên ngoài mạng vào trong nút j tại thời điểm t, ( )j0 t là lượng job từ nút j ra khỏi mạng tại thời điểm t và ( )ij t là lượng job chuyển từ nút i sang nút j tại thời điểm t ( ), 1, ,i j J i j=  . Với quy ước 0 là thời điểm quan sát xuất phát ban đầu và thời điểm n được định nghĩa qui nạp như sau: ( ) ( ) ( ) ( ) 1 0 0j ij 1 1 0, 1 0j ij 1 1 0, min | 0 ... min | 0 , 2,3,... J J J j i j j i J J J n n j i j j i t t t t t t n         = = =  − = = =    =  +       =  +  =          Khi đó mỗi một điểm ( )0,1,...n n = được xem như là bước luân chuyển thứ n của dòng job trong mạng hàng đợi. Để mô tả dòng job từ các mạng thành phần tại các nút của mạng chập ra ngoài mạng chập và dòng job ngoài mạng chập vào các mạng thành phần tại các nút của mạng chập, chúng ta bổ sung thêm mạng thành phần ( )0,0= (mạng thành phần hình thức), mạng hình thức này không chứa bất kỳ nút nào của mạng chập (là ký hiệu của môi trường ngoài của mạng chập). Dòng job ngoài mạng chập vào các mạng thành phần tại các nút của mạng chập chính là dòng job từ mạng ( )0,0= vào các mạng thành phần tại các nút của mạng chập, dòng job ra khỏi các mạng thành phần tại các nút của mạng chập chính là dòng job từ các mạng thành phần tại các nút của mạng chập vào mạng ( )0,0= . Các ký hiệu: - ( )   , | , 1,2,...,L i j i j J=  là tập tất cả các mạng thành phần của mạng hàng đợi; i L là tập các mạng thành phần có chứa nút ( )1,i i J= . Tại bước ( )1,2,...n n = : + , , 0, ( ) ( )c c i j i j J P n p n =  =   là ma trận xác suất định tuyến của mạng thành phần c (c L ) trong đó , ( ) c i jp n là xác suất định tuyến job chuyển từ nút i sang nút j trong mạng thành phần c . + 0 0 ( ) ( ) ( ) i i i S n s n S n   =      trong đó , , ( ) ( ) i c d i i c d L S n S n   =   là ma trận xác suất chuyển job trong nút i giữa các mạng thành phần với , ( )c diS n là xác suất chuyển job trong nút i từ mạng thành phần c sang mạng thành phần d và 8 ( )( ) ( ) i T c i i c L s n s n  = là véc tơ xác suất chuyển job từ nút i ra ngoài mạng hàng đợi với ( )cis n là xác suất chuyển job từ nút i trong mạng thành phần c ra ngoài mạng hàng đợi. + ( ) ( )( )   i c i i c L a n a n   = là véc tơ chỉ lưu lượng dòng job đến nút i trong mạng hàng đợi. Trong đó ( )cia n là lưu lượng dòng job đến nút i của mạng thành phần c ( ic L ) và ( ) 0ia n  = . + ( ) ( )( ) i c i i c L b n b n  = là véc tơ chỉ lưu lượng dòng job tại nút i trong mạng hàng đợi. Trong đó ( )cib n là lưu lượng dòng job tại nút i trong mạng thành phần c . + ( ) ( )( )   i c i i c L v n v n   = là véc tơ chỉ lưu lượng dòng job từ ngoài mạng hàng đợi vào nút i trong mạng hàng đợi. Trong đó ( )civ n là lưu lượng dòng job từ bên ngoài vào trong mạng thành phần c ( ic L ) tại nút i và ( ) 0iv n  = . + ( )id n là lưu lượng dòng job từ nút i ra khỏi mạng hàng đợi. 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 c L sử dụng tại bước thứ n ta có: ,( ) ( ) 1 i c c d i i d L s n S n  + = . (2.2) - Với mọi nút i được mạng thành phần ( ),h l L sử dụng tại bước n ta có: ( , ) ( , ) 0,i i,h ( , ) i,j 0 ( , ) ( , ) i,j j,i ( , ) ( , ) ( , ) , ,0 ( ) 1 ; ( ) 0 ( ) 1 ( ) ( ) 0 1, ( ) 0 ; ( ) 0, ( ) 0 h l h l J h l j h l h l h l h l h l l i i i p n n u i h p n n u i h p n p n p n v i j J v j i p n n u i l p n s n n u i l =  = = =    =   =  =    =  = =   Õ Õ í µ Õ Õ . (2.3) - Với mọi nút i không được mạng thành phần ( ),h l L sử dụng tại bước thứ n ta có: ( , ) ( , ) i,j j,i 0 ( , ) ( ) ( ) 0 ( ) 0 J h l h l j h l i p n p n s n =  + =   =  . (2.4) 2.2.1.1. Xác định 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 (1):=(i1 ,j1) và (2):=(i2 ,j2) Từ đặc điểm về dòng job luân chuyển trong mạng thành phần khi đó: - Nếu 1 1i j và 2 2i j :     1 2 1 2 1 2 1 2 (1), (2) (1) i n u i i ho c j j L n u i i v j j   =  = = Õ Æ Õ µ . 9 - Nếu 1 1i j và 2 2i j= :     2 2 (1), (2) (1) i i L L v i i i  =  =   í . - Nếu 1 1i j= và 2 2i j :     1 1 (1), (2) (2) i i L L v i i i  =  =   í . - Nếu 1 1i j= và 2 2i j= :       1 2 1 2 1 2 (1) (2) ( ) , i i i L L L v i i i i i i i  =  =  =       í hoặc     1 2 1 1 2 (1) ( ) i i i L L L v i i i i i  = =  =     = í . - Luân chuyển job trong mạng hàng đợi Γ ở bước n (n≥1) Lưu lượng dòng job từ ngoài mạng vào trong nút ( )1,i i J= mạng hàng đợi Γ ở bước n là: ( )   ( ) ( ) i c i i c L v n v n   = . (2.5) Lưu lượng dòng job đến nút i trong mạng hàng đợi Γ ở bước n là: ( )   ( ) ( ) i c i i c L a n a n   = với 1, , ( ) ( ) ( 1) ( 1) j J c c c c i i j ji j j i c L a n v n b n p n =   = + − − . (2.6) 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 i ở bước n là: ( )   ( )   (1) (1) (1) (1),(1) (2) (2) (2) (2),(2) (1) (1) (2) (2) (1) (1),(1) (2) (2),(1) (1) (1),(2) ( ( ) ( ) , ( ) ( ) (1) ( ) ( ) , ( ) ( ) (2) ( ) ( ) ( ) ( ) ( ), ( ) ( ) ( ) ( ) , ( ) ( ) i i i i i i i i i i i i i i i i i i i i i i a n s n a n S n n u L a n s n a n S n n u L r n a n s n a n s n a n S n a n S n a n S n a = = = + + + Õ Õ   2) (2),(2) (1), (2) ( ) ( ) i i n u L n S n        =      Õ . (2.7) Lưu lượng dòng job tại nút i của mạng hàng đợi Γ ở bước n là: ( )   ( )   (1) (1),(1) (1) (1) , (2) (2),(2) (2) (2) , (1) (1),(1) (2) (2),(1) (1) (1) , (1) (1),(2) ( ) ( ) ( 1) ( 1) (1) ( ) ( ) ( 1) ( 1) (2) ( ) ( ) ( ) ( ) ( ) ( 1) ( 1), ( ) ( ) i i i i i i i i i i i i i i i i i i i i i i i a n S n b n p n n u L a n S n b n p n n u L b n a n S n a n S n b n p n a n S n a + − − = + − − = = + + − − + Õ Õ   (2) (2),(2) (2) (2) , (1), (2) ( ) ( ) ( 1) ( 1) i i i i i n u L n S n b n p n        =    + − −    Õ . (2.8) Và lưu lượng dòng job từ nút i ra ngoài mạng hàng đợi Γ ở bước n là:       (1) (1) (1) (1) ,0 (2) (2) (2) (2) ,0 (1) (1) (2) (2) (1) (1) (2) (2) ,0 ,0 ( ) ( ) ( 1) ( 1) (1) ( ) ( ) ( ) ( 1) ( 1) (2) ( ) ( ) ( ) ( ) ( 1) ( 1) ( 1) ( 1) (1), (2) i i i i i i i i i i i i i i i i i i i i a n s n b n p n n u L d n a n s n b n p n n u L a n s n a n s n b n p n b n p n n u L  + − − =  = + − − =  + + − − + − − = Õ Õ Õ . (2.9) 10 Như vậy trong mục này luận án đã trình bày quá trình luân chuyển job của mạng hàng đợi được chập bởi 2 mạng thành phần. Công thức (2.8) thể hiện sự thay đổi về lưu lượng dòng job tại các nút mạng tại các bước qua đó thấy được sự luân chuyển job trong mạng hàng đợi. Công thức (2.9) thể hiện năng lực phục vụ của mạng hàng đợi. 2.2.1.2. Xác định luân chuyển job trong mạng hàng đợi Γ được chập bởi J2 mạng thành phần. - Luân chuyển job trong mạng hàng đợi Γ ở bước n (n≥1) Với lưu lượng dòng job từ ngoài mạng vào trong nút ( )1,i i J= của mạng hàng đợi Γ ở bước n là ( ) ( )( )   i c i i c L v n v n   = . (2.10) Khi đó lưu lượng dòng job đến nút i của mạng hàng đợi Γ ở bước n là: ( )   ( ) ( ) i c i i c L a n a n   = với 1; : ( ) ( ) ( 1) ( 1) j J c c c c i i j ji j j i c L a n v n b n p n =   = + − − . (2.11) 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 i ở bước n là: ( ) : ( ) ( )i i ir n a n S n= . (2.12) Lưu lượng dòng job tại nút i của mạng hàng đợi Γ ở bước n là: ( )( ) ( ) i c i i c L b n b n  = với ( ) ( ) ( 1) ( 1)c c c ci i i iib n r n b n p n= + − − . (2.13) Lưu lượng dòng job từ nút i ra ngoài mạng hàng đợi Γ ở bước n là: ( ) ( ) ,0( ) ( ) ( ) ( 1) ( 1) i c c c c i i i i i c L d n a n s n b n p n  = + − − . (2.14) Như vậy trong mục này luận án đã trình bày quá trình luân chuyển job của mạng hàng đợi được chập bởi 2J mạng thành phần. Công thức (2.13) thể hiện sự thay đổi về lưu lượng dòng job tại các nút mạng tại các bước qua đó thấy được sự luân chuyển job trong mạng hàng đợi. Công thức (2.14) thể hiện năng lực phục vụ của mạng hàng đợi tại các bước. Với lập luận và chứng minh ở trên, chúng ta có định lý sau đây: Định lý 2.2. 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à với các lưu lượng của dòng job (các thành phần ( )iv n , ( )ia n , ( )ib n , ( )id n ) tại bước n được tính theo các công thức (2.10),(2.11),(2.13),(2.14). 2.2.2. Xét trường hợp riêng – trong mạng chập không có sự luân chuyển dòng job giữa các mạng thành phần Các ký hiệu: - ( )   , | , 1,2,...,L i j i j J=  là tập tất cả các mạng thành phần của mạng hàng đợi tổng quát có J nút. 11 - ( , ) ( , )i,j , 0, h l h l i j J P p =  =   là ma trận xác suất định tuyến của mạng thành phần ( ),h l ( ( , )h l L ). Trong đó ( , ) i,j h lp là xác suất định tuyến job chuyển từ nút i sang nút j trong mạng thành phần ( ),h l tại thời điểm t , ( , )0,i h lp là xác suất định tuyến job từ ngoài mạng thành phần ( ),h l vào nút i trong mạng thành phần ( ),h l tại thời điểm t và ( , ) j,0 h lp là xác suất định tuyến job chuyển từ nút j trong mạng thành phần ( ),h l ra ngoài mạng thành phần ( ),h l tại thời điểm t ; - i,j , 0,i j JP p = =   là ma trận xác suất định tuyến của mạng chập. Trong đó i,jp là xác suất định tuyến job chuyển từ nút i sang nút j trong mạng chập tại thời điểm t , 0,ip là xác suất định tuyến job từ ngoài mạng chập vào nút i trong mạng chập tại thời điểm t và ,0jp là xác suất định tuyến job chuyển từ nút j ra ngoài mạng chập tại thời điểm t . - ( , ) , h l i jA là biến cố job chuyển từ nút i sang nút j trong mạng thành phần ( ),h l ( ( , )h l L ) tại thời điểm t , ( , ) 0, h l iA là biến cố job từ ngoài mạng thành phần ( ),h l vào nút i trong mạng thành phần ( ),h l tại thời điểm t và ( , ),0 h l jA là biến cố job chuyển từ nút j trong mạng thành phần ( ),h l ra ngoài mạng thành phần ( ),h l tại thời điểm t ; ,i jA là biến cố job chuyển từ nút i sang nút j trong mạng chập tại thời điểm t , 0,iA là biến cố job từ ngoài mạng chập vào nút i trong mạng chập tại thời điểm t và ,0jA là biến cố job chuyển từ nút j trong mạng chập ra ngoài mạng chập tại thời điểm t . Giả thiết 2.2. Giả thiết rằng đã biết dòng job luân chuyển trong các mạng thành phần. Trong mạng chập của các mạng thành phần giả thiết rằng dòng job luân chuyển trong các mạng thành phần độc lập với nhau và 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. 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.15) - 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ó: 12 ( )( , ), 0 0 J h l i j j p t = = . (2.16) 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 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.17) 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 p t p t p t p t  = + −  . (2.18) Từ giả thiết 2.2 và công thức (2.18) 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ó: ( ) ( )( , ), , ( , ) k l i j i j k l L A t A t  = . (2.19) 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ó: ( ) ( )( )( , ), , ( , ) 1 1 k li j i j k l L A t p t    = − −   . (2.20) Từ giả thiết của bài toán 2.2 và công thức (2.20) 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ề 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. 2.3.1. Tập các 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: 13 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 tương ứng Chỉ số hóa Mạng thành phần tương ứng Chỉ số hóa Mạng thành phần tương ứng 1 (1,1) 10 (2,5) 19 (4,4) 2 (1,2) 11 (3,1) 20 (4,5) 3 (1,3) 12 (3,2) 21 (5,1) 4 (1,4) 13 (3,3) 22 (5,2) 5 (1,5) 14 (3,4) 23 (5,3) 6 (2,1) 15 (3,5) 24 (5,4) 7 (2,2) 16 (4,1) 25 (5,5) 8 (2,3) 17 (4,2) 9 (2,4) 18 (4,3) 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 = 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 hàng đợi 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= 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 ( ) ( ) ( ) ( ) 1, : 1 1 , 1,5 j J c c c c i i j ji i j j i c L a n v n b n p n v i c L i =   = + − −   = í . (2.21) 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 14 ,( ) ( ) ( ) , 1,5 i d c c d i i i i c L r n a n S n d L i  =   = . (2.22) d. Lưu lượng dòng job tại các nút của hàng đợi tại bước n ( ) ( ) ( )1 ( 1) , 1,5c c ci i i ii ib n r n b n p n c L i= + − −   = . (2.23) e. Lưu lượng dòng job ra ngoà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.24) - 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.25) - 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.26) - 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.27) - 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.28) Như vậy 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 hiện có 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 có 5 nút. 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 Chương trình tính toán được thiết kế và xây dựng cho phép tạo lập một mạng hàng đợi với tổng số nút mạng tùy ý. Các tham số của mạng hàng đợi có thể tùy biến và cho phép lưu vào các tệp tin cấu hình cho phép tái sử dụng trong các lần chạy phần mềm thay vì phải thiết lập lại tham số mỗi khi chạy chương trình. Một số kết quả tính toán lưu lượng dòng job luân chuyển trong mạng được thể hiện trực quan dưới dạng biểu đồ thể hiện. 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 cho trước. Với kỹ thuật phân rã và tổng hợp mạng này 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 15 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. 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 Nội dung của chương 3 sử dụng các kết quả đã được công bố trong bài báo [1] thuộc danh mục các công trình đã công bố. Đối với mạng hàng đợi, 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 là 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. Chương 3 nghiên cứu lớp bài toán này với điều kiện 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 thỏa mãn giả thiết sau: 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. 3.1. Trạng thái và phương trình chuyển trạng thái của nút mạng 3.1.1. Định nghĩa, ký hiệu Gọi n  là thời điểm lần thứ ( )0,1,2,...n n = xuất hiện sự kiện job từ bên ngoài vào mạng hàng đợi hoặc job được phục vụ xong tại nút mạng nào đó (Xem định nghĩa 2.2 trong chương 2), trong đó 0 là thời điểm quan sát xuất phát ban đầu. a. Định nghĩa 3.1. Phân phối tựa nhị thức Cho ( )n n + biến ngẫu nhiên độc lập  | 1,i i n = có phân phối ( )iA q và ký hiệu là ( )i iA q  ( 1, )i n= (ở đây ( )iA q là phân phối của biến ngẫu nhiên Bernoulli với tham số iq ). Đặt 1 n i i   = = khi đó  được gọi là biến ngẫu nhiên có phân phối tựa nhị thức và được ký hiệu 1( ; ,..., )nB n q q  . Tính chất: ( ) ( )   1 1 1 ... 0 ,..., 0,1 [ =k] 1 i i n n i i k i n q q        − + + =    = −  . (3.1) 16 ( ) 1 n i i E q = = và ( ) ( ) 1 1 n i i i D q q = = − . (3.2) Trong trường hợp đặc biệt khi 1, i q q i n=  = , ta được phân phối nhị thức ( ; )B n q thông thường. b. Ký hiệu: - ( )j nX  là số job có trong nút j tại thời điểm n và được gọi là trạng thái nút j tại thời điểm n ( 1, , 1,2,...)j J n= = . 1( ) ( ( ),..., ( ))n n J nX X X  = là trạng thái mạng hàng đợi tại thời điểm n . - ijp là xác suất job chuyển từ nút i sang nút j ( )1, , 0,i J j J= = , trong đó 0ip là xác suất job được phục vụ xong tại nút i và ra khỏi mạng hàng đợi; iip là xác suất job vẫn còn tiếp tục được phục vụ tại nút i (trong chương này chúng ta xét xác suất chuyển (xác suất định tuyến) là không thay đổi theo thời gian). - jN là kích thước của hàng đợi tại nút j của mạng ( 1, , jj J N=  );  0,1,...,j jE N= . 3.1.2. Phương trình chuyển trạng thái của nút mạng Vì ( )ij n  là số job từ nút ( )1,i i J= chuyển sang nút j tại thời điểm n do vậy tổng số job ra khỏi nút i tại thời điểm n là: ( ) ( ) 0, J n ij n j j i d    =  =  . (3.3) Từ giả thiết về mạng hàng đợi và từ định nghĩa về thời điểm n khi đó ta có: ( ) ( ) ( ) 1 1, 1, 1, ( ) 1, (1 ) 1, ( 1, ,..., , ,..., ) 0,1,2,... ij n ij n ii J ij n j j j j j Jj i i j A p i J d A p i J B J p p p p n      − + =     =    −  =    −   =  . (3.4) Ký hiệu ( )j nA  là số job từ bên ngoài vào nút j trong khoảng thời gian ( 1,n n n  − = . Khi đó số job có trong nút j tại thời điểm n được xác định như sau: 1 0, 1, ( ) ( ) ( ) ( ) ( ) J J j n j n j n ji n ij n i i j i i j X X A      − =  =  = + − +  . (3.5) Công thức (3.5) chính là phương trình chuyển trạng thái tại nút j của mạng hàng đợi. 17 3.1.3. Phân phối xác suất chuyển trạng thái của nút mạng Ký hiệu 1 1 1 , ( ) ( , , , ) n n j j n j n n n n x x E Q q x x   − − −   =   trong đó 1 1 1 1 ( , , , ) ( ) | ( ) j n n n n j n n j n n q x x X x X x    − − − −  = = =  là xác suất chuyển trạng thái của quá trình trạng thái tại nút j từ trạng thái 1nx − tại thời điểm 1n − sang trạng thái nx tại thời điểm n . Khi đó: - Nếu 1 1n nx x − − : 1 1( , , , ) 0j n n n nq x x − − = . (3.6) - Nếu 1 1n nx x −= − : ( ) ( )1 1 1, ( , , , ) 1 1 ( ) 0 J j n n n n jj ij j n i i j q x x p p A  − − =   = − − =  . (3.7) - Nếu ( )1n nx x k k−= +  : ( ) ( )     ( ) ( ) ( )     1 1 1 1 min , 1 1 1 1 0 ... 1; ,..., 0,1 min 1, 1 1 0 ... 1; ,..., 0,1 ( , , , ) 1 ( ) 1 1 ( ) 1 i i n n i i n n k J J j n n n n jj ij ij j n y y i i j k J J jj ij ij j n y y i i j q x x p p p A k y p p p A k y                 − − − − = + + = =   + − − = + + = =    = − = −   + − − = + −        (3.8) Từ công thức (3.6), (3.7) và (3.8) ta có lược đồ chuyển trạng thái của ( )( ) ; 0,1,...j nX n = sau một bước như sau: 3.2. Phân phối và tính chất của quá trình trạng thái 3.2.1. Phân phối xác suất của trạng thái tại nút mạng sau một bước Giả sử rằng tại thời điểm 1n − đã biết phân phối xác suất của 1( )j nX  − khi đó từ phương trình chuyển trạng thái (3.5) và với jm E  ta có: 1 1 0 ( ) ( ) ( , , )j n j n j m l X m X l H m l n  − + =    = = =    . (3.9) Với 1 ( , ) 0 n u l g m l n u l  =   Õ m Õ > m và     min , 1 0, 0 1, min 1 , 1 0, 0 1, ( , , ) ( , ) ( ) 0 ( ) ( ) ( ) 1 ( ) ( ) 1 m l JJ J j ji n ij n j n i i j y i i j m l JJ J ji n ij n j n i i j y i i j H m l n g m l y A m l y y A m l y           − − =  = =  + − − =  = =       = = = = − −               + = = = + − −                Hình 3.1. Lược đồ chuyển trạng thái của quá trình trạng thái tại nút mạng m m+1 m+k m+2 m-1 1 2 0 18 Nhận xét 3.1. Nếu biết được phân phối xác suất của trạng thái nút j tại thời điểm hiện tại và phân phối xác suất của dòng job từ bên ngoài mạng vào nú