i đại học thái nguyên
Tr-ờng đại học công nghệ thông tin và truyền thông
Vũ NGọC Hà
Nghiên cứu một số kỹ thuật giải bài
toán hàng đợi Và ứng dụng mô phỏng hệ
thống giao dịch ngân hàng
luận văn thạc sĩ khoa học máy tính thái nguyên 2014
ii
đại học thái nguyên
Tr-ờng đại học công nghệ thông tin và truyền thông
Vũ NGọC Hà
Tôi xin chân thành cảm ơn Ban lãnh đạo Trường Đại học Công nghệ
thông tin và Truyền thông - Đại học Thái Nguyên và các giảng viên đã tạo
nhiều điều kiện giúp tôi hoàn thành luận văn này.
Tôi cũng xin gửi lời cảm ơn tới các bạn trong tập thể lớp Cao học
khoá 11A, ngành Khoa học máy tính đã ủng hộ, khuyến khích tôi trong
suốt quá trình học tập.
Sau cùng tôi xin bày tỏ lòng biết ơn đến người thân, cùng bạn bè,
đồng nghiệp cơ quan và gia đình, những người luôn cổ vũ động viên tôi
hoàn thành bản luận văn tốt nghiệp Thạc sĩ này. Thái Nguyên, ngày 26 tháng 5 năm 2014
HỌC VIÊN
Vũ Ngọc Hà
v MỤC LỤC
LỜI CAM ĐOAN Error! Bookmark not defined.
LỜI CẢM ƠN iv
MỤC LỤC v
2.2. Quy trình chung của việc phân tích hệ thống hàng đợi 34
2.3. Các bước giải bài toán hàng đợi dựa trên Petri Nets 36
2.4. Công cụ mô phỏng bài toán hàng đợi 37
2.4.1. Công cụ mô phỏng 37
2.4.2. Các thành phần cơ bản 38
2.4.3. Mô tả toán học 39
2.4.4. Một số thuộc tính 40
2.5. So sánh một số công cụ của Petri Nets 42
2.6. Các lĩnh vực hoạt động của Petri Nets 44
2.7. Các bước tạo một mô phỏng trên TNET 45
CHƢƠNG 3: SỬ DỤNG PETRI NETS TRONG BÀI TOÁN MÔ PHỎNG
HỆ THỐNG PHỤC VỤ GIAO DỊCH NGÂN HÀNG 47
3.1. Thiết lập bài toán hàng đợi không ưu tiên 47
3.2. Phân tích bài toán hàng đợi 48
3.2.1. Phân tích các yêu cầu của bài toán 48
3.2.2. Phân tích kết quả của bài toán bằng lý thuyết hàng đợi 50
3.3. Ứng dụng Petri Nets mô phỏng bài toán hệ thống giao dịch ngân hàng51
3.3.1 Mô hình Petri Nets 51
3.3.2. Kết quả chạy của mô hình F-nets 56
3.4. So sánh, đánh giá các kết quả mô phỏng 61
3.4.1. So sánh theo sự phân bố hàm Input, output 61
3.4.2. So sánh theo thời gian 71
KẾT LUẬN 74
vii
TÀI LIỆU THAM KHẢO 75
viii
DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT
DANH MỤC CÁC BẢNG
Bảng 1.1: Các yếu tố cấu thành một hệ thống hàng đợi 5
Bảng 1.2: Các tham số đặc trưng trong hệ thống hàng đợi 7
Bảng 1.3: Một số phương pháp phục vụ áp dụng trong lý thuyết hàng đợi 12
Bảng 2.1. Các tham số đặc trưng trong hệ thống hàng đợi 28
Bảng 2.2: Các thành phần trong kí hiệu Kendall 29
Bảng 2.3: Một số phân phối xác suất liên quan đến A và B trong mô tả Kendall30
Bảng 2.4: So sánh một số công cụ Petri Nets 42
Bảng 3.1: Các giá trị tham số đầu vào của t1 54
Bảng 3.2: Các giá trị tham số đầu vào của t8 55
Bảng 3.3: Các giá trị tham số đầu vào của t5 55
Bảng 3.4: Các giá trị tham số đầu vào của t6 56
Bảng 3.5: Các giá trị tham số đầu vào của t1 58
Bảng 3.6: Các giá trị tham số đầu vào của t5 58
Bảng 3.7: Các giá trị tham số đầu vào của t6 59
2 phương pháp 60
Bảng 3.9: Các giá trị tham số đầu vào của t1 61
Bảng 3.10: Các giá trị tham số đầu vào của t5 62
Bảng 3.11: Các giá trị tham số đầu vào của t6 63
Bảng 3.12: Các giá trị tham số đầu vào của t1 64
Bảng 3.13: Các giá trị tham số đầu vào của t5 64
Bảng 3.14: Các giá trị tham số đầu vào của t6 65
Bảng 3.15: Các giá trị tham số đầu vào của t1 66
Bảng 3.16: Các giá trị tham số đầu vào của t5 67
Bảng 3.17: Các giá trị tham số đầu vào của t6 67
Bảng 3.18: Các giá trị tham số đầu vào của t1 68
Bảng 3.19: Các giá trị tham số đầu vào của t5 69
Bảng 3.20: Các giá trị tham số đầu vào của t6 69
Bảng 3.21: So sánh theo phân bố Input, Output (t1) 70
Hình 2.18: Minh họa tính bất tử của Petri Nets 41
Hình 2.19: Minh họa tính không có đường bao giới hạn của Petri-net 41
Hình 2.20: Minh họa tính bảo thủ của Petri Nets 42
Hình 3.1: Hình minh họa bài toán giao dịch ngân hàng 48
xi
Hình 3.2: Mô tả các điều kiện bài toán 48
Hình 3.3: Sơ đồ thuật toán 49
Hình 3.4: Mô hình M/M/2/7 50
Hình 3.5: 51
Hình 3.6: Cửa sổ kết quả trên các transition 56
Hình 3.7: Cửa sổ kết quả trên các place 57
Hình 3.8: Cửa sổ kết quả trên các transition 59
Hình 3.9: Cửa sổ kết quả trên các place 60
Hình 3.10: Mô tả theo các tham số đầu vào chuẩn 62
Hình 3.11: Cửa sổ kết quả trên các place của mô hình chuẩn-chuẩn 63
Hình 3.12. Mô tả theo tham số đầu vào đều 65
Hình 3.13: Cửa sổ kết quả trên các place của mô hình chuẩn-đều 66
Hình 3.14: Cửa sổ kết quả trên các place của mô hình đều-chuẩn 68
Hình 3.15: Cửa sổ kết quả trên các place của mô hình đều-đều 70
Hình 3.16: Cửa sổ kết quả trên các place 71
Hình 3.17: Cửa sổ kết quả trên các place 72
Hình 3.18: Cửa sổ kết quả trên các place 72
các sự kiện theo một mô hình nhiều sự kiện xảy ra đồng thời (song song) với
việc xây dựng các hàm tạo ngẫu nhiên các sự kiện (random) cũng không hề
2
đơn giản, chính vì vậy đã xuất hiện các ngôn ngữ mô phỏng chuyên dụng.
Hiện nay có một số phương pháp đánh giá, mô phỏng được sử dụng rộng rãi
và có hiệu quả trên thực tế là phương pháp mô hình hoá và các mô hình được
sử dụng hiện nay là mô hình hàng đợi, mạng Petri, đồ thị, và các mô hình lai
ghép Trong đó mô hình hàng đợi là một mô hình đơn giản và tỏ ra có hiệu
quả trong thực tế [7,12].
Với Petri Nets và nhu cầu cần mô phỏng hệ thống hàng đợi, việc áp
dụng cách tiếp cận cũng như công cụ mô phỏng nào là một vấn đề quan trọng
do tính chất của hệ thống, quy mô của hệ thống có thể là những yếu tố ảnh
hưởng đến việc lựa chọn công cụ. Chính vì vậy, yêu cầu lựa chọn, so sánh,
đánh giá các công cụ Petri Nets và ứng dụng mô phỏng là một đề tài mang ý
nghĩa khoa học và thực tiễn cao. Với lý do đó, tôi lựa chọn đề tài “Nghiên
cứu một số kỹ thuật giải bài toán hàng đợi và ứng dụng mô phỏng hệ thống
giao dịch ngân hàng” cho luận văn tốt nghiệp Thạc Sĩ của mình.
*. Những nội dung nghiên cứu chính
Luận văn gồm: Phần mở đầu, ba chương chính, phần kết luận, tài liệu
tham khảo và phụ lục. Bố cục như sau:
Chương 1: TỔNG QUAN VỀ HỆ THỐNG HÀNG ĐỢI
Chương này trình bày tổng quan về hệ thống hàng đợi: Hệ thống hóa các
khái niệm, các thành phần cơ bản của hệ thống hàng đợi.
Chương 2: MỘT SỐ KỸ THUẬT ĐỂ GIẢI QUYẾT BÀI TOÁN HÀNG
ĐỢI
Chương này nghiên cứu một số kỹ thuật cơ bản để giải quyết bài toán
hàng đợi và mô phỏng bằng công cụ Petri Nets.
Chương 3: SỬ DỤNG PETRI NETS TRONG BÀI TOÁN MÔ PHỎNG HỆ
THỐNG GIAO DỊCH NGÂN HÀNG
- Phân phối thời gian phục vụ
- Số các kênh phục vụ
- Khả năng của hệ thống
- Qui mô (kích thước) khách hàng
4
- Nguyên tắc phục vụ Hình 1.1: Các thành phần cơ bản của một hàng đợi
1.2. Hệ thống hàng đợi
1.2.1. Mô tả hệ thống hàng đợi
Chúng ta làm quen với một ví dụ về hệ thống hàng đợi [2,15] với mô
hình được mô tả ở hình 1.1
Hình 1.2: Mô hình cơ bản của hệ thống hàng đợi (hay hệ thống phục vụ
đám đông)
Tên yếu tố
Giải thích
1
Dòng các yêu cầu
đầu vào
Khách hàng gọi điện thoại đến một tổng đài giải
đáp (Call Center), các xe ô tô đi vào bãi đậu xe,
các máy bay hạ cánh xuống một đường băng…
2
Hệ thống phục vụ
Là các máy phục vụ nhằm đáp ứng yêu cầu ứng
với từng loại đầu vào cụ thể ở trên, trong hệ thống
phục vụ có hàng đợi, tại đó, khách hàng xếp hàng
đợi đến lượt mình được phục vụ. Hệ thống phục
vụ có các máy phục vụ và chúng hoạt động theo
những quy luật, nguyên tắc phục vụ nào?
3
Các máy phục vụ
Các máy điện thoại bàn và nhân viên trong một
Call Center, đường băng tại sân bay, vị trí trong
bãi đậu xe…
4
Dòng các yêu cầu
đầu ra
Là các yêu cầu đã được phục vụ sau khi đi ra khỏi
hệ thống phục vụ ở trên
6
Về bản chất, khi xuất hiện các yêu cầu vượt quá khả năng đáp ứng của
Dòng yêu cầu đầu ra, là các yêu cầu đã đƣợc và không đƣợc
phục vụ, đặc trưng bởi tốc độ tối đa phục vụ. Lưu ý: λ < µ
4
N
q
(t)
Hàng đợi, đặc trưng bởi số lượng khe để phục vụ cho xếp hàng
5
W
i
Thời gian xếp hàng của khách hàng thứ i trong hàng đợi
6
N
s
(t)
Kênh phục vụ và các cách phục vụ, đặc trưng bởi số lượng
kênh, cụ thể có c kênh, cũng có nghĩa là đang có c khách hàng
đang được phục vụ
7
τ
i
Thời gian phục vụ với khách hàng thứ i
8
τ
Thời gian phục vụ trên tất cả các máy phục vụ
9
T
Tổng thời gian phục vụ của toàn bộ hệ thống
nhất của dòng vào là tốc độ đến (arrival rate), ký hiệu là λ.
Ví dụ: Khách hàng xếp hàng tại quầy bán vé xem phim, các container
chờ để được dỡ hàng, các xe ô tô chờ xếp hàng vào bãi, các máy bay chờ để
cấ
Chúng ta thấy rằng, dòng các yêu cầu đầu vào là một yếu tố xuất hiện
ngẫu nhiên, chúng có thể ít, có thể nhiều tùy theo thời điểm đến, nó có đặc
trưng bởi một số phân bố xác suất nào đó . Trong khóa luận này, chúng ta tập
trung xét hai loại dòng yêu cầu đầu vào thông dụng nhất là:
Dòng vào tiền định, đặc trưng bởi phân phối tất định D
Dòng vào Possion, tuân theo phân phối Possion
Dòng vào tiền định
Dòng vào tiền định là dòng vào trong đó các yêu cầu đến hệ thống phục
vụ tại các thời điểm cách đều nhau một khoảng a.
Dòng vào tiền định là một đại lượng ngẫu nhiên có hàm phân bố xác suất
theo phân phối D:
F(x) = 1, nếu x ≥ a
F(x) = 0, nếu x < a
(1.11)
9
Dòng vào Poisson
Dòng vào Poisson là dòng yêu cầu đi đến hệ thống, dòng vào này tuân
theo luật phân 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:
t
k
e
!
)(
(1.14)
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.
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:
t
o
etF 1
(1.15)
t
o
o
etf
(1.16)
10
1.3.2. Hàng đợi
Hàng đợi (Queue) là tập hợp các yêu cầu sắp xếp theo một nguyên tắc
nào đó để chờ đợi đến lượt được vào phục vụ trong hệ thống. Trong hàng đợi
ta có thể giới hạn hoặc không giới hạn số lượng khách chờ. Phần dưới đây,
chúng ta nói thêm về các quy luật xếp hàng chờ đợi đến lượt phục vụ
1.3.3. Kênh phục vụ
(1.18)
11
Trong đó:
μ
o
: là số yêu cầu được phục vụ trên mỗi kênh trong một đơn vị thời
gian (cường độ dòng phục vụ)
F(t): Hàm phân bố xác suất.
f(t): Hàm mật độ xác suất.
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.
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.16) và (1.17)
1.3.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.3.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.3.5. Các quy luật hoạt động của hệ thống phục vụ
Order
Phục vụ theo thứ tự ngẫu nhiên
4
PS – Processor Shared
Phục vụ có chia sẻ chung bộ xử lý
5
IS – Infinitive Server
Phục vụ không xác định
6
Static priorities
Phục vụ ưu tiên các yếu tố tĩnh
7
Dynamic priorities
Phục vụ ưu tiên các yếu tố động
8
Preemption
Thiết lập chế độ ưu tiên
13
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.4. Trạng thái hệ thống phục vụ
Phần này [11,14], 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.4.1. Định nghĩa
Trạng thái của hệ thống phục vụ, ký hiệu là x
k
cường độ
dòng vào λ
i
(t)
tại thời điểm t, hệ thống sẽ biến đổi từ trạng thái này sang trạng thái khác.
14
1.4.3. Sơ đồ trạng thái
Sơ đồ trạng thái của hệ thống được dùng để diễn tả quá trình thay đổi
trạng thái của hệ thống phục vụ. 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ệ
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, hình chữ nhật biểu diễn trạng thái của hệ thống. Tham số ghi trên
mũi tên biểu thị tác động của cường độ dòng biến cố kéo trạng thái dịch chuyển
theo hướng mũi tên.
Chúng ta ví dụ về một hệ thống có sự thay đổi trạng thái gồm bốn yếu tố,
và sự thay đổi trạng thái trong hệ thống được mô tả như hình vẽ 1.4
Hình 1.4: Sơ đồ trạng thái của hệ thống phục vụ
1.4.4. Qui tắc thiết lập hệ phương trình trạng thái
Căn cứ vào sơ đồ trạng thái, ta thiết lập quan hệ giữa xác suất xuất hiện
trạng thái x
k
(t)với xác suất xuất hiện là P
k
X
2
X
3
10
02
12
21
23
32
31
Copyright: Tài liệu đại học ©