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