Cơ chế luân chuyển dòng JOB trong mạng hàng đợi dạng tổng quát G/G/J

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

24
lượt xem 1
download

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

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

Chủ đề:

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

Lưu

Nội dung Text: Cơ chế luân chuyển dòng JOB trong mạng hàng đợi dạng tổng quát G/G/J

Kỹ thuật điện tử & Khoa học máy tính 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: … 0 i j 0 … Hình 1. Dòng job luân chuyển 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 62 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.” Nghiªn cøu khoa häc c«ng nghÖ 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: … 0 i j 0 … Hình 2. Dòng job luân chuyển 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 J 2 mạng thành phần  i, j  với i, j  1, 2,..., 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 P ( h,l )   pi,j( h,l )  là ma trận xác xuất job chuyển từ nút i sang nút j trong mạng  h, l  i , j  0, J  h, l 1, 2,..., J  tại thời điểm t ; P   pi,j  i , j 0, J 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 . Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 63 Kỹ thuật điện tử & Khoa học máy tính 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  i1 , j1  và  i2 , j2  . 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ó:  j  ik , i  0  J (ik , jk )   pi,j  1 i  1, J pi,j(ik , jk )  0 t nếu i  jk , j  0 Và  j 0 i  jk , j  0 k  1, 2  ( ik , jk ) Ký hiệu: Ai , j ( k  1, 2 ) là biến cố job chuyển từ nút i sang nút j trong mạng  ik , jk  tại thời điểm t ; Ai , j 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ó: Ai , j  Ai(,i1j , j1 )  Ai(,i2j , j2 )  P  Ai , j   P  Ai(,i1j , j1 )   P  Ai(,i2j , j2 )   P  Ai(,i1j , j1 ) Ai(,i2j , j2 )  Với giả thiết rằng hai mạng  i1 , j1  và  i2 , j2  độc lập với nhau. Khi đó ta có: P  Ai , j   P  Ai(,i1j , j1 )   P  Ai(,i2j , j2 )   P  Ai(,i1j , j1 )  P  Ai(,i2j , j2 )   pi,j(i1 , j1 )  P  Ai(,i1j , j1 )      (i2 , j2 ) Mà  pi,j  P  Ai , j   pi,j  pi,j(i1 , j1 )  pi,j(i2 , j2 )  pi,j(i1 , j1 ) pi,j(i2 , j2 ) ( i2 , j2 ) (2.1)   pi,j  P  Ai , j  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 J 2 mạng thành phần.   Ký hiệu: L   i, j  | i, j 1,2,..., J  là tập tất cả các mạng thành phần của mạng hàng đợi ( k ,l ) tổng quát. A i, j 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 . Ai , j 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ó: Ai , j   Ai(,kj,l )  P  Ai , j   P   Ai(,kj,l )   PAi, j  1 P  Ai(,kj,l)    k ,l  L   k ,l L    k ,l L     P  Ai , j   1  P   Ai(,kj,l )    k ,l L  Giả thiết rằng hoạt động của các mạng thành phần độc lập với nhau.  P  Ai , j   1    k ,l L    k ,l L  P  Ai(,kj,l )   P  Ai , j   1   1  P  Ai(,kj,l )    pi,j  1   1  p  ( k ,l ) i,j (2.2)  k ,l L 64 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.” Nghiªn cøu khoa häc c«ng nghÖ 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: Li là tập các mạng thành phần có chứa nút i i  1, J ; Và tại bước thứ  n  n  1, 2,... : -   pic, j (n) là xác xuất của biến cố job chuyển từ nút i sang nút j j  0, J trong mạng c trong bối cảnh mạng c hoạt động riêng rẽ và độc lập; Si   Sic,d (n) là ma trận c,dLi xác xuất chuyển job trong nút i giữa các mạng thành phần; si  sic (n)   cLi là xác xuất chuyển job từ nút i ra ngoài mạng hàng đợi. -     là lượng job đến nút i ; b  n   b  n là lượng job có trong ai  n  aic  n c 0 Li i i c cLi nút i ; v  n   v  n  i c i là lượng job từ ngoài mạng vào nút i .  c 0 Li 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) :  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 i1  j1 và i2  j2  Li  (1),(2) i  1, J . Li2  (1),(2) - Nếu i1  j1 và i2  j2   . Li  (1) : i  i2 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  Si (n)    si (n) Si (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 i1  j1 và i2  j2 : Vì i1  j1 và i2  j2  Li  (1),(2) i  1, J . Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 65 Kỹ thuật điện tử & Khoa học máy tính a. Xét trường hợp i1  i2 : . 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à: ai (1)  vi (1)  1 1 vi (1)  0, vi(1) (1),0  1 1   ai2 (1)  vi2 (1) với   (2) vi2 (1)  0,0, vi2 (1)   ai (1)   0,0,0 i  i1, i  i2 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à: ri (1) : ai (1)Si (1) 1 1 1 1 1 1  ri (1)  0, vi(1) (1)Si(1),(1) (1), vi(1) (1)Si(1),(2) (1) 1 1    ri2 (1) : ai2 (1)Si2 (1)   ri2 (1)  0, vi2 (1)Si2 (1), vi2 (1)Si(2),(2) (2) (2),(1) (2) 2 (1)    ri (1) :  0,0,0 i  i1, i  i2 ri (1)   0,0,0 i  i1, i  i2 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   bi (1)  bi1 (1), bi 2 (1)  vi(1) (1)Si(1),(1) (1), vi(1) (1)Si(1),(2) (1)  1 1 1 1   1    2 (2)   (2),(1) bi2 (1)  bi2 (1), bi2 (1)  vi2 (1)Si2 (1), vi2 (1)Si2 (1) (2) (2),(2)  (3.1)    bi (1)  bi1 (1), bi2 (1)   0,0 i  i1, i  i2  b. Xét trường hợp i1  i2 : 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à:  ak (1)  0, vk(1) (1), vk(2) (1)    với vk (1)  0, vk(1) (1), vk(2) (1) .  ai (1)   0,0,0 i  k 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à: rk (1) : ak (1)Sk (1)  ri (1) :  0,0,0 i  k  rk (1)  0, vk(1) (1)Sk(1),(1) (1)  vk(2) (1)Sk(2),(1) (1), vk(1) (1)Sk(1),(2) (1)  ak(2) (1)Sk(2),(2) (1)   ri (1)   0,0,0 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à:   bk (1)  bk1 (1), bk 2 (1)   vk(1) (1)Sk(1),(1) (1)  vk(2) Sk(2),(1) (1), vk(1) Sk(1),(2) (1)  vk(2) (1)Sk(2),(2) (1)  (3.2)   1  2  bi (1)  bi (1), bi (1)   0,0 i  k  3.2.1.2. Dòng job luân chuyển trong mạng chập G với điều kiện i1  j1 và i2  j2 : 66 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.” Nghiªn cøu khoa häc c«ng nghÖ Li2  (1),(2) Vì i1  j1 và i2  j2   . Li  (1) : i  i2 a. Xét trường hợp i1  i2 : 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à: ai (1)  vi (1)  1 1 vi (1)  0, vi(1) (1)  1 1   ai2 (1)  vi2 (1) với   a (1)   0,0,0  i  i , i  i (2) vi2 (1)  0,0, vi2 (1)    i 1 2 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à: ri (1) : ai (1)Si (1) 1 1 1 1 1  ri (1)  0, vi(1) (1)    ri2 (1) : ai2 (1)Si2 (1)  ri2 (1)  vi(2) 2  (1)si(2) 2 (1), vi(2) 2 (1)Si(2),(1) 2 (1), vi(2) 2 (1)Si(2),(2) 2 (1)    ri (1) :  0,0,0 i  i1, i  i2 ri (1)   0,0,0 i  i1, i  i2 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à:    bi (1)  bi1 (1)  vi(1) (1)  1 1 1       bi2 (1)  bi2  (1), bi2  (1)  vi(2) 1 2 2 (1)Si(2),(1) 2 (1), vi(2) 2 (1)Si(2),(2) 2 (1)  (3.3)    bi (1)  bi1 (1), bi2 (1)   0,0 i  i1, i  i2  b. Xét trường hợp i1  i2 : 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à: ak (1)  vk (1)   với vk (1)  0, vk(1) (1), vk(2) (1)  ai (1)   0,0 i  k 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à: rk (1) : ak (1)Sk (1)  ri (1) :  0,0 i  k  rk (1)  vk(2) (1)sk(2) (1), vk(1) (1)Sk(1),(1) (1)  vk(2) (1)Sk(2),(1) (1), vk(1) (1)Sk(1),(2) (1)  vk(2) (1)Sk(2),(2) (1)    ri (1)   0,0 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à: Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 67 Kỹ thuật điện tử & Khoa học máy tính  k  k k   b (1)  b1 (1), b 2 (1)  v(1) (1)S (1),(1) (1)  v(2) (1)S(2),(1) (1), v(1) (1)S(1),(2) (1)  v(2) (1)S (2),(2) (1) k k k k k k k k  (3.4)  1  2  bi (1)  bi (1), bi (1)   0,0 i  k  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à:  vi (2)  vic (2)  i i1, i2  c0Li Khi đó lượng job đến nút i trong mạng G tại bước 2 là:  ai (2)  aic (2)  c0Li Với: vic1 (2)  bic2 (1) pic2i1 (1) : c  Li2 , i2  i1 vic2 (2)  bic1 (1) pic1i2 (1) : c  Li1 , i1  i2 c c a (2)   c i1 ; ai2 (2)   c v  i1 (2) : c  Li2 ho Æ c i2  i1 vi2 (2) : c  Li1 hoÆc i1  i2 bic1 (1) pic1i (1)  bic2 (1) pic2i (1) : c  Li1 , c  Li2 , i  i1, i  i2  aic (2)  bic1 (1) pic1i (1) : c  Li1 , c  Li2 , i  i1  c c bi2 (1) pi2i (1) : c  Li2 , c  Li1 , i  i2 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 i i  1, J là:   ri (2) : ai (2)Si (2)    ai(1) (2)si(1) (2), ai(1) (2)Si(1),(1) (2) i : Li  (1)   ri (2)   ai(1) (2)si(1) (2)  ai(2) (2)si(2) (2), ai(1) (2)Si(1),(1) (2)  ai(2) (2)Si(2),(1) (2),   (1) (1),(2) (2) (2),(2)  i : Li  (1),(2)  ai (2)Si (2)  ai (2)Si (2)   bi(1) (2)  i : Li  (1)  bi (2)    bi (2), bi (2)  i : Li  (1), (2) (1) (2)   ai(1) (2) Si(1),(1) (2)  bi(1) (1) pi(1),i (1)  i : Li  (1) (3.5)    ai(1) (2) Si(1),(1) (2)  ai(2) (2) Si(2),(1) (2)  bi(1) (1) pi(1) ,i (1),   (1)  i : Li  (1), (2)  ai (2) Si (1),(2) (2)  ai(2) (2)Si( 2),(2) (2)  bi(2) (1) pi(,2)i (1)  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à: vi (n)   vic (n) i i1, i2 . c0Li Khi đó lượng job đến nút i trong mạng G tại bước n là ai (n)  aic (n)   c0Li với : J aic (n)  vic (n)   bcj (n 1) pcji (n 1) j 1, j i ,cLj 68 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.” Nghiªn cøu khoa häc c«ng nghÖ 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 i i  1, J là:   ri (n) : ai (n)Si (n)    ai(1) (n)si(1) (n), ai(1) (n)Si(1),(1) (n) i : Li  (1)   ri (n)   ai(1) (n)si(1) (n)  ai(2) (n)si(2) (n), ai(1) (n)Si(1),(1) (n)  ai(2) (n)Si(2),(1) (n),   (1) (1),(2) (2) (2),(2)  i : Li  (1),(2)  ai (n)Si (n)  ai (n)Si (n)   bi (n)  i : Li  (1) (1)  bi (n)    bi (n), bi (n) i : Li  (1),(2) (1) (2)   ai(1) (n)Si(1),(1) (n)  bi(1) (n  1) pi(1),i (n  1) i : Li  (1) (3.6)    ai(1) (n)Si(1),(1) (n)  ai(2) (n)Si(2),(1) (n)  bi(1) (n 1) pi(1),i (n  1),   (1)  i : Li  (1),(2)  ai (n)Si (1),(2) (n)  ai( 2) (n)Si(2),(2) (n)  bi(2) (n  1) pi(2) ( n  1)  ,i  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 J 2 mạng thành phần và có J 2   J  1 mạng thành phần chứa nút i i  1, 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à  c vi 1  v 1 i  c0Li 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à: ai (1)  vi (1) 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 i i  1, J là:   ri (1) : ai (1)Si (1) . 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 i i  1, J của   mạng G là:  bi (1)  bic (1)  cLi với bic (1)  ric (1) (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à vi  n  vic  n   c0Li . Khi đó lượng job đến nút i của mạng G là ai (n)  aic (n)   c0Li với: Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 69 Kỹ thuật điện tử & Khoa học máy tính J aic (n)  vic (n)   bcj (n 1) pcji (n 1) j 1; j i :cLj 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 i i  1, J là:   ri (n) : ai (n)Si (n) Vì vậy, lượng job có trong các nút của mạng G là bi (n)  bic (n)   cLi với : bic (n)  ric (n)  bic (n 1) piic (n  1) . (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 J 2 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. 70 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.”