ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THU THỦY

NGHIÊN CỨU VÀ ỨNG DỤNG
LÝ THUYẾT HÀNG ĐỢI TRONG BÀI TOÁN
MÔ PHỎNG HOẠT ĐỘNG MỘT SIÊU THỊ

Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ NGÀNH
CÔNG NGHỆ THÔNG TIN

Hà Nội - 2017
1


Nghiên cứu và ứng dụng lý thuyết hàng đợi trong bài toán mô
phỏng hoạt động một siêu thị
Nguyễn Thu Thủy

Trường Đại học Công nghệ
Luận văn Thạc sĩ ngành: Kỹ thuật phần mềm, mã số: 60480103
Người hướng dẫn: TS. Lê Quang Minh
Năm bảo vệ: 2017

Tổng quan: 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

hiệu suất của từng mô hình hàng đợi.
Hàng đợi (hay dòng chờ) là một dòng đợi dịch vụ. Yêu cầu được
phục vụ từ khách hàng sinh ra theo thời gian thông qua 1 nguồn
đầu vào. Khách hàng sẽ phải chờ trong hàng đợi đến lượt được
phục vụ. Khách rời khỏi hệ thống sau khi đã được phục vụ. Các
thành phần cơ bản và đặc điểm của hàng đợi được trình bày trong
hình 1.2.

3


Hình 1. 1- Thành phần cơ bản của hàng đợi
Mô hình hàng đợi trong thực tế rất đa dạng, trong đó cần kể đến
một số mô hình trình bày trong bảng 1.3
Bảng 1. 1-Một số mô hình hàng đợi cơ bản
Tên hàng
đơi

Số
kênh
phục
vụ

Số
bước
phục
vụ

Hệ thống
đơn hàng

đến
dòng
đến
Luật
Luật phân Không
phân
phối mũ
giới
phối mũ
hạn
Possion Luật phân Không
phối mũ
giới
hạn
Possion Luật phân Không
phối mũ
giới
hạn

4

Nguyê
n tắc
phục
vụ
FIFO

FIFO

FIFO

(1.1)
( )=
Và hàm phân phối xác suất có dạng
( )= 1 −
(1.2)
Với λ là cường độ dòng vào, đó là số yêu cầu trung bình xuất hiện
trong một đơn vị thời gian.
Điều kiện 3: Thời gian phục vụ của các kênh cũng là đại lượng
ngẫu nhiên tuân theo qui luật hàm số mũ.
Như vậy, hàm mật độ xác suất có dạng ( ) =
Và hàm
phân phối xác suất có dạng ( ) = 1 −
Với μ là năng suất
phục vụ của các kênh, đó là số yêu cầu được phục vụ tính bình
quân trên một đơn vị thời gian.
Phương pháp giải quyết bài toán bằng lý thuyết có đường lối
chung bao gồm các bước:
5


Bước 1: Phân tích hệ thống mà chủ yếu là phân tích tính chất của
dòng vào và các trạng thái của hệ thống;
Bước 2: Thiết lập hệ phương trình trạng thái để giải ra các xác
suất trạng thái;
Bước 3: Giải hệ phương trình để tìm ra các xác suất trạng thái và
từ đó thiết lập mối quan hệ giữa các chỉ tiêu cần phân tích;
Bước 4: Tính toán, phân tích các chỉ tiêu, trên cơ sở đó đưa ra
nhận xét và kết luận.
Chương 2: Công cụ mô phỏng GPSS World
Chương 2 tập trung trình bày về các công cụ mô phỏng hệ thống

- Khối các lệnh liên quan đến các thực thể thiết bị (Facility)
- Khối các lệnh liên quan đến dữ liệu tĩnh
- Khối các lệnh để điều khiển đường đi của các giao tác trong
mô hình mô phỏng
Qua quá trình nghiên cứu, luận văn đề xuất một quy trình ứng
dụng GPSS chung để mô phỏng một hệ thống hàng đợi như sau:
Thu thập dữ liệu:
Bước 1: Khảo sát và nghiên cứu hệ thống. Bước này cần xác định
được các thông số của hệ thống như: số nguồn các yêu cầu; có thứ
tự ưu tiên giữa các nguồn hay không; Cần quan sát hệ thống thật
trong những điều kiện hoạt động khác nhau; quan sát hành vi của
khách hàng trong hàng đợi, thời gian chờ đợi;
Bước 2: Quan sát thời gian phục vụ của hệ thống. Thu thập thông
tin về dịch vụ cũng là một yêu cầu cần thiết, tất cả quá trình sử
7


dụng dịch vụ, bao gồm cả thời gian dịch vụ rảnh rỗi cũng cần
được thu thập.
Phân tích dữ liệu thống kê:
Bước 3: Dữ liệu thô thu thập được từ 2 bước trước phải phân tích
để lấy được thông tin thống kê, xác định hàm phân phối xác suất.
Xác định luật phân bố đầu vào (input) của các kênh phục vụ. Mỗi
nguồn sinh các yêu cầu theo quy luật phân phối ngẫu nhiên nào.
Xác định các biến số thời gian gắn liền với đầu vào của các sự
kiện. Từ đó lựa chọn hàm phân bố tương ứng trong GPSS.
Bước 4: từ các hàm phân phối thu được ở bước 3, xác định các
Operation, phân phối tương ứng, xác định các tham số (min –
max, mean) và khoảng thời gian trung bình tương ứng.
Bước 5: Mã hóa chương trình mô phỏng.

80 chỗ đỗ xe ô tô được chia thành từng ô riêng biệt. Kết quả khảo
sát tại bộ phận an ninh thu được một số thông tin sau:
-

Khách hàng đến nếu không còn chỗ trống đậu xe thì sẽ rời
khỏi siêu thị ngay. Vào ngày cuối tuần, trung bình có 30 ±
5 giây thì có một xe vào bãi đậu xe.

-

Thời gian xe ô tô đậu ở bãi đậu xe được tính là thời gian
khách hàng vào chọn lựa mua hàng, thanh toán và di
chuyển trở lại xe. thời gian từ khi khách hàng rời xe đến
khi quay trở lại trung bình là là 60 phút.

Mục tiêu là mô phỏng: mô phỏng lại hoạt động của bãi đỗ xe
trong thời gian 1 ca làm việc của siêu thị (8 tiếng) nhằm so sánh
kết quả mô phỏng với kết quả tính toán bằng lý thuyết hàng đợi.
Giải quyết bài toán:
Từ những giả thiết có được, sau khi áp dụng lý thuyết để giải ta
xây dựng được được mô hình mô phỏng theo các bước trong sơ
đồ trình bày trong hình 3.2

10


Hình 3. 1- Mô hình thuật toán giải bài toán bãi đậu xe

11


trong
GPSS

Độ lệch

Số xe ô tô đến siêu thị

960

964

0.42%

Số xe có chỗ đậu

640

714

11.56%

Số xe không có chỗ đậu
(phải rời đi ngay)

320

250

21.88%


càng tiệm cận sát với kết quả của mô hình lý thuyết.

13


Bảng 3. 2. Kết quả mô phỏng với thời gian khác nhau
8 giờ

16 giờ

24 giờ

40 giờ

Lý
thuyết

GPS
S

Lý
thuyết

GPSS

Lý
thuyết

GPSS


1280

1320

1920

1941

3200

3236

Số xe ô tô không được phục
vụ tại bãi đỗ xe

320

250

640

1240

960

1861

1600

3156



khỏi siêu thị.

16


Mô tả hoạt động hệ thống được trình bày trong hình 3.5

Hình 3. 2- Mô tả mô hình hoạt động của siêu thị

17


Từ Mô hình thuật toán trên ta xác định được các thực thể sử dụng
trong mô phỏng sau:
TT

Loại thực thể

1.

2.

3.
4.

Số
lượng


bảng lưu thời gian
hệ thống

Sau khi xác định được các thực thể cần dùng cho mô hình, tiến
hàng mã hóa chương trình mô phỏng với một số nhãn và khối
lệnh sau:
Block 1: khối lệnh khai báo các đối tượng, các biến lưu
trữ;
Block 9 Sinh sự kiện phát sinh khách hàng theo phân
phối xác suất
Block 10 mô tả toàn bộ thời gian mua hàng để kiểm soát
trong suốt thời gian hệ thống thực hiện mô phỏng.
Nhãn PARKING: Gồm khối lệnh 2 (Block 2) và khối
18


lệnh 3 Mô tả hoạt động của khách hàng vào bãi đỗ xe, thiết lập
các giá trị tham biến cho khách hàng được phục vụ (khách hàng
đã được dịch vụ gửi xe phục vụ).
Nhãn QTELEJKA: gán lại giá trị cho hàng đợi xe đẩy khi
xe đẩy được chọn;
Nhãn MIN_OCH: mô phỏng quá trình mua hàng của
khách, thiết lập các giá trị lượng hàng mua theo tỷ lệ đầu bài đặt
ra; Block 6 đưa ra các số liệu thống kê đối với quầy thu ngân số 1
(quầy thu ngân cho các khách hàng mua nhanh);
Nhãn FIN: đưa ra số liệu thống kê đối với các quầy thu
ngân khác; sẽ tính toán và đưa ra các số liệu dạng bảng về thời
gian làm việc của hệ thống và số lượng hàng hóa được mua, giải
phóng đối tượng mua hàng sau 1 phiên mua hàng; mô tả các
luồng khách hàng rời khỏi dịch vụ thanh toán;

Số khách hàng đã vào siêu thị nhưng

1

chưa mua hàng
Số yêu cầu và hiệu suất sử dụng giỏ

45

0.018

667

0.938

hàng được phục vụ
Số yêu cầu và hiệu suất sử dụng xe
đẩy hàng được phục vụ
Số khách hàng thực hiện mua hàng

666

Số yêu cầu thanh toán được phục vụ

604

Lượng khách mua dưới 10 món hàng

46


thanh toán tại quầy 5

Tương tự cách tiến hành với mô hình bài toán bãi gửi xe, thực
hiện thay đổi thời gian mô phỏng bằng cách cài đặt lại biến thời
20


gian time_work trong Block 1 lần lượt bằng các giá trị:
16*60*60, 24*60*60, 40*60*60, 80*60*60 sau đó chạy mô
phỏng cho từng trường hợp thời gian. Đem so sánh kết quả từng
trường hợp với lý thuyết
Xét giá trị số xe được phục vụ tại bãi gửi xe, ta có bảng so sánh
kết quả 3.5.
Bảng 3. 4- So sánh lượng xe được phục vụ trong bài toán hệ
thống siêu thị
Thời gian

Lý thuyết

GPSS

% sai lệch

8 giờ

823

714

13%


2%

Kết quả của bài toán mô phỏng 2 cũng phù hợp với kết quả và
nhận xét đã trình bày trong phần kết luận của bài toán đầu tiên
(mục 3.2.3.3). Giữa tính toán lý thuyết và mô phỏng vẫn có sự sai
lệch; tuy nhiên, độ sai khác này sẽ giảm khi khi thời gian mô
phỏng lớn hơn; hay độ lấy mẫu càng lớn hơn thì độ lệch giữa kết
quả tính toán lý thuyết và kết quả mô phỏng theo GPSS càng
giảm. Trong một số bài toán phức tạp việc sử dụng công cụ tính
toán toán học thông thường theo lý thuyết hàng đợi là rất khó
khăn, trong những trường hợp như vậy chỉ có thể sử dụng mô
phỏng để tính toán. Việc mô phỏng hệ thống phục vụ đám đông
bằng GPSS World là một giải pháp hiệu quả.
21


KẾT LUẬN
Ý nghĩa thực tiễn mà đề tài muốn hướng tới là làm chủ được
phương pháp đánh giá hiệu suất, đo lường các giá trị liên quan
của một hệ thống phục vụ đám đông; nhằm xây dựng các ứng
dụng cải tiến dịch vụ, giảm thiểu lãng phí sinh ra bởi các dòng
chờ trong tương lai như: ứng dụng hàng đợi tiện ích trên thiết bị
di động. Luận văn tiếp cận bài toán hệ thống phục vụ đám đông
theo hướng giải tích và mô phỏng. Phương pháp giải tích là sử
dụng lý thuyết hàng đợi để phân tích bài toán. Sử dụng công cụ
mô phỏng chuyên dụng để mô hình hóa bài toán nhằm tăng hiệu
quả tính toán và giải quyết các bài toán phức tạp.
Từ hai phương pháp tiếp cận bài toán nêu trên, thông qua
thực nghiệm với bài toán thực tế, mô hình bài toán có được nhờ

liệu đối với bài toán siêu thị, nhưng chưa áp dụng triệt để phương
pháp đó để bài toán mô phỏng có tính chính xác cao hơn.
Từ những kiến thức bổ ích đã thu thập được trong quá
trình thực hiện luận văn; trong tương lai, hướng áp dụng tiếp theo
để phát triển luận văn này là: xây dựng ứng dụng nhằm cải tiến
hàng đợi truyền thống bằng mô hình hàng đợi tiện lợi trên các
thiết bị di động.
TÀI LIỆU THAM KHẢO
Tiếng Việt:
[1]
Lê Quang Minh, Phan Đăng Khoa, “Công cụ GPSS cho
bài toán mô phỏng các hệ thống phục vụ đám đông,” Báo cáo
tổng hợp đề tài cấp ĐHQGHN, Viện Công nghệ thông tin – Đại
học Quốc Gia Hà Nội, 2010.
[2] Lê Quang Minh, Phan Đăng Khoa, Nguyễn Thế Tùng,
Nghiêm Thị Hoa (2015), “Nghiên cứu mô phỏng các hệ thống
hàng đợi” – Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên
cứu cơ bản và ứng dụng Công Nghệ thông tin (FAIR), Hà Nội
2015;
Tiếng Anh:
23


[3]
Ivo Adan and Jacques Resing, “Department of
Mathematics and Computing Science” Eindhoven University of
Technology P.O. Box 513, 5600 MB Eindhoven, The Netherlands
[4]
Azmat Nafees and Liwen Liang, A ‘C level’ essay in
Statistics submitted in partial fulfillment of the requirements for