ĐẠ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. ................................................................................................ 10
2.2. Khái quát về hệ thống hàng đợi .............................................................................................. 10
2.2.1. Các thành phần cơ bản của một hệ thống hàng đợi ...................................................... 10
2.2.2. Các tham số đặc trưng của một hệ thống hàng đợi ........................................................ 12
2.2.3. Kí hiệu Kendall A / B / m / K / n / D ................................................................................ 13
2.2.4. Luật Little .......................................................................................................................... 14
2.3. Một số phân phối xác suất quan trọng ................................................................................... 15
2.3.1. Phân phối Bernoulli............................................................................................................ 15
2.3.2. Phân phối nhị thức.............................................................................................................. 16
2.3.3. Phân phối đa thức ................................................................................................................ 16
2.3.4. Phân phối Poisson ............................................................................................................... 16
2.3.5. Phân phối Erlangian (Gamma) ............................................................................................ 17
2.4. Một số mô hình hàng đợi cơ bản ............................................................................................. 19
2.4.1. Hệ thống hàng đợi cổ điển M/M/1 ..................................................................................... 19
2.4.2. Hệ thống hàng đợi M/M/m ................................................................................................. 21
2.4.3. Hệ thống hàng đợi M/M/1/K .............................................................................................. 22
2.4.4. Hệ thống hàng đợi M/M/m/K ............................................................................................. 24
Chương 3 NGHIÊN CỨU CÔNG CỤ MÔ PHỎNG HỆ THỐNG HÀNG ĐỢI GPSS WORLD ....... 28
3.1. Các hướng tiếp cận mô phỏng .................................................................................................... 28
3.2. Giới thiệu một số công cụ và ngôn ngữ mô phỏng ................................................................... 29
3.3. Ngôn ngữ mô phỏng GPSS ....................................................................................................... 29
3.3.1. Giới thiệu về ngôn ngữ GPSS ............................................................................................. 29
3.3.2. Những điểm nổi bật của ngôn ngữ GPSS ............................................................................ 30
3.3.2.1. Cung cấp các hàm phân phối xác suất có sẵn ............................................................... 31
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 .............. 31
3.3.3. Các ứng dụng của công cụ mô phỏng GPSS World ............................................................ 32
3.3.4. Một số khái niệm trong GPSS World.................................................................................. 32
3.3.5. Các thực thể trong GPSS ..................................................................................................... 34



4.6. Đánh giá kết quả mô phỏng........................................................................................................ 58
Chương 5 KẾT LUẬN ......................................................................................................................... 60
5.1. Kết luận ...................................................................................................................................... 60
5.2. Hạn chế và kiến nghị .................................................................................................................. 61


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

FEC

Future Event Chain

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 ...................................................................
Hình 3.2. Minh họa một segment .................................................................................
Hình 3.3. Mô hình một chương trình mô phỏng hệ thống hàng đợi đơn giản .............
Hình 3.4. Minh họa chương trình mô phỏng trong GPSS World...................................

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
pháp nghiên cứu sau:
- Phương pháp phân tích, tổng hợp: nghiên cứu các tài liệu có liên quan tới vấn đề hệ
thống hàng đợi và công cụ mô phỏng hệ thống hàng đợi, phân tích để rút ra các vấn đề

Chương này đưa ra cơ sở lý thuyết về hệ thống hàng đợi, bao gồm: Các yếu tố của hệ
thống phục vụ (dòng vào, dòng ra, hàng chờ, kênh phục vụ), luật Little, các quá trình
Markov và trạng thái của hệ thống, nghiên cứu một số mô hình hàng đợi cơ bản và
một số phân phối xác suất quan trọng.
Chương 3 – Nghiên cứu công cụ mô phỏng hệ thống hàng đợi
Nêu các hướng tiếp cận mô phỏng: lập trình truyền thống và các công cụ mô phỏng có
sẵn, trong đó tập trung vào công cụ GPSS World.
Chương 4 - Ứng dụng công cụ mô phỏng vào mô phỏng hệ thống hàng đợi thực tế
Ứng dụng công cụ mô phỏng GPSS World vào bài toán thực tế: 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. Từ bài toán
cụ thể đó phân tích, tính toán, tiến hành mô phỏng và đánh giá kết quả thu được.
Chương 5 - Kết luận
Tóm lược kết quả chính của luận văn và nêu định hướng phát triển trong thời gian tới.


10

Chương 2
TỔNG QUAN VỀ LÝ THUYẾT HÀNG ĐỢI
Chương này tập trung vào tìm hiểu tổng quan về lý thuyết hệ thống hàng đợi:
giới thiệu về lý thuyết hàng đợi, vai trò và ứng dụng của lý thuyết hàng đợi, các yếu tố
của hệ thống hàng đợi bao gồm: dòng yêu cầu đầu vào, hàng chờ, kênh phục vụ, dòng
yêu cầu đầu ra, các thông số mô tả về hệ thống; công thức Kendall, luật Little, một số
mô hình hàng đợi cơ bản và một số phân phối xác suất quan trọng.
2.1. Vai trò của lý thuyết hàng đợi.
Lý thuyết hàng đợi chủ yếu được nhìn nhận như là một nhánh của lý thuyết xác
suất ứng dụng, được ứng dụng trong rất nhiều lĩnh vực khác nhau như viễn thông, máy
tính, dịch vụ, sản xuất, kiểm soát XNC,... Lý thuyết hàng đợi còn được biết đến với
các tên gọi khác như lý thuyết giao thông, lý thuyết xếp hàng, lý thuyết giải quyết tắc
nghẽn, lý thuyết phục vụ đám đông hay lý thuyết của các hệ thống dịch vụ ngẫu nhiên

Số các kênh phục vụ
Khả năng của hệ thống (trong hàng chờ và trong quá trình được phục vụ)
Qui mô (kích thước) khách hàng
Nguyên tắc phục vụ

6. Nguyên tắc phục vụ





1.Tiến trình vào



2. Phân phối thời gian
phục vụ












Tiến trình ra


12

trước), LIFO/LCFS (Last in First Out/Last Come First Served - đến sau phục vụ
trước), SIRO (Service In Random Order - phục vụ theo thứ tự ngẫu nhiên), PNPN
(Priority service - phục vụ theo thứ tự ưu tiên), PS (Processor Sharing – chia sẻ bộ xử
lý), Round Robin (phục vụ quay vòng),...[10, tr.4-5]
2.2.2. Các tham số đặc trưng của một hệ thống hàng đợi
Các tham số đặc trưng trong hệ thống hàng đợi được tóm tắt trong bảng 2.1 dưới đây:
Bảng 2.1. Các tham số đặc trưng trong hệ thống hàng đợi
STT Ký hiệu
Mô tả
1

Cn

Khách hàng thứ n vào hệ thống

2

τn

Thời điểm đến của khách hàng thứ n (Cn)

3

tn

Khoảng thời gian giữa khách hàng Cn-1 và Cn (tn= τn - τn-1 )



Giới hạn hàm phân phối xác suất 𝑃 𝑡 ≤ 𝑡 = 𝐴 𝑡
Kí hiệu: An(t)A(t)

9

B(𝓍)

Phân phối thời gian phục vụ

10

𝛼 𝑡

Số khách hàng đến trong khoảng thời gian (0,t)

11

𝛿 𝑡

Số khách hàng ra khỏi hệ thống trong khoảng thời gian (0,t)

12

N(t)

Số khách hàng ở trong hệ thống tại thời điểm t
𝑁 𝑡 = 𝛼 𝑡 − 𝛿(𝑡)

13

thời gian trung bình sử dụng dịch vụ

18

Hệ số sử dụng hệ thống
ρ

19

pK

𝜆𝑥 𝑛ế𝑢 𝑐ó 1 𝑘ê𝑛𝑕 𝑝𝑕ụ𝑐 𝑣ụ
𝜌 = 𝜆𝑥
𝑛ế𝑢 𝑐ó 𝑚 𝑘ê𝑛𝑕 𝑝𝑕ụ𝑐 𝑣ụ
𝑚
xác suất có K khách hàng trong hệ thống

2.2.3. Kí hiệu Kendall A / B / m / K / n / D
David George Kendall (15/01/1918 – 23/10/2007) là nhà toán học và thống kê
học người Anh. Ông là người đầu tiên đưa ra ký hiệu dùng để mô tả các thành phần cơ
bản của một hàng đợi [9, tr.14] có dạng: A / B / m / K / n / D.
Ý nghĩa của các ký hiệu trong mô tả Kendall được trình bày trong bảng 2.2.
STT Ký hiệu

Bảng 2.2: Các thành phần trong kí hiệu Kendall
Ý nghĩa

1

A

D

Nguyên tắc phục vụ. Nếu trong ký hiệu không nêu tham số này thì
ngầm định nguyên tắc phục vụ là FIFO.

-

Thông thường A và B có thể nhận các giá trị là [5, tr.30-9]:
M (phân phối mũ, viết tắt của Markovian hoặc là Memoryless)
D (phân phối đều, viết tắt của Deterministic)
Ek (phân phối Erlangian với k pha, viết tắt của Erlang-k)
G (phân phối chung, viết tắt của General)
Hk (phân phối siêu mũ, viết tắt của Hyperexponential).


14

Sau đây là bảng các hàm phân phối xác suất của A và B [10, tr.5]
Bảng 2.3: Một số hàm phân phối xác suất trong ký hiệu Kendall
STT

Viết
tắt

Hàm phân phối

1

M



𝑘
𝑗 =1 𝑞𝑗

=1

Chúng ta thường quan tâm đến các giải pháp để đạt được trạng thái cân bằng
(steady state), nghĩa là sau một thời gian hoạt động lâu dài, hệ thống có xu hướng đạt
đến một trạng thái cân bằng, ví dụ như phân phối khách hàng của hệ thống không thay
đổi. Điều này phân biệt rõ với trạng thái nhất thời (transient state), trạng thái có được
khi chúng ta khảo sát phản hồi của hệ thống với các sự kiện khác nhau trong một
khoảng thời gian ngắn [10, tr.5-6].
Ví dụ về một số hàng đợi: M/M/1 là hàng đợi có phân phối đến Poisson, thời
gian phục vụ hàm mũ, 1 kênh phục vụ; M/G/m là hàng đợi có m kênh phục vụ, phân
phối đến Poisson và thời gian phục vụ phân phối chung; M/M/r/K/n là hàng đợi có
giới hạn số khách hàng đến là n, thời gian đến và thời gian phục vụ hàm mũ, có r kênh
phục vụ và kích thước hệ thống là K; M/M/7/50/2000/FIFO là hàng đợi có phân phối
đến và thời gian phục vụ phân phối hàm mũ, có 7 kênh phục vụ, dung lượng của hệ
thống là 50 (7 đang được phục vụ và 43 trong hàng đợi), hệ thống phục vụ được tối đa
là 2000 yêu cầu, nguyên tắc phục vụ là FIFO.
2.2.4. Luật Little
Thời gian chờ đợi trung bình và số khách hàng trung bình trong một hệ thống
dịch vụ là các số liệu quan trọng đối với một người quản lý để làm căn cứ đưa ra các
quyết định điều chỉnh hệ thống sao cho đạt hiệu quả cao nhất. Luật Little (John
D.C.Little là nhà nghiên cứu tại Viện công nghệ Massachusetts, Mỹ) đưa ra mối liên
hệ giữa hai số liệu này với tốc độ trung bình khách hàng đến hệ thống.
Luật Little [6, tr.2] được phát biểu như sau: “Trong điều kiện trạng thái cân
bằng, số lượng trung bình khách hàng trong một hệ thống hàng đợi bằng với tốc độ



các quyết định cá nhân hàng ngày [6, tr.4].
2.3. Một số phân phối xác suất quan trọng
Chúng ta xem xét một số phân phối xác suất quan trọng trong lý thuyết hàng đợi
[4, tr. 34-72]
2.3.1. Phân phối Bernoulli
Một biến X có phân phối Bernoulli nếu nó có hai khả năng xảy ra, đó là X=1 và
X=0, xảy ra với xác suất P{X=1}=p và P{X=0}=q, trong đó p+q=1. Xác suất này
thường dùng để mô tả việc tung đồng xu, với X=1 khi xảy ra mặt sấp. Biến Bernoulli
có hàm sinh xác suất là q + pz, giá trị trung bình p và phương sai pq.


16

2.3.2. Phân phối nhị thức
Phân phối nhị thức thể hiện số lần thành công trong n lần thử Bernoulli, theo
định nghĩa là một chuỗi liên tiếp n lần thử độc lập, với mỗi lần thử có xác suất thành
công là p và thất bại là q=1-p. Nếu gọi Sn là số lần thành công trong n lần thử
Bernoulli thì Sn có thể được biểu diễn bởi công thức Sn=X1 + ... + Xn, trong đó Xj là
biến Bernoulli có giá trị Xj=1 nếu phép thử thứ j thành công và Xj=0 nếu thất bại. Bởi
vì các {Xj} là độc lập với nhau, có phân bố ngẫu nhiên giống nhau với hàm sinh là q +
pz, nên Sn có hàm sinh (q + pz)n. Triển khai hàm sinh cho ta Sn có phân phối nhị thức:
𝑃 𝑆𝑛 = 𝑘 =

𝑛 𝑘
𝑝 (1 − 𝑝)𝑛−𝑘
𝑘

(k=0,1,...n)

(2.1)

𝑘 1 !…𝑘 𝑟 ! 1

𝑘1

… 𝑝𝑟 𝑘 𝑟

(2.2)

Đẳng thức (2.2) mô tả phân phối đa thức, là một phân phối nhiều chiều, và các
hàm sinh phân phối có thể định nghĩa dưới góc độ tương tự thể hiện cho các phân phối
nhiều chiều. Chú ý rằng khi r=2 thì đẳng thức (2.2) chính là phân phối nhị thức.
2.3.4. Phân phối Poisson
Với phân phối hàm mũ chúng ta chủ yếu đề cập đến thời gian phục vụ. Tổng quát
hơn, chúng ta quan tâm đến các thời điểm khách hàng đến, giả sử rằng khoảng cách giữa


17

các thời điểm đến thành công của khách hàng là độc lập, đồng nhất phân phối theo hàm
mũ. Gọi các thời điểm này là T1, T2,… và giả sử biến ngẫu nhiên Xj=Tj – Tj-1 (j=1,2,…;
T0=0) có phân phối hàm mũ
𝑋𝑗 > 𝑡 = 𝑒 −λt

(j=1,2,…)

(2.3)

Chúng ta có câu hỏi: Nếu khoảng cách (độ dài thời gian) Xj=Tj – Tj-1 giữa các thời
điểm thành công được phân bố độc lập theo công thức (2.3), thì số các điểm phát sinh
trong một khoảng thời gian cố định tuân theo phân phối gì?

Phân phối Poisson thường được sử dụng để mô tả quá trình đến của hệ thống hàng
đợi. Đó là, công thức (2.3) thể hiện phân phối thời gian giữa các lần đến của khách hàng,
và công thức (2.4) thể hiện phân phối số khách hàng đến trong một khoảng thời gian t cố
định.
2.3.5. Phân phối Erlangian (Gamma)
Chúng ta vẫn quan tâm đến các thời điểm khách hàng đến, giả sử rằng khoảng
cách giữa các thời điểm đến thành công của khách hàng là độc lập, đồng nhất phân phối
theo hàm mũ. Gọi các thời điểm này là T1, T2,… và giả sử biến ngẫu nhiên Xj=Tj – Tj-1


18

(j=1,2,…; T0=0) có phân phối hàm mũ 𝑃 𝑋𝑗 > 𝑡 = 𝑒 −𝜆𝑡 (j=1,2,…) [và do đó số các
điểm phát sinh trong khoảng thời gian (0,t) có phân phối Poisson với giá trị trung bình
λt]. Chúng ta muốn tìm phân phối của khoảng n điểm liên tiếp, đó là, phân phối của tổng
Sn=X1+…+Xn của n biến ngẫu nhiên độc lập, đồng nhất phân phối theo hàm mũ.
Bởi vì Sn là tổng của n khoảng thời gian giữa các lần đến phát sinh theo quá trình
{N(t), t≥0}, có được vì {Sn≤x} và {N(x)≥n} là tương đương, nên:
∞

𝑃 𝑆𝑛 ≤ 𝑥 = 𝑃 𝑁(𝑥) ≥ 𝑛 =
𝑗 =𝑛

(𝜆𝑥)𝑗 −𝜆𝑥
𝑒
𝑗!

Trong đó đẳng thức thứ 2 tuân theo giả thiết rằng {N(t),t≥0} là một quá trình
Poisson. Do đó, nếu ta ký hiệu F(x) = P{Sn≤x} thì ta có:
𝐹 𝑥 =1−

19

Các mật độ đã được đơn giản hóa để có đơn vị trung bình bằng cách lấy λ=n.
Hàm phân phối n-phase, với n là số nguyên dương là một trường hợp đặc biệt của
phân phối gamma, có hàm mật độ
𝑓 𝑥 =

(𝜆𝑥 )𝑝 −1
ᴦ(𝑝)

𝜆𝑒 −𝜆𝑥

(p>0, λ>0, x≥0)

Phân phối gamma có thể coi là trường hợp tổng quát của phân phối Erlanggian pphase, khi mà số phase p không yêu cầu phải là số nguyên nữa.
2.4. Một số mô hình hàng đợi cơ bản
Các hệ thống hàng đợi có thể phân loại theo số lượng của các nguồn yêu cầu
được phục vụ là hữu hạn hay vô hạn, theo phân phối xác suất của quá trình đến và quá
trình phục vụ, theo số lượng kênh phục vụ, theo nguyên tắc phục vụ,... Có thể kể đến
một số mô hình hệ thống hàng đợi cơ bản sau:
2.4.1. Hệ thống hàng đợi cổ điển M/M/1
Đây là hệ thống hàng đợi nổi tiếng và đơn giản nhất, có thể được mô tả hệ thống
như sau:
- Thời gian giữa các lần đến liên tiếp tuân theo luật phân phối mũ, với tham số 
- Thời gian phục vụ tuân theo luật phân phối mũ, với tham số µ.
- Hệ thống chỉ có một kênh phục vụ đơn và sử dụng nguyên tắc phục vụ FIFO.
- Hàng đợi có kích thước vô hạn.
Hệ thống hàng đợi M/M/1 được mô hình hóa trong hình 2.3
Hàng đợi (queue)
Khách đến

0

λ

1

μ

2

k-1

…

k

μ

…

μ

Hình 2.4. Sơ đồ tốc độ chuyển trạng thái hệ thống M/M/1
2.4.1.1 Các xác suất trạng thái dừng
Gọi Pk(t) là xác suất có k khách hàng trong hệ thống tại thời điểm t.
Kí hiệu xác suất trạng thái dừng mà hệ thống ở trong trạng thái k (k∈ N) là pk
𝑝𝑘 = lim𝑡→∞ 𝑃𝑘 (𝑡)
Điều kiện dừng của hệ thống hàng đợi M/M/1 là: 
với |x|
Server 1

Hàng đợi (queue)
nguyên tắc

Khách đến

λ/m
…

phục vụ

tốc độ 

Khách ra

Server 2

λ/m

thời gian đợi W

Server m

Hình 2.5. Mô hình hệ thống M/M/m
Sơ đồ tốc độ chuyển đổi trạng thái thể hiện trong hình 2.6

0

1


Hình 2.6. Sơ đồ tốc độ chuyển trạng thái hệ thống M/M/m.
Hệ thống có:
-

Tốc độ khách hàng đến λk=λ, k=0,1,2,…

-

Tốc độ phục vụ 𝜇𝑘 = 𝑚𝑖𝑛[𝑘𝜇, 𝑚𝜇] =

𝑘𝜇 𝑣ớ𝑖 0 ≤ 𝑘 ≤ 𝑚
𝑚𝜇 𝑣ớ𝑖 𝑚 < 𝑘


22

-

λ

Điều kiện dừng 𝜌 =

𝑚𝜇


∞

𝑃 đợ𝑖 =

∞

𝑝𝑘 =
𝑘=𝑚

𝑘=𝑚

(𝑚𝜌)𝑘 1
𝑝0
𝑚! 𝑚𝑘−𝑚

(2.11)

Do đó:
(
𝑃 đợ𝑖 =

𝑚𝜌 𝑘
𝑚!
𝑘

𝑚 −1 (𝑚𝜌 )
𝑘=1
𝑘!

)(


(2.12)

2.4.3. Hệ thống hàng đợi M/M/1/K
Bây giờ chúng ta xem xét trường hợp hệ thống hàng đợi có khả năng lưu trữ hữu
hạn. Chúng ta giả định hệ thống có thể phục vụ nhiều nhất K khách hàng (bao gồm cả
khách hàng trong hàng đợi và khách hàng đang được phục vụ). Nếu có khách hàng
mới đến, khi hệ thống đang có ít hơn K khách hàng thì khách hàng đó sẽ được phép
vào hệ thống, ngược lại khách hàng đó sẽ bị từ chối, phải rời khỏi hệ thống và không
bao giờ quay trở lại. Trạng thái này gọi là trạng thái đóng. Điều này là cần thiết vì nếu
trong trường hợp ngược lại, khách hàng đó tiếp tục đợi bên ngoài hệ thống cho đến khi
có chỗ trống thì tiến trình đến không còn tuân theo luật Markov nữa. Cũng giống như
hàng đợi M/M/1, trạng thái hệ thống được đặc trưng bởi số khách hàng trong hệ thống


23

và cũng là hệ thống sinh/tử nguyên thủy. Hệ thống này phù hợp hơn để mô phỏng các
“hệ thống thực” vì không gian bộ đệm luôn giới hạn.
Hệ thống hàng đợi M/M/1/K được mô hình hóa trong hình 2.7
Hàng đợi (queue)
Khách đến

Khách ra

nguyên tắc
Server

K-1 vị trí



μ

k

μ

μ

Hình 2.8. Sơ đồ tốc độ chuyển trạng thái hệ thống M/M/1/K.
Tốc độ vào hệ thống của khách hàng thứ k là 𝜆𝑘 =

𝜆
0

𝑘