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


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


1.5 Cách tiếp cận mô phỏng.....................................................................................26
1.6 Hiện trạng một số công cụ mô phỏng chuyên dụng...........................................26
1.7 Giới thiệu về GPSS World....................................................................................27
1.8 Hàng đợi có ưu tiên Priority Queueing...............................................................43
1.9 Các bước mô phỏng bài toán trên GPSS World..................................................44
CHƯƠNG 3. ỨNG DỤNG LÝ THUYẾT HÀNG ĐỢI VÀ CÔNG CỤ MÔ PHỎNG
VÀO BÀI TOÁN HÀNG ĐỢI SIÊU THỊ...................................................................48
1.10 Một số quan sát về hàng đợi siêu thị................................................................48
1.11 Bài toán xếp hàng gồm 1 phase phục vụ...........................................................49
1.12 Bài toán xếp hàng nhiều phase phục vụ...........................................................56
KẾT LUẬN.................................................................................................................69


DANH MỤC HÌNH VẼ


DANH MỤC CÁC BẢNG


LỜI MỞ ĐẦU
Hàng đợi ảnh hưởng đến nhiều mặt trong cuộc sống thực tế cũng như lĩnh vực kỹ
thuật. Trong hoạt động xã hội, hàng đợi là điều không mong muốn của các hệ thống
phục vụ đám đông, từ thực tế đó các nhà quản lý luôn mong muốn đánh giá được hiệu
quả hệ thống dịch vụ của họ để cải tiến chất lượng phục vụ, giảm chi phí vô ích.
Trong các hoạt động sản xuất kinh doanh cũng như đời sống hàng ngày đều tồn tại
những hệ thống phục vụ như: Bến cảng, khách sạn, nhà hàng, trạm điện thoại, cửa
hàng bán xăng dầu... Trong các hệ thống ấy thường diễn ra 2 quá trình: Quá trình nảy
sinh các yêu cầu và quá trình phục vụ các yêu cầu. Tuy nhiên, trong quá trình hoạt
động của hệ thống do nhiều nguyên nhân khác nhau thường dẫn đến các tình trạng:
-

GPSS, NS2,…). Công cụ mô phỏng cần sinh ngẫu nhiên sự kiện và quản lý vòng đời
của sự kiện theo thời gian và mô phỏng vận hành của của hệ thống, vì vậy sử dụng
công cụ lập trình để triển khai thuật toán tốn khá nhiều thời gian. Công cụ mô phỏng
sự kiện rời rạc của IBM phát triển vào khoảng thập niên 1960 - General Purpose
Simulation System (viết tắt là GPSS) là công cụ được lựa chọn để giới thiệu và sử
dụng trong luận văn này.
Vấn đề nghiên cứu và ứng dụng ngôn ngữ mô phỏng GPSS tại Liên bang Nga,
cũng như một số quốc gia phát triển khác không còn xa lạ [1]. Ở Việt Nam, việc ứng
dụng GPSS cũng đã được đề cập tới ở một số công trình, luận văn khoa học; tuy nhiên
việc áp dụng GPSS để mô phỏng chưa áp dụng theo một phương pháp có tính tổng
quát. Trên cơ sở các nghiên cứu về phương pháp giải bài toán hệ thống phục vụ đám
đông, luận văn đã tập trung vào các mục tiêu sau:
Luận văn tập trung nghiên cứu về một số kiến thức cơ bản trong “ Lý thuyết hàng
đợi”, các mô hình hàng đợi, công cụ mô phỏng hàng đợi là GPSS. Đề xuất quy trình
xây dựng mô phỏng bằng GPSS và vận dụng để giải quyết bài toán xếp hàng tại siêu
thị có thành phần ưu tiên và không ưu tiên.
Luận văn được trình bày trong ba chương với nội dung chính của mỗi chương như sau
Chương 1: Lý thuyết hàng đợi.
Luận văn tập trung trình bày về lý thuyết hàng đợi, các mô hình hàng đợi có thể sẽ liên
quan đến bài toán hoạt động của một siêu thị.
Chương 2: Công cụ mô phỏng GPSS
Luận văn tập trung trình bày về các công cụ mô phỏng GPSS các cách tiếp cận mô
phỏng. Quy trình mô phỏng bài toán thực tế bằng GPSS
Chương 3: Ứng dụng lý thuyết hàng đợi và công cụ mô phỏng vào bài toán hàng
đợi siêu thị.
Trình bày bài toán mô phỏng hoạt động của siêu thị cụ thể; bằng phương pháp phân
tích sử dụng lý thuyết hàng đợi. Áp dụng công cụ mô phỏng GPSS World và áp dụng
quy trình mô phỏng hệ thống hàng đợi để giải quyết bài toán. Từ kết quả thu được đưa
ra so sánh và đánh giá hiệu quả của mô phỏng.
Kết luận

Viết tắt

Tên

1

M

Phân phối
mũ

2

Ek

Phân phối
Erlang

Hàm phân phối

k

3

Hk

Phân phối
siêu bội

f (t ) = ∑q j (1 −e


1.1.2.1
Phân phối hình học (Geometric distribution)
Là phân phối đặc trưng cho số các biến cố sảy ra trong một khoảng thời gian cho
trước. Một biến ngẫu nhiên hình học [2 tr.18] với phân phối xác suất:

Với phân phối này chúng ta có một số công thức sau

1.1.2.2
Phân phối Poisson (Poisson distribution)
Là phân phối thường gặp nhất trong các mô hình hàng đợi phân phối Poisson [6
tr.6-7] được đặc trưng cho những quá trình đến và phục vụ hoàn toàn ngẫu nhiên, độc
lập. Một biến phân phối Poisson

với tham số

,

có phân phối

n=0, 1, 2,…

Trong đó:
-

là xác suất để trong khoảng thời gian τ có n yêu cầu xuất hiện;
n là số yêu cầu xuất hiện trong khoảng thời gian quan sát τ;
là số yêu cầu trung bình xuất hiện trong từng khoảng thời gian quan sát τ.

Phân phối Poisson ta có:


t>0.

Có hàm phân phối xác suất:

Với hàm phân phối này ta có một số công thức tính kỳ vọng và phương sai như
sau:

1.1.2.4
Một biến

Phân phối Erlang (Erlang distribution)
có một phân phối Erlang-k [9 tr.5] (k=1,2,…) với

của E biến độc lập
hoặc ngắn gọn là

có phân phối mũ chung
.

Hàm phân phối xác suất bằng:

nếu X là tổng

. Ký hiệu chung là


Tham số

được gọi là tham số quy mô (scale parameter),

. Hàm mật độ cho bởi:

hàm này luôn lớn hơn 1 hoặc bằng 1

1.1.3 Khái niệm hàng đợi và lý thuyết hàng đợi
Hàng đợi (hay dòng chờ) [11] 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ụ.
Đầu những năm 1900, A. K. Erlang, kỹ sư điện thoại Đan Mạch bắt đầu nghiên
cứu sự tắc nghẽn và thời gian chờ trong những cuộc gọi điện thoại. Từ đó, lý thuyết


hàng đợi đã phát triển và được sử dụng rộng rãi cho nhiều tình huống. Mô hình hàng
đợi gồm những biểu thức và những mối liên hệ được dùng để xác định những chỉ tiêu
phản ảnh đặc trưng của các hệ thống.

Hình 1. 2- Thành phần cơ bản của hàng đợi

Các thành phần cơ bản của hàng đợi [6 tr.6-7] bao gồm:
Tiến trình đến
Dòng yêu cầu đến hệ thống là dòng các đối tượng đi đến hệ thống và đòi hỏi
được thoả mãn yêu cầu phục vụ. Ví dụ: Dòng khách tới trung tâm bưu điện, dòng các
tàu biển đến cảng để bốc dỡ hàng hóa...
Dòng các yêu cầu đến hệ thống hàng đợi được đặc trưng bởi tốc độ đến (arrival
rate), ký hiệu là λ. Là một biến ngẫu nhiên được đặc trưng bởi phân phối xác suất của
các lần khách hàng đến liên tiếp. Dòng yêu cầu đến hệ thống là dòng biến cố ngẫu
nhiên và tuân theo những phân phối xác suất nhất định, như đã nêu ở mục 1.2.2.
Tiến trình phục vụ
Bao gồm hàng đợi phục vụ và quá trình phục vụ. Hàng đợi phục vụ: là tập hợp

Khách hàng đến với dịch vụ theo một lịch trình (VD: Cứ 15 phút có một bệnh
nhân đến khám hoặc đúng 30 phút có một sinh viên đến đăng ký học) hoặc đến một
cách ngẫu nhiên không xác định chính xác được thời gian khách hàng kế tiếp đến.
Để tính toán số khách hàng trung bình đến dịch vụ trong một khoảng thời gian,
hay trung bình số lần xảy ra thành công của một sự kiện trong một khoảng thời gian
nhất định ta sử dụng phân phối Possion [6 tr.8] với giá trị trung bình này được ký hiện
là . Những hàng đợi có khách hàng đến ngẫu nhiên, độc lập và không xác định trước
thời gian đến. Số yêu cầu đến tại một thời điểm bất kỳ có thể ước lượng bằng phân
phối xác suất Possion được biểu diễn bởi hàm sau:


Trong đó: P(x) = xác suất xuất hiện x khách hàng vào hệ thống
x= Số yêu cầu đến trong 1 đơn vị thời gian
tốc độ đến (arrivals rate) của khách hàng

Ví dụ: với

Khách hàng đến/1 giờ thì xác suất không có khách hàng (k=0)

đến tại thời điểm bất kỳ là 13%, khả năng 1 khách hàng là 27%, 2 khách hàng khoản
27%, 3 khách hàng là 18%, 4 khách hàng là khoảng 9%.
Hành vi (tính chất) của tiến trình đến
Con người hay máy móc nói chung thường tuân theo quy luật xếp hàng cho đến
khi được phục vụ mà không chuyển giữa các hàng. Nhiều khách hàng từ chối chờ hoặc
thiếu kiên nhẫn nên từ bỏ giữa chừng. Những khách hàng đó sẽ đến và rời khỏi khi
chưa được phục vụ. Trên thực tế, cả hai trong số các trường hợp này chỉ phục vụ để
làm nổi bật sự cần thiết cho lý thuyết xếp hàng.
b) Đặc điểm hàng đợi
Hàng đợi gồm 2 đặc điểm:
Kích thước: Chiều dài của hàng đợi cũng có thể là giới hạn hoặc vô hạn. Giới

hàng đợi, bao gồm 3 phần cơ bản: A/B/c, với:
-

-

-

A: là hàm phân phối thời gian của các lần đến liên tiếp. Tùy thuộc vào đặc điểm
của hàng đợi mà luật phân phối được thể hiện trong ký hiệu sẽ có giá trị tương
ứng như sau: M (phân phối mũ), G (phân phối chung), D (phân phối đều),
Er( phân phối Erlangian), H (phân phối siêu mũ)
B: hàm phân phối thời gian phục vụ. Tương tự như phân phối thời gian đến, luật
phân phối được thể hiện trong ký hiệu sẽ một trong những giá trị tương ứng như
sau: M (phân phối mũ), G (phân phối chung), D (phân phối đều), Er( phân phối
Erlangian), H (phân phối siêu mũ)
c: Số kênh phục vụ (c>0)
Ký tự mô tả có thể mở rộng thêm một số thông số sau:

-

K: Số lượng khách hàng lớn nhất có thể có trong hệ thống (trong hàng đợi và
đang được phục vụ)
n: Nguồn khác hàng vô hạn (∞) hoặc hữu hạn (n)
D: Nguyên tắc phục vụ

Một số ví dụ để hiểu rõ về ký hiệu Kendall:
Ví dụ 1: hệ thống hàng đợi M/M/1, là mô hình hệ thống hàng đợi cổ điển, đơn
giản nhất với 3 thành phần:
- Thời gian giữa các lần tín hiệu xuất hiện liên tiếp tuân theo luật phân phối mũ
(M).

Phân phối thời gian bận rộn của kênh phục vụ (là khoảng thời gian phục vụ liên
tục của kênh).
Đặc biệt, đối với hệ thống hàng đợi chúng ta quan tâm đến một số các tham số

sau:
Bảng 1. 2 - Một số tham số của hàng đợi
STT

Ký
hiệu

Mô tả

1.

λ

Tốc độ đến (arrival rate) của khách hàng

2.

µ

Tốc độ phục vụ (service rate)

3.

tn

Khoảng thời gian giữa khách hàng liên tiếp (tn= τn - τn-1 )

9.

Số khách hàng ra khỏi hệ thống trong khoảng thời gian (0,t)

10.

Số khách hàng ở trong hệ thống tại thời điểm t
L(t)

11.

Lq

Số khách hàng trong hàng đợi

12.

T

Tổng thời gian phục vụ của toàn bộ hệ thống

13.

Hệ số sử dụng hệ thống
ρ

14.

pK




Cuối cùng, khi áp dụng luật Little cho quầy phục vụ ta có

Với

là số khách hàng ở trong quầy phục vụ (áp dụng tương tự với hàm thời

gian phục vụ) và

là thời gian phục vụ.

1.2 Một số mô hình hàng đợi cơ bản
Trong thực tế có rất nhiều mô hình hàng đợi được áp dụng trong quản lý, Bảng
1.2 liệt kê một số mô hình thường thấy áp dụng trong các ứng dụng. Với mỗi mô hình
sẽ có những đặc điểm và quá trình chuyển trạng thái riêng; các đặc điểm và phương
pháp tính hiệu suất của từng mô hình sẽ được trình bày trong các tiểu mục của mục 1.2
này.
Bảng 1. 3-Một số mô hình hàng đợi cơ bản
Tên hàng đợi

Số kênh Số
phục vụ bước
phục
vụ

Phân
Phân phối Kích
Nguyên
phối tín thời gian thước


Hệ thống hàng 1
đợi có thời gian
phục vụ chính
xác (M/D/1)

1

Possion

Luật phân Không
phối mũ
giới hạn

FIFO

Hệ thống hàng c(c>1)
đợi M/M/c/K

c

Possion

Luật phân Giới hạn
phối mũ

FIFO

Trong phần tiếp theo, luận văn nêu chi tiết đặc điểm cũng như các độ đo hiệu
suất của những hàng đợi đã nêu trong bảng 1.3.

Môhình
hìnhhàng
hàngđợi
đợiM/M/1
M/M/1
b) Đo hiệu suất hàng đợi M/M/1

Hình 1. 4 - Sơ đồ chuyển trạng thái của hàng đợi M/M/1

Đối với mô hình chuyển trạng thái như hình 1.4 [4 tr.30] tốc độ đến và tốc độ phục vụ
không phụ thuộc trạng thái, mà được đặc trưng bởi số khách hàng trong hệ thống.
-

Phân phối thời gian đến

-

Phân phối thời gian phục vụ

-

Để hàng đợi đảm bảo điều kiện dừng (không vượt quá khả năng phục vụ) cần
đảm bảo ràng buộc [4 tr.29]

Ta có các biến cần tính toán sau:
= Số khách hàng đến trung bình trong một đơn vị thời gian
= Số khách hàng được phục vụ trong một đơn vị thời gian
Số lượng khách hàng lưu trú trong hệ thống (lượng khách đang chờ đợi + đang
được phục vụ)



Server c

Hình 1. 5- Mô hình hàng đợi M/M/c

-

Phân phối thời gian đến là

Output


-

Phân phối thời gian phục vụ

-

Hiệu suất phục vụ:

b) Đo điệu suất hệ thống M/M/c:

Hình 1. 6 - Sơ đồ chuyển trạng thái hàng đợi M/M/c
Sơ đồ chuyển trạng thái hình 1.7 [4 tr.43] cho thấy tốc độ phục vụ phụ thuộc vào
số kênh phục vụ; các biến của hệ thống M/M/c:
Số kênh phục vụ
= Số khách hàng đến trung bình trong một đơn vị thời gian
= Số khách hàng được phục vụ trong một đơn vị thời gian ở mỗi kênh
Xác xuất hệ thống không có khách hàng



Server 1

Input

Hàng đợi
(queue)

FCFS

Server 2

…
W thời gian
đợi

Server c

Hình 1. 7- Mô hình hàng đơi M/M/c/K

Output


a)
b)

Đặc điểm
Hàng gồm c kênh phục vụ
Nguyên tắc phục vụ FCFS
Không giới hạn kích thước dòng vào

1.3 Các điều kiện để bài toán có thể giải được bằng lý thuyết
Điều kiện 1: Dòng vào của hệ thống phải là dòng tối giản hoặc xấp xỉ tối giản.


Điều kiện 2: Khoảng thời gian (T) giữa 2 lần xuất hiện liên tiếp các yêu cầu 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:
(1.1)
Và hàm phân phối xác suất có dạng
(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
có dạng

Và hàm phân phối xác suất

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.
1.4 Phương pháp giải quyết bài toán bằng lý thuyết hàng đợi
Giải bài toán phục vụ đám đông bằng lý thuyết hàng đợi hay phương pháp giải
tích là phương pháp cơ bản và được sử dụng khá phổ biến. Đường lối chung của
phương pháp này bao gồm các bước:
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