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

Nguyễn Đức Hoàng Anh

Trường Đại học Công nghệ
Luận văn Thạc sĩ ngành: Kỹ thuật Điện tử; Mã số: 60 52 70
Người hướng dẫn: TS. Lê Quang Minh
Năm bảo vệ: 2012

Abstract: Trình bày 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 pháp toán học thuần túy có thể tìm ra lời giải của
bài toá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.
Nghiên cứu hiện trạng một số công cụ mô phỏng các bài toán hàng đợi: 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 toán hàng đợi.
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 giải bài toán hàng đợi bằng phương pháp mô phỏng. Tìm hiểu về ngôn ngữ
GPSS và công cụ GPSS World: đề 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. 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. Áp dụng ngôn ngữ GPSS vào bài toán thực tế: bài toá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.

Keywords: Kỹ thuật điện tử; Mạng truyền thông; Mô hình hàng đợi; Ngôn ngữ GPSS


Dòng yêu cầu đầu vào, đặc trưng bởi tốc
độ đến (arrival rate) của khách hàng
3
µ
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 chờ, đặ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 chờ
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


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ờ

Chương 1 trình bày về các quá trình Markov, một kiến thức nền quan trọng của bài toán hàng
đợi, và đưa ra 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:
Đặt p
j
(t) = P[X(t) = j]
Tỉ suất để quá trình X(t) sống ở trạng thái i
là

Khi X(t) nhảy từ trạng thái i sang trạng thái
j 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

υ
i

~
ij
q


Hình 1. 2 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 p
j
(0) =0,
p
i
(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.

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 một số ngôn ngữ, công cụ mô phỏng được sử dụng để giải quyết các
bài toá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

4
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.
Đầu tiên, chương 2 đề cập đến ngôn ngữ đặc tả Petri nets, gồm khái niệm, mô tả toán học, các
đặc trưng của chúng.
Petri nets gồm ba thành phần cơ bản: place, transition và directed arc.

Hình 2. 1 Ví dụ về Petri- net
Place
Transition

Directed Arc
Token
Marking
là các vị trí, biểu thị bởi hình tròn, kí hiệu là vị trí P
là trạng thái và sự nhảy trạng thái, biểu thị bởi hình chữ nhật hoặc ô vuông, kí

source code) được chạy tốt để ra kết quả.

5
GPSS có 7 nhóm đối tượng làm việc:
 Đối tượng động: là các transactions, bản chất là nguyên mẫu của “yêu cầu” trong thuật
ngữ của hệ thống phục vụ đám đông.
 Đối tượng điều hành: Đối tượng điều hành (Block Entities) của GPSS còn được gọi là
các khối (Blocks) tương ứng với thực thi lệnh – blocks của chương trình nguồn và cũng
thiết lập logic các hoạt động của mô hình bằng cách đưa ra các chỉ thị đối với các
Transactions: sẽ đi tới đâu và làm gì tiếp theo
 Đối tượng thuộc về thiết bị: Đối tượng thuộc về thiết bị (Facility Entities) tương tự như
các máy phục vụ và các thiết bị khác của hệ thống thực.
 Đối tượng tĩnh: Các đối tượng tĩnh được sử dụng để thu thập và xử lý các dữ liệu thống
kê về hoạt động của mô hình: Queue Entities và Table Entities.
 Đối tượng tính toán: Function và Variable
 Đối tượng lưu trữ: Các đối tượng kiểu này gồm có Savevalue Entities, Matrix Entities.
 Đối tượng nhóm: Các đối tượng thuộc nhóm gồm có Numeric Group Entities –
Chương 3 đề cập sâu vào Transaction với các đặc trưng liên quan đến chuỗi sự kiện và thiết
lập các bước giải bài toán hàng đợi dựa trên công cụ mô phỏng GPSS.
Transaction là các đối tượng động trong GPSS với tập các thuộc tính, các thuộc tính này được
gọi là các Parameters. Chúng được tạo ra trong các thời điểm xác định nào đó của quá trình
mô phỏng, được quản lý và dịch chuyển thông qua các Blocks và cuối cùng là được xóa bỏ.
Một transaction đơn lẻ có thể bao gồm vài thực thể riêng, giống như là nhiều người “được
phục vụ” bởi một thang máy. Transaction có thể xem như là một “yêu cầu”, hay một “sự
kiện” trong hệ thống phục vụ đám đông.
Chương 4. Áp dụng ngôn ngữ GPSS vào bài toán thực tế
Bài toán đá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.
Kết luận
Phần này tóm lược nội dung chính của khóa luận và nêu định hướng phát triển trong thời gian

thông tin – Đại học Quốc Gia Hà Nội, 2010.
Tiếng Anh
[2] Alberto Leon, Garcia; Probability and Random Processes for Electricial
Engineering, 2
nd
Edition, University of Toronto, 1994, Chapter 8, 9.
[3] (đã kiểm tra 1/9/2012)
[4] Alan Pilkington, Royal Holloway; GPSS – Getting Started, University of London,
2005.
[5] Geoffrey Gordon, IBM Corporation; The Development Of The General Purpose
Simulation System (GPSS), ACM, 1978.
[6] M Peter Jurkat; Short Introduction to GPSS.
[7] GPSS/PC general purpose simulation. Reference Manual–Minuteman Software.
P.O. Box 171. Stow, Massachusetts 01775, 1986.
[8] U. Narayan Bhat, An Introduction to Queueing Theory, Southern Methodist
University, USA, 2008.
[9] M. Ajmone Marsan, Stochastic Petri net: An elementary Introduction, Dipartimento
di Scienze dell’s Informazione, Università di Milano, Italy, 2007
[10] Vedran Kordic, Petri nets, Theory and Application, I-Tech Education and
Publishing, Vienna, Austria, 2008.
[11] G. Balbo, J. Desel, K. Jensen, W. Reisig, G. Rozenberg, M. Silva, Petri Nets 2000,
21
th
International Conference on Application and Theory of Petri Nets, Aarhus,
Denmark, June, 26-30, 2000.

7
[12] Mag.DI Dr. Christian Dombacher, Queueing Models for Call Centers, A-2232
Deustch –Wagram, 13.05.2010.
[13] G. Winskel, M. Nielsen. Models for Concurrency, Handbook of Logic and the