ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
--------&&&--------

NGUYỄN THẾ TÙNG

HỆ THỐNG HÀNG ĐỢI VÀ BÀI TOÁN MÔ PHỎNG
HOẠT ĐỘNG KIỂM SOÁT XUẤT NHẬP CẢNH
CỦA CỬA KHẨU SÂN BAY QUỐC TẾ NỘI BÀI

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

Hà Nội, 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
--------&&&--------

NGUYỄN THẾ TÙNG

HỆ THỐNG HÀNG ĐỢI VÀ BÀI TOÁN MÔ PHỎNG
HOẠT ĐỘNG KIỂM SOÁT XUẤT NHẬP CẢNH
CỦA CỬA KHẨU SÂN BAY QUỐC TẾ NỘI BÀI
Chuyên ngành: Kỹ thuật Phần mềm
Mã số: 60 48 01 03

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN
Người hướng dẫn khoa học

2.1. Vai trò của lý thuyết hàng đợi. .................................................... Error! Bookmark not defined.
2.2. Khái quát về hệ thống hàng đợi .................................................. Error! Bookmark not defined.
2.2.1. Các thành phần cơ bản của một hệ thống hàng đợi .......... Error! Bookmark not defined.
2.2.2. Các tham số đặc trưng của một hệ thống hàng đợi ............ Error! Bookmark not defined.
2.2.3. Kí hiệu Kendall A / B / m / K / n / D .................................... Error! Bookmark not defined.
2.2.4. Luật Little .............................................................................. Error! Bookmark not defined.
2.3. Một số phân phối xác suất quan trọng ....................................... Error! Bookmark not defined.
2.3.1. Phân phối Bernoulli................................................................ Error! Bookmark not defined.
2.3.2. Phân phối nhị thức.................................................................. Error! Bookmark not defined.
2.3.3. Phân phối đa thức .................................................................... Error! Bookmark not defined.
2.3.4. Phân phối Poisson ................................................................... Error! Bookmark not defined.
2.3.5. Phân phối Erlangian (Gamma) ................................................ Error! Bookmark not defined.
2.4. Một số mô hình hàng đợi cơ bản ................................................. Error! Bookmark not defined.
2.4.1. Hệ thống hàng đợi cổ điển M/M/1 ......................................... Error! Bookmark not defined.
2.4.2. Hệ thống hàng đợi M/M/m ..................................................... Error! Bookmark not defined.
2.4.3. Hệ thống hàng đợi M/M/1/K .................................................. Error! Bookmark not defined.
2.4.4. Hệ thống hàng đợi M/M/m/K ................................................. Error! Bookmark not defined.
Chương 3 NGHIÊN CỨU CÔNG CỤ MÔ PHỎNG HỆ THỐNG HÀNG ĐỢI GPSS WORLD .. Error!
Bookmark not defined.
3.1. Các hướng tiếp cận mô phỏng ........................................................ Error! Bookmark not defined.
3.2. Giới thiệu một số công cụ và ngôn ngữ mô phỏng ....................... Error! Bookmark not defined.
3.3. Ngôn ngữ mô phỏng GPSS ........................................................... Error! Bookmark not defined.
3.3.1. Giới thiệu về ngôn ngữ GPSS ................................................. Error! Bookmark not defined.
3.3.2. Những điểm nổi bật của ngôn ngữ GPSS ................................ Error! Bookmark not defined.
3.3.2.1. Cung cấp các hàm phân phối xác suất có sẵn ................... Error! Bookmark not defined.
3.3.2.2. Cung cấp khả năng xử lý đa nhiệm, đa luồng với các mức ưu tiên khác nhau ......... Error!
Bookmark not defined.
3.3.3. Các ứng dụng của công cụ mô phỏng GPSS World ................ Error! Bookmark not defined.
3.3.4. Một số khái niệm trong GPSS World...................................... Error! Bookmark not defined.


4.5.1. Thời điểm có lưu lượng khách trung bình ............................... Error! Bookmark not defined.
4.5.2. Thời điểm có lưu lượng khách đông ....................................... Error! Bookmark not defined.
4.5.3. Thực hiện mô phỏng để dự báo nhu cầu trong tương lai......... Error! Bookmark not defined.
4.6. Đánh giá kết quả mô phỏng............................................................ Error! Bookmark not defined.
Chương 5 KẾT LUẬN ............................................................................. Error! Bookmark not defined.
5.1. Kết luận .......................................................................................... Error! Bookmark not defined.
5.2. Hạn chế và kiến nghị ...................................................................... Error! Bookmark not defined.


4

DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT
Ký hiệu

Tiếng Anh

Giải thích theo tiếng Việt

CEC

Current Event Chain

Chuỗi sự kiện hiện tại

GPSS

General Purpose Simulation System

Ngôn ngữ mô phỏng hệ thống GPSS


5

DANH MỤC CÁC BẢNG
Bảng 2.1. Các tham số đặc trưng trong hệ thống hàng đợi ..........................................
Bảng 2.2. Các thành phần trong kí hiệu Kendall .........................................................
Bảng 2.3. Một số hàm phân phối xác suất trong ký hiệu Kendall................................
Bảng 3.1. Một số khối cơ bản làm việc với giao tác ....................................................
Bảng 3.2. Một số khối cơ bản làm việc với thiết bị .....................................................
Bảng 3.3. Một số khối cơ bản làm việc với QUEUE ...................................................
Bảng 3.4. Một số khối cơ bản điều khiển dịch chuyển của giao tác ............................
Bảng 4.1. Kết quả mô phỏng tại thời điểm có lưu lượng khách trung bình .................
Bảng 4.2. Kết quả mô phỏng tại thời điểm có lưu lượng khách đông .........................
Bảng 4.3. Kết quả mô phỏng với số lượng khách trung bình theo ngày ......................
Bảng 4.4. Dự báo số lượng hành khách XNC trong tương lai .....................................
Bảng 4.5. Kết quả mô phỏng dự báo nhu cầu trong tương lai .....................................


6

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 2.1. Các thành phần cơ bản của một hàng đợi .....................................................
Hình 2.2. Đồ thị hàm mật độ Erlang có n mức………………………………………..
Hình 2.3. Mô hình hàng đợi M/M/1 .............................................................................
Hình 2.4. Sơ đồ tốc độ chuyển trạng thái hệ thống M/M/1 ..........................................
Hình 2.5. Mô hình hệ thống M/M/1/K .........................................................................
Hình 2.6. Sơ đồ tốc độ chuyển trạng thái hệ thống M/M/1/K ......................................
Hình 2.7. Mô hình hệ thống M/M/m ............................................................................
Hình 2.8. Sơ đồ tốc độ chuyển trạng thái hệ thống M/M/m .........................................
Hình 2.9. Mô hình hệ thống M/M/m/K ........................................................................
Hình 3.1. Mối quan hệ giữa các đối tượng ...................................................................

thống là khá phức tạp, khó khăn, vì khi lập trình chúng ta phải quản lý các sự kiện theo
một mô hình nhiều sự kiện xảy ra đồng thời và chúng ta cũng phải xây dựng các hàm
ngẫu nhiên sinh các sự kiện.
Chính vì vậy, đã xuất hiện các công cụ và ngôn ngữ mô phỏng chuyên dụng như
GPSS (General Purpose Simulation System), Petri Nets, MatLab,…GPSS thuộc loại
ngôn ngữ lập trình hướng đối tượng, một ngôn ngữ mô phỏng các hệ thống phức tạp
rời rạc, được nhận định là hiệu quả nhất hiện nay. Các đối tượng của ngôn ngữ này
được sử dụng tương tự như các thành phần chuẩn của một hệ thống hàng đợi như là
các yêu cầu đầu vào, đầu ra, các thiết bị phục vụ, hàng đợi,… Với tập hợp đầy đủ các
thành phần như vậy, GPSS cho phép xây dựng các mô phỏng phức tạp trong khi vẫn
đảm bảo những thuật ngữ thông thường của hệ thống hàng đợi [1, tr.6].
Vấn đề nghiên cứu và ứng dụng ngôn ngữ mô phỏng GPSS rất phổ biến và phát
triển trên thế giới. Tuy nhiên, tại Việt Nam vấn đề này còn khá mới và chưa được ứng
dụng rộng rãi, nhất là ứng dụng trong lĩnh vực quản lý xuất nhập cảnh (XNC). Trên cơ
sở các nghiên cứu đã có, luận văn đã tập trung vào các mục tiêu và các vấn đề cần giải
quyết sau:


8

1.1. Mục tiêu và phạm vi nghiên cứu
Luận văn tập trung nghiên cứu về các mô hình hàng đợi cũng như một số kiến
thức cơ bản trong “ Lý thuyết hàng đợi”, tìm hiểu công cụ mô phỏng hàng đợi là GPSS
World với mục tiêu chính là hiểu được các thành phần cơ bản của một hệ thống hàng
đợi, một số mô hình hàng đợi cơ bản và phân phối xác suất quan trọng, nắm được công
cụ mô phỏng hàng đợi GPSS World và ngôn ngữ mô phỏng GPSS, để từ đó vận dụng
vào giải quyết các bài toán thực tế.
1.2. Phương pháp nghiên cứu
Trong luận văn này tôi đã lựa chọn và phối hợp nhiều phương pháp nghiên cứu
khác nhau phù hợp với khả năng cũng như yêu cầu của đề tài, bao gồm các phương

ĐHQGHN, Viện Công nghệ thông tin – Đại học Quốc Gia Hà Nội.
[2] Lê Quang Minh, Phan Đăng Khoa, Nguyễn Thế Tùng, Nghiêm Thị Hoa
(2015), “Nghiên cứu mô phỏng các hệ thống hàng đợi” – Kỷ yếu Hội nghị
Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công Nghệ thông
tin (FAIR), Hà Nội 2015;
Tiếng Anh
[3] JOHN A. GUBNER (2006) “Probability and Random Processes for Electrical
and Computer Engineers”, the United States of America by Cambridge
University Press, New York.
[4] Robert B.Cooper (1981) “Introduction To Queueing Theory”, Elserier North
Holland.
[5] Raj Jain (2008) “Introduction To Queueing Theory”, Washington University
in Saint Louis.
[6] John D.C. Little and Stephen C. Graves, “Little's Law”.
[7] William Stallings (2000), “Queuing Analysis”.
[8] Ivo Adan and Jacques Resing (2002), “Queueing Theory”, Department of
Mathematics and Computing Science, Eindhoven University of Technology,
P.O. Box 513, 5600 MB Eindhoven, The Netherlands
[9] Dr. János Sztrik, “ Basic Queueing Theory”, University of Debrecen, Faculty
of Informatics University of Debrecen Faculty of Informatics.
[10] Andreas Willig (1999) “A Short Introduction to Queueing Theory”,
Technical University Berlin, Telecommunication Networks Group.
[11] “GPSS World reference manual” (2000), Minuteman Software. P.O. Box
131. Holly Springs, NC 27540-0131 U.S.A.
[12] Alan Pilkington, Royal Holloway(2005), “GPSS – Getting Started”,
University of London.
[13] “GPSS World Tutorial Manual”
[14] http://www.minutemansoftware.com