Luận văn Thạc sĩ Khoa học Máy tính: Nghiên cứu lý thuyết hàng đợi và mô phỏng bãi gửi xe tại siêu thị Big C

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT & TT

NGHIÊN CỨU LÝ THUYẾT HÀNG ĐỢI VÀ MÔ PHỎNG BÃI GỬI XE TẠI SIÊU THỊ BIG C – HÀ NỘI

VŨ TUẤN DOANH

THÁI NGUYÊN 2015

LỜI CAM ĐOAN

Tôi cam đoan đây là công trình nghiên cứu do chính tôi thực hiện.

Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc

ai công bố trong bất kỳ công trình nào khác.

Thái Nguyên, Ngày 14 tháng 5 năm 2015

Tác giả

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Vũ Tuấn Doanh

MỤC LỤC

LỜI CAM ĐOAN .............................................................................................. i

MỤC LỤC……………………………………………………...……………..ii

DANH MỤC CÁC BẢNG……………………………………..….………....iv

DANH MỤC CÁC HÌNH……………………………………….………..…..v

LỜI MỞ ĐẦU…………………………………………………..………...…..1

Chƣơng 1:CƠ SỞ LÝ THUYẾT VỀ HÀNG ĐỢI ........................................... 3 1.1. Các khái niệm cơ bản .......................................................................... 3

1.1.1. Định nghĩa hàng đợi.................................................................... 3

1.1.2. Các tham số đặc trƣng của một hàng đợi ................................... 3

1.1.3. Các thông số hiệu năng thƣờng dùng khi phân tích hệ thống sử

dụng mô hình mạng xếp hàng ............................................................... 6

1.2. Ứng dụng của hệ thống hàng đợi ........................................................ 8

1.2.1. Hệ thống phục vụ ........................................................................ 8

1.2.2. Các yếu tố của hệ thống phục vụ .............................................. 10

1.2.3. Trạng thái hệ thống phục vụ ..................................................... 14

1.3. Kết luận chƣơng ................................................................................ 17

Chƣơng 2:NGHIÊN CỨU HÀNG ĐỢI VÀ MỘT SỐ BÀI TOÁNTRONG

SIÊU THỊ ........................................................................................................ 18 2.1. Một số hàng đợi trong bài toán mô phỏng siêu thị ........................... 18 2.2. Hàng đợi M/M/k ................................................................................ 20 2.2.1. Trạng thái ổn định của hàng đợi M/M/k .................................. 20

2.2.2. Phân bố dừng của hàng đợi M/M/k .......................................... 21

2.2.3. Hàng M /M / k / N..................................................................... 21

2.3. Hàng đợi G/G/1 .................................................................................. 23

2.3.1. Phƣơng pháp phƣơng trình tích phân ....................................... 24

2.3.2. Hàng đợi M/G/1 ........................................................................ 26

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

2.3.3. Các trƣờng hợp đặc biệt của hàng đợi M/G/1 .......................... 27

iii

2.3.4. Phương pháp chuỗi Markov nhúng áp dụng cho hàng G/M /1 29

2.3.5. Các cận trên của thời gian đợi trung bình của hàng ................. 31

2.4. Một số bài toán tổng quát trong siêu thị ............................................ 32

2.5. Quy trình sử dụng GPSS mô phỏnghàng đợi ..................................... 33

2.6. Kết luận chƣơng ................................................................................. 35

Chƣơng 3:BÀI TOÁN MÔ PHỎNG BÃI GỬI XE TẠISIÊU THỊ BIG C –

HÀ NỘI ........................................................................................................... 36 3.1 Bài toán bãi xe tại siêu thị (mô hình hoạt động đơn giản) .................. 36 3.1.1 Mô tả bài toán ............................................................................ 36 3.1.2 Phân tích bài toán ....................................................................... 36 3.1.3 Giải bài toán ............................................................................... 37 3.1.4 Mô hình GPSS World ................................................................ 38 3.2 Bài toán mô phỏng hoạt động của siêu thị .......................................... 39 3.2.1 Mô tả bài toán ............................................................................ 39 3.2.2 Phân tích bài toán ....................................................................... 41

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

3.2.3 Giải bài toán ............................................................................... 42 3.2.4 Mô hình GPSS World ................................................................ 43 3.3. Đánh giá, so sánh kết quả mô phỏng ................................................. 52 3.4. Kết luận chƣơng ................................................................................. 56 KẾT LUẬN ..................................................................................................... 57 TÀI LIỆU THAM KHẢO ............................................................................... 58

DANH MỤC CÁC BẢNG

Bảng 2.1: Các thành phần trong kí hiệu Kendall ............................................ 18

Bảng 2.2: Một số phân phối xác suất liên quan đến A và Btrong mô tả Kendall . 19

Bảng 3.1. So sánh kết quả tính toán theo lý thuyết với tính toán trong GPSS

với thời gian T = 8 giờ ............................................................................ 39

Bảng 3.2: So sánh kết quả tính toán theo lý thuyết với tính toán

trong GPSS với T = 8 giờ ....................................................................... 52

Bảng 3.3. So sánh kết quả tính toán theo lý thuyết với tính toán trong GPSS

theo thời gian T tại mô hình ở mục 3.1 ................................................... 53

Bảng 3.4: Mức độ sai lệch giữa mô phỏng và lý thuyết theo đại lƣợng

“Số xe ô tô đến siêu thị” với mô hình ở mục 3.1 .................................... 54

Bảng 3.5: Mức độ sai lệch giữa mô phỏng và lý thuyết theo đại lƣợng “Số xe

ô tô đƣợc phục vụ tại bãi xe” với mô hình ở mục 3.1 ............................. 54

Bảng 3.6: Mức độ sai lệch giữa mô phỏng và lý thuyết theo đại lƣợng

“Số xe ô tô đƣợc phục vụ tại bãi xe” với mô hình ở mục 3.2 ................. 55

Hình 3.7: Đồ thị phụ thuộc độ sai lệch tính toán giữa GPSS và lý thuyết

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

theo thời gian ........................................................................................... 55

DANH MỤC CÁC HÌNH

Hình 1.1: Mô hình chung của hệ thống hàng đợi ............................................ 3

Hình 1.2: Mô hình cơ bản của hệ thống phục vụ ............................................ 8

Hình 1.3: Mô tả hệ thống phục vụ đám đông ................................................. 9

Hình 1.4: Sơ đồ trạng thái của hệ thống phục vụ .......................................... 15

Hình 2.1: Đồ thị biểu diễn tốc độ phục vụ .................................................... 29

Hình 3.1: Mô hình hàng đợi của bãi xe ......................................................... 36

Hình 3.2: Sơ đồ thuật toán mô phỏng bãi xe ................................................ 37

Hình 3.3: Mô hình minh họa hoạt động của siêu thị ..................................... 41

Hình 3.4: Mô hình hoạt động các hàng đợi của siêu thị ............................... 41

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.5. Sơ đồ thuật toán mô phỏng hàng đợi của siêu thị ......................... 42

LỜI MỞ ĐẦU

Những năm gần đây, việc ứng dụng công nghệ thông tin vào các hoạt

động trong đời sống, xã hội là rất cần thiết. Trong thực tế, chúng ta bắt gặp rất

nhiều các hệ thống đƣợc thiết lập bởi các yêu cầu (của khách hàng), trong đó

các thời điểm xuất hiện đƣợc xem nhƣ một đại lƣợng ngẫu nhiên, còn nhu cầu

đƣợc đặc trƣng bằng khối lƣợng các công việc phải làm để phục vụ, thứ tự ƣu

tiên trƣớc sau, thời gian hoàn thành công việc và toà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, hệ thống phục vụ sử

dụng phòng máy thực hành, hệ thống các quầy thu ngân trong siêu thị, hệ

thống bán vé tự động, sân bay… Những hệ thống này đƣợc biết đến với tên

gọi hệ thống phục vụ đám đông (hay hệ thống hàng đợi).

Nhìn chung các hệ thống phục vụ đám đông là hệ thống phức tạp, việc

vận hành và tính toán các đặc trƣng của hệ thống để tƣ vấn cho nhà quản lý là

một vấn đề hết sức cần thiết. Trong quá khứ, có rất nhiều dự án xây dựng hệ

thống phục vụ phức tạp dựa trên hàng chờ (Queue) không thành công vì đã

không đặc tả đƣợc chính xác bài toán thực tiễn. Việc xây dựng mô hình toán

học cho mỗi hệ thống là rất cần thiết để giảm chi phí tối đa cho các hoạt động

đặc tả nó. Khi đó tính chất đầy đủ của các mô hình mô phỏng cần đạt đƣợc

việc mô phỏng quá trình làm việc của mỗi phần tử trong hệ thống với việc

đảm bảo logic, quy tắc của sự tƣơng tác và phát triển của chúng, cả trong

không gian và trong thời gian. Các câu hỏi đƣợc đặt ra là: Làm thế nào để mô

phỏng một hệ thống phức tạp dƣới dạng đơn giản nhƣng chính xác? Phƣơng

pháp nào là khả thi nhất, tối ƣu nhất?... Có rất nhiều phƣơng pháp đã đƣợc

đƣa ra để giải quyết bài toán trên nhƣ: Tính toán bằng các công thức toán học,

xây dựng hệ thống phục vụ bằng các ngôn ngữ lập trình (Pascal, C++…), mô

phỏng bằng các công cụ mô phỏng (Matlab, Petri Network…)… Để xây dựng

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

mô hình mô phỏng bằng cách sử dụng các ngôn ngữ lập trình truyền thống là

khá phức tạp, khó khăn do khi lập trình chúng ta phải quản lý các sự kiện theo

một mô hình nhiều sự kiện xảy ra đồng thời (song song) với việc xây dựng

hàm tạo ngẫu nhiên các sự kiện (random) cũng không hề đơn giản , chính vì

vậy đã xuất hiện nhƣ̃ng ngôn ngữ mô phỏng chuyên dụng . Một trong những

ngôn ngữ chuyên dụng mô phỏng hệ thống phức tạp, rời rạc có hiệu quả và

phổ biến nhất hiện nay là General Purpose Simulation System (GPSS), ngôn

ngữ này thuộc về lớp ngôn ngữ hƣớng vấn đề. Lĩnh vực áp dụng chính của

GPSS là hệ thống phục vụ đám đông. Đối tƣợng của ngôn ngữ này đƣợc sử

dụng tƣơng tự nhƣ: Thành phần chuẩn của một hệ thống phục vụ đám đông ;

các yêu cầu , thiết bị phục vụ , hàng đợi… Tập hợp đầy đủ nhƣ̃ng thành phần

nhƣ vậy cho phép xây dựng các mô phỏng phức tạp trong khi đảm bảo những

thuật ngữ thông thƣờng của hệ thống phục vụ đám đông.

Trên thế giới nói chung và ở Liên bang Nga nói riêng, việc nghiên cứu

và ứng dụng của GPSS rất phổ biến và phát triển. Tuy nhiên việc triển khai và

ứng dụng công cụ mô phỏng GPSS trong giải quyết các bài toán hệ thống

phục vụ đám đông vẫn là mới ở Việt Nam.

Chính vì vậy, yêu cầu lựa chọn, so sánh, đánh giá các công cụ dựa trên

định hƣớng xây dựng mô phỏng hệ thống phục vụ đám đông là một đề tài

mang ý nghĩa khoa học và thực tiễn cao. Với lý do đó, tôi lựa chọn đề tài

“Nghiên cứu lý thuyết hàng đợi và mô phỏng bãi gửi xe tại siêu thị Big C –

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hà Nội” cho luận văn tốt nghiệp Thạc sĩ của mình.

Chƣơng 1

CƠ SỞ LÝ THUYẾT VỀ HÀNG ĐỢI

1.1. Các khái niệm cơ bản

1.1.1. Định nghĩa hàng đợi

Hàng đợi là hệ thống bao gồm các thành phần : khách hàng vào/ ra hệ

thống (input/output), hệ thống phục vụ (server), hàng đợi(queue).

Hình 1.1: Mô hình chung của hệ thống hàng đợi

Khách hàng vào hệ thống đƣợc đƣa vào hàng đợi, đến lƣợt thì đƣợc

phục vụ ở server, sau khi đƣợc phục vụ xong thì ra khỏi hệ thống. Khi dùng

hàng đợi ta hiểu là toàn bộ hệ thống xếp hàng bao gồm các yêu cầu đợi phục

vụ và các yêu cầu đang đợi phục vụ và các yêu cầu đang đƣợc phục vụ [2].

Hệ thống đƣợc mô hình hoá dƣới dạng hàng đợi nhƣ sau:

 Mỗi loại tài nguyên của hệ thống tƣơng ứng với một trung tâm dịch

vụ (server center).

 Mỗi giao dịch yêu cầu tài nguyên thứ i sẽ là một khách hàng trong

hàng đợi Qi tƣơng ứng với loại tài nguyên đó.

1.1.2. Các tham số đặc trƣng của một hàng đợi

- Tính chất của dòng khách hàng đến hàng đợi hay phân bố xác suất

khoảng thời gian giữa các yêu cầu hàng đợi.

- Phân bố xác suất khoảng thời gian dịch vụ cho mỗi yêu cầu trong hàng đợi.

- Số các server tại hàng đợi.

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Dung lƣợng bộ đệm hay dung lƣợng lƣu trữ tại hàng đợi.

- Tổng số các yêu cầu hiện đang có mặt tại hàng đợi.

- Các kiểu dịch vụ.

Theo kí pháp của Kendall một hệ thống xếp hàng đƣợc phân loại qua

các kí hiệu của bộ mô tả kendall tổng quát có dạng //m//N/Q.

: phân bố xác suất của khoảng thời gian yêu cầu để phục vụ các khách

hàng trong hệ thống xếp hàng .

: phân phối xác suất trong khoảng thời gian yêu cầu để phục vụ các

khách hàng trong hệ thống xếp hàng

: kích thƣớc bộ đệm hoặc dung lƣợng lƣu trữ tại hệ thống xếp hàng.

N : số lƣợng khách hàng đƣợc phép chuyển qua hệ thống.

Q: phƣơng thức phục vụ.

Một số các phân bố xác suất đƣợc sử dụng để biểu diễn các đại lƣợng

đặc trƣng của hệ thống xếp hàng nhƣ sau:

 Phân bố xác định (D-Deterministic): Khoảng thời gian giữa hai khách

hàng đến hay rời hệ thống liên tiếp là bằng nhau:

 Phân bố mũ(M-exponential): Khoảng thời gian giữa hai lần khách

hàng đến hệ thống liên tiếp là hoàn toàn độc lập với khoảng thời gian đến

trƣớc đó. Biến ngẫu nhiên mô tả quá trình có phân phối mũ:

 Phân phối erlang-r ( ): Trung tâm dịch vụ đƣợc biểu diễn bằng một

dãy các giai đoạn trễ mỗi giai đoạn có cùng thời gian dịch vụ trung bình và

có phân phối mũ. Không có các hàng đợi tại bất kì giai đoạn phục vụ nào vì

yêu cầu tiếp theo sẽ không đƣợc đáp ƣng nều yêu cầu trƣớc đó chƣa đƣợc

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hoàn thành:

 Phân phối Hypexponential ( ): Mỗi giai đoạn trễ trong mô hình

có các thời gian dịch vụ khác nhau với các giai đoạn đƣợc phục vụ song song

 Phân phối tổng quát(G-General): là một hàm bất kỳ.

Các phương thức phục vụ khách hàng bao gồm :

 LIFO(Last In First Out): các khách hàng tới gần đây nhất sẽ đƣợc

phục vụ hoặc phải đợi.

 LIFO PR (LIFO with PRe-emptive): khi khách hàng tới gần đây

nhất ngay lập tức đƣợc thế chỗ cho khách hàng đƣợc phục vụcho đến khi

nó đƣợc phục vụ xong thì dịch vụ có thể tiếp tục đối với một khách hàng

bị thế chỗ ngay nơi mà nó bị ngắt trƣớc đó.

 RR(Round Robin): Thời gian tại một tài nguyên (đĩa , CPU…

)đƣợc phân chia thành một số các thông số trong khoảng nhỏ có độ dài cố

định đƣợc gọi là các lƣợng tử. Một khách hàng tới tham gia vào hàng đợi

và chờ để đƣợc lên đầu hàng theo nguyên tắc FCFS và cuối cùng khách

hàng nhận đƣợc một lƣợng tử cho quá trình phục vụ khi lƣợng tử này hết

mà khách hàng vẫn chƣa đƣợc phục vụ thì khách hàng đó phải quay lại

hàng đợi cho đến khi khách hàng đó đƣợc phục vụ xong.

 PS(Processor Shariny) : Trong hệ thống này các bộ vi xử lý đóng

vai trò nhƣ server có tốc độ phục vụ cố định. Nó có thể phân phối khả

năng phục vụ bằng nhau cho các khách hàng trong hệ thống có nghĩa là

không có hàng đợi nào trong hệ thống cả. Mỗi khách hàng đến lập tức

đƣợc phục vụ.

 P: Chế độ có ƣu tiên. Một số khách hàng đƣợc quyền ƣu tiên hơn

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

những ngƣời khác và đƣợc phục vụ trƣớc.

1.1.3. Các thông số hiệu năng thƣờng dùng khi phân tích hệ thống sử

dụng mô hình mạng xếp hàng

- Tốc độ đến của các khách hàng () [3]:  =

Trong đó A - số các khách hàng đến hệ thống. T-Thời gian quan sát

(hay thời gian đó). Trong khi A đếm số các yêu cầu đến hàng đợi thì  biểu

diễn tốc độ mà các yêu cầu đó đến. Đơn vị đo của tốc độ là : khách hàng đơn

vị thời gian. Ví dụ, nếu một hệ điều hành đƣợc cung cấp các công cụ để mà

đếm số yêu cầu về phục vụ một số tài nguyên (CPU, đĩa...) thì tổng số lần

đếm trong một đơn vị thời gian chính là tốc độ đến.

- Thông lƣợng (throughput) của hệ thống xếp hàng hay là tốc độ trung

bình các khách hàng chuyển qua hệ thống : =

Trong đó C là số các khách hàng hoàn thành dịch vụ. Đại lƣợng này

cũng biểu thị tốc độ. Do nó là một đại lƣợng có thể đo tốc độ hoàn thành dịch

vụ một cách trực tiếp, giống nhƣ tốc độ đến. Trong một số trƣờng hợp ta sẽ

thấy tốc độ đến hệ thống của các khách hàng  sẽ bằng với thông lƣợng X.

Dạng biểu diễn khác: , (khách hàng /giây),

trong đó Pn là xác suất trạng thái cân bằng khi hệ thống có n khách hàng trong

hệ thống. Thông lƣợng trung bình là trung bình trọng số của các tốc độ dịch

vụ (n) còn các xác suất trạng thái cân bằng Pn đƣợc dùng nhƣ các trọng số.

- Số khách hàng trung bình trong hệ thống xếp hàng :

(khách hàng)

Độ đo này là trung bình trọng số của số các khách hàng trong hệ thống

xếp hàng với các xác suất trạng thái đƣợc dùng nhƣ các trọng số. Các biểu

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

diễn khác.

Trong đó,  - tổng thời gian thƣờng trú của tất cả khách hàng đã hoàn

thành dịch vụ.

- Thời gian đáp ứng (R-Response time):

=  = (giây)

Trong đó,  là tổng thời gian thƣờng trú của tất cả các khách hàng đã

hoàn thành dịch vụ.

Cách biểu diễn khác, thời gian đáp ứng : R = W+S (thời gian thường

trú bằng tổng thời gian phục vụ và thời gian mà khách hàng đó phải đợi

trước khi được phục vụ).

- Thời gian phục vụ (S-service time) đƣợc định nghĩa là : =

Trong đó B - tổng thời gian hệ thống bận trong khoảng thời gian T. Đại

lƣợng này không phải là tốc độ mà nó biểu diễn tổng thời gian trung bình để

hoàn thành phục vụ một yêu cầu đến.

- Thời gian dợi (W-waiting time) thời gian đợi của một khách hàng

trƣớc khi đƣợc phục vụ đƣợc xác định : W=SQ, trong đó Q - số các khách

hàng trung bình trong hàng đợi, S - tốc độ dịch vụ.

- Độ hiệu dụng (utilitization) hay là xác suất để hệ thống xếp hàng là

không rỗng và tất cả các server bận (trƣờng hợp nhiều server): U = 1 - po

Cách định nghĩa khác : độ hiệu dạng trung bình U = : Đại lƣợng này

biểu diễn tổng thời gian trung bình mà server hay tài nguyên bị bận trong

khoảng thời gian quan sát T. Độ hiệu dụng không có đơn vị mà thƣờng đƣợc

biểu diễn dƣới dạng %.

- Xác suất để hệ thống xếp hàng là rỗng po

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Xác suất để tất cả các kênh phục vụ đều bận hay xác suất để 1 khách

hàng bị từ chối là : PN hay P[quetteing] (trong đó N-kích thước hệ thống).

Nhận xét: Một điều đáng lƣu ý là hầu nhƣ tất cả các độ đo hiệu năng,

đƣợc xét đến đều phụ thuộc vào giá trị của các xác suất trạng thái cân bằng

Pn, n = 0, 1, 2... Do vậy để xác định đƣợc các độ đo hiệu năng đó cần phải tìm

ra đƣợc giá trị của các xác suất trạng thái cân bằng.

Các độ đo trên có thể đƣợc dùng trực tiếp không chỉ trong các hệ thống

xếp hàng đơn mà còn có thể đƣợc áp dụng cho một hàng đợi trong mạng xếp

hàng nơi mà xác suất trạng thái thành phần của hàng đó.

1.2. Ứng dụng của hệ thống hàng đợi

1.2.1. Hệ thống phục vụ

Một hệ thống phục vụ điển hình đƣợc biết đến với mô hình đƣợc mô tả

ở hình 1.2

Hình 1.2: Mô hình cơ bản của hệ thống phục vụ

Trong đó:

- Dòng các yêu cầu vào: Các yêu cầu đƣợc phục vụ và không đƣợc phục vụ

- Hệ thống phục vụ: Bao gồm các máy phục vụ

- Máy phục vụ: Các kênh phục vụ

- Dòng yêu cầu ra: Các yêu cầu đƣợc phục vụ

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Chi tiết về hệ thống phục vụ sẽ đƣợc trình bày cụ thể trong phần 1.1.2.

Trong các hệ thống phục vụ, hàng đợi xuất hiện bất cứ lúc nào khi nhu

cầu hiện tại đối với dịch vụ vƣợt quá khả năng cung ứng dịch vụ tại thời điểm

đó. Thời gian một yêu cầu đến phải chờ đợi phụ thuộc vào một số yếu tố nhƣ:

Số lƣợng giao dịch trong hệ thống, số kênh giao dịch cung ứng dịch vụ tại

thời điểm đó và thời gian phục vụ cho mỗi yêu cầu đến. Ta có thể sử dụng

một trong hai phƣơng pháp “hộp đen” hoặc phƣơng pháp “hộp trắng” để mô

tả một hệ thống phục vụ đám đông [1].

Hình 1.3:Mô tả hệ thống phục vụ đám đông

Một hệ thống phục vụ đám đông có thể đƣợc ký hiệu theo Kendall dƣới

dạng: A|B|m|n.

Trong đó:

A: Phân phối của thời gian vào.

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

m: Số máy phục vụ.

n: Số chỗ trong hàng đợi.

A, B có thể nhận một trong các phân phối sau:

λ: Cƣờng độ xuất hiện của sự kiện đầu vào

µ: Cƣờng độ phục vụ của kênh phục vụ

- M: Phân phối mũ có hàm phân phối:

(1.1)

Trong đó:

: Hàm phân bố của phân phối mũ

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- : Phân phối Erlang pha có hàm phân phối:

(1.2)

Phân phối Erlang là trƣờng hợp đặc biệt của phân phối Gamma với tham

số hình dạng là số nguyên, đƣợc phát triển để dự đoán các thời gian đợi trong

các hệ thống hàng đợi.

Trong đó:

: Hàm phân bố của phân phối

- Hk: Phân phối siêu lũy thừa với hàm phân phối:

x ≥0 (1.3)

Với:

: Hàm phân bố của phân phối mũ

: Phân phối tất định (Deterministic distribution), tức thời gian vào và -

thời gian phục vụ là hằng số. Hàm phân phối của phân phối này:

1, nếu x ≥ x0

F (x) = (1.4)

0, nếu x

- : Phân phối tổng quát (General distribution)

- 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ó các dạng sau:

+ MMPP: The Markov modulated Poisson process

+ The Markovian arrival process

+ BMAP: The Batch Markovian arrival process

- PH: Phân phối pha

1.2.2. Các yếu tố của hệ thống phục vụ

Một hệ thống phục vụ, dù ở qui mô nào, tính chất hoạt động ra sao, đều

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

đƣợc đặc trƣng bởi các yếu tố chủ yếu sau:

1.2.2.1. Dòng vào

Dòng vào là dòng các yêu cầu đến hệ thống phục vụ, đòi hỏi đƣợc thỏa

mãn một yêu cầu nào đó.

Ví dụ: Khách hàng xếp hàng tại quầy bán vé xem phim, các container

chờ để đƣợc dỡ hàng, các máy bay chờ để cất cánh, hạ cánh…

Tại các thời điểm khác nhau, các yêu cầu đến hệ thống phục vụ một cách

ngẫu nhiên nên các dòng yêu cầu là những đại lƣợng ngẫu nhiên, tuân theo

một luật phân bố xác suất nào đó, do vậy có nhiều loại dòng vào. Trong luận

văn này, ta chỉ tập trung vào hai loại dòng yêu cầu quan trọng, thƣờng gặp

nhất ở mọi hệ thống phục vụ, đó là: Dòng vào tiền định và dòng vào Poisson.

a. Dòng vào tiền định

ầu đến hệ thống Dòng vào tiền định là dòng vào trong đó nhƣ̃ng yêu c

phục vụ tại các thời điểm cách đều nhau một khoảng a, là một đại lƣợng ngẫu

nhiên có hàm phân bố xác suất là:

0, nếu x < a

F (x) = (1.5)

1, nếu x ≥ a

b. Dòng vào Poisson

Dòng vào Poisson (Poat-xong) là dòng yêu cầu đến hệ thống tuân theo

luật phân phối Poisson.

Dòng vào Poisson đƣợc chia làm hai loại:

- 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 , kể từ thời điểm , phụ thuộc vào , nghĩa là:

(1.6)

Trong đó: là số trung bình yêu cầu xuất hiện từ đến .

- Dòng vào Poisson dừng: Là dòng vào mà xác suất trong khoảng thời

gian , kể từ thời điểm , có yêu cầu xuất hiện, không phụ thuộc vào ,

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

nghĩa là:

(1.7)

Trong đó: λ là cƣờng độ xuất hiện của dòng yêu cầu.

Nếu là khoảng thời gian giữa lần xuất hiện các yêu cầu liên tiếp, thì là

một đại lƣợng ngẫu nhiên tuân theo luật chỉ số, nghĩa là có hàm phân bố xác

suất dạng:

(1.8)

Và hàm mật độ xác suất là:

f(t) = λe-λt (1.9)

1.2.2.2. Hàng chờ (Queue)

Hàng chờ 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ờ đƣợ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ờ.

1.2.2.3. Kênh phục vụ

Kênh phục vụ là toàn bộ các thiết bị kĩ thuật, con ngƣời hoặc một tổ

hợp các thiết bị kĩ thuật có cùng công nghệ tƣơng ứng mà hệ thống sử dụng

để phục vụ yêu cầu khách hàng. 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é…

Đặc trƣng quan trọng nhất của kênh phục vụ là thời gian phục vụ. Đó là

thời gian mỗi kênh phải tiêu phí để phục vụ một yêu cầu. Thời gian phục vụ là

một đại lƣợng ngẫu nhiên tuân theo một quy luật xác suất nào đó. 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 yêu cầu đƣợc phục vụ trên các kênh phục vụ (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 dạng:

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

= 1- e –μt (1.10)

Và hàm mật độ xác suất có dạng:

= μe –μt (1.11)

Trong đó:

μ: Là cƣờng độ phục vụ của kênh phục vụ.

: Hàm phân bố xác suất.

: Hàm mật độ xác suất.

Khoảng thời gian giữa nhƣ̃ng l ần xuất hiện liên tiếp các yêu cầu trong

dòng phục vụ của mỗi kênh chính là khoảng thời gian kênh đó phục vụ xong

từng yêu cầu, nghĩa là thời gian phục vụ của kênh.

Nếu dòng phục vụ trên mỗi kênh là dòng tối giản thì thời gian phục vụ

của kênh đó là đại lƣợng ngẫu nhiên tuân theo luật chỉ số, nghĩa là có hàm

phân phối xác suất và mật độ xác suất dạng (1.10), (1.11).

1.2.2.4. Dòng ra

Dòng ra là dòng yêu cầu đi ra khỏi hệ thống, bao gồm các yêu cầu đã

đƣợc phục vụ và các yêu cầu chƣa đƣợc phục vụ.

- Dòng yêu cầu ra đã đƣợc phục vụ: Đó là những yêu cầu đã đƣợc phục

vụ ở mỗi kênh, nếu dòng đó là tối giản thì nó có một vai trò rất lớn trong hệ

thống dịch 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.

- Dòng yêu cầu ra không đƣợc phục vụ: Đây là bộ phận 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.2.5. Nguyên tắc phục vụ của hệ thống dịch vụ

Nguyên tắc phục vụ của hệ thống dịch vụ là cách thức nhận các yêu cầu

vào phục vụ của hệ thống đó và các quy định khác đối với yêu cầu. Nó chỉ ra:

- Trong trƣờng hợp nào thì yêu cầu đƣợc nhận vào phục vụ

- Cách thức bố trí các yêu cầu vào các kênh phục vụ

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Khi nào và trong trƣờng hợp nào thì yêu cầu bị từ chối hoặc phải chờ

- Cách thức hình thành hàng chờ của các yêu cầu

Các yếu tố của phƣơng pháp phục vụ nhƣ: tần suất phục vụ, lựa chọn

máy phục vụ… Các phƣơng pháp phục vụ bao gồm: FCFS: First Come First

Served (yêu cầu nào đến trƣớc phục vụ trƣớc), LCFS: Last Come First Served

(yêu cầu đến sau đƣợc phục vụ trƣớc), SIRO: Service In Random Order (phục

vụ các yêu cầu theo thứ tự ngẫu nhiên), PS: Processor Shared, IS: Infinitive

Server, Static priorities, Dynamic priorities, Preemption (chế độ ƣu tiên).

1.2.3. Trạng thái hệ thống phục vụ

1.2.3.1. Định nghĩa

Trạng thái của hệ thống phục vụ, ký hiệu là , là khả năng kết hợp dòng

vào và dòng ra của hệ thống ở một thời điểm nhất định.

Theo nghĩa đó thì trạng thái của hệ thống phục vụ tại thời điểm chính là

tình huống mà trong hệ thống có yêu cầu đƣợc phục vụ, hay nói cách khác

hệ thống đang có kênh phục vụ đang bận (đang làm việc) và do đó có

kênh đƣợc rỗi (không làm việc).

Hệ thống phục vụ đang ở trạng thái nào đó là một quá trình ngẫu nhiên, quá

trình này tuân theo một luật phân phối xác suất nào đó. Nên khả năng xuất hiện

một trong các trạng thái nào đó tại thời điểm , có xác suất là

một giá trị xác định .

1.2.3.2. Quá trình thay đổi trạng thái của hệ thống phục vụ

Trong quá trình hoạt động, hệ thống phục vụ chuyển từ trạng thái này

sang trạng thái khác dƣới tác động của dòng vào và dòng phục vụ. Xác suất

của quá trình đó đƣợc gọi là xác suất chuyển trạng thái. Nguyên nhân gây ra sự

chuyển trạng thái là do tác động của dòng vào và dòng phục vụ, số kênh bận và

số yêu cầu trong hệ thống thay đổi, tức là dƣới tác động của dòng phục vụ μ(t)

và dòng vào λi(t)tại thời điểm t, hệ thống sẽ biến đổi từ trạng thái này sang

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

trạng thái khác.

1.2.3.3. Sơ đồ trạng thái

Sơ đồ trạng thái của hệ thống đƣợc dùng để diễn tả quá trình thay đổi trạng

thái của hệ thống phục vụ. 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 đó nhƣ̃ng 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,

hình chữ nhật biểu diễn trạng thái của hệ thống. Tham số ghi trên mũi tên biểu

thị tác động của cƣờng độ dòng biến cố kéo trạng thái dịch chuyển theo hƣớng

mũi tên.

Hình 1.4: Sơ đồ trạng thái của hệ thống phục vụ

1.2.3.4. Qui tắc thiết lập hệ phương trình trạng thái

Căn cứ vào sơ đồ trạng thái, ta thiết lập quan hệ giữa xác suất xuất hiện

trạng thái xk(t): Pk(t), với nhƣ̃ng tác nhân gây ra sự biến đổi trạng thái đó. Mối quan hệ này đƣợc hiển thị bởi nhƣ̃ng phƣơng trình toán học chứa xác suất Pk(t) và cƣờng độ dòng chuyển trạng thái của hệ thống.

- Nội dung quy tắc:

Đạo hàm bậc nhất theo thời gian của xác suất xuất hiện trạng thái xk(t),

Pk(t), bằng tổng đại số của một số hữu hạn số hạng, số các số hạng này bằng

số mũi tên nối liền trạng thái xk(t), với trạng thái xj(t) khác, trong đó số số

hạng mang dấu (+) tƣơng ứng với số mũi tên hƣớng từ xj(t) về xk(t) ; số hạng

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

mang dấu (-) tƣơng ứng với số mũi tên hƣớng từ xk(t) sang xj(t). Mỗi số hạng

có giá trị bằng tích giữa cƣờng độ của dòng biến cố hƣớng theo mũi tên và

xác suất xuất hiện trạng thái mà mũi tên xuất phát.

(1.12)

- Hệ phƣơng trình trạng thái:

(k=0,1,2,…,n)

(1.13)

Với điều kiện:

Trong (2.12): λjk (t) là cƣờng độ dòng biến cố (dòng yêu cầu hoặc dòng phục vụ) chuyển trạng thái xj(t) về trạng thái xk(t). λjk(t): ý nghĩa ngƣợc lại Pj(t) là xác suất xuất hiện trạng thái xj(t) ở thời điểm t (trạng thái trong hệ thống có j kênh đang làm việc). Pk(t) ý nghĩa tƣơng tự.

- Định lý Markov

Dƣới tác động của dòng tối giản, quá trình thay đổi trạng thái của hệ

thống sẽ có tính chất dừng, theo nghĩa:

(1.14)

Khi đó, hệ phƣơng trình (2.12) có dạng:

(1.15)

Với điều kiện:

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(1.16)

1.3. Kết luận chƣơng

Nội dung chƣơng 1 tập trung vào cơ sở lý thuyết phục vụ đám đông (lý

thuyết hàng đợi), bao gồm các mô tả về một hệ thống phục vụ nói chung nhƣ:

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ụ), trạng thái của hệ thống (quá trình thay đổi trạng thái của hệ thống phục

vụ, sơ đồ trạng thái, quy tắc thiết lập hệ phƣơng trình trạng thái).

Tâ ̣p trung giải quyết các vấn đề: Mô tả hệ thống phục vụ: Dòng các yêu cầu vào, hệ thống phục vụ, các

kênh phục vụ, dòng yêu cầu ra.

Các yếu tố của hệ thống phục vụ: Dòng vào (dòng vào tiền định, dòng

vào Poisson); hàng chờ (Queue); kênh phục vụ; dòng ra; nguyên tắc phục vụ

của hệ thống dịch vụ.

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Trạng thái hệ thống phục vụ: Đƣa ra định nghĩa; quá trình thay đổi trạng thái của hệ thống phục vụ; sơ đồ trạng thái; qui tắc thiết lập hệ phƣơng trình trạng thái (nội dung quy tắc, hệ phƣơng trình trạng thái, định lý Markov).

Chƣơng 2

NGHIÊN CỨU HÀNG ĐỢI VÀ MỘT SỐ BÀI TOÁN

TRONG SIÊU THỊ

2.1. Một số hàng đợi trong bài toán mô phỏng siêu thị

Các thành phần cơ bản của một hàng đợi đƣợc mô tả ngắn gọn trong kí

hiệu Kendall[10] có dạng: A / B / m / K / n / D.

Ý nghĩa của các ký hiệu trong mô tả Kendall đƣợc trình bày trong

bảng 2.1.

Bảng 2.1: Các thành phần trong kí hiệu Kendall

TT Ký hiệu Ý nghĩa

Kí hiệu cho A(t) - hàm phân phối thời gian của các lần đến

liên tiếp. A có giá trị là: M (phân phối mũ), D (phân phối 1 A đều), Er( phân phối Erlangian), G (phân phối chung), H

(phân phối siêu mũ)

Kí hiệu cho B(t) - hàm phân phối thời gian phục vụ. B có giá

B trị là: M (phân phối mũ), D (phân phối đều), Er( phân phối 2

Erlangian), G (phân phối chung), H (phân phối siêu mũ)

m Số lƣợng kênh phục vụ 3

Dung lƣợng của hệ thống, là số khách hàng lớn nhất có mặt

K mà hệ thống bao gồm cả khách hàng trong hàng đợi và 4

khách hàng đang đƣợc phục vụ

Số lƣợng nguồn khách hàng (population size) 5 n

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Nguyên tắc phục vụ 6 D

Sau đây là bảng các hàm phân phối xác suất của A và B.

Bảng 2.2: Một số phân phối xác suất liên quan đến A và Btrong mô tả Kendall

Hàm phân phối TT Viết tắt

1 M

2 Ek , k ≥ 1 là pha

3 Hk

𝒌 𝒋=𝟏

Ví dụ: Hệ thống hàng đợi M/M/3/20/1500/FCFS, có nghĩa là: - Thời gian giữa các lần đến liên tiếp tuân theo luật phân phối mũ - Thời gian phục vụ tuân theo luật phân phối mũ - 3 kênh phục vụ - Dung lƣợng hệ thống là 20: 3 phục vụ + 17 đợi - Nếu số yêu cầu đến trên 20, thì các yêu cầu trên 20 sẽ bị mất (lost) - Tổng số các yêu cầu 15000 có thể đƣợc phục vụ - Nguyên tắc phục vụ đến trƣớc phục vụ trƣớc Một ví dụ nữa để hiểu rõ hơn về kí hiệu Kendall là hệ thống hàng đợi

Trong đó: μj >0, qj>0, j{1..k}, 𝒒𝒋 = 𝟏

G/G/1, có nghĩa là G/G/1/∞/∞/FCFS, hệ thống có:

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Dung lƣợng hệ thống là vô hạn - Số lƣợng khách (population size) là vô hạn - Nguyên tắc phục vụ đến trƣớc phục vụ trƣớc - 1 kênh phục vụ - Thời gian giữa các lần đến liên tiếp theo luật phân phối G (General) - Phân phối thời gian phục vụ là: G Đối với bài toán mô phỏng siêu thị, xuất hiện những vấn đề đặt ra nhƣ dòng khách hàng đến mua hàng, thời gian mua hàng, số lƣợng hàng đƣợc mua, thời gian đến mua hàng, thời gian tham gia mua hàng ở siêu thị, thời

gian thanh toán tiền …. Nên nếu nhìn ở mức đơn giản, chỉ coi tổng thời gian tham gia xem hàng, mua hàng, thanh toán tiền là 1 tham số thì sẽ có một bài toán hệ thống phục vụ đơn giản với bài toán mô phỏng bãi gửi xe với 1 hàng đợi duy nhất, và mô hình là M/M/1, G/G/1. Tuy nhiên nếu nhìn nhận hệ thống phức tạp hơn, với bài toán thanh toán tiền, có thể có nhiều quầy thu ngân, ở đó có thể có những bài toán mô hình nhiều kênh phục vụ M/M/k, G/G/k.

Những dạng hàng đợi này sẽ đƣợc xem xét kỹ hơn ở các mục sau trong

Chƣơng này.

2.2. Hàng đợi M/M/k

2.2.1. Trạng thái ổn định của hàng đợiM/M/k

Hàng M /M / k có quá trình đến Poisson, thời gian phục vụ theo phân bố

mũ và k Server. Trong trƣờng hợp này chuỗi thời gian liên tục {l(t)}t≥0 với

. [4]

không gian trạng thái {0,1,2,...} là một quá trình sinh tử vô hạn có có tốc độ

𝜆

sinhλi = λ và tốc độ tử

> 𝑘 thì hệ

𝜇

* Khi λ>k𝜇hay cường độ lưu thông (traffic intensity) 𝜌 =

thống không đạt đƣợc trạng thái ổn định. Chuỗi 𝑙(𝑡) t≥0 không hồi qui

(transient). Số các khách hàng trong hệ thống sẽ dần đến vô hạn.

* Khi λ = kμ hay ρ = k , chuỗi 𝑙(𝑡) t≥0 hồi qui không (null - recurrent),

hệ thống cũng không đạt trạng thái ổn định. Số khách hàng trong hệ thống

không tiến về một trạng thái nào. Thời gian trung bình để hệ thống xuất phát

từ một trạng thái bất kỳ quay về lại trạng thái này là vô hạn.

* Khi λ

hệ thống đạt đƣợc trạng thái ổn định. Nghĩa là khi tốc độ đến nhỏ hơn tốc độ

phục vụ tối đa của hệ thống thì số khách hàng ở trong hệ thống có khuynh

hƣớng tiến về không và hệ thống quay trở lại trạng thái 1 nếu có một khách

hàng mới đến khi hệ thống đang rỗng.

* Tại thời điểm t bất kỳ đặt là khoảng thời gian cho đến khi khách hàng

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

tiếp theo rời khỏi hệ thống. Định lý Burke phát biểu rằng khi t →∞ thì d (t) có

phân bố mũ vớitham số λ và độc lập với số khách hàng trong hệ thống tại thời

điểm t. Nói cách khác, chuỗi giới hạn các khách hàng rời khỏi hệ thống M /M

/ k là một quá trình Poisson tham số λ (Burke, 1976).

2.2.2. Phân bố dừng của hàng đợi M/M/k

Khi hay thì hệ thống đạt trạng thái ổn định có phân bố

dừng thoả mãn [7]:

(2.1)

Từ điều kiện suy ra:

(2.2)

2.2.3. Hàng M /M / k / N

Đây là hàng có quá trình đến Poisson với tốc độ λ , thời gian phục vụ

có phân bố mũ tốc độ 𝜇 với k Server. Trạng thái của hệ thống bị giới hạn bởi

số lƣợng N. Khi một khách hàng đến hệ thống thì xảy ra hiện tƣợng sau: Nếu

đã có đủ N khách hàng trong hàng thì lập tức khách hàng này rời khỏi hệ

thống còn trƣờng hợp ngƣợc lại thì khách hàng sẽ xếp vào xếp hàng. Nhƣ vậy

không gian trạng thái của chuỗi 𝑙 𝑡 t≥0 là {0,1,…,N}, đây là một quá trình

sinh tử hữu hạn. Chuỗi l(t) chuyển từ trạng thái i đến i +1 khi một khách hàng

đến và đổi trạng thái i về i −1 khi một phục vụ vừa hoàn tất. Tốc độ sinh là

hằng số λi= λ với mọi 𝑖 = 1,2, …. Tốc độ tửμi= min(k,i)𝜇

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hệ thống đạt trạng thái ổn định với phân bố dừng thoả mãn:

(2.3)

(2.4)

Một vài trƣờng hợp đặc biệt

♦ Khi N →∞ ta có nhận đƣợc công thức (2.1)-(2.2) của trƣờng hợp

M/M/k.

♦ Khi N = k ta đƣợc công thức mất của Erlang (Erlang's loss formula).

Ví dụ: Về mô hình M/M/1 (mô hình xếp hàng một kênh, lƣợng khách

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hàng đến theo phân phối Poisson và thời gian phục vụ tuân theo hàm mũ).

2.2.4. Phát biểu bài toán:Một tổng đài quân sự có một trung kế gọi ra

mạng dân sự. Ƣớc tính có trung bình 15 cuộc gọi/giờ (cuộc gọi ra ngoài mạng

QĐ). Thời gian trung bình mỗi cuộc gọi là 3 phút

a. Xác định tải trọng của hệ thống

b. Tính % thời gian chờ của hệ thống

c. Tính số lƣợng cuộc gọi xếp hàng trong hệ thống

e. Tính xác suất khi hệ thống phục vụ hết cuộc gọi (call=0) và khi

d. Tính thời gian trung bình của cuộc gọi trong hệ thống

(call=4)

2.3. Hàng đợi G/G/1

Hệ thống có 1 Server, quá trình đến là tổng quát nhƣng các thời gian đến

trung gian tn độc lập, có cùng phân bố và có kỳ vọng chung là E[t1]. Thời

gian phục vụ trong mỗi chu kỳ cũng độclập, cùng phân bố và có kỳ vọng

chung E[s1]. Kendall ký hiệu hệ thống này là G/G/1 (cũng cókhi ký hiệu GI

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

/GI /1, ở đây I thay cho independence nghĩa là độc lập).

Ta sẽ đƣa ra 3 phƣơng pháp để phân tích các trƣờng hợp đặc biệt đối với

quá trình sắp hàng G/G/1.

- Phƣơng pháp thứ nhất đƣợc gọi là phương pháp phương trình tích

phân. Phƣơng pháp này đƣa bài toán tìm các phân bố giới hạn thời gian đợi

của khách hàng thứ n (khi n→∞) về bài toán giải phƣơng trình tích phân dạng

Wiener - Hopf.

- Phƣơng pháp thứ 2 khảo sát chuỗi Markov nhúng (Embedded

Markov Chain). Nếu quá trình đến là Poisson thì chuỗi Markov nhúng đƣợc

xét là độ dài của hàng tại những thờiđiểm khi có một khách hàng vừa đƣợc

phục vụ xong.

Nếu thời gian phục vụ có phân bố mũ và quá trình đến có phân bố tổng

quát thì chuỗi Markov nhúng có đƣợc bằng cách kê khai kích thƣớc của hàng

tại mỗi thời điểm khi có một khách hàng mới đến. Khi đó quá trình trở thành

một chuỗi Markov với cấu trúc đặc biệt.

-Phƣơng pháp thứ 3 nghiên cứu các tính chất của biến ngẫu nhiên W(t) là

thời gian một khách hàng phải đợi nếu anh ta đến hệ thống tại thời điểm t. Đại

lƣợng này đƣợc gọi là thời gian đợi thực sự của khách hàng với giả thiết

khách hàng đến hệ thống tại thời điểm t.

2.3.1. Phương pháp phương trình tích phân

Ký hiệu:

- Wn: là thời gian đợi của khách hàng thứ n (không bao gồm thời gian

phục vụ).

- sn: là thời gian phục vụ khách hàng thứ n .

- tn: là thời gian đến trung gian của khách hàng thứ n và thứ n +1. tn =

Tn+1-Tn

- Tn : là thời điểm khách hàng thứ n đến hệ thống,

với giả thiết W0 , s0 ,T0 đều bằng 0. Nghĩa là ta giả thiết rằng ngƣời thứ

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

nhất đến tại thời điểm t = 0 và không có ai đứng chờ trƣớc anh ta.

Rõ ràng Wn+ snlà khoảng thời gian khách hàng thứ n ở trong hệ thống

(thời gian chờ +thời gian phục vụ). Do đó, nếu tn>Wn+ snthì khi khách hàng

thứ n +1 đến sẽ không có ai trong hàng vì vậy thời gian đợi Wn+1= 0 . Trƣờng

hợp tn≤Wn+ sn thì thời gian đợi là Wn+ sn− tn. Tóm lại

(2.5)

Kí hiệu: Un = sn – tn và Z+ = max (Z,0) (2.6)

𝑈𝑛 ∞

𝑛=1là dãy các biến ngẫu nhiên độc lập, cùng phân bố với U. Giả sử Fn(x)là hàm phân bố của 𝑊𝑛và g(x) là hàm mật độ phân bố của U. Vì Wn và Un

Thì (2.7) Wn+1 = (𝑊𝑛 + 𝑠𝑛 − 𝑡𝑛 )+ = ( Wn + Un )+

𝐹𝑛 +1 𝑥 = 𝑃 𝑊𝑛+1 < 𝑥 = 𝑃 max⁡(𝑊𝑛 + 𝑈𝑛 ; 0) < 𝑥 = 𝑃 𝑊𝑛 + 𝑈𝑛 < 𝑥

𝐹

là các biến ngẫu nhiên độc lập, do đó với mọi x ≥ 0:

n(x-y)dy (2.8)

𝑦≤𝑥

∞ −∞

g(y)dy = = 𝑃 𝑊𝑛 + 𝑈𝑛 < 𝑥 𝑈𝑛 = y

Vì ngƣời thứ nhất đến hệ thống tại thời điểm t = 0 và không đợi nên

1 𝑛ế𝑢 𝑥 ≥ 0 0 𝑛ế𝑢 𝑥 < 0

(2.9) F1(x) =

Mặt khác: Fn(x) = 0 với mọi x <0, với mọi n = 0,1, 2,...Do đó

𝐹𝑛−1(x − y) − 𝐹𝑛 (x − y) g( y)dy

F1(x) − F2 (x) ≥ 0, ∀x∈ R.

Fn(x) - Fn+1(x) = 𝑦≤𝑥

Bằng qui nạp ta chứng minh đƣợc, với mọi n

(2.10) Fn(x) - Fn+1(x) ≥ 0, ∀x∈R.

∞ không tăng, không âm nên hội tụ về hàm F(x) ,∀x∈ 𝑛=1

Dãy hàm 𝐹𝑛 (x)

𝐹

R. Chuyển qua giới hạn của đẳng thức (2.8) ta đƣợc:

𝑦≤𝑥

(x-y)g(y) dy (2.11) F (x) =

Đặt z= x-y ta đƣợc:

∞ 0

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(x-y) dz = F(x)* g(x) (2.12) F (x) = − 𝐹(𝑧)𝐺

Từ đây ta có một số nhận xét nhƣ sau: [5]

𝑥 𝑔 𝑥

(i) Với mọi x < 0, F(x) = 0 .

∞ −∞

𝑥 𝑔(𝑥)

dx ≥ 0, thì F(x) = 0, ∀x∈R< 0 (ii) Nếu E[U ] =

∞ −∞

dx<0 thì F(x) là hàm phân bố (là hàm không (iii) Nếu E[U ] =

𝐹 𝑥 = 1

lim 𝑥→−∞

𝐹 𝑥 = 0 , lim 𝑥→∞

giảm, liên tục trái và thoả mãn:

Thời gian từ lúc một khách hàng rời khỏi hệ thống và hệ thống trở

thànhrỗng cho đến khi có một khách hàng tiếp theo đến hệ thống gọi là chu kỳ

rỗi của hệ thống. Ký hiệu chu kỳ rỗi thứ n là in . [8]

Nếu E[U]<∞ thì hệ thống đạt đƣợc trạng thái ổn định và thời gian đợi

trung bình trong hàng

E[ 𝑈2] −2E[𝑈]

2] E [ 𝑖1 2E [𝑖1]

- (2.13) Wq=

trong đó i1 là chu kỳ rỗi đầu tiên.

Nhận xét: Nếu ta tính đƣợc moment cấp1 và cấp 2 của thời gian rỗi i1

thì công thức (2.13) cho ta tính đƣợc thời gian đợi trung bình của hàng Wq.

Dựa vào "kết quả nhỏ" sẽ cho phép tính đƣợc các số đo hiệu năng còn lại

L, Lq và W .

2.3.2. Hàng đợi M/G/1

Ta giả thiết quá trình đến Poisson tốc độ λ, nghĩa là quá trình đến trung

gian tn có phân bố mũ tốc độ λ. Quá trình phục vụ 𝑠𝑛 đƣợc xét một cách

tổng quát nhƣng giả thiết thời gian phục vụ trong các chu kỳ là độc lập với

nhau và có cùng luật phân bố.

λ, E [t1

2 ] = 2 λ

E [t1]= 1

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Do đó cƣờng độ lƣu thông

𝜌

𝜆

E[s1 ] E[t1]

− ρ

> 0

ρ = , =λE [s1 ] ⇒ E 𝑠1 =

λ=1−ρ

-E [U1 ] = E [t1 - s1 ] = 1

E[U2 + 2

2] + 2(1−ρ)

1]= E[(s1-t1)2]= E[s1

2] - 2E[s1] 1

𝛌𝟐 = E [s1

𝛌𝟐

Mặt khác, vì quá trình đến là Poisson nên khoảng thời gian từ một thời

điểm bất kỳ đến lúccó một khách hàng tiếp theo đến hệ thống luôn có phân bố

mũ. Do đó thời gian từ lúc một khách hàng rời khỏi hệ thống và hệ thống trở

thành rỗng cho đến khi có một khách hàng tiếp theo đến hệthống (chu kỳ rỗi

2] = 2 𝛌𝟐

của hệ thống) cũng có phân bố mũ tốc độ λ.Vậy E [i1 ] = 1 ; E [i1

Thay vào công thức (2.13) ta đƣợc công thức Pollaczek - Khinchin (P-

E 𝑠1

2(1−ρ ) 𝛌𝟐

K)cho hàng M /G/1.

2 λ E 𝑠1 2(1−ρ)

2 𝛌𝟐 2 λ

2 + 2(1−ρ ) λ

- = (2.14) Wq =

(2.15) W = Wq + E [s1 ]

Từ "kết quả nhỏ" suy ra các số đo hiệu năng còn lại.

2.3.3. Các trường hợp đặc biệt của hàng đợi M/G/1

1) Hàng M /M /1:

Quá trình đến Poisson với tốc độ đến λ, thời gian phục vụ có phân bố mũ

2 ; = λ

tốc độ μ.

2 = 2 μ

2𝜆 𝜇 2

E [s1 ] = 2 ; E 𝑠1

)

𝜆 2(1− 𝜇

= 𝜆 (2.16)Wq = 𝜇 (𝜇 −𝜆)

𝜆

(2.17)

𝜇

𝜇 (𝜇 −𝜆)

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

= = (2.18) W= Wq + 1 + 1 𝜇

𝜇 (𝜇 −𝜆)

(2.19) ; Lq= 𝜆Wq= 𝜆2 L = 𝜆W = 𝜆 𝜇 −𝜆

2) Hàng M / D/1:

Quá trình đến Poisson với tốc độ đến λ, thời gian phục vụ không đổi tốc

2 =

độ μ.

2 ; = λ

2 - E [s1 ]2=0 ⇒E 𝑠1

λ μ 2

(2.20) E [s1 ]= 1 ; var [s1 ]= E 𝑠1

)

λ 2(1− μ

𝜆

Wq= (2.21) = λ 2μ(μ−λ)

𝜇

2𝜇 (𝜇 −𝜆)

= (2.22) W= Wq + 1 + 1 𝜇 = 2𝜇 −𝜆 2𝜇 (𝜇 −𝜆)

2𝜇 (𝜇 −𝜆)

L = 𝜆W = 𝜆2 (2.23) ; Lq= 𝜆Wq= 𝜆2 + 𝜆 𝜇 2𝜇 (𝜇 −𝜆)

3) Hàng M / Ek/1:

Quá trình đến Poisson với tốc độ đến λ, thời gian phục vụ ngẫu nhiên

2 =

độc lập có cùng phân bố Erlang- k với tốc độ μ.

2 + 1

2; = λ

2⇒E 𝑠1

2 = 1 kμ

kμ

(2.24) E [s1 ] = 1 ; var [s1 ]= 𝑘 = 𝑘 λ 0

)

λ (k +1) 𝑘 μ 2 λ 2(1− μ

Wq= (2.25) = (k+1)λ 2kμ(μ−λ)

(2.26) W= Wq + 1 = (k+1)λ 2kμ(μ−λ) + 1 μ

2kμ(μ−λ)

L = W = (k+1)λ 2 (2.27) ; Lq= Wq= (k+1)λ 2 + λ μ

Nhận xét:

1. Thời gian đợi trung bình mà một khách hàng phải mất ở hàng đợi là số

đo trễ xẩyra ở hệ thống sắp hàng. Ta có

𝑊𝑞𝑀 / 𝐷/1≤𝑊𝑞𝑀 / 𝐸𝑘 /1≤𝑊𝑞𝑀 / 𝐸/1

(2.28)

Khi k = 1 : 𝑊𝑞𝑀 / 𝐸𝑘 /1=𝑊𝑞𝑀 / 𝑀/1

Khi k →∞: lim𝑘→∞ 𝑊𝑞𝑀 / 𝐸𝑘 /1 =. 𝑊𝑞𝑀 / 𝐷/1 2. Xét hệ toạ độ trực chuẩn Oxy. Trên trục hoành ta chọn các hoành độ

μ(μ−λ)

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

nguyên k = 1, 2,..., trục tung chọn đơn vị là thì đồ thị của 𝑊𝑞𝑀 / 𝐸𝑘 /1

khi k làhyperbol 𝑘+1 2𝑘 = 1 2 + 1 2𝑘 đạt cực đại bằng 1 khi k = 1 và tiệm cận đến 1 2

→∞.

2μ(μ−λ)

3. Hệ số lớn nếu λ gần bằng μ. Nhƣ vậy khi tốc độ đến gần với tốc

độ phục vụthì hàng đợi tăng lên nhanh chóng tỉ lệ nghịch với hiệu số hai tốc

λ μ(μ − λ)

1 2

độ.

Hình 2.1: Đồ thị biểu diễn tốc độ phục vụ

2.3.4. Phương pháp chuỗi Markov nhúng áp dụng cho hàng G/M /1

Xét hệ thống sắp hàng có 1 server, các chu kỳ thời gian phục vụ sn độc

lập cùng có phân bố mũ tốc độ μ. Quá trình đến là độc lập, tổng quát, có cùng

phân bố và thời gian đến trung gian là biến ngẫu nhiên có hàm phân bố H(u).

Ta xét chuỗi Markov nhúng là số khách hàng trong hàng tại những thời

điểm khi có khách hàng mới đến hệ thống.

Gọi q là trạng thái của hệ thống khi có 1 ngƣời mới đến và gọi q'là trạng

thái sau khi có 1 ngƣời tiếp theo đến :

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

q'= q +1−N (2.29)

Trong đó N là số khách hàng đƣợc phục vụ trong chu kỳ giữa hai lần

đến. Vì phân bố mũ có tính chất "không nhớ" nên số khách hàng N đƣợc phục

vụ trong chu kỳ giữa 2 lần đến chỉ phụ thuộc vào độ dài của khoảng và q mà

không phụ thuộc vào phạm vi phục vụ mà khách hiện tại đã đƣợc nhận phục

vụ. Với các giả thiết này công thức (2.29) xác định chuỗi Markov có xác suất

0 𝑛ế𝑢 𝑗 > 𝑖 + 1

chuyển P= [ pij] thỏa mãn [6]:

𝑃 N = i + 1 − j 𝑛ế𝑢 𝑖 + 1 ≥ 𝑗 ≥ 1

(2.30) pij=P 𝑞′ = j⎤ 𝑞 = y =Wn+1

0 𝑛ế𝑢 𝑗 > 𝑖 + 1

Đặt ak= P{N = k} thì

𝑎𝑖+1−𝑗 𝑛ế𝑢 𝑖 + 1 ≥ 𝑗 ≥ 1

(2.31) pij=

Áp dụng công thức xác suất đầy đủ và từ giả thiết thời gian phục vụ có

∞

phân bố mũ với tốc độ μ có thể chứng minh đƣợc:

𝑘!

dH(u) (2.32) ak= 𝑒−μu 𝑢 𝑘 μ

trong đó H(u) là hàm phân bố của chu kỳ đến trung gian.

Cuối cùng các xác suất chuyển pi0 ( j = 0 ) là xác suất mà tất cả i

ngƣời trong hàng đã đƣợc phục vụ trƣớc khi có ngƣời mới đến.

pij

∞ 𝑗 =1 = 1- a0- a1 -…- ai

(2.33) pi0=1-

Vậy ma trận xác suất chuyển

0 0 𝑎0 0 𝑎1 𝑎0 𝑎2 𝑎1 … … … …

0 … … ⎤ 0 … … 0 … . 𝑎0 … . … … . . … . . .

𝑟0 𝑎0 𝑟1 𝑎1 𝑟2 𝑎2 𝑟3 𝑎3 … … … … trong đó ri= 1−a0 – a1−…−ai.

(2.34) P=

𝑘𝑎𝑘

∞ 𝑘=0

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Cƣờng độ lƣu thông ρ =1/

𝑘𝑎𝑘

∞ 𝑘=0

Hệ thống đạt trạng thái ổn định khi ρ< 1 hay

𝑖

Phân bố dừng

; i = 0,1,2,... (2.35) Π = [π0 ,π1,π2 ,...] có dạng π = (1−ξ0 )ξ

𝑘

trong đó ξ0 là nghiệm duy nhất của phƣơng trình

∞ 𝑘=0 ξ 𝑎𝑘

(2.36) f (ξ0 )= ξ0 (0<ξ0<1) với f(ξ)=

Thời gian đợi W

Nếu ρ < 1thì hệ thống đạt trạng thái ổn định, khi đó hàm phân bố độ dài của

hàng cũng đạt đến phân bố ổn định. Với điều kiện này ta xét thời gian đợi W .

Xác suất không phải đợi là r0 = 1−ξ0 .

Nếu khách hàng đến và đã có n ≥ 1 khách hàng ở trong hàng thì anh ta

phải đợi với tổng số n lần phục vụ có phân bố độc lập và cùng phân bố mũ

trƣớc khi đến lƣợt anh ta.

Ta biết rằng tổng của n phân bố mũ độc lập tham số μ là phân bố Erlang-

n −1

n tham số μ . Do đó

d , n≥ 1 (2.37)

eμτ

t P 𝑊 < t ⎤ có n người trong hàng = 0

𝑢 𝑛 τ (𝑛−1)!

n, 𝑛 ≥ 1

Mặt khác:

(2.38) P có n ngƣời trong hàng = π = 1 − ξ 0 ξ0

P 𝑊 < t ⎤ có n người trong hàng P có n ngƣời trong hàng .

Áp dụng công thức xác suất đầy đủ ta đƣợc W(t) =P 𝑊 < t

∞ 𝑛=1

n −1

+ π0

e−μτd

t =(1 − ξ0) 0

𝑢 𝑛 τ (𝑛−1)!

+(1 − ξ0).

(2.39) W(t)=(1 − ξ0) + ξ0( 1 − e−μt(1−ξ0) )

2.3.5. Các cận trên của thời gian đợi trung bình của hàng

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Để tính các số đo hiệu năng của hàng ta có công thức (2.13) và "kết quả

nhỏ".Tuy nhiên trong trƣờng hợp tổng quát chƣa có qui tắc tính E[i1] và E[𝑖1

G/G/1

Thay cho công thức tính chính xác ngƣời ta tìm các cận trên và cận dƣới

của chúng. Ở đây ngƣời ta nêu một vài cận trên cho Wq

2] E[𝑈. −2E[𝑈]

2] E[𝑖1 E[𝑖1]

Vì số hạng (2.40) ≥ 0 nên Wq≤

- Mặt khác ta còn có thể chứng minh đƣợc là:

var [𝑈]

−2E[U]Wq ≤ var[U] và − 2E[U] > 0

−2E[𝑈]

do đó Wq≤ (2.41)

3. Khi cƣờng độ lƣu thông ρ→ 0 thì thời gian rỗi i1 tiến đến 0. Điều này

làm cho E[𝑖1

2] E[𝑖1 E[𝑖1]

] →0 vì vậy tiến đến 0 nhanh hơn E[i1]. Do đó [

(2.42)

2.4. Một số bài toán tổng quát trong siêu thị

Bài toán 1:

Trong một ngày siêu thị mở cửa phục vụ trong thời gian là t giờ, tại bãi

đỗ xe của siêu thị có n vị trí đỗ xe ô tô, mỗi vị trí chỉ đỗ đƣợc duy nhất 1 xe.

Cứ trung bình t’giây thì có một xe đến mua hàng, thời gian khách vào mua

hàng chính là thời gian mà ô tô của khách đỗ tại bãi gửi xe. Yêu cầu của bài

toán là mô phỏng lại hoạt động của bãi đỗ xe trong một ngày làm việc.

Bài toán 2:

Siêu thị có một bãi đậu xe với số lƣợng n vị trí đỗ xe. Nếu tất cả các vị trí

đều có xe thì bãi đậu xe sẽ thông báo không nhận thêm xe và khi đó phải tìm vị

trí đậu xe ở ngoài khu vực của siêu thị. Thời gian khách hàng đi từ bãi đậu xe

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

vào đến siêu thị đƣợc ƣớc tính khoảng t giây theo một hàm phân bố đều. Tại

siêu thị có m xe đẩy cho khách mua hàng và m’ giỏ hàng xách tay cho các khách

hàng mua sắm nhỏ (số lƣợng mua hàng nhỏ hơn 10 loại hàng hóa). Phục vụ siêu

thị có x quầy thu ngân, trong đó quầy số 1 là quầy phục vụ các khách hàng mua

nhanh với một số lƣợng hàng tối thiểu (nhỏ hơn 10 loại hàng hóa).

Luồng khách hàng (xe ô tô) đến mua hàng đƣợc phân bố trong khoảng

thời gian trung bình từ giây. Nếu bãi xe có chỗ trống thì khách hàng sẽ vào

đậu xe và mua hàng.

Nếu ngƣời mua hàng mua nhiều hơn 10 loại hàng hóa thì họ sẽ lấy xe

đẩy, trong trƣờng hợp ngƣợc lại, họ chỉ lấy giỏ hàng xách tay. Sau khi ngƣời

mua hàng lấy xe đẩy hay giỏ xách tay, có thể coi số hàng họ mua là những

con số ngẫu nhiên trong miền giá trị từ 5 đến 100 loại hàng.

Thời gian mua hàng của 1 khách hàng đƣợc tính bằng tỷ lệ số lƣợng

hàng đƣợc mua nhân với thời gian chi phí cho 1 món hàng là giây.

Khi mua hàng xong, ngƣời khách hàng sẽ đến quầy thu ngân để trả tiền,

quầy thu ngân sẽ mất thời gian tƣơng ứng cho việc thanh toán của 1 khách

hàng là 2 giây cho mỗi món hàng và cộng thêm một khoảng thời gian T giây

cho một khách hàng.

Sau khi mua hàng xong, khách hàng sẽ mất thời gian từ giây cho

việc ra khỏi siêu thị để lên xe ô tô và ra khỏi bãi đậu xe.

Các yêu cầu đặt ra:

1. Xây dựng mô phỏng mô hình làm việc của siêu thị trong thời gian

của 1 ca làm việc liên tục (8 tiếng đồng hồ).

2. Đƣa ra các con số đặc trƣng của siêu thị này: hệ số sử dụng của các

loại xe đẩy, giỏ hàng, của các quầy thu ngân.

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

2.5. Quy trình sử dụng GPSS mô phỏng hàng đợi

GPSS World có một ƣu điểm là tính trong suốt với các dẫn chứng cụ thể

nhƣ sau:[5]

- Đầu tiên, nếu chúng ta mô phỏng theo dạng "hộp đen" (Black-Box),

chúng ta không thể quan sát bên trong hộp này có những thành phần gì, chúng

hoạt động ra sao, tƣơng tác với nhau thế nào. Điều này dẫn đến việc chúng ta

không thể kiểm soát đƣợc hộp đen ngay tại thời điểm làm việc, cũng nhƣ

không thể dự đoán đƣợc hành vi của nó trong tƣơng lai. Đó là điều không ai

muốn.

- Thứ hai, chỉ thật sự có lợi cả về mặt mục tiêu cũng nhƣ về vấn đề thời

gian khi và chỉ khi chúng ta mô phỏng thành công. Trên cơ sở đó, khi có sự

thay đổi nhân lực, những thành viên mới đến làm việc sẽ hiểu đƣợc và tiếp

quản đƣợc những công việc đã làm, cũng nhƣ phát triển tiếp sau này.

- Thứ ba, một vấn đề nhỏ nhƣng có ý nghĩa khi mô phỏng. Đó là làm sao

chúng ta có thể nhận thấy động lực học bên trong (Internal Dynamics) hệ

thống tại thời điểm quyết định khi một ngƣời có kinh nghiệm tiến hành mô

phỏng.

GPSS World đƣợc thiết kế với những điểm mạnh có thể liệt kê nhƣ:

- Là ngôn ngữ hƣớng đối tƣợng, chạy đƣợc trên nhiều nền tảng hệ điều

hành khác nhau nhƣ Windows, Linux.

- Hình ảnh hóa các mô hình, từ đó giúp ngƣời dùng hiểu rõ, nắm bắt mô

hình tốt nhất có thể, đồng thời sao lƣu lại dƣới dạng hình ảnh thống kê dễ

hiểu.

- Khả năng tƣơng tác của nó giúp ngƣời dùng dễ dàng tìm hiểu và vận

hành các bài toán mô phỏng nhờ giao diện thân thiện.

- Tích hợp các cở sở phân tích dữ liệu để tính toán các thành phần trong

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hệ thống một cách trực quan.

- Là công cụ có thể làm nhiều việc khác nhau tại một thời điểm

(Multitask) và hoạt động trên cơ sở sử dụng bộ nhớ ảo, do đó không tốn kém

tài nguyên của máy tính.

Để nghiên cứu các bài toán hàng đợi nói chung và siêu thị nói riêng,

cần tiến hành theo 7 bƣớc để thực hiện mô phỏng trên công cụ GPSS[1]:

Bƣớc 1:Đánh giá bài toán theo ghi chú Kendall để xác định các yếu tố

A/B/m/K theo lý thuyết hàng đợi

Bƣớc 2: Xác định A, B thuộc loại phân phối xác suất nào (mục 2.2)

Bƣớc 3: Sau khi xác định xong A, B thì chúng ta chọn lựa các tham số

theo hàm GENERATE của GPSS.

Bƣớc 4: Thiết lập lƣu đồ thuật toán, lập các biến, các Block, các

Transaction… theo yêu cầu của bài toán

Bƣớc 5: Viết mã nguồn cho bài toán dựa theo giải thuật.

Bƣớc 6: Chạy chƣơng trình, sửa lỗi trong quá trình viết mã nguồn…

Bƣớc 7: Hiển thị kết quả, đánh giá kết quả trong sự so sánh với tính toán

lý thuyết từ mô hình đƣợc trình bày trong các mục 2.3, 2.4 của chƣơng này.

2.6. Kết luận chƣơng

Trong chƣơng này trình bày về một số dạng bài toán tổng quát sử dụng

hàng đợi trong siêu thị BigC Hà Nội. Bên cạnh đó, chƣơng này còn trình bày

các hàng đợi cơ bản và phân tích một số các ƣu điểm, nhƣợc điểm của các hệ

thống hàng đợi, từ đó đánh giá và đƣa ra các mô hình hàng đợi sử dụng cho

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

bài toán mô phỏng trong siêu thị BigC Hà Nội.

Chƣơng 3

BÀI TOÁN MÔ PHỎNG BÃI GỬI XE TẠI

SIÊU THỊ BIG C – HÀ NỘI

3.1 Bài toán bãi xe tại siêu thị (mô hình hoạt động đơn giản)

3.1.1 Mô tả bài toán

Tại bãi đỗ xe của siêu thị BigC Hà Nội có 100 chỗ đỗ xe, mỗi chỗ chỉ

đỗ đƣợc đúng 1 chiếc. Cứ trung bình 30 ± 5 giây thì có một xe đến mua hàng.

Thời gian xe ô tô đậu ở bãi đậu xe đƣợc tính là thời gian khách hàng vào mua

hàng và là một khoảng thời gian đƣợc phân bố theo dạng hàm mũ

(EXPONENTIAL) với giá trị trung bình là 60 phút.

- Cần 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.

3.1.2 Phân tích bài toán

- Mô hình phân tích

Hình 3.1: Mô hình hàng đợi của bãi xe

Các xe ô tô xếp hàng đi vào bãi gửi xe theo cƣờng độ xuất hiện là 30±5

giây, tức là λ = 1/30. Bãi xe có kích cỡ là 100 chỗ gửi xe, mỗi xe ở trong bãi

trung bình 60 phút (tƣơng đƣơng 3600 giây), tức là mỗi kênh phục vụ sẽ có

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

cƣờng độ phục vụ là μ=1/3600.

- Sơ đồ thuật toán

Bắt đầu

Hết thời gian

Kiểm tra thời gian mô phỏng

Còn thời gian mô phỏng

Sinh ngẫu nhiên xe vào bãi

End

30±5 giây

Kiểm tra bãi xe

còn trống hay

không

Xe vào bãi, ở đó 60

Xe bỏ đi

phút

Xe ra khỏi bãi, giải

phóng chỗ trống

Hình 3.2: Sơ đồ thuật toán mô phỏng bãi xe

3.1.3 Giải bài toán

- Với thời gian mô phỏng là 8h, tổng thời gian mô phỏng là T=8.60.60 =

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

28800 giây. Theo lý thuyết về bài toán hàng đợi M/M/k với k = 100, ta sẽ có

- Số xe ô tô đến siêu thị là:

N1 = T.λ = 28800. 1/30 = 960 (xe)

- Số xe ô tô có thể đƣợc phục vụ tại siêu thị là:

N2 = 100.T.μ = 100.28800.1/3600 = 800 (xe)

- Số xe không vào siêu thị là 960 – 800 = 160 (xe)

3.1.4 Mô hình GPSS World

******************************************************* * Mô hình bãi đậu xe tại siêu thị * * MESTA STORAGE 100 ;Số chỗ đậu xe trong bãi đỗ là 100 chiếc. GENERATE 30,5,,,1;trung bình 30 +- 5 giây có 1 khách hàng đến siêu thị GATE SNF MESTA,OTKAZ ;Kiểm tra bãi đỗ xe còn trống hay không * ENTER MESTA ;Xe đi vào vị trí còn trống ADVANCE (EXPONENTIAL (1,0,3600));Thời gian xe ô tô sử dụng bãi đỗ xe LEAVE MESTA ;Giải phóng vị trí đỗ xe TERMINATE ; OTKAZ TERMINATE 0 GENERATE 28800 ;Thời gian mô phỏng là 8x60x60 giây TERMINATE 1 ; START 1 ; Kết quả thực hiện: GPSS World Simulation Report - sieuthi_1.14.1 Sunday, April 12, 2015 10:10:25 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 28800.000 9 0 1 NAME VALUE MESTA 10000.000 OTKAZ 7.000 LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY 1 GENERATE 961 0 0 2 GATE 961 0 0 3 ENTER 845 0 0 4 ADVANCE 845 95 0 5 LEAVE 750 0 0 6 TERMINATE 750 0 0 OTKAZ 7 TERMINATE 116 0 0 8 GENERATE 1 0 0 9 TERMINATE 1 0 0 STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY MESTA 100 5 0 100 845 1 90.106 0.901 0 0

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Kết quả mô phỏng cho thấy nhƣ sau:

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

- Số xe ô tô vào đƣợc vào siêu thị để mua hàng: 845 xe.

- Số xe ô tô đã đƣợc phục vụ xong là: 750 xe

- Số xe ô tô vẫn đang còn ở trong bãi đỗ xe của siêu thị sau khi kết thúc

8h mô phỏng là: 95 xe

- Số xe ô tô không vào đƣợc siêu thị (bỏ về): 116 xe

Nhận xét:

Bảng 3.1. So sánh kết quả tính toán theo lý thuyết với tính toán trong GPSS với thờ i gian T = 8 giờ

Tính toán theo lý thuyết Tính toán trong GPSS

Số xe ô tô đến siêu thị 960 961

Số xe ô tô đƣợc vào phục vụ tại siêu thị 800 845

Số xe ô tô đã đƣợc phục vụ tại siêu thị 800 750

Số xe ô tô không vào đƣợc siêu thị 160 116

95 Số xe ô tô vẫn ở bãi xe sau khi kết thúc ca làm việc 8h Không tính được

3.2 Bài toán mô phỏng hoạt động của siêu thị

3.2.1 Mô tả bài toán

Siêu thị BigC Hà Nội có một bãi đậu xe với số lƣợng 100 chỗ. Nếu tất

cả các chỗ đều có xe thì bãi đậu xe sẽ thông báo không nhận thêm xe và khi

đó phải tìm chỗ đậu xe ở ngoài khu vực của BigC. Thời gian khách hàng đi từ

bãi đậu xe vào đến siêu thị đƣợc ƣớc tính khoảng 60 ± 40 giây theo một hàm

phân bố đều. Tại siêu thị có 100 xe đẩy cho khách mua hàng và 50 giỏ hàng

xách tay cho các khách hàng mua sắm nhỏ (số lƣợng mua hàng nhỏ hơn 10

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

loại hàng hóa). Phục vụ siêu thị có 5 quầy thu ngân, trong đó quầy số 1 là

quầy phục vụ các khách hàng mua nhanh với một số lƣợng hàng tối thiểu

(nhỏ hơn 10 loại hàng hóa).

Luồng khách hàng (xe ô tô) đến mua hàng đƣợc phân bố trong khoảng

thời gian trung bình từ 30 ± 5 giây. Nếu bãi xe có chỗ trống thì khách hàng sẽ

vào đậu xe và mua hàng.

Nếu ngƣời mua hàng mua nhiều hơn 10 loại hàng hóa thì họ sẽ lấy xe

đẩy, trong trƣờng hợp ngƣợc lại, họ chỉ lấy giỏ hàng xách tay. Sau khi ngƣời

mua hàng lấy xe đẩy hay giỏ xách tay, có thể coi số hàng họ mua là những

con số ngẫu nhiên trong miền giá trị từ 5 đến 100 loại hàng.

Thời gian mua hàng của 1 khách hàng đƣợc tính bằng tỷ lệ số lƣợng

hàng đƣợc mua nhân với thời gian chi phí cho 1 món hàng là 60 giây.

Khi mua hàng xong, ngƣời khách hàng sẽ đến quầy thu ngân để trả tiền,

quầy thu ngân sẽ mất thời gian tƣơng ứng cho việc thanh toán của 1 khách

hàng là 2 giây cho mỗi món hàng và cộng thêm một khoảng thời gian T = 90

giây cho một khách hàng.

Sau khi mua hàng xong, khách hàng sẽ mất thời gian từ 60 ± 50 giây

cho việc ra khỏi siêu thị để lên xe ô tô và ra khỏi bãi đậu xe.

Các yêu cầu đặt ra:

3. Xây dựng mô phỏng mô hình làm việc của siêu thị trong thời gian

của 1 ca làm việc liên tục (8 tiếng đồng hồ).

4. Đƣa ra các con số đặc trƣng của siêu thị này: hệ số sử dụng của các

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

loại xe đẩy, giỏ hàng, của các quầy thu ngân.

3.2.2 Phân tích bài toán

Bãi xe đầy

Quầy số 1: Phục vụ nhanh

50 giỏ

Bãi xe 100 chỗ

Khách hàng 60± 40

100 xe đẩy

Quầy 2,3,4,5: Phục vụ thƣờng

- Mô phỏng hình ảnh thực tế

Hình 3.3: Mô hình minh họa hoạt động của siêu thị

Bãi xe

đầy

Khách

Phục vụ

hàng dùng

nhanh

xe đẩy

Khách

Bãi xe

hàng

100 chỗ

(60 ±40)

Khách

Phục vụ

hàng dùng

thƣờng

giỏ

- Mô hình phân tích

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.4: Mô hình hoạt động các hàng đợi của siêu thị

- Sơ đồ thuật toán

Star

t

Hết thời gian

Kiểm tra thời gian

mô phỏng

Còn thời gian mô phỏng

Sinh ngẫu nhiên

End

xe vào bãi 30±5

giây Kiểm tra

bãi xe còn

Xe rời bãi

trống hay

Xe bỏ đi

Xe vào bãi, không

Xác định

các giá trị

khách hàng vào Khách hàng mua hàng chọn xe đẩy,

Hình 3.5. Sơ đồ thuật toán mô phỏng hàng đợi của siêu thị

thời gian

giỏ hàng, chọn

khách mua 3.2.3 Giải bài toán

hàng, thanh - Số lƣợng khách hàng (xe ô tô xuất hiện) đến mua hàng là: hàng toán tiền

28800. 1/30 = 960

- Tỷ lệ giữa khách hàng mua từ 2 đến 9 món hàng (mua bằng giỏ hàng)

với khách hàng mua bằng xe đẩy (từ 10 đến 99 món hàng) là: 7/40.

- Thời gian trung bình một khách hàng ở siêu thị là:

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

+ Thời gian gửi xe: 60 (giây)

+ Thời gian mua hàng: số món hàng x 60 giây: (100+6)/2 . 60 = 3180 (giây)

+ Thời gian thanh toán tiền: (100+6)/2 .2 + 90 = 196 (giây)

+ Thời gian mang hàng ra xe và rời khỏi bãi xe:60 (giây)

+ Tổng thời gian: 3496 (giây)

- Số lƣợng khách hàng có thể đƣợc phục vụ ở siêu thị là: 28800/3496 x

100 = 823.

3.2.4 Mô hình GPSS World

3.2.4.1 Cách tiếp cận để giải quyết bài toán đặt ra

Xuất hiện một số điểm đặc biệt đáng phải lƣu ý khi giải quyết các yêu

cầu đặt ra: Cần thiết phải thiết lập một luồng các khách hàng đến siêu thị

trong một khoảng thời gian là 1 ca làm việc. Trong khoảng thời gian mô

phỏng, cần xác định một đơn vị chung để tiến hàng mô phỏng đƣợc tính bằng

giây, do đặc điểm các đơn vị thời gian khác nhau ở mỗi hàng đợi, vì vậy tổng

thời gian mô phỏng sẽ là 8x60x60 giây. Thiết lập mô hình mô phỏng và có thể

tách chúng thành một số khối (Block) khác nhau nhƣ:

+ Block 1 mô tả các thông tin về các hàm làm việc của siêu thị;

+ Block 2 mô tả các thông tin về lƣợng khách hàng đến mua hàng, xác

định số lƣợng hàng đƣợc mua theo hƣớng từ việc các khách hàng lựa chọn xe

đẩy hay giỏ hàng.

+ Trong Block 3 sẽ mô tả và tính toán các giá trị thống kê tại các hàng

đợi trong việc lấy giỏ hàng;

+ Trong Block 4 sẽ mô tả và tính toán các giá trị thống kê tại các hàng

đợi trong việc lấy xe đẩy;

+ Block 5 sẽ mô phỏng các yêu cầu dịch chuyển theo từng trạng thái

hệ thống;

+ Trong Block 6 sẽ đƣ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);

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

+ Block 7 sẽ đƣa ra số liệu thống kê đối với các quầy thu ngân khác;

+ Block 8 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;

+ Block 9 mô tả các luồng khách hàng đến tham gia mua hàng;

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

3.2.4.2 Chương trình bằng ngôn ngữ GPSS để mô phỏng bài toán

; Block 1

RMULT 1187

; xác định một tập hợp các hệ số nhân tƣơng ứng cho

; bộ sinh số ngẫu nhiên

kassa_2 EQU 2

; quy định cụ thể số lƣợng các kênh dịch vụ và tƣơng ứng

; với hàng đợi cho họ

kassa_N EQU 5

; số lƣợng quầy thu ngân là 5.

time_work VARIABLE 8#60#60 ; xác định hệ thống mô phỏng tính bằng giây

n_pokupok VARIABLE (RN1@96+5) ; số lƣợng hàng mua mỗi ngƣời mua từ 5

;đến 100 món hàng

finance VARIABLE (RN1@3+1)#40+150 ; biến xác định số tiền thanh toán

; Mua sắm

time_system TABLE M1,1000,1000,7

; tạo ra một bảng đại diện cho

; Một tập hợp các số cho biểu đồ

pokupki TABLE P$kol_pokupok,10,10,10 ; mỗi số nguyên

; Đại diện cho một lớp của các tần số trong biểu đồ

n_pokupatel TABLE X$pokupatel,100,50,12

park STORAGE 100

; năng lực của các bãi đậu xe, số lƣợng xe cho phép

telejka STORAGE 100

; số lƣợng xe đẩy cho phép

korzina STORAGE 50

; số giỏ

kassir VARIABLE (P$kol_pokupok)#2+90 ; biến quy định cụ thể

; thời gian của nhân viên thu ngân tại ngƣời mua dịch vụ

time_mag VARIABLE P$kol_pokupok#60 ; thời gian tìm kiếm hàng của một ngƣời

;mua hàng

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

INITIAL X$pokupatel,0 ; xác định giá trị ban đầu

; giá trị của ai là giá trị đƣợc lƣu trữ trong đầu của sự thay đổi là 0

******************************************

; Block 2

parking TRANSFER Both,,Lost

; nếu bãi xe rảnh thì phục vụ, ngƣợc lại sẽ

;chuyển sang Lost

ENTER park

; Cho xe vào bãi gửi

ADVANCE 60,40

;ngƣời mua vào siêu thị

SAVEVALUE pokupatel+,1

;tăng số lƣợng ngƣời mua hàng lên 1

ASSIGN kol_pokupok,V$n_pokupok

;gán tham biến cho giá trị số lƣợng hàng

;hóa đƣợc mua

ASSIGN oplata,V$finance

; Gán các tham biến cho việc thanh toán tiền

TEST LE P$kol_pokupok,10,Qtelejka

; xác định ngƣời mua hàng bằng xe đẩy

; hay giỏ hàng

GATE SNF korzina,Qtelejka ; kiểm tra số lƣợng còn lại của xe đẩy và giỏ hàng

*******************************************

; Block 3

QUEUE korzina_Q

; Hàng đợi của giỏ hàng

ENTER korzina

; thu thập thông tin về việc sử dụng giỏ hàng

DEPART korzina_Q

; giải phóng hàng đợi

ASSIGN tara,korzina

; Gán các tham biến của giỏ hàng

TRANSFER ,magazin

; chuyển các yêu cầu từ thời điểm khách vào siêu thị

*********************************************

; Block 4

Qtelejka QUEUE telejka_Q

; Hàng đợi của xe đẩy

ENTER telejka

; Thu thập thông tin về việc sử dụng xe đẩy

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DEPART telejka_Q

; giải thoát hàng đợi

ASSIGN tara,telejka

; Gán các tham biến của xe đẩy

**********************************************

; Block 5

magazin ADVANCE V$time_mag ;Thời gian mua hàng của khách hàng trong

;siêu thị

TEST LE P$kol_pokupok,10,min_och ;xác định hình thức của ngƣời mua hàng

COUNT L kassir_0,kassa_2,kassa_n,1,Q ; xác định số lƣợng đối tƣợng

;thỏa mãn các yêu cầu đầu bài

TEST E P$kassir_0,0,min_och

; xác định các yêu cầu tiếp theo

**********************************************

; Block 6

QUEUE bistro_q ; Lấy các thông tin thống kê hàng đợi của quầy phục vụ nhanh

SEIZE bistro

DEPART bistro_q

; Giải phóng hàng đợi

ADVANCE V$kassir

; Lấy thời gian phục vụ ở quầy phục vụ nhanh

RELEASE bistro

LEAVE P$tara

;hoàn thành việc thống kê hàng đợi ở quầy phục vụ nhanh

TRANSFER ,fin

; chuyển đối tƣợng đến block FIN

**********************************************

; Block 7

min_och SELECT MIN min_ocher,kassa_2,kassa_n,,Q

; chọn đối tƣợng

;thỏa mãn điều kiện

QUEUE P$min_ocher

SEIZE P$min_ocher

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DEPART P$min_ocher

ADVANCE V$kassir

RELEASE P$min_ocher

LEAVE P$tara

**********************************************

; Block 8

fin TABULATE time_system

; đặt thời gian để mô phỏng

TABULATE pokupki

; Lấy thông tin về số lƣợng hàng hóa đƣợc mua

SAVEVALUE pokupatel-,1

; giảm số lƣợng khách hàng 1 đơn vị

ADVANCE 60,50 ;

LEAVE park

TERMINATE

lost TERMINATE

********************************************

; Block 9

GENERATE 30,5,,,1

; Sử dụng hàm phân bố xác suất

; đối với khách mua hàng

TRANSFER ,parking

**********************************************

; Block 10

GENERATE V$time_work

; xác định thời gian mô phỏng của hệ thống

TABULATE n_pokupatel

; Lấy thông tin về số lƣợng khách đến siêu thị

TERMINATE 1

START 1

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Kết quả của quá trình mô phỏng:

GPSS World Simulation Report - sieuthi_2.7.1

Sunday, April 12, 2015 16:22:42

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 28800.000 47 5 3

NAME VALUE

BISTRO 10028.000

BISTRO_Q 10027.000

FIN 36.000

FINANCE 10010.000

KASSA_2 2.000

KASSA_N 5.000

KASSIR 10017.000

KASSIR_0 10025.000

KOL_POKUPOK 10020.000

KORZINA 10016.000

KORZINA_Q 10024.000

LOST 42.000

MAGAZIN 18.000

MIN_OCH 29.000

MIN_OCHER 10026.000

N_POKUPATEL 10013.000

N_POKUPOK 10009.000

OPLATA 10021.000

PARK 10014.000

PARKING 1.000

POKUPATEL 10019.000

POKUPKI 10012.000

QTELEJKA 14.000

TARA 10023.000

TELEJKA 10015.000

TELEJKA_Q 10022.000

TIME_MAG 10018.000

TIME_SYSTEM 10011.000

TIME_WORK 10008.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

PARKING 1 TRANSFER 960 0 0

2 ENTER 671 0 0

3 ADVANCE 671 2 0

4 SAVEVALUE 669 0 0

5 ASSIGN 669 0 0

6 ASSIGN 669 0 0

7 TEST 669 0 0

8 GATE 45 0 0

9 QUEUE 45 0 0

10 ENTER 45 0 0

11 DEPART 45 0 0

12 ASSIGN 45 0 0

13 TRANSFER 45 0 0

QTELEJKA 14 QUEUE 624 0 0

15 ENTER 624 0 0

16 DEPART 624 0 0

17 ASSIGN 624 0 0

MAGAZIN 18 ADVANCE 669 65 0

19 TEST 604 0 0

20 COUNT 44 0 0

21 TEST 44 0 0

22 QUEUE 37 0 0

23 SEIZE 37 0 0

24 DEPART 37 0 0

25 ADVANCE 37 0 0

26 RELEASE 37 0 0

27 LEAVE 37 0 0

28 TRANSFER 37 0 0

MIN_OCH 29 SELECT 567 0 0

30 QUEUE 567 27 0

31 SEIZE 540 0 0

32 DEPART 540 0 0

33 ADVANCE 540 4 0

34 RELEASE 536 0 0

35 LEAVE 536 0 0

FIN 36 TABULATE 573 0 0

37 TABULATE 573 0 0

38 SAVEVALUE 573 0 0

39 ADVANCE 573 2 0

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

40 LEAVE 571 0 0

41 TERMINATE 571 0 0

LOST 42 TERMINATE 289 0 0

43 GENERATE 960 0 0

44 TRANSFER 960 0 0

45 GENERATE 1 0 0

46 TABULATE 1 0 0

47 TERMINATE 1 0 0

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

2 143 0.941 189.538 1 821 0 0 0 6

3 133 0.896 193.969 1 736 0 0 0 7

4 130 0.879 194.695 1 779 0 0 0 7

5 134 0.872 187.480 1 823 0 0 0 7

BISTRO 37 0.135 105.297 1 0 0 0 0 0

QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY

2 10 6 149 6 5.718 1105.207 1151.579 0

3 10 7 140 4 5.449 1120.991 1153.962 0

4 10 7 137 3 5.253 1104.265 1128.987 0

5 9 7 141 3 5.031 1027.637 1049.977 0

TELEJKA_Q 1 0 624 624 0.000 0.000 0.000 0

KORZINA_Q 1 0 45 45 0.000 0.000 0.000 0

BISTRO_Q 1 0 37 34 0.006 4.402 54.290 0

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

PARK 100 0 0 100 671 1 93.710 0.937 0 0

TELEJKA 100 5 0 100 624 1 90.202 0.902 0 0

KORZINA 50 49 0 3 45 1 0.894 0.018 0 0

TABLE MEAN STD.DEV. RANGE RETRY FREQUENCY CUM.%

TIME_SYSTEM 4190.597 1979.354 0

- 1000.000 46 8.03

1000.000 - 2000.000 25 12.39

2000.000 - 3000.000 101 30.02

3000.000 - 4000.000 117 50.44

4000.000 - 5000.000 71 62.83

5000.000 - 6000.000 79 76.61 6000.000 - _ 134 100.00

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Kết quả mô phỏng cho thấy nhƣ sau:

- Số xe ô tô (khách hàng) đến mua hàng: 960

- Số khách hàng vào đƣợc siêu thi (gửi xe): 671

- Số khách hàng bỏ về: 289

- Số khách hàng vào đƣợc siêu thị nhƣng chƣa mua hàng: 2

- Số khách hàng thực hiện mua hàng: 669

- Số khách hàng mua hàng bằng giỏ hàng: 45

- Số khách hàng mua hàng bằng xe đẩy: 624

- Số khách hàng đã thực hiện thanh toán: 604

- Số khách hàng mua dƣới 10 món hàng: 44

- Số khách hàng đƣợc phục vụ tại quầy thanh toán nhanh: 37

- Số khách hàng thanh toán tại các quầy khác: 567

+ quầy số 2: 149

+ quầy số 3: 140

+ quầy số 4: 137

+ quầy số 5: 141

- Hiệu suất sử dụng của quầy thanh toán nhanh: 0,135

- Hiệu suất sử dụng của quầy số 2: 0,941

- Hiệu suất sử dụng của quầy số 3: 0,896

- Hiệu suất sử dụng của quầy số 4: 0,879

- Hiệu suất sử dụng của quầy số 5: 0,872

- Hiệu suất sử dụng của xe đẩy: 0,902

- Hiệu suất sử dụng của giỏ hàng: 0,018

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Hiệu suất sử dụng bãi đậu xe: 0,937

Nhận xét

Bảng 3.2: So sánh kết quả tính toán theo lý thuyết với tính toán trong GPSS với T = 8 giờ

Tính toán theo lý thuyết Mô phỏng trong GPSS

960 960 Số lƣợng khách hàng (xe ô tô xuất hiện) đến mua hàng trong 8 giờ

Số lƣợng khách hàng đƣợc phục vụ 823 669

Qua các kết quả thực nghiệm thu đƣợc cho thấy: Kết quả mô phỏng và

tính toán trong GPSS World phù hợp với kết quả tính toán theo lý thuyết.

Đồng thời, khi thời gian càng tăng (độ lấy mẫu càng lớn) thì độ chính xác

giữa kết quả tính toán lý thuyết và kết quả mô phỏng theo GPSS càng cao.

Đây chỉ là các bài toán hệ thống phục vụ đám đông điển hình, việc tính toán

bằng công thức toán học không quá phức tạp. Trong thực tế, có rất nhiều hệ

thống có mô hình phức tạp hơn; số lƣợng nguồn yêu cầu tăng; số lƣợng kênh

phục vụ nhiều hơn; quy luật phục vụ cũng nhƣ thời gian phục vụ theo các quy

luật phân bố khác nhau… Khi đó 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 này, 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ả.

3.3. Đánh giá, so sánh kết quả mô phỏng

Trong các mục 3.1, 3.2 đã tiến hành mô phỏng 2 mô hình hàng đợi

khác nhau, với mô hình tại mục 3.1 là mô hình đơn giản, chỉ coi bãi gửi xe là

1 hàng đợi và mô hình ở mục 3.2 là một hệ thống các hàng đợi phức tạp: bãi

gửi xe, quầy thanh toán, phục vụ khách hàng bằng các hình thức xe đẩy, rỏ

hàng… Tại Bảng 3.1 và Bảng 3.2 đã đƣa ra các kết quả mô phỏng và kết quả

tính toán lý thuyết. Những kết quả này cho thấy vẫn có những sai lệch nhất

định trong kết quả mô phỏng và kết quả lý thuyết tính toán ra, cụ thể là trong

8 giờ mô phỏng, số lƣợng xe đến bãi xe theo lý thuyết là 960 chiếc, theo kết

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

quả mô phỏng là 961 chiếc (sai lệch 0,1%).

Tại mô hình 1 trong mục 3.1, số lƣợng xe ô tô đƣợc phục vụ là 845

chiếc theo kết quả mô phỏng và 800 chiếc theo lý thuyết (sai lệch 5,6%).

Thực hiện mô phỏng và tính toán lại đối với mô hình ở mục 3.1 với 16

giờ, 24 giờ, 40 giờ, 80 giờ với việc cài đặt lại chƣơng trình mô phỏng ở câu

lệnh khống chế về thời gian thực hiện mô phỏng

;Lần lượt được thay bằng 57600, 86400, 144000;

------------------------------------------ GENERATE 28800 ;Thời gian mô phỏng là 8x60x60 giây

------------------------------------------

Kết quả thực hiện với mô hình 1 (ở mục 3.1) nhƣ sau:

Bảng 3.3. So sánh kết quả tính toán theo lý thuyết với tính toán trong GPSS theo thời gian T tại mô hình ở mục 3.1

8 giờ 16 giờ 24 giờ 40 giờ

GPSS

Lý thuyết

960

961

1920

1922

2880

2882

4800

4803

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

800

845

1600

1565

2400

2387

4000

3985

Số xe ô tô được vào phục vụ tại siêu thị

800

750

1600

1468

2400

2287

4000

3887

Số xe ô tô đã đƣợc phục vụ tại siêu thị

Với số lƣợng xe ô tô đến siêu thị, đây là đại lƣợng đầu vào hàng đợi,

nên mô hình lý thuyết và mô hình mô phỏng GPPS gần nhƣ không có sự sai

lệch đáng kể, vì đây chỉ là đại lƣợng do các hàm toán học phân bố ngẫu nhiên

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

mà GPSS sử dụng (bảng 3.4).

Bảng 3.4: Mức độ sai lệch giữa mô phỏng và lý thuyết theo đại lượng “Số xe ô tô đến siêu thị” với mô hình ở mục 3.1

Thời gian Lý thuyết GPSS % sai lệch

960 961 0,10 % 8 giờ

1920 1922 0,10 % 16 giờ

2880 2882 0,07 % 24 giờ

4800 4803 0,06 % 40 giờ

Với số lƣợng xe ô tô đƣợc vào phục vụ tại siêu thị, từ bảng 3.3 chúng ta

có thể nhận thấy với thời gian mô phỏng hay tính toán càng tăng, số lƣợng

phần trăm sai lệch ngày càng giảm, các kết quả chi tiết này đƣợc tính toán tại

bảng 3.4. Khi T=8 giờ, sai lệch là 5,6%, khi T=40 giờ, sai lệch chỉ còn lại là

0,38% (bảng 3.5).

Bảng 3.5: Mức độ sai lệch giữa mô phỏng và lý thuyết theo đại lượng “Số khách hàng được phục vụ tại bãi xe” với mô hình ở mục 3.1

Thời gian Lý thuyết GPSS % sai lệch

800 845 5,63 % 8 giờ

1600 1565 2,19 % 16 giờ

2400 2387 0,54 % 24 giờ

4000 3985 0,38 % 40 giờ

Với kết quả ở bảng 3.5 cho ta thấy, khi thời gian mô phỏng càng

lớn, các kết quả mô phỏng ngày càng tiệm cận sát với kết quả của mô

hình lý thuyết.

Tƣơng tự cách tiến hành với mô hình tại mục 3.2, thay đổi thời gian mô

phỏng đƣợc tiến hành khi cài đặt lại trong Block 1 của chƣơng trình trong

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

phần sau:

time_work VARIABLE 8#60#60

; xác định hệ thống mô phỏng

;tính bằng giây thay vì 8x60x60 sẽ là 16x60x60, 24x60x60,

40x60x60, 80x60x60 giây

-------------------------------------

Chúng ta sẽ nhận đƣợc kết quả đối với đại lƣợng “số xe ô tô đƣợc phục

vụ tại bãi xe, liệt kê tại bảng 3.6.

Bảng 3.6: Mức độ sai lệch giữa mô phỏng và lý thuyết theo đại lượng “Số khách hàng được phục vụ tại bãi xe” với mô hình ở mục 3.2

Thời gian Lý thuyết GPSS % sai lệch

823 669 18,71% 8 giờ

1646 1484 9,84% 16 giờ

2469 2290 7,25% 24 giờ

4115 3980 3,28% 40 giờ

8230 8027 2,47% 80 giờ

Dựa trên các kết quả của bảng 3.6, chúng ta có thể nhận đƣợc đồ thị

0,2 0,18 0,16 0,14 0,12 0,1 0,08 0,06 0,04 0,02 0

phụ thuộc của đại lƣợng % sai lệch vào thời gian mô phỏng (hình 3.6).

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.7: Đồ thị phụ thuộc độ sai lệch tính toán giữa GPSS và lý thuyết theo thời gian

Theo các kết quả tại bảng 3.6 và hình 3.6, có thể nhận thấy khi thời gian

mô phỏng càng lớn, các kết quả lý thuyết và mô phỏng ngày càng tiệm cận.

3.4. Kết luận chƣơng

Trong chƣơng này, luận văn trình bày về ứng dụng đƣợc viết để phục

vụ cho siêu thị BigC Hà Nội sử dụng hệ thống hàng đợi. Bên cạnh đó đƣa ra

các đánh giá so sánh các kết quả thu đƣợc từ tính toán thực tế giữa các hệ

thống hàng đợi với nhau. Các kết quả mô phỏng cho thấy hoạt động của các

mô hình mô phỏng có thể đƣa ra những thông số hợp lý, có thể tham khảo để

đƣa ra những tƣ vấn, hoạch định cho các hệ thống phức tạp. Đặc biệt khi thực

hiện mô phỏng với thời gian mô phỏng lớn, các kết quả mô phỏng đã tiệm cận

đến những giá trị có thể tính toán đƣợc trên lý thuyết, điều này cho thấy tính

đúng đắn của các kết quả mô phỏng.

Mặc dù trên thực tế còn rất nhiều hệ thống hàng đợi phức tạp hơn

nhƣng trong khuôn khổ luận văn này chỉ trình bày nhằm phục vụ hệ thống gửi

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

xe trong siêu thị BigC Hà Nội./.

KẾT LUẬN

Từ việc nghiên cứu bài toán mô phỏng hệ thống phục vụ đám đông ,

luâ ̣n văn đã đƣa ra phƣơng pháp mô ph ỏng hệ thống phục vụ đám đông bằng

ngôn ngữ mô phỏng GPSS. Qua những kết quả thực nghiệm đạt đƣợc cho

thấy tính hữu dụng của phƣơng pháp này.

Về mặt nội dung, luâ ̣n văn đã đạt đƣợc những kết quả sau:

- Giới thiệu hệ thống phục vụ đám đông: khái niệm, mô hình, đầu vào,

đầu ra, hƣớng tiếp cận.

- Nghiên cứu ngôn ngữ mô phỏng GPSS: Nêu đƣợc cơ sở lí thuyết,

định nghĩa, cấu trúc của ngôn ngữ GPSS. Đồng thời giới thiệu một trong

những công cụ hỗ trợ ngôn ngữ này: GPSS World Student Version – phiên

bản đƣợc cung cấp miễn phí nhằm phục vụ mục đích học tập và nghiên cứu.

- Thông qua cơ sở lí thuyết của ngôn ngữ GPSS để giải quyết bài toán

mô phỏng hệ thống phục vụ đám đông. Luận văn đã xây dựng đƣợc các bƣớc

để ứng dụng GPSS trong mô phỏng hệ thống phục vụ đám đông.

- Xây dựng chƣơng trình để triển khai bài toán bãi tại siêu thị và bài

toán mô phỏng hoạt động của siêu thị bằng ngôn ngữ mô phỏng GPSS.

Bên cạnh những nghiên cứu đạt đƣợc, do hạn chế về mặt thời gian, tài

liê ̣u và kiến thức, luâ ̣n văn vẫn còn tồn tại một số hạn chế sau:

- Luận văn chƣa tìm hiểu đƣợc hết tất cả các ứng dụng của ngôn ngữ

mô phỏng GPSS trong các bài toán thực tiễn.

- Luận văn chƣa tiến hành kiểm tra sự thực thi của việc mô phỏng hệ

thống phục vụ đám đông bằng ngôn ngữ GPSS trên tất cả các phiên bản của

GPSS World.

Định hƣớng tƣơng lai

Trong tƣơng lai , luâ ̣n văn s ẽ tiếp tục khắc phục những hạn chế trên.

Đồng thời cũng cố gắng hoàn thiện nghiên cứu để có thể đƣa GPSS áp dụng

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

rộng rãi vào các ứng dụng trong thực tế.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Lê Quang Minh, Phan Đăng Khoa (2010), Báo cáo đề tài cấp ĐHQGHN

QCT-09-01: Công cụ GPSS cho bài toán mô phỏng các hệ thống phục vụ đám

đông, Viện Công nghệ thông tin – Đại học Quốc Gia Hà Nội.

[2] Lê Quyết Thắng, Phạm Nguyên Khang, Dƣơng Văn Hiếu (2006), Bài

giảng:Lý thuyết xếp hàng, Khoa CNTT & TT, Đại học Cần Thơ.

[3] Phạm Văn Giáp, Nguyễn Ngọc Huệ, Quy hoạch Cảng, Chương 8:Lý

thuyết xếp hàng xác định số lượng bến, NXB Xây Dựng 12/2010, ISBN:

9980000289579.

Tiếng Anh

[4] JOHN A. GUBNER(2006) “Probability and Random Processes for Electrical and Computer Engineers”, the United States of America by Cambridge University Press, New York.

[5] Robert B.Cooper (1981) “Intro To Queueing Theory”, Elserier

North Holland.

[6] John D.C. Little and Stephen C. Graves, “Little's Law”.

[7] Leonard Kleinrock(1975) “Queueing Systems – Volume 1 Theory”,

John Wiley and Sons New York.

[8] William Stallings(2000), “Queuing Analysis”.

[9] Dr. János Sztrik, “ Basic Queueing Theory”, University of Debrecen, Faculty of Informatics University of Debrecen Faculty of Informatics.

[10] Andreas Willig(1999) “A Short Introduction to Queueing Theory”,

Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Technical University Berlin, Telecommunication Networks Group.

Luận văn Thạc sĩ Khoa học Máy tính: Nghiên cứu lý thuyết hàng đợi và mô phỏng bãi gửi xe tại siêu thị Big C – Hà Nội

2] + 2(1−ρ)

eμτ

e−μτd

Bắt đầu

Star

t

Hết thời gian

Kiểm tra thời gian

mô phỏng

Còn thời gian mô phỏng

Sinh ngẫu nhiên

End

xe vào bãi 30±5

giây Kiểm tra

bãi xe còn

Xe rời bãi

trống hay

Xe bỏ đi

Xe vào bãi, không

Xác định

các giá trị

khách hàng vào Khách hàng mua hàng chọn xe đẩy,

thời gian

giỏ hàng, chọn

khách mua 3.2.3 Giải bài toán

hàng, thanh - Số lƣợng khách hàng (xe ô tô xuất hiện) đến mua hàng là: hàng toán tiền

; Block 1

; Block 2

; Block 3

; Block 4

; Block 5

; Block 6

; Block 7

; Block 8

; Block 9

; Block 10

Kết quả của quá trình mô phỏng:

GPSS

GPSS

GPSS

GPSS

Lý thuyết

Lý thuyết

Lý thuyết

Lý thuyết

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok