ĐẠ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Ỹ

Ngƣời hƣớng dẫn khoa học:



5
5
7
7
8
8

1.3 Trạng thái của hệ thống phục vụ
1.3.1 Quá trình Markov
1.3.2 Định nghĩa về trạng thái của hệ thống phục vụ
1.3.3 Quá trình thay đổi trạng thái của hệ thống phục vụ

9
9
10
11

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

13

Kết luận

14

Chương 2: Hiện trạng một số cơng cụ mơ phỏng các bài tố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ả tốn học về Petri net

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 cụ Visual Studio.NET

25
25

2.4 So sánh giữa P/T net và GPSS

26

Kết luận

27

Chương 3: Tìm hiểu về ngơn ngữ GPSS và công cụ mô phỏng GPSS World ___28
3.1 Cấu trúc lệnh của GPSS khi lập trình

28

3.2 Các đối tượng trong GPSS

29

3.3 Các block cơ bản trong GPSS
3.3.1 Transactions
3.3.2 Bộ lập lịch cho Transaction
3.3.3 Các block làm việc với Transactions
3.3.4 Facilities

41
42
43

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 tốn
4.2.2 Lưu đồ giải thuật

45
45
46

4.2.3 Chương trình và kết quả mô phỏng

46

Kết luận

48

Kết luận chung ______________________________________________________48
TÀI LIỆU THAM KHẢO _____________________________________________49


v

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

Tiếng Anh

P/T net

Place/ Transition Network

Một loại ngôn ngữ mô tả toán học,
dựa trên lý thuyết về tập hợp


vi

Danh sách các hình vẽ
Hình 1. 1 Ví dụ về hệ thống hàng đợi. .......................................................................... 1
Hình 1. 2 Mơ hình hóa các yếu tố của một hệ thống hàng đợi ...................................... 2
Hình 1. 3 Mơ tả sự chuyển trạng thái của chuỗi Markov ............................................ 12
Hình 1. 4: Sơ đồ trạng thái của hệ thống phục vụ ...................................................... 13
Hình 1. 5: Minh họa hoạt động của hệ M/M/1 ........................................................... 13
Hình 2. 1 Ví dụ về Petri- net.
Hình 2. 2 Minh họa tính tiếp cận của P/T net
Hình 2. 3 Minh họa tính bất tử của P/T net
Hình 2. 4 Minh họa tính khơng có đường bao giới hạn của P/T net
Hình 2. 5 Minh họa tính bảo thủ của P/T net
Hình 2. 6 Minh họa cửa sổ làm việc của GPSS World
Hình 2. 7 Minh họa cơng cụ Netlab tích hợp trên nền tảng Matlab
Hình 2. 8 Minh họa Applet: The Petri – Net – Simulator chạy trên nền Java
Hình 2. 9 Minh họa công cụ YASPER phát triển trên công nghệ .NET

16
18
19
19


Danh sách các bảng biểu
Bảng 1: Các yếu tố cấu thành một hệ thống phục vụ đám đông ................................... 1
Bảng 2: Các tham số đặc trưng trong hệ thống hàng đợi ............................................. 2
Bảng 3: Các yếu tố theo quy tắc Kendall khi mô tả về hàng đợi ................................... 4
Bảng 4: Các phân phối xác suất liên quan đến A và B trong mô tả Kendall ................. 5
Bảng 5: Một số phương pháp phục vụ áp dụng trong lý thuyết hàng đợi ...................... 8
Bảng 6: So sánh giữa P/T net và GPSS ...................................................................... 26
Bảng 7: Các tham số của lệnh GENERATE ............................................................... 34
Bảng 8: Báo cáo thông kê kết quả hoạt động của phịng xử lý thơng tin ..................... 43


1

Mở đầu
Ngày nay, khoa học và công nghệ được ứng dụng vào các hoạt động trong đời sống,
xã hội rất nhiều. Trong đó, chúng ta gặp nhiều hệ thống được xây dựng lên dựa vào các yêu
cầu đầu vào. Cụ thể: thông tin đầu vào là các thời điểm xuất hiện, chúng được coi như một đại
lượng ngẫu nhiên. Các yêu cầu được đặc tả bởi khối lượng các công việc cần phải làm để đáp
ứng cho thông tin đầu vào, thứ tự ưu tiên các cơng việc đó (trước, sau), thời gian hồn thành
một phần cơng việc và tồ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, bãi đậu xe, phi trường... Các hệ thống này được gọi là hệ thống phục vụ đám đông
(hay hệ thống hàng đợi) [1,2,12].
Trên thực tế, các hệ phục vụ đám đơng có đặc thù phức tạp, và việc tư vấn cho các nhà
quản lý, nhà hoạch định chính sách về các hệ này là hết sức cần thiết sao cho khi hệ thống
được đưa vào sử dụng phải đạt hiệu suất cao nhất có thể. Nên chúng ta phải tính tốn, thiết lập
thật rõ ràng, kỹ lưỡng các đặc tả về chúng sát với thực tiễn nhất trong điều kiện cho phép.
Chúng ta cần xây dựng mơ hình tốn học cho từng hệ thống; mơ tả quá trình làm việc
của các thành phần trong hệ thống; sự tương tác qua lại giữa chúng theo thời gian, và trong
khơng gian để giảm chi phí tối đa cho các hoạt động đặc tả hệ thống. Vấn đề ở đây là: Cần có

pháp tốn học thuần túy mà chúng ta có thể tìm ra lời giải của bài tốn hàng đợi khi dựa vào
hệ phương trình trạng thái với các điều kiện ban đầu.
Chương 2: Hiện trạng một số cơng cụ mơ phỏng các bài tốn hàng đợi: Chương này

giới thiệu một số ngôn ngữ, công cụ mô phỏng được sử dụng để giải quyết các bài tốn
hàng đợi. Chúng ta sẽ tìm hiểu qua về ngơn ngữ đặc tả P/T net, và ngôn ngữ General
Purpose Simulation System – GPSS, tiến hành so sánh, đánh giá hai ngơn ngữ đó. GPSS có
ưu điểm hơn P/T net khi chúng ta giải bài toán hàng đợi bằng phương pháp mơ phỏng.
Chương 3 Tìm hiểu về ngơn ngữ GPSS và công cụ GPSS World: Chương này đề cập cụ thể,
chi tiết về cấu trúc của một thao tác lệnh, các đối tượng và các khối (block) cơ bản trong
GPSS. Đồng thời, chương 3 trình bày các bước tiến hành mơ phỏng một bài toán hàng đợi khi
sử dụng phương pháp mô phỏng qua công cụ GPSS World.
Chương 4. Áp dụng ngơn ngữ GPSS vào bài tốn thực tế: Bài tốn đánh giá hoạt động của
Tổng đài điện thoại, và đánh giá hoạt động của một phịng xử lý thơng tin tại nơi làm việc.
Qua đó, chúng ta thấy được một phần nào đó hiệu quả hoạt động của hai đối tượng mà chúng
ta khảo sát.
Phần kết luận tóm lược nội dung chính của luận văn và nêu định hướng phát triển trong thời
gian tới.


1

Chương 1: Cơ sở lý thuyết về hệ thống hàng đợi
Chương này tập trung vào tìm hiểu cơ sở lý thuyết về hệ thống hàng đợi: các đặc
điểm của hệ thống, các yếu tố của hệ thống gồm có 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… và tìm hiểu về
quá trình Markov và trạng thái của hệ thống phục vụ…
1.1 Mô tả về 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, 12, 18] (hay còn gọi là
hệ thống phục vụ đám đơng) như hình vẽ 1.1:



2

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 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

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 một dịch
vụ nào đó tại một thời điểm nào đó, hàng đợi sẽ xuất hiện.
Sự chờ đợi (nhanh hay chậm để được đáp ứng yêu cầu) phụ thuộc mạnh vào số
lượng kênh phục vụ của hệ thống, cũng như quy tắc phục vụ của hệ thống.
1.1.1 Mơ hình hóa một hệ thống hàng đợi
Chúng ta có thể mơ hình đơn giản cho một hệ thống hàng đợi trong hình 1.2 :

Hình 1. 2 Mơ hình hóa các yếu tố của một hệ thống hàng đợi
Các thông số mô tả liên quan đến hệ thống hàng đợi gồm có:


Nq(t)

Hàng chờ, đặc trưng bởi số lượng khe để phục vụ cho xếp hàng

5

Wi

6

Ns(t)

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


1.1.3 Công thức Little
Thời gian phục vụ là một đại lượng ngẫu nhiên, chúng ta khó có thể đo
được. Tuy nhiên, nhìn tổng thể, thời gian phục vụ trung bình là một yếu tố rất quan
trọng, đem lại nhiều ý nghĩa để đánh giá hiệu suất hoạt động của hệ thống hàng đợi.


4

Công thức Litte phát biểu rằng:
Hệ thống hàng đợi đạt được trạng thái dừng khi mà
Trung bình các khách hàng trong hệ thống bằng Tốc độ đến trung bình
nhân với Thời gian phục vụ trung bình trong hệ thống hàng đợi đó.

E[N(t)] = λtb E[T]

(1.4)

Khi đó, chúng ta suy ra các hệ quả sau:
E[Nq(t)] = λtb E[W]

(1.5)

Trung bình khách hàng chờ đợi và Thời gian chờ đợi trung bình
1- p0 = E[Ns(t)] = λtb E[τ]

(1.6)

( đây là xác suất trạng thái dừng của hệ thống khi có khách hàng)
Trung bình khách hàng đang được phục vụ tại thời điểm t
và tồn bộ thời gian phục vụ trung bình trên các máy phục vụ


Phân phối xác suất của thời gian phục vụ.

3

m

Số lượng máy phục vụ.

4

K

Dung lượng của hệ thống, là số khách hàng lớn nhất có mặt mà hệ thống
phục vụ được, có tính đến cả khách hàng đang chờ


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] liên quan đến yếu tố A và B trong bảng 4:

STT

1

Bảng 4: Các phân phối xác suất liên quan đến A và B trong mô tả Kendall
Viết
Phân phối

F x

1

e

j 0

x

( x) j
, λ là hệ
j!

(1.10)

số kỳ vọng, k là pha, x ≥ 0,
3

Hk

Phân phối siêu lũy thừa,
k

qj /

E[X]

i



a là một thời điểm nào đó cố định
5

G

Phân phối tổng quát

6

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ục vụ
độc lập nhau.

Đặc trưng bởi chuỗi Markov hoặc quá
trình Possion, sẽ trình bày kỹ hơn về
chuỗi này sau

7

PH

Phân phối pha

Đặc trưng bởi chuỗi Markov, sẽ trình
bày kỹ hơn về chuỗi này sau


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à q 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]

( t )k
e
k!

t

(1.14)

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à:
(1.15)
e a (t , t )
x
x( Dt )
a t, t
!

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



(1.17)
(1.18)

1.2.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.2.3 Kênh phục vụ
Thực tế, chúng ta thấy ngay một vài ví dụ về một số dạng kênh phục vụ như: đường
băng sân bay, kênh đường điện thoại, quầy bán vé…
Kênh phục vụ bao gồm con người cùng với các thiết bị kĩ thuật hoạt động tại một vị trí
nào đó trên bề mặt quả đất hoặc trong khơng gian. Tùy thuộc vào quy mơ, tính chất, mục tiêu
hoạt động của hệ thống mà những nhà hoạch định, nhà quản lý sẽ thiết lập nhân lực, vật lực,
phương tiện, trang thiết bị cho hệ thống đó.
Đặc điểm quan trọng nhất của kênh phục vụ là thời gian phục vụ τi (xem bảng 1.2).
Đó là thời gian mỗi kênh phải tiêu phí để phục vụ một yêu cầu. Nói dễ hiểu là “Anh tốn bao
nhiêu thời gian để phục vụ xong một khách hàng”.
Thời gian phục vụ cũng là một đại lượng ngẫu nhiên tuân theo một quy luật xác suất
nào đó bởi nó phụ thuộc rất mạnh vào thời gian đến của các yêu cầu. Các dòng 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 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 và hàm mật độ xác suất giống hệt như dòng vào Possion dừng ở phần trên

F t

f t


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 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, ngồ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 u cầu đầu vào. Nó chỉ ra:
Khi nào thì 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 u cầu đó vào các kênh phục vụ
Khi nào thì yêu cầu bị từ chối hoặc phải chờ đợi trong hàng đợi
Cách bố trí hàng đợi tùy theo các loại yêu cầu
Một số phương pháp phục vụ

Bảng 5: Một số phương pháp phục vụ áp dụng trong lý thuyết hàng đợi
STT

Tên viết tắt – tên tiếng Anh của
phương pháp phục vụ

Giải thích

1



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

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 q trình chỉ phụ thuộc vào hiện tại, không phụ thuộc vào quá khứ.


là “Hiện tại” của quá trình

tk
tk+1

là “Tương lai” của quá trình

t1, t2 ,…, tk-1

là “Quá khứ” của q trình

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

P[ N (t )

k]

( t )k
e
k!

(1.24)
t


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[X1 = i1 / X0 = i0] * P[X0 = i0]

(1.26)

Ta thấy ngay rằng Xn được xác định thông qua giá trị pj(0) = P[X0 = j]
và ma trận xác suất chuyển một bước có tổng các số hạng trong một hàng có giá trị
bằng 1:
p00

p01

p02

p03 …

p10

p11

p12

p13 …

pi1

pi1

pi2


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)
- Sự thay đổi dòng phục vụ trong các kênh phục vụ
- Số kênh trong hệ thống phục vụ đang bận và đang hoạt động
- Bản thân hệ thống phục vụ có sự điều chỉnh sao cho phù hợp với các yêu cầu đầu
vào, các yêu cầu phục vụ…
Chúng ta quan tâm tới yếu tố gọi là xác suất chuyển trạng thái, tức là khả năng để
hệ thống nhảy từ trạng thái i sang trạng thái j.
Thời gian sống của một trạng thái là một biến ngẫu nhiên X(t) tuân theo quy luật
phân phối mũ.
Chúng ta giả sử trạng thái a của hệ thống tồn tại trong khoảng thời gian Ta. Khi đó,
xác suất để hệ thống ở trạng thái a trong khoảng thời gian lớn hơn t giây là
P[Ta > t]
Nếu chúng ta cho rằng hệ thống ở trạng thái a trong khoảng thời gian t giây, và nó
vẫn ở trạng thái a đó thêm s giây nữa (hệ thống ở trạng thái a trong t + s giây). Khi đó:
P[Ta > t+s / Ta >s] = P[Ta > t+s / X(s’)= a, 0 ≤ s’≤ s]
(1.28)
Theo định nghĩa về chuỗi Markov (các quá trình Markov nhận giá trị nguyên),
chúng ta thấy rằng phần quá khứ sẽ không liên quan đến chuỗi Markov, do đó:
P[Ta > t+s / Ta >s] = P[Ta > t] = e – v * t
Với v = νa, kỳ vọng của X(t) là E[X(t)] = 1/ νa

(1.29)

Công thức Chapman – Kolmogorov liên quan đến xác suất trạng thái của hệ thống
và tốc độ dịch chuyển từ trạng thái i sang trạng thái j nào đó cho một chuỗi Markov với
thời gian liên tục, được mô tả như sau:


i

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.
λ01

λ12

X1

X0

λ10

λ21

λ02

λ32
λ31

X3



i j

(1.31)

pj

p j đây là phương trình cân bằng tồn cục.

i

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
Hệ M/M/1 [2,19, ] với sơ đồ chuyển trạng thái minh họa như hình 1.5:

λ

λ
1

0

J+1

j

μ

μ

μ


(
1!

)2
2!

(1.32)

...

o( )

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


14

P[ A( )
-

P[

(1.33)

2] o( )

Xác suất để khách hàng được phục vụ hoàn toàn trong hệ M/M/1 trong
khoảng thời gian δ là:
(1.34)


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

E[ ]
1

E[W ] E[T ] E[ ]

-

1

Tổng số khách hàng bị trì hỗn lại trong M/M/1 (theo (1.7)và (1.35)):
(1.37)
E[ N (t )]
/
1/
E[ ]
1

1
-

(1.36)

E[ ]

1

E[ ]



15

Bài toán hàng đợi liên quan mật thiết đến lý thuyết về các q trình Markov, đó
là những q trình ngẫu nhiên mà kết quả của chúng chỉ phụ thuộc vào hiện tại, không
phụ thuộc vào quá khứ. Hơn nữa, chúng ta xét đến hệ phương trình vi phân Chapman
– Kolmogorov từ đó, chúng ta biết được trạng thái hoạt động của hệ thống hàng đợi.
Tuy nhiên, để giải được các mơ hình, phương trình tốn học là điều khó khăn
trong hệ thống hàng đợi. Với sự phát triển của khoa học máy tính như ngày nay, với
ưu thế của sự tích hợp các phân phối xác suất tốn học vào trong các phần mềm mô
phỏng và việc xây dựng, thiết lập các mơ hình, việc tìm ra các giải thuật, chúng ta giải
quyết bài toán hàng đợi phức tạp này thông qua phương pháp mô phỏng trên phần
mềm. Điều đó khắc phục rất tốt những hạn chế của phương pháp toán học thuần túy
khi giải quyết bài toán hàng đợi.


16

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
Chương này 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.
2.1 Các công cụ mô phỏng sử dụng ngôn ngữ đặc tả Petri- net
[9-11,13,15] , (còn gọi là Place/Transition net, hoặ
ữ
ả
ọc về các hệ thống song song và các hệ thống
phân tán. Petri nets đượ
ủa việc
phát minh ra Petri nets là để

Sự phân bố các Token trên các Place