B GIO DC V ĐO TO B QUC PHNG
VIN KHOA HC V CÔNG NGH QUÂN S
-----------------------------------
NGUYỄN TRUNG DŨNG
MỘT SỐ DẠNG HNG ĐỢI V CÁC NGUYÊN LÝ XỬ LÝ
LUẬN ÁN TIẾN SĨ TOÁN HC
Hà Nội - 2018
B GIO DC V ĐO TO B QUC PHNG
VIN KHOA HC V CÔNG NGH QUÂN S
----------------------------------
NGUYỄN TRUNG DŨNG
MỘT SỐ DẠNG HNG ĐỢI V CÁC NGUYÊN LÝ XỬ LÝ
Chuyên ngnh: Cơ sở toán học cho tin học
M s : 9460110
LUẬN ÁN TIẾN SĨ TOÁN HC
NGƯI HƯNG DN KHOA HC:
1. TS.NCVCC Nguyễn Hồng Hải
2. TS Trần Quang Vinh
H Nội - 2018
i
LỜI CAM ĐOAN
Tôi xin cam đoan các công trình nghiên cứu trong luận án này là của cá
nhân tôi. Các kết quả được nêu trong luận án là trung thực và chưa từng được
ai công bố trong các công trình nào khác. Các dữ liệu tham khảo được trích
dẫn đầy đủ.
Tác giả
Nguyễn Trung Dũng
ii
LỜI CÁM ƠN
Luận án được nghiên cứu thực hiện tại Viện Công nghệ thông tin - Viện
Khoa học Công nghệ Quân sự/BQP và Bộ tư lệnh 86/BQP, dưới sự hướng
dẫn khoa học của TS.Nguyễn Hồng Hải và TS.Trần Quang Vinh.
Lời đầu tiên nghiên cứu sinh xin bày tỏ lòng biết sâu sắc tới thầy giáo
Nguyễn Hồng Hải và thầy giáo Trần Quang Vinh, những người thầy đã giúp
đỡ và đưa nghiên cứu sinh đến lĩnh vực nghiên cứu này. Các thầy đã tận tình
giảng dạy, hướng dẫn, động viên, khuyến khích và chỉ dẫn giúp nghiên cứu
sinh tiếp cận và đạt được thành công trong học tập, nghiên cứu và hoàn
thành bản luận án này.
Nghiên cứu sinh xin bày tỏ lòng biết ơn tới Đảng ủy, chỉ huy Viện
Công nghệ thông tin - Viện KH-CN Quân sự; Đảng ủy, chỉ huy BTL 86; các
cán bộ Phòng Đào tạo - Viện KH-CN Quân sự; cán bộ phòng Toán ứng dụng
- Viện Công nghệ thông tin - Viện KH-CN Quân sự; cán bộ phòng Phần mềm
và CSDL – BTL 86 đã nhiệt tình ủng hộ, động viên kịp thời và hết lòng giúp
đỡ nghiên cứu sinh trong suốt quá trình học tập và nghiên cứu tại đơn vị.
Cuối cùng nghiên cứu sinh xin chân thành cảm ơn toàn thể gia đình,
những người luôn ở bên cạnh và dành cho nghiên cứu sinh những tình cảm và
chia sẻ động viên giúp đỡ tinh thần những lúc khó khăn trong cuộc sống,
cũng như trong quá trình học tập và nghiên cứu.
Tác giả
Nguyễn Trung Dũng
iii
MỤC LỤC
Trang
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................... V
DANH MỤC CÁC BẢNG ................................................................................... VIII
DANH MỤC CÁC HÌNH VẼ ................................................................................ IX
CHƯƠNG 1. MỘT SỐ VẤN ĐỀ CƠ BẢN VỀ LÝ THUYẾT HÀNG ĐỢI
VÀ MẠNG HÀNG ĐỢI ............................................................................................. 5
1.1. Một số khái niệm xác suất có liên quan ............................................... 6
1.1.1. Biến ngẫu nhiên ............................................................................................ 6
1.1.2. Hàm phân phối xác suất của biến ngẫu nhiên ........................................... 6
1.1.3. Các đặc trưng của biến ngẫu nhiên ............................................................. 7
1.1.4. Một số đại lượng ngẫu nhiên quan trọng (thường dùng) .......................... 8
1.2. Quá trình Markov ................................................................................ 10
1.2.1. Các định nghĩa và một số tính chất ban đầu ................................... 10
1.2.2. Xích Markov thời gian rời rạc ........................................................ 11
1.3. Lý thuyết hàng đợi và mạng hàng đợi ............................................... 14
1.3.1. Hàng đợi ...................................................................................................... 14
1.3.2. Mạng hàng đợi ............................................................................................ 18
1.4. Tình hình nghiên cứu trong nước và ngoài nước về mạng hàng đợi
.. 27
CHƯƠNG 2. MẠNG ĐA LỚP TỔNG QUÁT - THUẬT TOÁN PHÂN RÃ
VÀ TỔNG HỢP ......................................................................................................... 41
2.1. Phân rã mạng hàng đợi tổng quát thành các mạng thành phần ..... 42
2.2. Tổng hợp mạng hàng đợi tổng quát theo các mạng thành phần .... 46
2.2.1. Luân chuyển job trong mạng hàng đợi tổng quát G/G/J trong bối cảnh
job luân chuyển giữa các mạng thành phần ........................................................ 47
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 .............................................................................. 65
2.3. Về một mô hình mạng hàng đợi cụ thể .............................................. 68
2.3.1. Tập các mạng thành phần .......................................................................... 69
2.3.2. Dòng job luân chuyển trong mạng hàng đợi tại bước n (n≥1) ............... 70
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