ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG
NGHIÊN CỨU VÀ SỬ DỤNG CÔNG CỤ
GENERAL PURPOSE SIMULATION SYSTEM
TRONG BÀI TOÁN MÔ PHỎNG HÀNG ĐỢI
Thái Nguyên - 2012
Thái Nguyên - 2012
i
LỜI CAM KẾT
Tôi xin cam đoan Luận văn là do tôi thực hiện, được hoàn thành trên cơ
sở tìm kiếm, nghiên cứu, tổng hợp phần lý thuyết và các phương pháp kĩ thuật
được trình bày bằng văn bản trong nước và trên thế giới. Mọi tài liệu tham
khảo đều được nêu ở phần của Luận văn. Luận văn này là
mới và không sao chép nguyên bản từ bất kì một nguồn tài liệu nào
khác.
Nếu có gì sai sót, tôi xin chịu mọi trách nhiệm./. HỌC VIÊN Nguyễn Ngọc Thanh
2.1. Ngôn ngữ mô phỏng GPSS và công cụ GPSS World 15
2.1.1. Giới thiệu về ngôn ngữ GPSS 15
2.1.2. Sự ra đời của ngôn ngữ GPSS 15
2.1.3. Những ưu điểm của ngôn ngữ GPSS 16
2.1.4. Các ứng dụng của công cụ mô phỏng GPSS World 17
2.2. Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri-net 19
2.2.1. Các khái niệm cơ bản về Petri-net 19
2.2.2. Mô tả toán học về Petri-net 21
2.2.3. Một số thuộc tính của Petri-net 22
2.2.4. Một số công cụ sử dụng ngôn ngữ Petri-net 23
2.2.5. Ứng dụng của mạng Petri-net 24
iii
2.3. Ngôn ngữ lập trình Matlab 24
2.4. Ngôn ngữ lập trình Java 25
2.5. Ngôn ngữ lập trình C++ và bộ công cụ Visual Studio.net 26
Chƣơng 3: 28
NGHIÊN CỨU VỀ NGÔN NGỮ GPSS VÀ CÔNG CỤ GPSS WORLD 28
3.1. Tổng quan về GPSS 28
3.2. Thao tác lệnh của GPSS 31
3.3. Các đối tƣợng trong GPSS 32
3.4. Block cơ bản trong GPSS 34
3.4.1. Block làm việc với Transactions 36
3.4.2. Facilities 39
3.4.3. Queue 40
3.4.4. Các Blocks dùng để điều khiển dịch chuyển của Transactions41
3.4.5. Phân phối xác suất nội tại (Built-in Probability Distributions)41
Future Events Chain
GPSS
General Purpose Simulation System
WoPeD
Workflow Petri-net Designer
TAPAAL
Tool for Verification of Timed-Arc Petri-nets vi
DANH MỤC CÁC HÌNH Trang
Hình 1.1: Mô hình cơ bản của hệ thống phục vụ
4
Hình 1.2: Mô tả hệ thống phục vụ đám đông
5
Hình 1.3: Sơ đồ trạng thái của hệ thống phục vụ
12
Hình 2.1: Minh họa cửa sổ làm việc của GPSS World
16
Hình 2.2: Ví dụ về Petri-net
20
Hình 2.3: Minh họa tính tiếp cận của Petri-net
22
Hình 2.4: Minh họa tính bất tử của Petri-net
23
Hình 2.5: Minh họa tính không có đường bao giới hạn của Petri-net
23
Hình 2.6: Minh họa tính bảo thủ của Petri-net
1
MỞ ĐẦU
Những năm gần đây, việc ứng dụng công nghệ thông tin vào các hoạt
động trong đời sống, xã hội là rất cần thiết. Trong thực tế, chúng ta bắt gặp rất
nhiều các hệ thống được thiết lập bởi các yêu cầu (của khách hàng), trong đó
các thời điểm xuất hiện được xem như một đại lượng ngẫu nhiên, còn nhu cầu
được đặc trưng bằng khối lượng các công việc phải làm để phục vụ, thứ tự ưu
tiên trước sau, thời gian hoàn thành công việc và toàn bộ công việc. Đó là
những hệ thống như: Mạng điện thoại, mạng máy tính, hệ thống phục vụ sử
dụng phòng máy thực hành, hệ thống các quầy thu ngân trong siêu thị, hệ
thống bán vé tự động, sân bay, Những hệ thống này được biết đến với tên
gọi hệ thống phục vụ đám đông (hay hệ thống hàng đợi) [1].
Nhìn chung các hệ thống phục vụ đám đông là hệ thống phức tạp, việc
vận hành và tính toán các đặc trưng của hệ thống để tư vấn cho nhà quản lý là
một vấn đề hết sức cần thiết. Trong quá khứ, có rất nhiều dự án xây dựng hệ
thống phục vụ phức tạp dựa trên hàng chờ (Queue) không thành công vì đã
không đặc tả được chính xác bài toán thực tiễn. Việc xây dựng mô hình toán
học cho mỗi hệ thống là rất cần thiết để giảm chi phí tối đa cho các hoạt động
đặc tả nó. Khi đó tính chất đầy đủ của các mô hình mô phỏng cần đạt được
việc mô phỏng quá trình làm việc của mỗi phần tử trong hệ thống với việc
đảm bảo logic, quy tắc của sự tương tác và phát triển của chúng, cả trong
không gian và trong thời gian. Các câu hỏi được đặt ra là: Làm thế nào để mô
phỏng một hệ thống phức tạp dưới dạng đơn giản nhưng chính xác? Phương
pháp nào là khả thi nhất, tối ưu nhất ? Có rất nhiều phương pháp đã được đưa
ra để giải quyết bài toán trên như: Tính toán bằng các công thức toán học, xây
dựng hệ thống phục vụ bằng các ngôn ngữ lập trình (Pascal, C++,…), mô
phỏng bằng các công cụ mô phỏng (Matlab, Petri Network, …). Để xây dựng
phục vụ, sơ đồ trạng thái, quy tắc thiết lập hệ phương trình trạng thái).
3
Chƣơng 2. Một số công cụ mô phỏng các bài toán hàng đợi: Giới
thiệu tổng quan một số công cụ mô phỏng được sử dụng trong thực tế để giải
quyết các bài toán hàng đợi, như: Ngôn ngữ mô phỏng GPSS và công cụ
GPSS World; Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri-net;
Ngôn ngữ lập trình Matlab; Ngôn ngữ lập trình Java; Ngôn ngữ lập trình C++
và bộ công cụ Visual Studio.NET.
Chƣơng 3. Nghiên cứu về ngôn ngữ GPSS và công cụ GPSS World:
Mô tả chi tiết về ngôn ngữ mô phỏng GPSS bao gồm định nghĩa, khái niệm
cũng như cấu trúc thành phần. Nội dung chính của chương đề cập cấu
trúc của một thao tác lệnh, các đối tượng (đối tượng động, đối tượng điều
hành, đối tượng thuộc về thiết bị, đối tượng tĩnh, đối tượng hỗ trợ tính toán,
đối tượng phục vụ lưu trữ, đối tượng nhóm) và các Block cơ bản trong GPSS.
Chương này cũng giới thiệu một trong những công cụ phổ biến hỗ trợ thao tác
với ngôn ngữ công cụ GPSS World.
Chƣơng 4. Sử dụng ngôn ngữ GPSS vào bài toán thực tế: Chương
này tập trung vào việc giới thiệu bài toán phân phối trong sử dụng phòng máy
thực hành . ặc tả quy
trình chung sử dụng GPSS để mô phỏng một hệ thống phục vụ đám đông,
cách tiếp cận giải quyết bài toán thông qua GPSS World.
Kết luận: Tóm lược nội dung chính của và nêu định hướng
phát triển trong thời gian tới.
- Dòng yêu cầu ra: Các yêu cầu được phục vụ
5
Chi tiết về hệ thống phục vụ sẽ được trình bày cụ thể trong phần 1.2.
Trong các hệ thống phục vụ, hàng đợi xuất hiện bất cứ lúc nào khi nhu
cầu hiện tại đối với dịch vụ vượt quá khả năng cung ứng dịch vụ tại thời điểm
đó. Thời gian một yêu cầu đến phải chờ đợi phụ thuộc vào một số yếu tố như:
Số lượng giao dịch trong hệ thống, số kênh giao dịch cung ứng dịch vụ tại
thời điểm đó và thời gian phục vụ cho mỗi yêu cầu đến. Ta có thể sử dụng
một trong hai phương pháp “hộp đen” hoặc phương pháp “hộp trắng” để mô
tả một hệ thống phục vụ đám đông. Trong Luận văn này, chúng ta sẽ mô tả hệ
thống phục vụ đám đông bằng phương pháp “hộp đen” [2]. Hình 1.2: Mô tả hệ thống phục vụ đám đông
Một hệ thống phục vụ đám đông có thể được ký hiệu theo Kendall [2,3]
dưới dạng: A|B|m|n.
Trong đó:
A: Phân phối của thời gian vào.
B: Phân phối thời gian phục vụ.
m: Số máy phục vụ.
n: Số chỗ trong hàng đợi.
A, B có thể nhận một trong các phân phối sau:
λ: Cường độ xuất hiện của sự kiện đầu vào
các hệ thống hàng đợi.
Trong đó:
- H
k
: Phân phối siêu lũy thừa [15] với hàm phân phối:
k
j
x
j
exF
1
j
)1(q
x ≥0 (1.3)
Với:
F(x): Hàm phân bố của phân phối mũ
- D: Phân phối tất định (Deterministic distribution), tức thời gian vào và
thời gian phục vụ là hằng số. Hàm phân phối của phân phối này:
1, nếu x ≥ x
0
F (x) = (1.4)
0, nếu x < x
0- G: Phân phối tổng quát (General distribution)
- GI: Phân phối tổng quát với các thời gian vào hệ thống hoặc thời gian
phân phối Poisson.
dòng vào Poisson được chia làm hai loại:
- 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à:
8
x
tta
tta
e
Dtx ,
!
)(
),(
(1.6)
Trong đó: a(t, Dt) là số trung bình yêu cầu xuất hiện từ t đến Dt.
- 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
t
t
e
Dtx ).(
!
yêu cầu được phục vụ trong kênh phục vụ gọi là “dòng phục vụ”.
Khi dòng yêu cầu được phục vụ trên các kênh phục vụ (dòng phục vụ) là
tối giản thì 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 là
một đại lượng ngẫu nhiên tuân theo luật chỉ số, nghĩa là đại lượng ngẫu nhiên
có phân bố xác suất dạng:
F (t) = 1- e
–μt
(1.10)
Và hàm mật độ xác suất có dạng:
f(t) = μe
–μt
(1.11)
Trong đó:
μ: Là cường độ phục vụ của kênh 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 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.10), (1.11).
1.2.4. Dòng ra
Dòng ra là dòng yêu cầu đi ra khỏi hệ thống, bao gồm các yêu cầu đã
được phục vụ và các yêu cầu chưa được phục vụ.
- Dòng yêu cầu ra đã được phục vụ: Đó là những 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 dịch 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.
kênh được rỗi (không làm việc).
Hệ thống phục vụ đang ở trạng thái nào đó là một quá trình ngẫu nhiên, quá
trình này tuân theo một luật phân phối xác suất nào đó. Nên khả năng xuất hiện
11
một trong các trạng thái x
k
(t) (k = 0,1,2, ) nào đó tại thời điểm t, có xác suất là
một giá trị xác định P
k
(t).
1.3.2. Quá trình thay đổi trạng thái của hệ thống phục vụ
Trong quá trình hoạt động, hệ thống phục vụ
chuyển từ trạng thái này
sang trạng thái khác dưới
tác động của cường độ dòng vào và cường độ dòng
phục vụ
. Xác suất của quá trình đó được gọi là xác suất chuyển trạng thái.
Nguyên nhân gây ra sự chuyển trạng thái là do tác động của
cường độ
dòng
vào và
cường độ
dòng phục vụ, số kênh bận và số yêu cầu trong hệ thống thay
đổi, tức là dưới tác động của
cường độ
dòng phục vụ μ(t) và
cường độ
X
3
10
02
12
21
23
32
31
12
Hình 1.3: Sơ đồ trạng thái của hệ thống phục vụ
1.3.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): P
k
(t), với tác nhân gây ra sự biến đổi trạng thái đó. Mối
quan hệ này được hiển thị bởi phương trình toán học chứa xác suất P
k
(t)
Với điều kiện:
kj
jk
k
k
tt
dt
td
t .'
1tt
kj
k
kj
j
(1.13)
13
Trong (1.12): λ
jk
(t) là cường độ dòng biến cố (dòng yêu cầu hoặc dòng
phục vụ) chuyển trạng thái x
j
(t) về trạng thái x
k
(t). λ
vụ, sơ đồ trạng thái, quy tắc thiết lập hệ phương trình trạng thái).
- Mô tả hệ thống phục vụ: Dòng các yêu cầu vào, hệ thống phục vụ, các
kênh phục vụ, dòng yêu cầu ra.
0
'
k
kj
kjk
kj
jjk
1
kj
k
kj
j
14
- Các yếu tố của hệ thống phục vụ: Dòng vào (dòng vào tiền định, dòng
vào Poisson); hàng chờ (Queue); kênh phục vụ; dòng ra; nguyên tắc phục vụ
của hệ thống dịch vụ.
- Trạng thái hệ thống phục vụ: Đưa ra định nghĩa; quá trình thay đổi
trạng thái của hệ thống phục vụ; sơ đồ trạng thái; qui tắc thiết lập hệ phương
trình trạng thái (nội dung quy tắc, hệ phương trình trạng thái, định lý Mác-cốp).
Chúng được thiết kế sao cho gần gũi với tư duy tự nhiên của con người,
thuận tiện cho việc thao tác, đơn giản cho việc viết câu lệnh khai báo cấu trúc,
tham số liên quan khi lập trình. Đồng thời, chúng tích hợp sẵn bên trong
(dạng Built-in) những hàm chức năng thông dụng liên quan đến bài toán mô
phỏng, nhằm giảm thời gian lập trình cho người sử dụng.
2.1.2. Sự ra đời của ngôn ngữ GPSS
Khoảng thập niên 1960, Geoffrey Gordon ở hãng IBM đã phát triển ngôn
ngữ GPSS - Gordon’s Programmable Simulation System, sau này đổi thành
General Purpose Simulation System [4-8, 13], loại ngôn ngữ mô phỏng các sự
kiện rời rạc. GPSS World là một dạng khác của GPSS dành cho máy tính cá
nhân (GPSS/PC - General Purpose Simulation System/Personal Computer).
Công bố năm 1984, GPSS/PC nhanh chóng đạt được thành công lớn,
cũng như đem lại tiết kiệm hàng triệu đô la cho người dùng. Minh chứng cụ
thể là việc khai thác GPSS World trên nền hệ điều hành Windows đã mở rộng
khả năng của nó trong môi trường liên mạng Internet toàn cầu.
16
Ngôn ngữ mô phỏng GPSS tạo ra các giao dịch (Transaction) và quản lý
chúng theo giai đoạn, hoặc theo các khối (Block). Đây là đặc điểm khác biệt
của ngôn ngữ GPSS. Một Transaction liên quan đến hai khái niệm sau:
- CEC: Current Event Chain - Chuỗi sự kiện hiện tại
- FEC: Future Event Chain - Chuỗi sự kiện tương lai
Mỗi Transaction được quản lý trên một ô nhớ khác nhau, nó có thể được
thực hiện ngay nếu gặp CEC, hoặc chờ thêm các sự kiện FEC thì sẽ thực hiện.
Từ cửa sổ màn hình lập trình GPSS, chúng ta có thể quan sát được vị trí của
các Transaction này thông qua CEC/FEC.
- Là ngôn ngữ hướng đối tượng, chạy được trên nhiều nền tảng hệ điều
hành khác nhau như Windows, Linux.
- Hình ảnh hóa các mô hình, từ đó giúp người dùng hiểu rõ, nắm bắt mô
hình tốt nhất có thể, đồng thời sao lưu lại dưới dạng hình ảnh thống kê dễ
hiểu.
- Khả năng tương tác của nó giúp người dùng dễ dàng tìm hiểu và vận
hành các bài toán mô phỏng nhờ giao diện thân thiện.
- Tích hợp các cở sở phân tích dữ liệu để tính toán các thành phần trong
hệ thống một cách trực quan.
- Là công cụ có thể làm nhiều việc khác nhau tại một thời điểm
(Multitask) và hoạt động trên cơ sở sử dụng bộ nhớ ảo, do đó không tốn kém
tài nguyên của máy tính.
2.1.4. Các ứng dụng của công cụ mô phỏng GPSS World
Các ứng dụng chính của công cụ mô phỏng GPSS World có thể kể đến
như:
Copyright: Tài liệu đại học ©