Cơ chế luân chuyển dòng Job trong mạng hàng đợi dạng tổng quát G/G/J - Nguyễn Trung Dũng

Kỹ thuật điện tử & Khoa học mỏy tớnh N.T.Dũng,T.Q.Vinh, “Cơ chế luõn chuyển dũng job trong mạng hàng đợi dạng tổng quỏt G/G/J.” 62 CƠ CHế LUÂN CHUYểN DòNG JOB TRONG MạNG HàNG ĐợI DạNG TổNG QUáT G/G/J NGUYỄN TRUNG DŨNG*, TRẦN QUANG VINH** Túm tắt: Trong bài bỏo này, chỳng tụi trỡnh bày kỹ thuật kết hợp giữa phõn ró và tổng hợp để xột một mạng đa lớp tổng quỏt với cỏc luồng thụng tin đa chiều được xem như là mạng tổng hợp (chập) của cỏc mạng cú hướng (mạng thành phần) và từ cơ sở đú dẫn bài toỏn nghiờn cứu mạng phức tạp về xột bài toỏn trờn cỏc mạng đơn giản thành phần. Bài bỏo trỡnh bày kết quả nghiờn cứu mạng thành phần và cỏc kết quả liờn quan đến mạng tổng hợp của cỏc mạng mạng thành phần đú. Từ khúa: Mạng hàng đợi; Nỳt; Job. 1. ĐẶT VẤN ĐỀ Đối với mạng hàng đợi, bài toỏn đỏnh giỏ hoạt động, bài toỏn xỏc định cơ chế luõn chuyển job trong mạng núi chung và mạng đa lớp núi riờng là những bài toỏn phức tạp. Cú rất nhiều cụng trỡnh nghiờn cứu của nhiều tỏc giả đó đề cập đến cỏc bài toỏn nờu trờn. Mạng hàng đợi được đề cập đến trong [1] là mạng hàng đợi đơn lớp với đặc điểm chớnh của mạng hàng đợi này là cú dũng job từ bờn ngoài vào mạng là dũng vào tổng quỏt và cú thể đến bất kỳ nỳt nào trong mạng hàng đợi, job sau khi được phục vụ xong tại một nỳt cú thể đến bất kỳ nỳt khỏc hoặc ra khỏi mạng (nếu đó được phục vụ xong). Mạng hàng đợi được đề cập trong [2] là mạng hàng đợi đa lớp được nghiờn cứu bởi tỏc giả Kelly. Trong bài bỏo này, chỳng tụi nghiờn cứu về cơ chế luõn chuyển job trong mạng đa lớp tổng quỏt. Để tiện cho việc mụ tả dũng job từ ngoài mạng vào trong mạng và dũng job từ trong mạng ra ngoài, chỳng ta bổ sung thờm nỳt 0 (nỳt hỡnh thức) vào mạng. Như vậy, job từ bờn ngoài vào mạng chớnh là job từ nỳt 0 vào cỏc nỳt khỏc trong mạng hàng đợi và job từ trong mạng ra khỏi mạng chớnh là job từ cỏc nỳt khỏc chuyển tới nỳt 0 . Hỡnh 1 thể hiện dũng job từ bờn ngoài vào mạng tổng quỏt và dũng job luõn chuyển giữa cỏc nỳt trong mạng tổng quỏt: Bài bỏo trỡnh bày kỹ thuật kết hợp giữa phõn ró và tổng hợp để xột một mạng tổng quỏt với cỏc luồng thụng tin đa chiều được xem như là mạng tổng hợp (“chập”) của cỏc mạng thành phần và từ cơ sở đú dẫn bài toỏn nghiờn cứu mạng phức tạp về xột bài toỏn trờn cỏc mạng đơn giản i j 0 0 Hỡnh 1. Dũng job luõn chuyển trong mạng tổng quỏt. Nghiên cứu khoa học công nghệ Tạp chớ Nghiờn cứu KH&CN quõn sự, Số 36, 04 - 2015 63 thành phần. Mỗi một mạng thành phần được ký hiệu là  ,i j (trong đú i và j là cỏc nỳt của mạng) và cú cỏc đặc điểm: Dũng job từ bờn ngoài chỉ vào nỳt i của mạng và dũng job ra khỏi mạng chỉ tại nỳt j . Hỡnh 2 thể hiện dũng job từ ngoài vào mạng và dũng job luõn chuyển giữa cỏc nỳt trong mạng thành phần: Như vậy, mạng tổng quỏt chớnh là mạng chập (tổng hợp-tớch hợp) của 2J mạng thành phần  ,i j với  , 1, 2,...,i j J và job cú trong cựng một mạng thành phần thỡ được coi là cựng một lớp. Với việc phõn ró mạng tổng quỏt thành cỏc mạng thành phần, khi đú chỳng ta cú thể biết được hoạt động của mạng tổng quỏt dựa trờn việc nghiờn cứu hoạt động của cỏc mạng thành phần. Cấu trỳc bài bỏo gồm cú 4 phần chớnh: 1. Đặt vấn đề. 2. Dũng job luõn chuyển trong mạng hàng đợi dạng tổng quỏt G/G/J với điều kiện Job khụng luõn chuyển giữa cỏc mạng thành phần. 3. Dũng job luõn chuyển trong mạng hàng đợi dạng tổng quỏt G/G/J với điều kiện Job cú thể luõn chuyển giữa cỏc mạng thành phần. 4. Kết luận. 2. DềNG JOB LUÂN CHUYỂN TRONG MẠNG HÀNG ĐỢI TỔNG QUÁT G/G/J VỚI ĐIỀU KIỆN JOB KHễNG LUÂN CHUYỂN GIỮA CÁC MẠNG THÀNH PHẦN Trong mục này chỳng ta giả thiết rằng đó biết dũng job luõn chuyển bờn trong cỏc mạng thành phần trong bối cảnh mạng thành phần hoạt động riờng rẽ và độc lập. Trong mạng chập chỳng ta giả thiết rằng dũng job thuộc mạng thành phần nào thỡ chỉ luõn chuyển trong mạng thành phần đú và độc lập với dũng job thuộc mạng thành phần khỏc. Với cỏc yếu tố đó biết nờu trờn, chỳng ta cần nghiờn cứu và xỏc định dũng job luõn chuyển trong mạng chập. 2.1. Một số ký hiệu ( , ) ( , ) i,j , 0, h l h l i j J P p      là ma trận xỏc xuất job chuyển từ nỳt i sang nỳt j trong mạng  ,h l   , 1, 2,...,h l J tại thời điểm t ; i,j , 0,i j JP p     là ma trận xỏc xuất job chuyển từ nỳt i sang nỳt j trong mạng hàng đợi tổng quỏt tại thời điểm t . i j 0 0 Hỡnh 2. Dũng job luõn chuyển trong mạng thành phần. Kỹ thuật điện tử & Khoa học mỏy tớnh N.T.Dũng,T.Q.Vinh, “Cơ chế luõn chuyển dũng job trong mạng hàng đợi dạng tổng quỏt G/G/J.” 64 2.2. Dũng job trong mạng hàng đợi là chập của hai mạng thành phần Xột mạng hàng đợi tổng quỏt G là chập của 2 mạng thành phần  1 1,i j và  2 2,i j . Như đó trỡnh bày tại mục 1 về đặc điểm dũng job luõn chuyển trong mạng thành phần khi đú ta cú: ( , ) i,j 0 k ki jp t  nếu , 0 , 0 , 0 k k k j i i i j j i j j         Và ( , ) i,j 0 1 1, 1, 2 k k J i j j p i J k          Ký hiệu: ( , ), k ki j i jA ( 1, 2k  ) là biến cố job chuyển từ nỳt i sang nỳt j trong mạng  ,k ki j 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 hàng đợi G tại thời điểm t . Khi đú ta cú: 1 1 2 2( , ) ( , ) , , , i j i j i j i j i jA A A   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 A P A P A P A A                 Với giả thiết rằng hai mạng  1 1,i j và  2 2,i j độc lập với nhau. Khi đú 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 A P A P A P A P A                     Mà 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 P A p P A p P A                 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 p p p p   (2.1) Với giả thiết đó nờu ở trờn, từ cụng thức (2.1) khi đú nếu mạng hàng đợi G là chập của hai mạng thành phần và nếu biết xỏc xuất job luõn chuyển giữa cỏc nỳt trong hai thành phần. Khi đú chỳng ta sẽ xỏc định được xỏc xuất job luõn chuyển giữa cỏc nỳt trong mạng hàng đợi G . 2.3. Dũng job trong mạng hàng đợi tổng quỏt G/G/J Nếu mạng hàng đợi tổng quỏt cú J nỳt khi đú chỳng ta sẽ phõn ró mạng hàng đợi tổng quỏt thành 2J mạng thành phần. 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. ( , ), k l i jA là biến cố job chuyển từ nỳt i sang nỳt j trong mạng  ,k l 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 hàng đợi tổng quỏt tại thời điểm t . Khi đú ta cú:   ( , ) , , , k l i j i j k l L A A       ( , ) , , , k l i j i j k l L P A P A              ( , ) , , , 1 k li j i j k l L P A P A               ( , ) , , , 1 k li j i j k l L P A P A               Giả thiết rằng hoạt động của cỏc mạng thành phần độc lập với nhau.    ( , ) , , , 1 k li j i j k l L P A P A               ( , ) , , , 1 1 k li j i j k l L P A P A                ( , ) i,j i,j , 1 1 k l k l L p p     (2.2) Nghiên cứu khoa học công nghệ Tạp chớ Nghiờn cứu KH&CN quõn sự, Số 36, 04 - 2015 65 Với giả thiết đó nờu ở trờn, từ cụng thức (2.2) khi đú nếu chỳng ta biết xỏc xuất job chuyển giữa cỏc nỳt trong tất cả cỏc mạng thành phần cấu thành mạng hàng đợi tổng quỏt. Khi đú chỳng ta sẽ xỏc định được xỏc xuất job luõn chuyển giữa cỏc nỳt trong mạng tổng quỏt. 3. DềNG JOB LUÂN CHUYỂN TRONG MẠNG HÀNG ĐỢI TỔNG QUÁT G/G/J VỚI ĐIỀU KIỆN JOB Cể THỂ LUÂN CHUYỂN GIỮA CÁC MẠNG THÀNH PHẦN Trong mục nay chỳng ta giả thiết rằng đó biết dũng job luõn chuyển trong cỏc mạng thành phần trong bối cảnh mạng thành phần hoạt động riờng rẽ (độc lập). Khi chập cỏc mạng thành phần này lại với nhau khi đú tại mỗi nỳt của mạng chập xuất hiện hiện tượng job luõn chuyển giữa cỏc mạng thành phần và giả thiết rằng chỳng ta biết được phõn phối luõn chuyển job giữa cỏc mạng thành phần này tại mỗi nỳt. Với cỏc yếu tố đó biết nờu trờn, chỳng ta cần nghiờn cứu và xỏc định dũng job luõn chuyển trong mạng chập. Để thấy được quỏ trỡnh luõn chuyển job trong mạng G , chỳng ta thực hiện việc phõn chia quỏ trỡnh luõn chuyển job thành cỏc bước (Trong đú mỗi một bước bắt đầu khi job đến cỏc nỳt và kết thỳc của một bước khi job được phõn phối đến cỏc mạng thành phần trong mỗi nỳt) và chỳng ta giả thiết rằng tại bước thứ 1 trong mạng hàng đợi khụng cú job. 3.1. Một số ký hiệu và định nghĩa Ký hiệu: iL là tập cỏc mạng thành phần cú chứa nỳt  1,i i J ; Và tại bước thứ  1, 2,...n n  : - , ( ) c i jp n là xỏc xuất của biến cố job chuyển từ nỳt i sang nỳt  0,j j J trong mạng c trong bối cảnh mạng c hoạt động riờng rẽ và độc lập; , , ( ) i c d i i c d L S S n      là ma trận xỏc xuất chuyển job trong nỳt i giữa cỏc mạng thành phần;  ( ) i c i i c L s s n   là xỏc xuất chuyển job từ nỳt i ra ngoài mạng hàng đợi. -       0 i c i i c L a n a n    là lượng job đến nỳt i ;      i c i i c L b n b n   là lượng job cú trong nỳt i ;       0 i c i i c L v n v n    là lượng job từ ngoài mạng vào nỳt i . 3.2. Dũng job luõn chuyển trong mạng hàng đợi G là chập của hai mạng thành phần  1 1(1) : ,i j và  2 2(2) : ,i j . 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,iL i J   . - Nếu 1 1i j và 2 2i j      2 2 (1),(2) (1) : i i L L i i       . Và quỏ trỡnh luõn chuyển job trong nỳt i tại bước thứ n cú thể được biểu diễn bởi ma trận: 0 0 ( ) ( ) ( )i i i S n s n S n        3.2.1. Dũng job luõn chuyển trong mạng chập G tại bước 1 3.2.1.1. Dũng job luõn chuyển trong mạng chập G với điều kiện 1 1i j và 2 2i j : Vỡ 1 1i j và 2 2i j   (1),(2) 1,iL i J   . Kỹ thuật điện tử & Khoa học mỏy tớnh N.T.Dũng,T.Q.Vinh, “Cơ chế luõn chuyển dũng job trong mạng hàng đợi dạng tổng quỏt G/G/J.” 66 a. Xột trường hợp 1 2i i : . Vỡ tại thời điểm ban đầu khụng cú job trong mạng hàng đợi nờn lượng job đến cỏc nỳt của mạng G là:   1 1 2 2 1 2 (1) (1) (1) (1) (1) 0,0,0 , i i i i i a v a v a i i i i          với     1 1 2 2 (1) (2) (1) 0, (1),0 (1) 0,0, (1) i i i i v v v v     Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong cỏc nỳt mạng là:   1 1 1 2 2 2 1 2 (1) : (1) (1) (1) : (1) (1) (1) : 0,0,0 , i i i i i i i r a S r a S r i i i i                 1 1 1 1 1 2 2 2 2 2 (1) (1),(1) (1) (1),(2) (2) (2),(1) (2) (2),(2) 1 2 (1) 0, (1) (1), (1) (1) (1) 0, (1) (1), (1) (1) (1) 0,0,0 , i i i i i i i i i i i r v S v S r v S v S r i i i i           Vỡ thời điểm ban đầu khụng cú job trong mạng hàng đợi nờn lượng job cú trong cỏc nỳt mạng là:                      1 1 1 1 1 1 1 2 2 2 2 2 2 2 1 2 (1) (1),(1) (1) (1),(2) 1 2 (2) (2),(1) (2) (2),(2) 1 2 1 2 (1) (1), (1) (1) (1), (1) (1) (1) (1), (1) (1) (1), (1) (1) (1) (1), (1) 0,0 , i i i i i i i i i i i i i i i i i b b b v S v S b b b v S v S b b b i i i i                (3.1) b. Xột trường hợp 1 2 :i i k  : Vỡ tại thời điểm ban đầu khụng cú job trong mạng hàng đợi nờn lượng job đến cỏc nỳt của mạng G là:     (1) (2)(1) 0, (1), (1) (1) 0,0,0 k k k i a v v a i k       với  (1) (2)(1) 0, (1), (1)k k kv v v . Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong cỏc nỳt mạng là:   (1) : (1) (1) (1) : 0,0,0 k k k i r a S r i k            (1) (1),(1) (2) (2),(1) (1) (1),(2) (2) (2),(2)(1) 0, (1) (1) (1) (1), (1) (1) (1) (1) (1) 0,0,0 k k k k k k k k k i r v S v S v S a S r i k         Vỡ tại bước 1 khụng cú job trong mạng hàng đợi nờn lượng job cú trong cỏc nỳt của mạng G là:               1 2 (1) (1),(1) (2) (2),(1) (1) (1),(2) (2) (2),(2) 1 2 (1) (1), (1) (1) (1) (1), (1) (1) (1) (1) (1), (1) 0,0 k k k k k k k k k k k i i i b b b v S v S v S v S b b b i k            (3.2) 3.2.1.2. Dũng job luõn chuyển trong mạng chập G với điều kiện 1 1i j và 2 2i j : Nghiên cứu khoa học công nghệ Tạp chớ Nghiờn cứu KH&CN quõn sự, Số 36, 04 - 2015 67 Vỡ 1 1i j và 2 2i j      2 2 (1),(2) (1) : i i L L i i       . a. Xột trường hợp 1 2i i : Vỡ tại bước 1 khụng cú job trong mạng hàng đợi nờn lượng job đến cỏc nỳt của mạng G là:   1 1 2 2 1 2 (1) (1) (1) (1) (1) 0,0,0 , i i i i i a v a v a i i i i          với     1 1 2 2 (1) (2) (1) 0, (1) (1) 0,0, (1) i i i i v v v v     Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong cỏc nỳt mạng là:   1 1 1 2 2 2 1 2 (1) : (1) (1) (1) : (1) (1) (1) : 0,0,0 , i i i i i i i r a S r a S r i i i i                 1 1 2 2 2 2 2 2 2 (1) (2) (2) (2) (2),(1) (2) (2),(2) 1 2 (1) 0, (1) (1) (1) (1), (1) (1), (1) (1) (1) 0,0,0 , i i i i i i i i i i r v r v s v S v S r i i i i           Vỡ tại bước 1 khụng cú job trong mạng hàng đợi nờn lượng job cú trong cỏc nỳt của mạng G là:                     1 1 1 2 2 2 2 2 2 2 1 (1) 1 2 (2) (2),(1) (2) (2),(2) 1 2 1 2 (1) (1) (1) (1) (1), (1) (1) (1), (1) (1) (1) (1), (1) 0,0 , i i i i i i i i i i i i i b b v b b b v S v S b b b i i i i                (3.3) b. Xột trường hợp 1 2 :i i k  : Vỡ tại bước 1 khụng cú job trong mạng hàng đợi nờn lượng job đến cỏc nỳt của mạng G là:   (1) (1) (1) 0,0 k k i a v a i k      với  (1) (2)(1) 0, (1), (1)k k kv v v Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong cỏc nỳt mạng là:   (1) : (1) (1) (1) : 0,0 k k k i r a S r i k            (2) (2) (1) (1),(1) (2) (2),(1) (1) (1),(2) (2) (2),(2)(1) (1) (1), (1) (1) (1) (1), (1) (1) (1) (1) (1) 0,0 k k k k k k k k k k k i r v s v S v S v S v S r i k         Vỡ tại bước 1 khụng cú job trong mạng hàng đợi nờn lượng job cú trong cỏc nỳt của mạng G là: Kỹ thuật điện tử & Khoa học mỏy tớnh N.T.Dũng,T.Q.Vinh, “Cơ chế luõn chuyển dũng job trong mạng hàng đợi dạng tổng quỏt G/G/J.” 68                1 2 (1) (1),(1) (2) (2),(1) (1) (1),(2) (2) (2),(2) 1 2 (1) (1), (1) (1) (1) (1) (1), (1) (1) (1) (1) (1) (1), (1) 0,0 k k k k k k k k k k k i i i b b b v S v S v S v S b b b i k             (3.4) 3.2.2. Dũng job luõn chuyển trong mạng chập G tại bước thứ 2 Lượng job từ ngoài mạng vào trong nỳt i mạng G tại bước thứ 2 là:      1 20(2) (2) ,i c i i c L v v i i i      Khi đú lượng job đến nỳt i trong mạng G tại bước 2 là:    0 (2) (2) i c i i c L a a    Với: 1 2 2 1 2 1 1 2 2 1 2 1 (2) (1) (1) : , (2) (2) : c c c i i i i ic i c i i v b p c L i i a v c L ho c i i         ặ ; 2 1 1 2 1 2 2 1 1 2 1 2 (2) (1) (1) : , (2) (2) : c c c i i i i ic i c i i v b p c L i i a v c L ho c i i        ặ 1 1 2 2 1 2 1 1 1 2 2 2 2 1 1 2 1 2 (1) (1) (1) (1) : , , , (2) (1) (1) : , , (1) (1) : , , c c c c i i i i i i i i c c c i i i i i i c c i i i i i b p b p c L c L i i i i a b p c L c L i i b p c L c L i i                Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong nỳt  1,i i J là: (2) : (2) (2)i i ir a S        (1) (1) (1) (1),(1) (1) (1) (2) (2) (1) (1),(1) (2) (2),(1) (1) (1),(2) (2) (2),(2) (2) (2), (2) (2) : (1) (2) (2) (2) (2) (2), (2) (2) (2) (2), : (1),(2) (2) (2) (2) (2) i i i i i i i i i i i i i i i i i i i a s a S i L r a s a s a S a S i L a S a S                            (1) (1) (2) (1) (1),(1) (1) (1) , (1) (1),(1) (2) (2),(1) (1) (1) , (1) (1),(2) (2) ( (2) : (1) (2) (2), (2) : (1), (2) (2) (2) (1) (1) : (1) (2) (2) (2) (2) (1) (1), (2) (2) (2) i i i i i i i i i i i i i i i i i i i i i i i b i L b b b i L a S b p i L a S a S b p a S a S                 2),(2) (2) (2) , : (1), (2) (2) (1) (1) i i i i i L b p          (3.5) 3.2.3. Dũng job luõn chuyển trong mạng chập G tại bước thứ n Lượng job từ ngoài mạng vào trong nỳt i mạng G tại bước thứ n là:      1 20( ) ( ) ,i c i i c L v n v n i i i      . Khi đú lượng job đến nỳt i trong mạng G tại bước n là    0 ( ) ( ) 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        Nghiên cứu khoa học công nghệ Tạp chớ Nghiờn cứu KH&CN quõn sự, Số 36, 04 - 2015 69 Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong nỳt  1,i i J là: ( ) : ( ) ( )i i ir n a n S n        (1) (1) (1) (1),(1) (1) (1) (2) (2) (1) (1),(1) (2) (2),(1) (1) (1),(2) (2) (2),(2) ( ) ( ), ( ) ( ) : (1) ( ) ( ) ( ) ( ) ( ), ( ) ( ) ( ) ( ), : (1),(2) ( ) ( ) ( ) ( ) 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 i L r n a n s n a n s n a n S n a n S n i L a n S n a n S n                            (1) (1) (2) (1) (1),(1) (1) (1) , (1) (1),(1) (2) (2),(1) (1) (1) , (1) (1),(2) ( ( ) : (1) ( ) ( ), ( ) : (1),(2) ( ) ( ) ( 1) ( 1) : (1) ( ) ( ) ( ) ( ) ( 1) ( 1), ( ) ( ) i i i i i i i i i i i i i i i i i i i i i i b n i L b n b n b n i L a n S n b n p n i L 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 i L n S n b n p n            (3.6) Như vậy trong mục này chỳng tụi đó trỡnh bày quỏ trỡnh luõn chuyển của mạng hàng đợi được chập bởi 2 mạng thành phần và cỏc cụng thức (3.1),(3.2),(3.3),(3.4),(3.5),(3.6) thể hiện sự thay đổi về lượng job cú trong 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. 3.3. Dũng job luõn chuyển trong mạng hàng đợi tổng quỏt / /G G J Vỡ cú J nỳt mạng nờn mạng tổng quỏt là chập của 2J mạng thành phần và cú  2 1J J  mạng thành phần chứa nỳt  1,i i J của mạng G . 3.3.1. Dũng job luõn chuyển trong mạng tổng quỏt tại bước thứ 1 Với lượng job từ ngoài mạng vào trong nỳt i của mạng G tại bước 1 là       0 1 1 i c i i c L v v    và tại bước 1 khụng cú job trong mạng hàng đợi nờn lượng job đến nỳt i của mạng G là: (1) (1)i ia v Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong nỳt  1,i i J là: (1) : (1) (1)i i ir a S . Vỡ tại bước 1 khụng cú job trong mạng hàng đợi nờn lượng job cú trong nỳt  1,i i J của mạng G là:  (1) (1) i c i i c L b b   với (1) (1)c ci ib r (3.7) 3.3.2. Dũng job luõn chuyển trong mạng tổng quỏt tại bước thứ n Với lượng job từ ngoài mạng vào trong nỳt i mạng G tại bước n là       0 i c i i c L v n v n    . Khi đú lượng job đến nỳt i của mạng G là    0 ( ) ( ) i c i i c L a n a n    với: Kỹ thuật điện tử & Khoa học mỏy tớnh N.T.Dũng,T.Q.Vinh, “Cơ chế luõn chuyển dũng job trong mạng hàng đợi dạng tổng quỏt G/G/J.” 70 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        Job sau khi đến cỏc nỳt của mạng G thỡ trong mỗi nỳt mạng, job sẽ luõn chuyển giữa cỏc mạng thành phần. Lượng job luõn chuyển được giữa cỏc mạng thành phần trong nỳt  1,i i J là: ( ) : ( ) ( )i i ir n a n S n Vỡ vậy, lượng job cú trong cỏc nỳt của mạng G 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    . (3.8) Như vậy, trong mục này chỳng tụi đó trỡnh bày quỏ trỡnh luõn chuyển của mạng hàng đợi được chập bởi 2J mạng thành phần và cụng thức (3.8) thể hiện sự thay đổi về lượng job cú trong 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. 4. KẾT LUẬN Nghiờn cứu về hoạt động của mạng hàng đợi và quỏ trỡnh dũng job luõn chuyển trong mạng hàng đợi trong bối cảnh dũng job vào mạng là dũng tổng quỏt và sự luõn chuyển job giữa cỏc nỳt một cỏch tựy ý sẽ gặp nhiều khú khăn phức tạp vỡ vậy bài bỏo đó trỡnh bày kỹ thuật kết hợp giữa phõn ró và tổng hợp để xột một mạng đa lớp tổng quỏt với cỏc luồng thụng tin đa chiều được xem như là mạng “chập” (tổng hợp-tớch hợp) của cỏc mạng thành phần và từ cơ sở đú dẫn bài toỏn nghiờn cứu mạng phức tạp về xột bài toỏn trờn cỏc mạng đơn giản thành phần. TÀI LIỆU THAM KHẢO [1]. Nguyễn Trung Dũng, Nguyễn Hải Nam.(2013). Một vài kết quả nghiờn cứu về trạng thỏi của mạng hàng đợi dạng tổng quỏt G/G/J. Tạp chớ Nghiờn cứu khoa học và cụng nghệ. ISSN 1859-1043, Số 26 (08-2013), Viện Khoa học và Cụng nghệ Quõn sự. [2]. Hong Chen, David D.Yao.(July 2000). Fundamentals of Queueing Netwworks. Springer . ABSTRACT THE MECHANISM OF ROUTING THE JOB FLOWS IN THE GENERAL QUEUEING NETWORK G/G/J In this paper, we present the combining technique between disintegration and synthesization to evaluate a general multiclass queueing network with multi-directional information flow as a combining network of directional queueing networks. This technique enables us to study the complex queueing network as the simple component networks. The paper shows the result of the study on directional networks and the results related to the combining networks of the directional networks. Keywords: Queueing network, Queue, Node, Job. Nhận bài ngày 19 tháng 8 năm 2014 Hoàn thiện ngày 10 tháng 4 năm 2015 Chấp nhận đăng ngày 15 tháng 4 năm 2015 Địa chỉ: * Viện Cụng nghệ thụng tin, Viện KH-CNQS, BQP. ĐT: 01697.569.069. Email: ntdtoanud2011@gmail.com ** Khoa Toỏn tin, Đại học Sư phạm Hà Nội.