ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THU THỦY
NGHIÊN CỨU VÀ ỨNG DỤNG
LÝ THUYẾT HÀNG ĐỢI TRONG BÀI TOÁN
MÔ PHỎNG HOẠT ĐỘNG MỘT SIÊU THỊ
Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã số: 60480103
LUẬN VĂN THẠC SĨ NGÀNH
CÔNG NGHỆ THÔNG TIN
Hà Nội - 2017
1
Nghiên cứu và ứng dụng lý thuyết hàng đợi trong bài toán mô phỏng hoạt động một siêu thị
Nguyễn Thu Thủy
Trường Đại học Công nghệ
Luận văn Thạc sĩ ngành: Kỹ thuật phần mềm, mã số: 60480103
Người hướng dẫn: TS. Lê Quang Minh
Năm bảo vệ: 2017
Tổng quan: Trình bày cơ sở lý thuyết về hệ thống hàng đợi: đưa ra cơ sở lý thuyết về hệ thống hàng đợi, bao gồm: các yếu tố của hệ thống phục vụ (dòng vào, dòng ra, hàng chờ, kênh phục vụ), các quá trình Markov và trạng thái của hệ thống. Ngoài cách tiếp cận bằng lý thuyết hàng đợi, luận văn tập trung nghiên cứu hiện trạng một số công cụ mô phỏng các bài toán hàng đợi: giới thiệu ngôn ngữ, công cụ mô phỏng GPSS World và sử dụng để giải quyết bài toán hàng đợi thực tế.Về ngôn ngữ GPSS và công cụ GPSS World: đề cập cụ thể, chi tiết về cấu trúc của một thao tác lệnh, các đối tượng và các khối (block) cơ bản trong GPSS. Trình bày các bước tiến hành mô phỏng một bài toán hàng đợi khi sử dụng phương pháp mô phỏng qua công cụ GPSS World. Áp dụng ngôn ngữ GPSS vào bài toán thực tế: mô phỏng hoạt động hàng đợi đơn giản là bãi đỗ xe tại siêu thị, và mô phỏng hoạt
2
động của hệ thống dịch vụ phức tạp với nhiều phase phục vụ được cung cấp tại siêu thị từ gửi xe, giỏ hàng tới khi thanh toán và rời hệ thống.
Từ khóa: Hàng đợi; Mô hình hàng đợi; Ngôn ngữ GPSS.
Nội dung
TÓM TẮT LUẬN VĂN THẠC SỸ
Chương I: Lý thuyết hàng đợi
Chương 1 tập trung trình bày về lý thuyết hàng đợi bao gồm: các khái niệm cơ bản như biến ngẫu nhiên, các phân phối xác suất thường gặp, khái niệm hàng đợi và các đặc điểm của hàng đợi; Ký hiệu Kendall và định nghĩa các biến cần quan tâm khi giải quyết bài toán hàng đợi; từ những khái niệm cơ bản đã nêu, phần 2 của chương giới thiệu một số hàng đợi cơ bản thường thấy, phân tích chi tiết quá trình chuyển trạng thái và công thức tính hiệu suất của từng mô hình hàng đợi.
Hàng đợi (hay dòng chờ) là một dòng đợi dịch vụ. Yêu cầu được phục vụ từ khách hàng sinh ra theo thời gian thông qua 1 nguồn đầu vào. Khách hàng sẽ phải chờ trong hàng đợi đến lượt được phục vụ. Khách rời khỏi hệ thống sau khi đã được phục vụ. Các thành phần cơ bản và đặc điểm của hàng đợi được trình bày trong hình 1.2.
3
Hình 1. 1- Thành phần cơ bản của hàng đợi
Mô hình hàng đợi trong thực tế rất đa dạng, trong đó cần kể đến một số mô hình trình bày trong bảng 1.3
Bảng 1. 1-Một số mô hình hàng đợi cơ bản
Tên hàng đơi
Phân phối thời gian phục vụ
Số kênh phục vụ Số bước phục vụ Phân phối tín hiệu đến Nguyê n tắc phục vụ
1 1 FIFO
Luật phân phối mũ
Luật phân phối mũ Possion Luật phân 1 FIFO
phối mũ c (c>1)
1 1 Possion Luật phân FIFO
phối mũ
Kích thước của dòng đến Không giới hạn Không giới hạn Không giới hạn
Hệ thống đơn hàng M/M/1 Hệ thống đa hàng M/M/c Hệ thống hàng đợi thời có gian phục vụ chính
4
1 Possion Luật phân FIFO
c(c>1 ) Giới hạn phối mũ
xác (M/D/1) Hệ thống hàng đợi M/M/c/K Với mỗi mô hình có những đặc trưng và hiệu suất khác nhau. Tuy nhiên có những mô hình phức tạp rất khó để giải được bằng lý thuyết toán học. Để bài toán giải được bằng lý thuyết cần đáp ứng một số điều kiện sau:
Điều kiện 1: Dòng vào của hệ thống phải là dòng tối giản hoặc xấp xỉ tối giản. Điều kiện 2: Khoảng thời gian (T) giữa 2 lần xuất hiện liên tiếp các yêu cầu là đại lượng ngẫu nhiên tuân theo qui luật hàm số mũ. Như vậy, hàm mật độ xác suất có dạng:
(1.1) ( ) =
Và hàm phân phối xác suất có dạng
( ) = 1 − (1.2)
Với λ là cường độ dòng vào, đó là số yêu cầu trung bình xuất hiện trong một đơn vị thời gian. Điều kiện 3: Thời gian phục vụ của các kênh cũng là đại lượng ngẫu nhiên tuân theo qui luật hàm số mũ. Như vậy, hàm mật độ xác suất có dạng ( ) = Và hàm phân phối xác suất có dạng ( ) = 1 − Với μ là năng suất phục vụ của các kênh, đó là số yêu cầu được phục vụ tính bình quân trên một đơn vị thời gian. Phương pháp giải quyết bài toán bằng lý thuyết có đường lối chung bao gồm các bước:
5
Bước 1: Phân tích hệ thống mà chủ yếu là phân tích tính chất của dòng vào và các trạng thái của hệ thống;
Bước 2: Thiết lập hệ phương trình trạng thái để giải ra các xác suất trạng thái;
Bước 3: Giải hệ phương trình để tìm ra các xác suất trạng thái và từ đó thiết lập mối quan hệ giữa các chỉ tiêu cần phân tích;
Bước 4: Tính toán, phân tích các chỉ tiêu, trên cơ sở đó đưa ra nhận xét và kết luận.
Chương 2: Công cụ mô phỏng GPSS World
Chương 2 tập trung trình bày về các công cụ mô phỏng hệ thống hàng đợi, cách giải bài toán bằng công cụ mô phỏng. Áp dụng lý thuyết hàng đợi với những mô hình phức tạp thường khó khăn. Mô phỏng là một trong những phương pháp hiệu quả nhất để nghiên cứu các hệ thống phức tạp. Bản chất của công cụ mô phỏng là là tái tạo quá hoạt động của một hệ thống theo sự kiện và thời gian theo đúng quy luật quan sát được ngoài thực tế. Khi đó tính chất đầy đủ của các mô hình mô phỏng cần đạt được là mô phỏng vòng đời của mỗi phần tử trong hệ thống đúng theo logic và quy tắc tương tác và phát triển của chúng cả trong thời gian và trong không gian.
Với ý nghĩa ứng dụng thực tiễn, từ những năm 1960 trở lại đây, đã có nhiều các công cụ mô phỏng ra đời. Giai đoạn đầu hầu hết các công cụ phục vụ cho môi trường PC, nhưng thời điểm hiện tại có thể tìm thấy các toolbox chạy trên môi trường Internet [8] đáp ứng nhu cầu nghiên cứu và ứng dụng với phạm vi khác nhau.
GPSS World được thiết kế để cung cấp câu trả lời một cách nhanh chóng và đáng tin cậy, với nỗ lực ít nhất, đạt được các kết
6
quả được xem xét trên nhiều góc độ trực quan nhất, phù hợp với các mục tiêu khác nhau của các mô phỏng.
GPSS bao gồm các đối tượng sau:
- Model Objects (đối tượng mô hình);
- Simulation Objects (đối tượng mô phỏng);
- Report Objects (đối tượng báo cáo);
- Text Objects (đối tượng văn bản).
Tập hợp các câu lệnh khối (Block) được sử dụng trong GPSS World có thể chia thành 4 nhóm với hơn 50 câu lệnh:
- Khối lệnh liên quan đến các giao tác (Transactions)
- Khối các lệnh liên quan đến các thực thể thiết bị (Facility)
- Khối các lệnh liên quan đến dữ liệu tĩnh
- Khối các lệnh để điều khiển đường đi của các giao tác trong mô hình mô phỏng
Qua quá trình nghiên cứu, luận văn đề xuất một quy trình ứng dụng GPSS chung để mô phỏng một hệ thống hàng đợi như sau:
Thu thập dữ liệu:
Bước 1: Khảo sát và nghiên cứu hệ thống. Bước này cần xác định được các thông số của hệ thống như: số nguồn các yêu cầu; có thứ tự ưu tiên giữa các nguồn hay không; Cần quan sát hệ thống thật trong những điều kiện hoạt động khác nhau; quan sát hành vi của khách hàng trong hàng đợi, thời gian chờ đợi;
Bước 2: Quan sát thời gian phục vụ của hệ thống. Thu thập thông tin về dịch vụ cũng là một yêu cầu cần thiết, tất cả quá trình sử 7
dụng dịch vụ, bao gồm cả thời gian dịch vụ rảnh rỗi cũng cần được thu thập.
Phân tích dữ liệu thống kê:
Bước 3: Dữ liệu thô thu thập được từ 2 bước trước phải phân tích để lấy được thông tin thống kê, xác định hàm phân phối xác suất.
Xác định luật phân bố đầu vào (input) của các kênh phục vụ. Mỗi nguồn sinh các yêu cầu theo quy luật phân phối ngẫu nhiên nào. Xác định các biến số thời gian gắn liền với đầu vào của các sự kiện. Từ đó lựa chọn hàm phân bố tương ứng trong GPSS.
Bước 4: từ các hàm phân phối thu được ở bước 3, xác định các Operation, phân phối tương ứng, xác định các tham số (min – max, mean) và khoảng thời gian trung bình tương ứng.
Bước 5: Mã hóa chương trình mô phỏng.
Bước 6: Đưa ra kết luận dựa trên mục đích mô phỏng, độ nhạy liên quan. Trong quá trình phân tích có thể thay đổi các tham số hoặc cấu trúc mô hình để có được những kết luận khác phục vụ mục tiêu mô phỏng. Kết quả mô phỏng càng chính xác khi bước mô phỏng càng lớn.
8
Hình 2. 1- Quy trình mô phỏng bài toán bằng GPSS World
Tùy vào đặc trưng của hệ thống mà áp dụng phương pháp thu thập dữ liệu khác nhau. Đối với hoạt động của siêu thị có thể áp dụng phương pháp thu thập dữ liệu bằng bảng câu hỏi khảo sát như phụ lục 2.1 nêu trong luận văn này. Sau khi thu thập dữ liệu cụ thể, xây dựng bảng kết quả và tính toán được những thông số thực tế để xây dựng mô hình bài toán như trong phụ lục 2.2.
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ị.
Chương 3 nêu ra 2 bài toán. Bài toán thứ nhất mô phỏng bãi gửi xe tại một siêu thị theo mô hình hàng đợi M/M/80/∞/∞/FCFS. Đây là bài toán đại diện cho mô hình hàng đợi đơn giản nhưng có
9
tính khái quát chung cho một số hàng đợi như bãi gửi xe, quầy cân đồ, quầy bán đồ ăn nhanh và một số dịch vụ đơn giản khác. Bài toán thứ 2 mô phỏng hệ thống gồm các bước phục vụ khác nhau mà siêu thị cung cấp gồm: Gửi xe, giỏ hàng, thanh toán và rời khỏi hệ thống.
Nêu bài toán 1: Tại siêu thị Lan Chi thành phố Thái Nguyên có
80 chỗ đỗ xe ô tô được chia thành từng ô riêng biệt. Kết quả khảo
sát tại bộ phận an ninh thu được một số thông tin sau:
- Khách hàng đến nếu không còn chỗ trống đậu xe thì sẽ rời
khỏi siêu thị ngay. Vào ngày cuối tuần, trung bình có 30 ±
5 giây thì có một xe vào bãi đậu xe.
- Thời gian xe ô tô đậu ở bãi đậu xe được tính là thời gian
khách hàng vào chọn lựa mua hàng, thanh toán và di
chuyển trở lại xe. thời gian từ khi khách hàng rời xe đến
khi quay trở lại trung bình là là 60 phút.
Mục tiêu là mô phỏng: mô phỏng lại hoạt động của bãi đỗ xe
trong thời gian 1 ca làm việc của siêu thị (8 tiếng) nhằm so sánh
kết quả mô phỏng với kết quả tính toán bằng lý thuyết hàng đợi.
Giải quyết bài toán:
Từ những giả thiết có được, sau khi áp dụng lý thuyết để giải ta xây dựng được được mô hình mô phỏng theo các bước trong sơ đồ trình bày trong hình 3.2
10
Hình 3. 1- Mô hình thuật toán giải bài toán bãi đậu xe
11
Áp dụng các bước đề xuất ở trên tiến hành mô phỏng bài toán theo các bước
- Xác định được thực thể cần mô phỏng - Mã hóa và chạy chương trình mô phỏng - Kết luận bài toán dựa vào mục tiêu mô phỏng
Một số các kết luận đáng chú ý là:
- Kết quả tính toán mô phỏng và trong GPSS World phù hợp với kết quả tính toán theo lý thuyết. Tuy nhiên vẫn có những sai lệch nhất định.
- Khi thời gian mô phỏng càng lớn, thì 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.
Những kết luận trên đưa ra dựa trên kết quả được so sánh khi tính toán bằng lý thuyết và tính toán bằng mô phỏng như bảng so sánh 3.1.
Bảng 3. 1- Kết quả mô phỏng với thời gian 8h
Độ lệch Một số yếu tố cần so sánh Tính toán theo lý thuyết Tính toán trong GPSS
0.42% 964 Số xe ô tô đến siêu thị 960
11.56% 714 Số xe có chỗ đậu 640
21.88% 250 320 Số xe không có chỗ đậu (phải rời đi ngay)
640 634 0.94%
Lượng xe ô tô đã rời khỏi bãi sau khi đã được phục vụ
12
80 Không xác định Số xe ô tô vẫn ở bãi xe sau khi kết thúc ca làm việc 8h
Thực hiện mô phỏng và tính toán lại đối với mô hình với thời
gian mô phỏng là 16 giờ, 24 giờ, 40 giờ, 80 giờ bằng cách thiết
lập lại thời gian trong chương trình mô phỏng. Kết quả thực hiện
điều chỉnh thời gian mô phỏng như bảng 3.2. Từ đó đưa ra kết
luận thời gian mô phỏng càng lớn, thì 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.
13
Bảng 3. 2. Kết quả mô phỏng với thời gian khác nhau
8 giờ 16 giờ 24 giờ 40 giờ
GPSS GPSS GPSS Lý thuyết GPS S Lý thuyết Lý thuyết Lý thuyết
Số xe ô tô đến siêu thị 960 964 1925 2883 4801 1920 2880 4800
714 1320 1941 3236 640 1280 1920 3200 Số xe ô tô được vào phục vụ tại siêu thị
250 1240 1861 3156 320 640 960 1600 Số xe ô tô không được phục vụ tại bãi đỗ xe
14
Nêu bài toán 2: Siêu thị Lan Chi có một bãi xe với số lượng 100
chỗ. Khách hàng rời đi ngay nếu không có chỗ đỗ xe. Luồng
khách hàng đến mua hàng được phân bố trong khoảng thời gian
trung bình từ 30 ± 5 giây. Tùy vào dự định mua hàng mà khách
chọn xe đẩy hay giỏ để chứa hàng Thời gian đi chuyển từ bãi đậu
xe vào đến siêu thị khoảng 60 ± 40 giây.
Tại siêu thị có 100 xe đẩy cho khách mua hàng và 50 giỏ
hàng phục vụ cho khách hàng mua sắm nhỏ (số lượng mua hàng ít
hơn 10 loại hàng hóa). Tỷ lệ giữa khách hàng chọn giỏ hàng với
khách hàng mua bằng xe đẩy là: 7/40. Có 5 quầy thu ngân, trong
đó quầy số 5 ưu tiên phục vụ khách hàng mua với số lượng hàng
ít (nhỏ hơn 10 mặt hàng). Số lượng món hàng khách chọn là một
biết ngẫu nhiên nằm trong khoảng 5 đến 100 mặt hàng. Khách
chọn một món hàng trong khoảng thời gian trung bình là 60 giây,
tổng thời gian mua hàng sẽ được tính bằng số lượng hàng nhân
60s.
Khi mua hàng xong, khách hàng chọn quầy thu ngân có
ước lượng chiều dài hàng đợi ngắn nhất hoặc quầy thứ 5 nếu số
lượng hàng ít hơn 10. Tùy vào lượng hàng và cách thanh toán mà
thời gian thanh toán tương ứng với từng khách hàng là khác nhau.
Tuy nhiên có thể xác định được thời gian thanh toán cho một món
hàng đã đầy đủ thông tin là 2s; và trung bình mất 2 ± 1 phút để
thực hiện thu tiền, trả lại, in hóa đơn hoặc quẹt thẻ, ký tên lên
biên lai thanh toán. Sau khi mua sắm xong, khách hàng sắp xếp
lại đồ, di chuyển ra bãi đậu xe trong khoảng 60 ± 50 giây và rời
15
khỏi siêu thị.
16
Mô tả hoạt động hệ thống được trình bày trong hình 3.5
Hình 3. 2- Mô tả mô hình hoạt động của siêu thị
17
Từ Mô hình thuật toán trên ta xác định được các thực thể sử dụng trong mô phỏng sau:
TT Loại thực thể Ghi chú Số lượng
1. Thực thể lưu trữ 3
2. Thực thể hàng đợi 7
3. Thực thể thiết bị 5
4. Thực thể bảng 3 Gồm các thực thể lưu kích thức bãi đỗ xe, kích thước giỏ hàng, kích thước xe hàng Gồm: hàng đợi giỏ hàng, hàng đợi xe hàng, 5 hàng đợi của các quầy thanh toán Thực thể thiết bị là các quầy thanh toán Gồm các thực thể bảng lưu thời gian hệ thống
Sau khi xác định được các thực thể cần dùng cho mô hình, tiến
hàng mã hóa chương trình mô phỏng với một số nhãn và khối
lệnh sau:
Block 1: khối lệnh khai báo các đối tượng, các biến lưu
trữ;
Block 9 Sinh sự kiện phát sinh khách hàng theo phân
phối xác suất
Block 10 mô tả toàn bộ thời gian mua hàng để kiểm soát
trong suốt thời gian hệ thống thực hiện mô phỏng.
Nhãn PARKING: Gồm khối lệnh 2 (Block 2) và khối
18
lệnh 3 Mô tả hoạt động của khách hàng vào bãi đỗ xe, thiết lập
các giá trị tham biến cho khách hàng được phục vụ (khách hàng
đã được dịch vụ gửi xe phục vụ).
Nhãn QTELEJKA: gán lại giá trị cho hàng đợi xe đẩy khi
xe đẩy được chọn;
Nhãn MIN_OCH: mô phỏng quá trình mua hàng của
khách, thiết lập các giá trị lượng hàng mua theo tỷ lệ đầu bài đặt
ra; Block 6 đưa ra các số liệu thống kê đối với quầy thu ngân số 1
(quầy thu ngân cho các khách hàng mua nhanh);
Nhãn FIN: đưa ra số liệu thống kê đối với các quầy thu
ngân khác; sẽ tính toán và đưa ra các số liệu dạng bảng về thời
gian làm việc của hệ thống và số lượng hàng hóa được mua, giải
phóng đối tượng mua hàng sau 1 phiên mua hàng; mô tả các
luồng khách hàng rời khỏi dịch vụ thanh toán;
Nhãn LOST: hủy bỏ yêu cầu phục vụ khi bãi xe đầy.
Kết luận rút ra từ báo cáo mô phỏng sau khi chạy chương trình
mô phỏng với thời gian 8h như trong bảng 3.4.
Bảng 3. 3 – Kết quả mô phỏng hoạt động của siêu thị
Chỉ tiêu Số lượng Hiệu suất
Số yêu cầu đến trong thời gian mô 953
phỏng
239 Số yêu cầu gửi xe được không phục
vụ
19
714 0.890 Số yêu cầu và hiệu suất sử dụng của
bãi gửi xe
Số khách hàng đã vào siêu thị nhưng 1
chưa mua hàng
Số yêu cầu và hiệu suất sử dụng giỏ 45 0.018
hàng được phục vụ
Số yêu cầu và hiệu suất sử dụng xe 667 0.938
đẩy hàng được phục vụ
Số khách hàng thực hiện mua hàng 666
Số yêu cầu thanh toán được phục vụ 604
Lượng khách mua dưới 10 món hàng 46
145 Số khách hàng và hiệu suất sử dụng 0.146
thanh toán tại quầy 1
Số khách hàng và hiệu suất sử dụng 131 0.941
thanh toán tại quầy 2
Số khách hàng và hiệu suất sử dụng 129 0.896
thanh toán tại quầy 3
Số khách hàng và hiệu suất sử dụng 125 0.879
thanh toán tại quầy 4
Số khách hàng và hiệu suất sử dụng 40 0.870
thanh toán tại quầy 5
Tương tự cách tiến hành với mô hình bài toán bãi gửi xe, thực
hiện thay đổi thời gian mô phỏng bằng cách cài đặt lại biến thời
20
gian time_work trong Block 1 lần lượt bằng các giá trị:
16*60*60, 24*60*60, 40*60*60, 80*60*60 sau đó chạy mô
phỏng cho từng trường hợp thời gian. Đem so sánh kết quả từng
trường hợp với lý thuyết
Xét giá trị số xe được phục vụ tại bãi gửi xe, ta có bảng so sánh
kết quả 3.5.
Bảng 3. 4- So sánh lượng xe được phục vụ trong bài toán hệ thống siêu thị
Thời gian Lý thuyết GPSS % sai lệch
823 714 13% 8 giờ
1647 1484 10% 16 giờ
2471 2213 10% 24 giờ
4118 3956 4% 40 giờ
8237 8093 2% 80 giờ
Kết quả của bài toán mô phỏng 2 cũng phù hợp với kết quả và nhận xét đã trình bày trong phần kết luận của bài toán đầu tiên (mục 3.2.3.3). Giữa tính toán lý thuyết và mô phỏng vẫn có sự sai lệch; tuy nhiên, độ sai khác này sẽ giảm khi khi thời gian mô phỏng lớn hơn; hay độ lấy mẫu càng lớn hơn thì độ lệch giữa kết quả tính toán lý thuyết và kết quả mô phỏng theo GPSS càng giảm. Trong một số bài toán phức tạp việc sử dụng công cụ tính toán toán học thông thường theo lý thuyết hàng đợi là rất khó khăn, trong những trường hợp như vậy chỉ có thể sử dụng mô phỏng để tính toán. Việc mô phỏng hệ thống phục vụ đám đông bằng GPSS World là một giải pháp hiệu quả.
21
KẾT LUẬN Ý nghĩa thực tiễn mà đề tài muốn hướng tới là làm chủ được phương pháp đánh giá hiệu suất, đo lường các giá trị liên quan của một hệ thống phục vụ đám đông; nhằm xây dựng các ứng dụng cải tiến dịch vụ, giảm thiểu lãng phí sinh ra bởi các dòng chờ trong tương lai như: ứng dụng hàng đợi tiện ích trên thiết bị di động. Luận văn tiếp cận bài toán hệ thống phục vụ đám đông theo hướng giải tích và mô phỏng. Phương pháp giải tích là sử dụng lý thuyết hàng đợi để phân tích bài toán. Sử dụng công cụ mô phỏng chuyên dụng để mô hình hóa bài toán nhằm tăng hiệu quả tính toán và giải quyết các bài toán phức tạp.
Từ hai phương pháp tiếp cận bài toán nêu trên, thông qua thực nghiệm với bài toán thực tế, mô hình bài toán có được nhờ mô phỏng cho ra những kết quả có ý nghĩa với các dữ liệu đầu vào khác nhau. Dựa vào kết quả đạt được đó luận văn đã đưa ra được những đánh giá cụ thể trên mô hình bài toán thực tế.
Nội dung luận văn đã làm rõ những vấn đề sau: - Tổng kết những vấn đề căn bản trong cở sở lý thuyết về hệ thống hàng đợi; tổng kết một số mô hình cơ bản; các đặc điểm quan trọng của hàng đợi như mức độ ưu tiên, quy luật liên quan đến trạng thái của hệ thống; điều kiện giải được và các bước giải quyết bài toán bằng phương pháp giải tích;
- Nghiên cứu ngôn ngữ mô phỏng GPSS: nêu được tập các đối tượng, các định nghĩa, cấu trúc lệnh của ngôn ngữ GPSS. Đồng thời giới thiệu và sử dụng công cụ GPSS World Student Version được cung cấp miễn phí để giải quyết bài toán thực tế;
- Đề xuất quy trình xây dựng mô phỏng hệ thống phục vụ
đám đông bằng GPSS World;
- Sử dụng công cụ GPSS vào bài toán thực tiễn tại siêu thị, đã phân tích và so sánh kết quả mô phỏng với kết quả tính toán trên lý thuyết, từ đó rút ra kết luận.
22
Bên cạnh những kết quả đã đạt được, luận văn vẫn còn tồn tại một số hạn chế sau:
- Chưa kiểm chứng được quy trình xây dựng mô phỏng trong nhiều trường hợp áp dụng để đi đến khẳng định quy trình đề xuất đúng trong mọi trường hợp.
- 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.
- Mặc dù đã nêu được phương pháp cụ thể để thu thập dữ liệu đối với bài toán siêu thị, nhưng chưa áp dụng triệt để phương pháp đó để bài toán mô phỏng có tính chính xác cao hơn.
Từ những kiến thức bổ ích đã thu thập được trong quá trình thực hiện luận văn; trong tương lai, hướng áp dụng tiếp theo để phát triển luận văn này là: xây dựng ứng dụng nhằm cải tiến hàng đợi truyền thống bằng mô hình hàng đợi tiện lợi trên các thiết bị di động.
TÀI LIỆU THAM KHẢO
Tiếng Việt:
[1] Lê Quang Minh, Phan Đăng Khoa, “Công cụ GPSS cho bài toán mô phỏng các hệ thống phục vụ đám đông,” Báo cáo tổng hợp đề tài cấp ĐHQGHN, Viện Công nghệ thông tin – Đại học Quốc Gia Hà Nội, 2010.
[2] Lê Quang Minh, Phan Đăng Khoa, Nguyễn Thế Tùng, Nghiêm Thị Hoa (2015), “Nghiên cứu mô phỏng các hệ thống hàng đợi” – Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công Nghệ thông tin (FAIR), Hà Nội 2015;
Tiếng Anh:
23
[3] Ivo Adan and Jacques Resing, “Department of Mathematics and Computing Science” Eindhoven University of Technology P.O. Box 513, 5600 MB Eindhoven, The Netherlands
[4] Azmat Nafees and Liwen Liang, A ‘C level’ essay in Statistics submitted in partial fulfillment of the requirements for the degree of
“GPSS World reference manual” (2001), Minuteman
[5] Software. P.O. Box 131. Holly Springs, NC 27540-0131 U.S.A.
Alan Pilkington, Royal Holloway(2005), “GPSS –
[6] Getting Started”, University of London
[7] http://www.minutemansoftware.com/tutorial/tutorial_manual.htm
[8] http://simjs.com/queuing/index.html
24
