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

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN ĐỨC HOÀNG ANH

NGHIÊN CỨU VỀ HỆ THỐNG HÀNG ĐỢI
VÀ XÂY DỰNG CHƢƠNG TRÌNH MÔ PHỎNG
MÔ HÌNH TRÊN CÔNG CỤ MÔ PHỎNG GPSS

LUẬN VĂN THẠC SĨ ĐIỆN TỬ - VIỄN THÔNG

HÀ NỘI - 2012


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

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN ĐỨC HOÀNG ANH

NGHIÊN CỨU VỀ HỆ THỐNG HÀNG ĐỢI
VÀ XÂY DỰNG CHƢƠNG TRÌNH MÔ PHỎNG
MÔ HÌNH TRÊN CÔNG CỤ MÔ PHỎNG GPSS

Ngành: Công nghệ Điện tử Viễn thông
Chuyên ngành: Kỹ thuật điện tử
Mã số: 60 52 70

LUẬN VĂN THẠC SỸ



1.3.1 Quá trình Markov
1.3.2 Định nghĩa về trạng thái của hệ thố
1.3.3 Quá trình thay đổi trạng thái của hệ
1.4 Một số kết quả tổng hợp về hệ thống hàng đợi kinh điển M/M/1
Kết luận
Chương 2: Hiện trạng một số công cụ mô phỏng các bài toán hàng đợi _______ 16

2.1 Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri- net
2.1.1 Các khái niệm cơ bản về P/T net
2.1.2 Mô tả toán học về Petri net
2.1.3 Một số thuộc tính của P/T net
2.1.4 Một số công cụ sử dụng ngôn ngữ
2.1.5 Ứng dụng của mạng Petri net

2.2 Ngôn ngữ mô phỏng GPSS và công cụ GPSS World
2.2.1 Giới thiệu về ngôn ngữ GPSS
2.2.2 Sự ra đời của ngôn ngữ GPSS
2.2.3 Những ưu điểm của ngôn ngữ GPS
2.2.4 Các ứng dụng của công cụ mô phỏn
2.3 Một số ngôn ngữ lập trình bậc cao dùng để giải quyết bài toán hàng đợi
2.3.1 Ngôn ngữ lập trình Matlab


iv

2.3.2 Ngôn ngữ lập trình Java
2.3.3 Ngôn ngữ lập trình C++ và bộ công
2.4 So sánh giữa P/T net và GPSS
Kết luận

4.1.2 Lưu đồ giải thuật
4.1.3 Viết chương trình và chạy kết quả
4.1.4 Đánh giá kết quả
4.2 Bài toán đánh giá hoạt động của một phần dây chuyền sản xuất tại E112
4.2.1 Phân tích bài toán
4.2.2 Lưu đồ giải thuật
4.2.3 Chương trình và kết quả mô phỏng
Kết luận
Kết luận chung ______________________________________________________ 48
TÀI LIỆU THAM KHẢO _____________________________________________ 49

Bảng các ký hiệu và chữ viết tắt
Ký hiệu


CEC

Cu

GPSS

Ge
Sy

GPSS/PC

Ge
Sy

FEC

19
22
24
25
26

Hình 3. 1 Một hệ phục vụ đám đông đơn giản
Hình 3. 2 Minh họa mô hình của hệ phục vụ đám đông đơn kênh hở

37
37

Hình 4. 1 Mô hình luồng thông tin đi vào hệ thống
Hình 4. 2 Lưu đồ giải thuật
Hình 4. 3 Đánh giá hiệu suất của các bộ phận A, B, C với 300 thông tin
Hình 4. 4 Đánh giá hiệu suất của A, B, C với tối đa 1500 thông tin
Hình 4. 5 Mô hình bài toán
Hình 4. 6. Lưu đồ giải thuật của bài toán
Hình 4. 7 Đánh giá hiệu quả của bể mạ trong bài toán

40
41
44
44
45
46
47


vii

sự đơn giản hóa nhưng chính xác các đặc điểm của hệ thống phục vụ đám đông dưới dạng
mô hình. Dùng phương pháp luận nào, phương pháp nào? Xem xét phương án nào là khả thi
nhất, tối ưu nhất?...
Để giải bài toán trên như, chúng ta có thể: tìm kiếm và giải quyết bằng các mô hình
toán học, dùng tìm ra các giải thuật và dùng các ngôn ngữ lập trình (C++, Pascal…), mô
phỏng bằng các công cụ mô phỏng (Java, Matlab, P/T Net…) Mô phỏng hệ thống bằng cách
sử dụng các ngôn ngữ lập trình truyền 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ới việc xây
dựng các hàm sinh ngẫu nhiên các sự kiện. Chính vì vậy đã xuất hiện các ngôn ngữ mô phỏng
chuyên dụng.
Ngôn ngữ lập trình GPSS (General Purpose Simulation System) [4], 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. GPSS dự đoán các hành vi trong tương lai của các hệ
thống phục vụ đám đông . 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 phục vụ đám đông; như là các yêu cầu, các thiết bị phục
vụ, hàng đợi… Tập hợp đầy đủ các thành phần như vậy cho phép xây dựng các mô phỏng
phức tạp trong khi đảm bảo những thuật ngữ thông thường của hệ thống phục vụ đám đông.
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
tại Liên bang Nga cũng như một số quốc gia khác. Tuy nhiên, ở Việt Nam ta, vấn đề này còn
khá mới. Trên cơ sở các nghiên cứu đã có, luận văn giới thiệu ví dụ thực tế: đánh giá hoạt
động của tổng đài và phòng xử lý thông tin ở nơi tôi đang làm việc
Luận văn gồm các chương với nội dung được mô tả sơ bộ dưới đây:


2

Chương 1. Cơ sở lý thuyết về hệ thống hàng đợi: đư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ụ), các
quá trình Markov và trạng thái của hệ thống. Với sự phát triển của khoa học máy tính, phương
pháp mô phỏng chứng tỏ những khả năng tốt cho việc giải bài toán hàng đợi, ngoài phương


Hình 1. 1 Ví dụ về hệ thống hàng đợi, hay còn gọi là hệ thống phục vụ đám đông.
Trong mô hình này, chúng ta quan sát thấy có yếu tố khách đến, khách bỏ đi
(do không có thời gian chờ đợi, hoặc các lý do khác), khách xếp hàng chờ tới lượt
mình được phục vụ, các máy phục vụ, và khách hàng đã được phục vụ xong, rời khỏi
hệ thống phục vụ trên.
Các yếu tố này có thể tóm lược sơ bộ gồm các thành phần trong bảng 1:
STT

Tên yếu tố

1

Dòng các yêu cầu
đầu vào

2

Hệ thống phục vụ


3

Các máy phục vụ

4

Dòng các yêu cầu
đầu ra


Wi

6

Ns(t)

7

τi

8

τ

9

T

Có nhiều nguyên tắc phục vụ, hoặc nguyên tắc xếp hàng. Chúng ta lấy ví dụ
đơn giản nhất khi xếp hàng là: Ai đến trước phục vụ trước – First In, First Out. Khi đó,
Tổng thời gian trễ Ti của khách hàng thứ i sẽ là tổng của thời gian xếp hàng W i và thời
gian phục vụ τi. Chúng ta có:
T i = W i + τi
1.1.2 Quan điểm về hiệu suất của hệ thống hàng đợi
Có hai quan điểm về vấn đề này [2]
Nếu nhìn ở góc độ khách hàng, chúng ta đã biết tốc độ đến (arrival rate) là λ, và
có một số khách hàng bỏ đi, với tốc độ bỏ đi là λ b. Khi đó chúng ta sẽ tính hiệu suất hệ
thống (theo góc độ dòng yêu cầu đầu vào, hay góc độ khách hàng):
η1 = λb/ λ
Nếu nhìn ở góc độ phân bố tài nguyên trong hệ thống, hiệu suất hệ thống tính


(1.8)

Các ký hiệu trong mô tả Kendall được trình bày trong bảng 3:

STT

Ký hiệu

1

A

2

B

3

m

4

K


5

Chi tiết hơn, với ký hiệu X là biến ngẫu nhiên của phân phối xác suất và E[X] là
kỳ vọng , hoặc giá trị trung bình của X, chúng ta nói về các phân phối xác suất [8, 20]

4

D

P
g
v

5

G

P

6

GI

P
c
h
đ

7

PH

P

1.2 Các yếu tố của hệ thống phục vụ

phối Poisson với N(t) là số các biến cố xảy ra trong khoảng thời gian [0, t]
N(t) là quá trình ngẫu nhiên liên tục, không giảm theo thời gian.
N(t) có phân phối Poission có kỳ vọng là λt, và có biểu diễn như sau:

P[N (t) k]
-

Dòng vào Poisson không dừng: Là dòng vào mà xác suất xuất hiện x yêu
cầu trong khoảng thời gian Dt, kể từ thời điểm t, phụ thuộc vào t, nghĩa là:

x(Dt )
Trong đó a(t, Dt) là số trung bình các yêu cầu xuất hiện từ t đến Dt.
-

Dòng vào Poisson dừng: Là dòng vào mà xác suất trong khoảng thời gian
Dt, kể từ thời điểm t, có x yêu cầu xuất hiện, không phụ thuộc vào t, nghĩa là:

x(Dt )


Trong đó, λo là số yêu cầu trung bình xuất hiện trong một đơn vị thời gian (cường
độ dòng yêu cầu). Nói cách khác là mật độ dòng yêu cầu không đổi.


7

Nếu t là khoảng thời gian giữa lần xuất hiện các yêu cầu liên tiếp, thì t là một đại
lượng ngẫu nhiên tuân theo luật chỉ số, nghĩa là t có hàm phân bố xác suất và hàm mật
độ như sau:


Khoảng thời gian giữa các lần xuất hiện liên tiếp các yêu cầu trong dòng phục vụ của
mỗi kênh chính là khoảng thời gian kênh đó phục vụ xong từng yêu cầu, nghĩa là thời gian
phục vụ của kênh.


8

Nếu dòng phục vụ trên mỗi kênh là dòng tối giản thì thời gian phục vụ của kênh đó là
đại lượng ngẫu nhiên tuân theo luật chỉ số, nghĩa là có hàm phân phối xác suất và mật độ xác
suất dạng (1.18) và (1.19)
1.2.4 Dòng yêu cầu đầu ra
Dòng yêu cầu đầu ra (gọi tắt là dòng ra) là dòng các yêu cầu đi ra khỏi hệ thống. Có
hai loại dòng ra:
Dòng yêu cầu ra đã được phục vụ xong: là các yêu cầu đã được phục vụ ở mỗi kênh,
nếu dòng đó là tối giản thì nó có một vai trò rất lớn trong hệ thống phục vụ. Người
ta đã chứng minh được rằng: nếu dòng vào là tối giản thì dòng ra được phục vụ tại
mỗi kênh sẽ là dòng xấp xỉ tối giản (như đã trình bày ở phần 1.2.3)
Dòng yêu cầu ra không được phục vụ: là một phần các yêu cầu đến hệ thống nhưng
không được phục vụ vì một lí do nào đó.
1.2.5 Các quy luật hoạt động của hệ thống phục vụ
Một hệ thống phục vụ hoạt động theo những quy luật nào, nguyên tắc nào? Sự hiệu quả
của những quy luật đó ra sao? Ứng với loại dòng vào cụ thể, hệ thống phục vụ phải chọn lựa
ra cách thức phục vụ nào để tối ưu nhất?... Đó là một vài câu hỏi đặt ra cho hệ thống phục vụ
Đặc điểm chung về các quy luật phục vụ
Như vậy, các quy luật phục vụ của hệ thống phục vụ là cách mà hệ thống tiếp nhận các
yêu cầu đầu vào, tiến hành phân loại, sắp xếp và phục vụ các yêu cầu đó trong hệ thống, ngoài
ra, các quy luật này còn thiết lập một số các quy định khác đối với yêu cầu đầu vào. Nó chỉ ra:
Khi nào thì yêu cầu đáp ứng được các quy luật phục vụ và yêu cầu đó được nhận
vào phục vụ
Cách phân bổ các yêu cầu đó vào các kênh phục vụ


6

Static priorities

7

Dynamic priorities

8

Preemption

Tùy thuộc vào việc chúng ta chọn phương pháp phục vụ, hàng đợi sẽ được điều
chỉnh theo phương pháp đó sao cho có hiệu quả nhất.

1.3 Trạng thái của hệ thống phục vụ
Phần này, chúng ta quan tâm đến trạng thái hoạt động của hệ thống phục
vụ. Làm thế nào để tìm hiểu xem hệ thống phục vụ với những yếu tố, các quy luật đã
trình bày ở trên, chúng ta tìm ra trạng thái hoạt động của nó? Trước hết, chúng ta tìm
hiểu về quá trình Markov.
1.3.1 Quá trình Markov
Quá trình Markov (Markov Process) là một quá trình ngẫu nhiên, trong đó, tương lai
của quá trình chỉ phụ thuộc vào hiện tại, không phụ thuộc vào quá khứ.
Cụ thể, nếu với mọi cách chọn thời điểm tùy ý: t1 < t2 < t3 < … < tk < tk+1
P[X(tk+1) = xk+1/ X(tk) = xk, … , X(t1) = x1]
= P[X(tk+1) = xk+1/ X(tk) = xk]
Nếu X(t) là một quá trình ngẫu nhiên rời rạc, khi đó X(t) là một quá trình Markov nếu
P[a < X(tk+1) = xk+1 < b / X(tk) = xk, … , X(t1) = x1]
= P[a < X(tk+1) = xk+1 < b / X(tk) = xk] với mọi cách chọn tk và mọi k

Xét quá trình ngẫu nhiên Poission có biểu diễn như sau:

P[N (t) k]


10

Từ định nghĩa trên, chúng ta thấy ngay, quá trình ngẫu nhiên Poission là
một quá trình Markov liên tục:
P[N(tk+1) = j / N(tk)= i , N(tk-1 =xk-1), …, N(t1)= x1]
=

P [j - i sự kiện xảy ra trong khoảng thời gian tk+1- tk giây]

t)

(
=
=

P

ij

(j

P[N(tk+1) = j / N(tk)= i]

Xét một chuỗi Markov Xn (là quá trình ngẫu nhiên Markov nhận các giá
trị nguyên), vấn đề là làm thế nào để xác định được Xn

…

…

…

1.3.2 Định nghĩa về trạng thái của hệ thống phục vụ
Xét hệ thống phục vụ với c máy phục vụ (server). Trạng thái của hệ thống phục vụ,
ký hiệu là xk(t), là khả năng kết hợp dòng vào và dòng ra của hệ thống ở một thời điểm t
nhất định nào đó. Chúng ta mô tả đơn giản về số kênh làm việc trong hệ thống như sau:
Thời điểm
t


11

k
Số kênh đang làm
việc
Số kênh rảnh rỗi
c–k
Tại một thời điểm t nào đó, hệ thống phục vụ đang ở trạng thái cụ thể. Bản chất
trạng thái đó là một quá trình ngẫu nhiên, nó hoạt động theo một luật phân phối xác
suất nhất định. Do vậy, tồn tại khả năng xuất hiện một trong các trạng thái x k(t) (k =
0,1,2,...) tại thời điểm t, với xác suất là một giá trị xác định Pk(t).
1.3.3 Quá trình thay đổi trạng thái của hệ thống phục vụ
Hệ thống tồn tại ở trạng thái i trong một khoảng thời gian nhỏ nào đó, sau đó, hệ
thống sẽ nhảy đến trạng thái j khác với trạng thái i. Nguyên nhân gây ra sự thay đổi
trạng thái gồm có:
- Sự thay đổi của dòng yêu cầu đầu vào (dòng vào)

khả năng xảy ra biến cố đó là
Tốc độ mà quá trình X(t) nhảy từ trạng thái i
sang trạng thái j được tính bằng
Khi đó, chúng ta thiết lập được hệ phương trình vi phân Chapman – Kolmogorov :

p'j (t)

Hình 1. 3 Mô tả sự chuyển trạng thái của chuỗi Markov
Để giải được hệ phương trình (1.30), chúng ta cần biết rõ các điều kiện ban đầu
pj(0) =0, pi(0)=1 với mọi i#j; j = 0, 1, 2,… Đây là phương trình trạng thái của hệ thống.
Sơ đồ trạng thái là tập hợp các mũi tên, hình vẽ, diễn tả quá trình biến đổi trạng
thái của hệ thống phục vụ, trong đó các mũi tên nối liền các trạng thái mô tả bước
chuyển từ trạng thái này sang trạng thái khác, các hình chữ nhật biểu diễn trạng thái
của hệ thống. Tham số ghi trên các mũi tên biểu thị tác động của cường độ của dòng
biến cố kéo trạng thái dịch chuyển theo hướng mũi tên.

X0

X3

λ23


13

Hình 1. 4: Sơ đồ trạng thái của hệ thống phục vụ



Khi t ∞, chúng ta thu được p’j(t)

Khoảng thời gian giữa các lần đến là các biến ngẫu nhiên độc lập, tuân theo
phân phối mũ, có trung bình là 1/ λ
Thời gian phục vụ là các biến ngẫu nhiên độc lập, tuân theo phân phối mũ, tốc
độ trung bình là 1/μ.
Lưu ý: Tốc độ trung bình khi đến = λ < μ = Tốc độ tối đa phục vụ
Hàm xác suất trạng thái dừng của hệ M/M/1, có ký hiệu N(t).
Thời gian đến khi mà các khách hàng đến tiếp theo là biến ngẫu nhiên phân
phối mũ. Biến ngẫu nhiên này độc lập với thời gian mà khách hàng thực sự
được phục vụ ở bên trong của hệ M/M/1.
Do tính chất không nhớ của phân phối mũ, đối chiếu với định nghĩa về quá trình
Markov, chúng ta kết luận N(t) =k là một chuỗi Markov liên tục
Xét theo mô tả Kendall: A/B/m/K đối chiếu cho hệ M/M/1/1 (chọn K=1)
-

A(t) là số khách hàng đến, là quá trình Poission,
Trong khoảng thời gian δ, xác suất có một khách hàng đến là

P[A( ) 1]
-

Trong khoảng thời gian δ, xác suất có ít nhất hai khách hàng đến là


14

P[ A( ) 2] o( )
-

P[


-

Thời gian chờ trung bình trong M/M/1 là
(1.38)

E[W] E[T] E[ ]

-

Thời gian trung bình (theo (1.5)) là

(1.39)

E[Nq
Sử dụng dịch vụ của M/M/1 có hệ số là:
1- p0 = λ/ µ
-

(1.40)

Ngoài hệ M/M/1 kinh điển chúng ta giới thiệu này, bài toán hàng đợi rất
đa dạng với các hệ M/M/1/K, M/M/c, M/M/c/c, M/M/∞, M/G/1 [2; 12]
Kết luận
Chương 1 tập trung làm rõ mô hình lý thuyết, mô tả toán học các yếu tố,
các tham số liên quan đến hệ thống hàng đợi, và tìm hiểu về trạng thái của hệ thống.
Chúng ta quan tâm tới yếu tố dòng vào, dòng ra. Chúng mang bản chất
toán học là các phân phối xác suất, cùng với công thức Little để đánh giá thời gian
phục vụ trung bình của hệ thống hàng đợi. Các quy luật phục vụ trong hệ thống hàng
đợi rất đa dạng, và tùy theo yếu tố dòng vào thuộc loại phân phối xác suất toán học nào