ĐẠ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ênngà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ôngnghệthông tin
Chuyênngành: Kỹthuậtphầnmềm
Mãsố: 60480103

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


Biến ngẫu nhiên...........................................................................................8

1.1.2

Phân phối sác xuất thƣờng gặp ...................................................................8

1.1.3

Khái niệm hàng đợi và lý thuyết hàng đợi ................................................11

1.1.4

Kí hiệu Kendall .........................................................................................15

1.1.5

Định nghĩa các độ đo hiệu suất .................................................................16

1.1.6

Luật Little ..................................................................................................17

1.2

Một số mô hình hàng đợi cơ bản .....................................................................18

1.2.1

Hệ thống một kênh phục vụ M/M/1 ..........................................................19



Giới thiệu về GPSS World ...............................................................................26

2.3.1

Đặc điểm nổi bật của ngôn ngữ GPSS World ...........................................26

2.3.2

Một số khái niệm trong GPSS World .......................................................27

2.3.3

Các thực thể trong GPSS ...........................................................................30

2.3.4

Cú pháp lệnh GPSS ...................................................................................33

2.3.5

Các khối cơ bản trong GPSS .....................................................................35

2.3.6

Một số hàm thƣ viện..................................................................................41

2.3.7

Cài đặt và sử dụng GPSS World Student Version ....................................41


Mô phỏng bài toán bằng công cụ mô phỏng .............................................52

3.3

Bài toán xếp hàng nhiều phase phục vụ ...........................................................56

3.3.1

Phát biểu bài toán ......................................................................................56

3.3.2

Phân tích bài toán bằng lý thuyết hàng đợi ...............................................57

3.3.3

Mô phỏng bài toán bằng công cụ mô phỏng .............................................61

KẾT LUẬN ...................................................................................................................70

3


DANH MỤC HÌNH VẼ
Hình 1. 1- Sơ đồ chuyển trạng thái của phân phối Erlang-k với biến quy mô là .......11
Hình 1. 2- Thành phần cơ bản của hàng đợi .................................................................12
Hình 1. 3 - Mô hình hàng đợi M/M/1 ............................................................................19
Hình 1. 4- Mô hình hàng đợi M/M/1 .............................................................................19
Hình 1. 5 - Sơ đồ chuyển trạng thái của hàng đợi M/M/1 .............................................19

Bảng 3. 4- Kết quả tính toán hàng đợi gửi xe ô tô ........................................................58
Bảng 3. 5-Bảng kết quả tính toán hàng đợi bãi gửi xe máy ..........................................58
Bảng 3. 6- Kết quả tính toán hàng đợi giỏ hàng trong 8h .............................................59
Bảng 3. 7- Kết quả tính toán hàng đợi xe đẩy trong 8h.................................................60
Bảng 3. 8 – Kết quả mô phỏng hoạt động của siêu thị ..................................................66
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 gian v_time_work 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. Đem so sánh kết
quả từng trƣờng hợp với lý thuyết. Bảng 3. 9 đƣa ra so sánh thời gian phục vụ của các
quầy phục vụ với thời gian trung bình tính toán từ lý thuyết (225 giây). .....................68
Bảng 3. 10. Bảng so sánh thời gian thanh toán trung bình ............................................68

5


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

Khả năng phục vụ của hệ thống không đáp ứng yêu cầu dẫn đến kết quả là một
số yêu cầu không được phục vụ hoặc phải chờ đợi để được phục vụ.
Khả năng phục vụ của hệ thống vượt quá yêu cầu dẫn đến kết quả là hệ thố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
Tóm lƣợc kết quả chính của luận văn, nêu lên các hạn chế của nghiên cứu từ đó định
hƣớng phát triển trong thời gian tới.

1

M

Phân phối
mũ

2

Ek

Phân phối
Erlang

3

Hk

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

Hàm phân phối

f (t ) 

k

q
j 1


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

Biến ngẫu nhiên tuân có phân phối Poisson khi dòng đến có đủ các đặc điểm của
quá trình Poisson. Quá trình Poisson có 3 tính chất sau:
Tính không hậu quả: Dòng yêu cầu có tính không hậu quả có nghĩa là: nếu xác
suất xuất hiện một số yêu cầu nào đó trong một khoảng thời gian nhất định không phụ
thuộc vào việc đã có bao nhiêu yêu cầu xuất hiện trƣớc khoảng thời gian đó. Hay nói
khác, số yêu cầu xuất hiện trƣớc và sau thời điểm nào đó không chịu ảnh hƣởng qua
lại lẫn nhau.
9


Tính đơn nhất Dòng yêu cầu có tính chất đơn nhất có nghĩa là: nếu xét trong
khoảng thời gian khá bé thì biến cố “có nhiều hơn một yêu cầu xuất hiện” hầu nhƣ
không xảy ra. Về mặt thời gian, chúng ta có thể xem dòng yêu cầu có tính chất đơn


. Ký hiệu chung là

.

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

Tham số

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

(shape parameter) Một sơ đồ trạng thái của

là tham số hình dạng

đƣợc biểu diễn bởi Hình 1.1

10


Hình 1. 1- Sơ đồ chuyển trạng thái của phân phối Erlang-k với biến quy mô là
Các đặc trƣng phƣơng sai, phƣơng sai và hệ số bình phƣơng bằng nhau đều bằng nhau

1.1.2.5 Phân phối siêu bội
Một biến ngẫu nhiên
là phân phối siêu bội [2 tr.24] nếu
i=1,...,k một biến phân phối mũ

,


Đặc điểm hàng đợi:
· Kích thước của hàng đợi
· Nguyên tắc phục vụ

Đặc điểm dòng đến
· Kích thước khách hàng
· Quy tắc của dòng đến
· Hành vi (tính chất) của
tiến trình đến

Tiến trình ra

Đặc điểm dịch vụ:
· Thiết kế của hệ thống dịch vụ
· Phân bố thời gian phục vụ

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
các yêu cầu sắp xếp theo một trật tự để chờ đƣợc phục vụ theo một nguyên tắc phục vụ

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
13


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

tế, hầu hết thời gian phục vụ thƣờng tuân theo phân phối ngẫu nhiên.
1.1.4 Kí hiệu Kendall
Kendall [3 tr.14] sử dụng ký tự để mô tả một cách ngắn gọn cấu trúc hệ thống
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

Phân phối số lƣợng khách hàng trong hệ thống (bao gồm hoặc không bao gồm
những khách hàng đang đƣợc phục vụ).
Phân phối khối lƣợng các công việc trong hệ thống (Tổng thời gian khách hàng
chờ đợi và thời gian còn lại của khách hàng trong dịch vụ).
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.

B(𝓍)

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

8.

Số khách hàng đến trong khoảng thời gian (0,t)

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.



Để mô tả cho luật Little ta xét với mô hình hàng đợi 1 quầy phục vụ. Với mô
hình này chúng ta có thể thu đƣợc một số thông số hiệu suất khi áp dụng luật. Áp
dụng luật cho hàng đợi (không gồm quầy phục vụ) thu đƣợc mối quan hệ giữa chiều
dài hàng đợi và thời gian đợi
nhƣ sau:

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


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

FIFO

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

FCFS

Server

W thời gian
đợi Hình
Hình 1.
1. 34-- Mô
Mô hình
hình hàng
hàng đợi
đợi M/M/1
M/M/1
b) Đo hiệu suất hàng đợi M/M/1

Hình 1. 5 - 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

Hàng đợi
(queue)

FCFS

Server 2

Output

…
W thời gian
đợi

Server c

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

20


-

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

-

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

-


M/M/1. Cả chiều dài hàng đợi và thời gian chờ đợi trung bình đều giảm một nửa.
Độ dài trung bình của hàng đợi

Thời gian đợi trung bình

Số khách hàng trung bình trong hệ thống

Thời gian đợi trung bình trong hệ thống

1.2.4 Hệ thống hàng đợi giới hạn kích thƣớc M/M/c/K
Là hệ thống đa kênh và chỉ có tối đa K khách hàng đƣợc phép lƣu trú trong hệ thống.
Hệ thống hàng đợi M/M/m/K đƣợc mô hình hóa trong Hình 1.8

Server 1

Input

Hàng đợi
(queue)

FCFS

Server 2

Output

…
W thời gian
đợi


Trong mô hình trên, hệ thống ở trạng thái i khi có i khách hàng đƣợc phục vụ
đồng thời.
Chiều dài hàng đợi trung bình, xác suất có k khách hàng và 0 khách hàng trong
hệ thống [3 tr.55]:

Trung bình khách hàng trong hệ thống

Và do

Chúng ta có:

Ngoài các hệ thống hàng đợi đã giới thiệu (M/M/1, M/M/1/K, M/M/c, M/M/c/K)
trên đây, còn có rất nhiều mô hình hệ thống hàng đợi khác nhƣ M/M/c/K/M, M/G/1, M
/Er /1, Er /M/1, M/G/1,G/M/m, G/G/1 đƣợc trình bày khá chi tiết trong tài liệu [3].
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.
23