Luận văn 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

B: số hiệu hoặc vị trí khối. Số hoặc tên tham số khi A nhận giá trị là P (tùy chọn) C: vị trí hoặc số hiệu khối. Giá trị tăng trong trường hợp A là FN hoặc P D: sự tăng số hiệu khối trong trường hợp A là ALL nhảy tới một vị trí khối mới. - A là BOTH thì khối được chỉ định trong B được kiểm tra. Nếu nó từ chối giao tác hoạt động đăng nhập thì khối được chỉ định trong C được kiểm tra. Khối đầu tiên cho phép giao tác nhập vào sẽ là đích mới. Nếu không khối nào cho phép giao tác nhập vào thì nó sẽ ở lại khối TRANSFER cho đến khi nó nhập vào được một khối. - A là PICK đích mới sẽ được lựa chọn ngẫu nhiên trong khoảng B và C - Nếu A là P, Active Transaction sẽ nhảy đến một vị trí đã tính toán từ tổng giá trị của tham số và toán hạng C. Nếu C không được chỉ định thì giá trị của tham số là vị trí đích mới của giao tác -Nếu A là All, khối chỉ định trong B được kiểm tra. Nếu khối này từ chối giao tác hoạt động đăng nhập, các khối tiếp theo được kiểm tra lần lượt - Nếu A là SBR( subroutine mode) Active Transaction nhảy đến vị trí được chỉ định bởi toán hạng B, vị trí khối chuyển đổi được đặt trong toán tử C - Nếu A là SIM (simultaneous mode) giao tác hoạt động nhảy đến một trong hai vị trí được chỉ định trong C và chỉ số Delay được thiết lập lại ( turned off). Nếu chỉ số Delay được thiết lập lại (off) giao tác nhảy đến vị trí đã chỉ định bởi toán tử B TEST O,A,B,C O: phép toán quan hệ, có thể nhận một trong các giá trị E, G, GE, L, LE, or NE. A: giá trị kiểm tra B: giá trị tham chiếu So sánh các giá trị, đích của giao tác hoạt động dựa trên kết quả của việc so sánh. C: số hiệu khối đích 2.3.6 Một số hàm thư viện Trong một mô phỏng chúng ta có thể gọi đến một thủ tục nằm trong một thư viện thủ tục. Có hai loại thư viện: thư viện người dùng (User Library) và thư viện GPSS World. Thư viện người sử dụng là tập hợp các thủ tục PLUS. Các thư viện GPSS World chứa một tập hợp thủ tục toán học và chuỗi được tích hợp sẵn, có thể triệu gọi trong các biểu thức PLUS. Một trong số các thủ tục được tích hợp sẵn trong thư viện thủ tục đó là: các thủ tục tiện ích (Utility Procedures), các thủ tục tệp (File Procedures), các thủ tục gọi động (Dynamic Call Procedures), các thủ tục toán học (Math Procedures), các phân bố xác suất (Probability Distributions), các thủ tục chuỗi (String Procedures), và các thủ tục truy vấn (Query Procedures). 2.3.7 Cài đặt và sử dụng GPSS World Student Version GPSS World Student Version là phiên bản được cung cấp miễn phí nhằm mục đích học tập và nghiên cứu; Để mô phỏng hệ thống phục vụ đám đông bằng ngôn ngữ mô phỏng GPSS cần cài đặt bộ công cụ với các bước đơn giản. Ngoài Student version còn nhiều phiên bản khác như GPSS World Personal Version, GPSS World Commercial Version, GPSS World Student Version; Tuy nhiên, luận văn này sử dụng phiên bản GPSS World Student Version nhằm mục đích nghiên cứu, thử nghiệm và xây dựng bài toán áp dụng. Sau khi tải phiên bản miễn phí GPSS World Student Version về, tiến hành cài đặt như các phần mềm thông thường. Để xây dựng một mô phỏng người dùng cần một số thao tác cơ bản sau: - Tạo một mô hình: vào menu File / New /Model /OK. - Thực hiện viết code chương trình với bộ soạn thảo và các tiện ích chèn Block lệnh nhanh mà GPSS cung cấp trong trình soạn thảo mô hình. - Biên dịch: là bước translator thực hiện biên dịch mã nguồn, bước này có thể được kết hợp trong lệnh Command / Create Simulation nếu trong mã nguồn đã thiết lập trước thời gian mô phỏng. Nếu không có thể chạy lệnh Start [thời gian mô phỏng] để tạo mô hình sau khi biên dịch thành công - Tạo mô phỏng mới: vào menu Command / Create Simulation. Khi mô hình được tạo người dùng có thể theo dõi quá trình mô phỏng thông qua các cửa sổ thiết kế riêng cho từng thực thể như: Blocks Window, Facilities Window, Plot Window, Queues Window các màn hình này cung cấp đầy đủ số liệu liên quan đến thực thể đó như: số lần thực thể được sử dụng, hiệu suất (với Facility Entity), và các thông số liên quan. Theo dõi và phân tích kết quả. Để tiện theo dõi quá trình mô phỏng người sử dụng có thể dùng các lệnh trong menu Command như: START, STEP, HALT, CONTINUE, hoặc sử dụng các phím tắt tiện lợi. Khi quá trình mô phỏng kết thúc mặc định một cửa sổ báo cáo kết quả (Report Window) sẽ xuất hiện. Đây là một ví dụ mô phỏng đơn giản: Hình 2. 3- Mô hình một chương trình mô phỏng hệ thống hàng đợi đơn giản GENERATE mô tả việc “yêu cầu” xuất hiện trong hệ thống. QUEUE diễn tả việc “yêu cầu” (sự kiện) đi vào hàng đợi SEIZE yêu cầu được phục vụ, nếu kênh phục vụ bận thì “yêu cầu” phải tiếp tục bị giữ ở trong hàng đợi, ngược lại thì “yêu cầu” sẽ được chuyển vào kênh phục vụ DEPART biểu diễn hành vi “yêu cầu” được ra khỏi hàng đợi ADVANCE mô tả việc “yêu cầu” được phục vụ ở kênh phục vụ (máy phục vụ). RELEASE giải phóng kênh phục vụ TERMINATE “yêu cầu” được giải phóng khỏi hệ thống. Một chương trình mô phỏng trong GPSS World sẽ có dạng như hình 2.5 2.4 Hàng đợi có ưu tiên Priority Queueing Đối với lớp bài toán mô phỏng hàng đợi có ưu tiên cần thể hiện được sự ưu tiên của các lớp sự kiện ở các mức độ khác nhau. Các công cụ mô phỏng cung cấp cách thức để người sử dụng có thể dễ dàng làm được điều đó dựa vào cách thức lấy cách yêu cầu ra khỏi hàng đợi để phục vụ như hình 2.4. Hình 2. 4- Cách lấy yêu cầu của hàng đợi Priority Queueing - Tính năng đặc biệt của hàng đợi ưu tiên là ở bộ lập lịch. Có 4 mức ưu tiên gồm: mức cao, mức trung bình, mức bình thường, và mức thấp. Bộ lập lịch sẽ chọn lựa yêu cầu có mức độ ưu tiên cao hơn, tiếp theo đó là các yêu cầu có mức độ ưu tiên thấp dần để phục vụ. - Bộ lập lịch Priority Queueing có một số thuận lợi và hạn chế. Các gói trong hàng đợi ưu tiên cao có thể đạt 100% băng thông liên kết, với độ trì hoãn nhỏ và độ biến động trễ nhỏ. Thật ra, khi nghẽn mạch, các gói trong hàng đợi ưu tiên thấp tốn nhiều thời gian phục vụ. Khi liên kết tắc nghẽn, các ứng dụng người dùng có thể ngừng làm việc nếu các gói đặt trong hàng đợi ưu tiên thấp. - Priority Queueing phân lớp các gói dựa trên nội dung của các tiêu đề. Nó sử dụng tối đa 4 hàng đợi. Chỉ áp dụng chính sách hủy gói cuối hàng đợi (tail drop), mặt khác sau khi phân lớp các gói, nếu hàng đợi tương ứng đầy, các gói bị bỏ. Mặt khác, chiều dài mỗi hàng đợi là nguyên nhân ảnh hưởng đến độ trễ và mất gói. Thật ra, Priority Queueing có thể thiết lập chiều dài hàng đợi trở về giá trị 0, có nghĩa là chiều dài hàng đợi “không giới hạn”. “Không giới hạn” có nghĩa là khi bộ định tuyến ra ngoài vùng nhớ, các gói không thể lập lịch, tuy nhiên chúng ta gặp vấn đề rắc rối hơn việc lập lịch cho gói nếu bộ định tuyến ngoài vùng nhớ. 2.5 Các bước mô phỏng bài toán trên GPSS World Qua quá trình nghiên cứu, luận văn áp dụng một quy trình ứng dụng GPSS để mô phỏng một hệ thống hàng đợi được trình bày trong hình 2.7 gồm các bước chính như sau: Bước 1: Xác định vấn đề Mục đích là xác định được mục tiêu và phạm vi mô phỏng, các yếu tố khác liên quan đến bài toán. Xây dựng yêu cầu đầu vào cho bài toán. Xác định cách thức thu thập dữ liệu và kiểm tra dữ liệu. Bước 2: Thiết lập đối tượng Mục đích thiết lập danh sách các đối tượng sẽ sử dụng trong mô phỏng dựa trên đầu vào được xác định ở bước 1. Bước 3: Khái niệm hóa và thu thập dữ liệu Mục đích thiết kế các khái niệm đầu vào và đầu ra của bài toán làm tiêu chuẩn cho bước xác nhận mô hình sau này. Các khái niệm trong quá trình mô phỏng như tập các đối tượng, thực thể, khối sẽ được định nghĩa trước khi xây dựng mô phỏng. Mục đích của quá trình thu thập dữ liệu nhằm thu thập và phân tích dữ liệu đầu vào và đầu ra trong thực tế. Từ đó thống kê, phân tích để lấy được số liệu, xác định hàm phân phối xác suất. Trong đó 2 tham số quan trọng cần xác đinh được trong bước này: - Xác định luật phân bố đầu vào (input) của các kênh phục vụ, 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 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 sử dụng trong chương trình mô phỏng. - Xác định hàm phân phối thời gian phục vụ từ dữ liệu thống kê. Bước 4: Xây dựng mô hình; Sử dụng GPSS để viết mã nguồn chương trình dựa trên các thông tin được xây dựng ở bước 3. Bước 5: Xác minh mô hình Bước này kiểm tra xác minh mô hình đã xây dựng có đúng thiết kế và đảm bảo sử dụng đúng sác xuất hay không. Nếu chương trình có lỗi trong khi kiểm tra thì cần phải chỉnh sửa lại mã nguồn. Nếu chương trình đã đảm bảo các thiết kế của bước 3 thì chuyển sang bước kiểm thử xác nhận. Bước 6: Xác nhận Mục đích của bước này là kiểm thử chấp nhận hệ thống. Bằng cách sử dụng các bộ dữ liệu đầu vào và đầu ra thu được ở bước thu thập dữ liệu để so sánh với kết quả của mô hình tính toán được. Khi mô phỏng đảm bảo thiết kế mà không thu được kết quả phù hợp thì cần xem xét lại mô hình khái niệm. Ngoài ra cũng cần kiểm tra lại các kết quả tính toán có được từ bước thu thập dữ liệu, vì bước này có thể đưa ra tính toán sai về xác suất đầu vào dẫn đến mô phỏng sai. Khi mô phỏng đảm bảo đúng thiết kế và cho ra kết quả phù hợp với đầu ra của hệ thống thực tế, thì mô phỏng đã đúng và có thể sử dụng cho mục đích phân tích hệ thống ở bước sau. Bước 7: Thử nghiệm và phân tích Mục tiêu quan trọng khi xây dựng mô phỏng là cải tiến mô hình. Bước thử nghiệm cho phép người dùng thay đổi tham số hệ thống để phân tích ưu nhược điểm khi cải tiến mô hình. Quá trình thử nghiệm có thể chạy nhiều lần để so sánh các kết quả trước khi triển khai mô hình có kết quả phân tích tốt nhất vào thực tế. Hình 2. 5- Quy trình mô phỏng Một số yếu tố có thể ảnh hưởng đến kết quả mô phỏng: - Đối tượng không rõ ràng, khách quan - Mô hình không hợp lệ, mô hình mô phỏng quá phức tạp hoặc quá đơn giản, giả định sai lầm hay giả định không có căn cứ trên tài liệu. - Sử dụng sai phân bố xác suất đầu vào. 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 [7,10] 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ể, cần xây dựng bảng kết quả và tính toán 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. Một số phương pháp xác minh mô hình mô phỏng là: - So sánh kết quả tính toán từ mô hình với dữ liệu quan sát thực tế. Đây là phương pháp phổ biến và đảm bảo tính chính xác cao. Để làm được điều này cần chuẩn bị nhiều bộ dữ liệu quan sát đảm bảo các ràng buộc của bài toán. VD: thu thập số liệu với ràng buộc thời gian bận vào giờ cao điểm của các quầy thu ngân. Khi làm mô phỏng cần chuẩn bị các bộ dữ liệu vào giờ cao điểm giờ thấp điểm với đầy đủ các thông số cần quan tâm như, lượng khách được ưu tiên, hình thức thanh toán. - Phương pháp thứ hai là so sánh kết quả tính toán từ mô hình với dữ liệu tính toán từ lý thuyết. Phương pháp này được áp dụng khi không thể xây dựng bộ dữ liệu quan sát thực tế. Tuy vậy, lý thuyết hàng đợi đã được chứng minh tính đúng đắn nên hoàn toàn có thể dùng để xác minh mô hình mô phỏng. Hạn chế của phương pháp này là vẫn cần đảm bảo xác định đúng xác suất dòng vào và tốc độ phục vụ vì vậy việc xác minh mô hình không được khách quan. Một lưu ý khi so sánh kết quả nhằm xác minh mô hình là luôn có độ lệch trong phép so sánh. Yếu tố tạo ra chênh lệch chính là yếu tố ngẫu nhiên khi sinh sự kiện. Vì vậy cần kiểm chứng mô hình với nhiều quy mô lấy mẫu khác nhau để tìm ra kết luận. Trong bài toán áp dụng ở chương 3 của luận văn này, do không có điều kiện để thu thập dữ liệu quan sát cụ thể nên đã sử dụng phương pháp tính toán bằng lý thuyết để xác minh mô hình mô phỏng. Kết luận chương Trong chương 2 đã tập trung làm rõ cách tiếp cận bài toán phục vụ đám đông bằng phương pháp mô phỏng. Cung cấp các kiến thức cơ bản về công cụ mô phỏng chuyên dụng GPSS Word. Trong đó, đã đề cập đến tương đối đầy đủ các đối tượng, các khối lệnh liên quan đến đối tượng, cơ chế hoạt động của khác khối lệnh. Từ những hiểu biết đã nêu trên, luận văn đưa ra một quy trình chung bao gồm các bước từ thu thập dữ liệu thực tế cho đến phân tích dữ liệu để thu được phân phối sác xuất của tiến trình đến và tiến trình phục vụ; Từ đó xác định mô hình cần mô phỏng. Mã hóa chương trình mô phỏng và đưa ra các nhận xét kết luận dựa trên kết quả mô phỏng. Trong phần tiếp theo của luận văn sẽ tập trung vận dụng những kiến thức thu thập được từ chương 1 và chương 2 để áp dụng giải bài toán hàng đợi thực tế của siêu thị. 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Ị 3.1 Một số quan sát về hàng đợi siêu thị Bên cạnh các yếu tố chất lượng sản phẩm, giá thì chất lượng dịch vụ cũng là chìa khóa để thu hút khách đến với siêu thị. Hàng đợi với với lượng khách hàng phải chờ phục vụ quá lâu là điều không mong muốn đối với người quản lý. Siêu thị cung cấp nhiều dịch vụ cho khách hàng từ khi vào cho đến khi rời khỏi như: gửi xe, gửi đồ, thử đồ, cân đồ, thanh toán Với các siêu thị lớn tại Hà Nội như Big C, AEON, đều áp mô hình hàng đợi đa hàng, tuy nhiên một số dịch vụ lại áp dụng mô hình đơn hàng như: quầy bánh mì. Phân tích các đặc điểm của hàng đợi trong hoạt động của siêu thị: a. Đặc điểm dòng đến Đặc điểm nhóm dân cư (pollution size) đến với siêu thị: Khách hàng đến với siêu thị có nhu cầu không đồng nhất với nhau: có khách hàng mua hàng có chủ đích và khách hàng đến với những nhu cầu khác như: khảo sát giá, xem hàng rồi mới nảy sinh nhu cầu mua hàng. Nhưng nhìn chung khách đi siêu thị là chủ động và lúc này các siêu thị có thể kiểm soát được hành vi của khách hàng là chấp nhận hay không chấp nhận dịch vụ. Tóm lại, lượng khách hàng đến với các siêu thị (đặc biệt là các siêu thị có mô hình trung tâm thương mại) hay kích thước dòng đến các hàng đợi siêu thị là vô hạn. Dòng đến theo quy luật phân bố Poisson Khách hàng đến trong khoảng thời gian [t, t+s) phụ thuộc vào khoảng thời gian s nhưng không phụ thuộc đến thời gian bắt đầu t. Hay nói cách khác khách hàng đến trong 2 khoảng thời gian không giao nhau là các biến ngẫu nhiên và độc lập. Lượng khách hàng đến tại thời điểm [t+s) hoàn toàn độc lập với khách hàng đến tại thời điểm t. Số lượng khách hàng trong mỗi thời điểm là một biến ngẫu nhiên. Vậy khách hàng đến dịch vụ tại siêu thị là quá trình Poisson và tuân theo phân bố Poisson. Đặc điểm hàng đợi: Hàng đợi tại siêu thị hầu hết là hàng đợi không giới hạn kích thước. Các dịch vụ được cung cấp cũng không phải là dịch vụ khẩn cấp vì vậy hầu hết đều phục vụ theo nguyên tắc FCFS. Tuy nhiên, một số siêu thị trong nước hiện nay đang áp dụng hình thức phân loại quầy hàng dành cho khác hàng mua ít sản phẩm và quầy dành cho khách hàng mua nhiều sản phẩm (Big C Garden), đây là hình thức phân loại mức độ ưu tiên và không ưu tiên trong hàng đợi. Nắm bắt được tâm lý của khách hàng điển hình như: chờ đợi có việc bao giờ cũng tốt hơn chờ đợi không có việc; Các nhà quản lý đã khéo léo đánh lạc hướng cảm giác chờ đợi bằng việc bố trí các màn hình quảng cáo, các kệ sản phẩm nhỏ, các khay đựng catologe, nhằm giúp khách giết thời gian và có thêm thông tin trong quá trình chờ đợi. Vì vậy, tỷ lệ khách hàng từ bỏ hàng đợi không lớn hay có thể xét trường hợp không có khách hàng rời hàng đợi mà vẫn đảm bảo đúng mô hình bài toán. b. Đặc điểm dịch vụ Thiết kế hệ thống dịch vụ Tùy thuộc vào yêu cầu phục vụ từ khách hàng mà các siêu thị bố trí số lượng quầy phục vụ. Đối với quầy thu ngân, hầu hết các siêu thị hiện nay áp dụng mô hình phục vụ đa kênh. Một thực trạng dễ thấy là, những ngày thường khách đến siêu thị phân tán, không tập trung tại một thời điểm, lượng khách vào các ngày thường cũng ít hơn các ngày lễ tết. Tại những giờ thấp điểm như vậy số lượng quầy thanh toán ít đi, những ngày lễ tết các quầy phục vụ hết công suất thậm trí còn mở thêm số lượng quầy. Thời gian phục vụ tuân theo phân bố mũ. Thời gian phục vụ khách hàng là khác nhau. Trong thanh toán – số lượng, chủng loại hàng, hình thức thanh toán (tiền mặt, quẹt thẻ) khác nhau dẫn đến thời gian phục vụ cũng khác nhau. Như đã nêu ở trên, dòng đến tuân theo phân bố Poisson, vậy khoảng thời gian giữa các khách hàng đến tuân theo quy luật phân phối mũ. Mà theo quan sát, thời gian khách hàng đến cũng là thời gian các dịch vụ luôn luôn bận rộn. Vì vậy, có thể kết luận rằng thời gian phục vụ cũng tuân theo phân bố mũ. 3.2 Bài toán xếp hàng gồm 1 phase phục vụ Bài toán xếp hàng không ưu tiên diễn ra ở rất nhiều quầy phục vụ tại siêu thị. Trong bài toán áp dụng này, luận văn trình bày một đại diện cho mô hình hàng đợi đơn giản nhưng có 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. 3.2.1 Phát biểu bài toán 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ị. Vào ngày thường, trung bình có 50 ± 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à 1h. Mục tiêu là mô phỏng: mô phỏng lại hoạt động của bãi đỗ xe 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. 3.2.2 Phân tích bài toán bằng lý thuyết hàng đợi. Đặc điểm của hàng đợi này là: số kênh phục vụ c=80. Không giới hạn kích thước hàng đợi, tuy nhiên xe rời siêu thị ngay khi không có chỗ đỗ. Với số yêu cầu đến hàng đơi trong gian quan sát chỉ phụ thuộc vào độ lớn của chứ không phụ thuộc vào vị trí của trên dòng thời gian. Có thể xác định mô hình hàng đợi mô phỏng đến bãi đậu xe M/M/80/ / /FCFS Ô tô đến xếp hàng đi vào bãi gửi xe theo tần suất xuất hiện là 50±5 giây, vậy giá trị đến trong đơn vị thời gian giờ (h) được tính là: Tốc độ đến Tốc độ phục vụ ( )= 1 khách hàng Số kênh phục vụ (c) =80. Theo những quan sát nêu ở mục 3.1 thời gian phục vụ tuân theo phân bố mũ. Áp dụng lý thuyết hàng đợi ta có: Thời gian trung bình giữa 2 lần khách hàng đến: Thời gian phục vụ trung bình: Hiệu suất phục vụ của hệ thống là: Hiệu suất thỏa mãn điều kiện dừng với Xác suất không có khách hàng trong hệ thống (P0): Dòng vào Bãi đậu xe với 80 vị trí Dòng ra =0.0000 Số xe trung bình trong hệ thống là: 74.36765 (Khách hàng) Thời gian trung bình khách hàng ở trong hàng đợi: Số xe trong hàng đợi phục vụ là: Vì thời gian chờ đợi là 2 phút và chiều dài hàng đợi xấp xỉ 2 khách hàng nên có thể xem là không có khách hàng rời đi mà không được phục vụ. Thời gian trung bình khách hàng trong hệ thống (bao gồm thời gian chờ và được phục vụ) 1.03288 Số xe ô tô đến siêu thị trong thời gian quan sát 8h là: k = *λ = 8*72 = 576 (xe) Thời gian trung bình trong hệ thống của 1 xe là: 1.03288h Số xe ô tô hệ thống có thể phục vụ trong thời gian 8h là: Vậy, Hiệu suất hoạt động của hệ thống là 90%, trung bình có 74 xe trong bãi đỗ. Xác suất số khách hàng trong hệ thống được hiển thị trong hình Hình 3. 1- Đồ thị sác xuất số khách hàng trong hệ thống 3.2.3 Mô phỏng bài toán bằng công cụ mô phỏng 3.2.3.1 Xác định mô hình mô phỏng Từ những kết quả phân tích bài toán bằng lý thuyết, ta xác định được mô hình mô phỏng theo các bước trong sơ đồ trình bày trong hình 3.2 Hình 3. 2- Mô hình thuật toán giải bài toán bãi đậu xe Bảng dưới xác định các thực thể sẽ có trong mô phỏng: TT Loại thực thể Số lượng Ghi chú 1. Thực thể lưu trữ 1 Là thực thể lưu kích thước bãi đỗ xe. 3.2.3.2 Mã hóa chương trình mô phỏng Mã nguồn bài toán mô phỏng được thể hiện trong hình 3.3 Hình 3. 3- Mã nguồn mô phỏng bài toán bãi đỗ xe Một số kết quả thu được sau khi chạy mô phỏng: Số lượng xe đến trong 8h: 576 xe Trong đó: - Số xe được vào bãi gửi xe là : 576 xe. - Số xe không được vào bãi gửi xe là: 0 xe - Số xe đã rời khỏi trong thời gian mô phỏng là: 503 - Số xe ô tô vẫn đang còn ở trong bãi đỗ tại thời điểm dừng mô phỏng là: 73 xe. - Báo cáo thu được sau khi chạy mô phỏng được thể hiện trong hình 3.4. Hình 3. 4- Báo cáo thu được khi chạy mô phỏng 3.2.3.3 Kết luận thu được sau mô phỏng Căn cứ mục tiêu mô phỏng bảng sau so sánh kết quả thu được từ quá trình tính toán: Bảng 3. 1- Kết quả mô phỏng với thời gian 8h 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 Độ lệch Số xe ô tô đến siêu thị 576 576 0% Số xe có chỗ đậu 574 572 1% Lượng xe trung bình trong hệ thống 74 73 1% Lượng xe ô tô đã rời khỏi bãi khi thời gian mô phỏng kết thúc Không xác định 503 Số xe ô tô vẫn ở bãi xe khi thời gian mô phỏng kết thúc Không xác định 73 Số xe không được phục vụ 0 0 0% Kết luận: 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. Thực hiện chạy lại mô hình với thời gian mô phỏng là 16 giờ, 24 giờ, 48 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ư sau: Bảng 3. 2. Kết quả mô phỏng với thời gian khác nhau Số giờ 8 16 24 48 Lý thuyết GPSS Lý thuyết GPSS Lý thuyết GPSS Lý thuyết GPSS Số xe ô tô đến siêu thị 576 576 1152 1153 1728 1728 3456 3459 Số xe ô tô được vào phục vụ tại siêu thị 574 572 1152 1153 1728 1694 3456 3459 Với số lượng xe ô tô đến siêu thị, đây là đại lượng do các hàm toán học phân bố ngẫu nhiên, 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ể, khi thời gian mô phỏng lớn thì độ lệch gần như bằng 0 Xét biến lượng xe ô tô được vào phục vụ tại bãi đỗ xe; Kết quả so sánh ở bảng 3.3 cho 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 Bảng 3. 3- Bảng so sánh độ lệch giữa mô phỏng và tính toán từ lý thuyết của lượng xe được phục vụ Thời gian Lý thuyết GPSS % sai lệch 8 giờ 574 576 1% 16 giờ 1152 1153 1% 24 giờ 1728 1728 0% 48 giờ 3456 3459 0% Kết luận: 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 với kết quả của mô hình lý thuyết. 3.3 Bài toán xếp hàng nhiều phase phục vụ 3.3.1 Phát biểu bài toán Siêu thị Lan Chi có một bãi xe với số lượng 150 chỗ dành cho xe máy và 80 chỗ dành cho xe ô tô. Theo thống kê tỷ lệ xe ô tô so với các phương tiện khác là 3/7. 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ừ 50 ± 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 di chuyển từ bãi đậu xe vào đến siêu thị và lấy giỏ hàng hoặc xe đẩy 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), xác suất chọn vật chứa hàng là: giỏ hàng 0.08; xe đẩy 0.92. 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. Hoạt động của nhân viên thu ngân: 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 khỏi siêu thị. Mục tiêu mô phỏng: Xây dựng mô phỏng hoạt động của bãi đậu xe, giỏ hàng, quầy thanh toán của siêu thị trong thời gian 8h làm việc liên tục. Từ đó đưa ra các kết luận cụ thể cho các đặc trưng của siêu thị như: hệ số sử dụng của bãi xe, xe đẩy, giỏ hàng, quầy thu ngân. 3.3.2 Phân tích bài toán bằng lý thuyết hàng đợi Thời gian khách hàng trong hệ thống được tính như sau: + Thời gian gửi xe: 60 (giây) + Thời gian trung bình mua hàng của khách là: (100+5)/2 *60 = 3150 (giây)=50 phút + Thời gian thanh toán tiền: (100+5)/2 *2 + 120 = 225 (giây) + Thời gian trung bình mang hàng ra xe và rời khỏi bãi xe: 60 (giây) + Tổng thời gian khách trong hệ thống là: 3495 (giây) 1 giờ. + Số lượng khách hàng có thể được phục vụ ở siêu thị là: 28800/3496 x 100 = 824. Mô tả hoạt động hệ thống được trình bày trong hình 3.5 Hình 3. 5- Mô tả mô hình hoạt động của siêu thị Phase 1: Dịch vụ gửi xe Dịch vụ gửi xe gồm 2 hàng đợi: ô tô và xe máy, với sác xuất tương ứng 0.3 và 0.7. Áp dụng cách tính hiệu suất như bài toán 1 ta có kết quả tính toán cho từng hàng đợi như sau: Bảng 3. 4- Kết quả tính toán hàng đợi gửi xe ô tô Đơn vị thời gian 8 Giờ Tốc độ đến (λ) 172.8 khách hàng Tốc độ phục vụ (μ) 8 khách hàng Số kênh phục vụ 80 quầy Thời gian trung bình giữa 2 khách hàng đến 0.006 h Thời gian phục vụ trung bình 0.125 h Lưu lượng hệ thống ((λ/μ) 0.27 Hiệu suất trung bình của hệ thống 27.0% Lượng khách hàng trung bình trong hàng đợi (Lq) 0.00000 khách hàng Lượng khách hàng trung bình trong hệt thống (L) 21.60000 khách hàng Thời gian chờ đợi trung bình của 1 khách hàng (Wq) 0.00000 h Thời gian trung bình của khách hàng trong hệ thống (W) 0.12500 h Xác suất không có khách hàng trong hệ thống (P0) 0.00000 (xác suất hệ thống rảnh) Xác suất tất cả các quầy đều bận 0.00% (tỷ lệ khách hàng phải chờ đợi) Xác suất có ít nhất 1 quầy trống 100.0% (Tỷ lệ khách hàng không phải đợi) Bảng 3. 5-Bảng kết quả tính toán hàng đợi bãi gửi xe máy Đơn vị thời gian 8 giờ Tốc độ đến (λ) 403.2 khách hàng Tốc độ phục vụ (μ) 8 khách hàng Số kênh phục vụ 150 quầy Thời gian trung bình giữa 2 khách hàng đến 0.002 h Thời gian phục vụ trung bình 0.125 h Lưu lượng hệ thống (λ/μ) 0.336 Hiệu suất trung bình của hệ thống 33.6% Lượng khách hàng trung bình trong hàng đợi (Lq) 0.00000 khách hàng Lượng khách hàng trung bình trong hệt thống (L) 50.40000 khách hàng Thời gian chờ đợi trung bình của 1 khách hàng (Wq) 0.00000 h Thời gian trung bình của khách hàng trong hệ thống (W) 0.12500 h Xác suất không có khách hàng trong hệ thống (P0) 0.00000 (xác suất hệ thống rảnh) Xác suất tất cả các quầy đều bận 0.00% (tỷ lệ khách hàng phải chờ đợi) Xác suất có ít nhất 1 quầy trống 100.0% (Tỷ lệ khách hàng không phải đợi) Phase 2: Dịch vụ giỏ hàng, xe đẩy Gồm 2 hàng đợi: giỏ hàng và xe đẩy, với sác xuất chọn lựa vật mang hàng tương ứng 0.08 và 0.92 Áp dụng cách tính hiệu suất như bài toán 1 ta có kết quả tính toán cho từng hàng đợi như sau: Bảng 3. 6- Kết quả tính toán hàng đợi giỏ hàng trong 8h Đơn vị thời gian 8 giờ Tốc độ đến (λ) 46.08 khách hàng Tốc độ phục vụ (μ) 8 khách hàng Số kênh phục vụ 50 quầy Thời gian trung bình giữa 2 khách hàng đến 0.022 h Thời gian phục vụ trung bình 0.125 h Lưu lượng hệ thống (λ/μ) 0.1152 Hiệu suất trung bình của hệ thống 11.5% Lượng khách hàng trung bình trong hàng đợi (Lq) 0.00000 khách hàng Lượng khách hàng trung bình trong hệt thống (L) 5.76000 khách hàng Thời gian chờ đợi trung bình của 1 khách hàng (Wq) 0.00000 h Thời gian trung bình của khách hàng trong hệ thống (W) 0.12500 h Xác suất không có khách hàng trong hệ thống (P0) 0.00315 (xác suất hệ thống rảnh) Xác suất tất cả các quầy đều bận 0.00% (tỷ lệ khách hàng phải chờ đợi) Xác suất có ít nhất 1 quầy trống 100.0% (Tỷ lệ khách hàng không phải đợi) Bảng 3. 7- Kết quả tính toán hàng đợi xe đẩy trong 8h Đơn vị thời gian 8 giờ Tốc độ đến (λ) 529.92 khách hàng Tốc độ phục vụ (μ) 8 khách hàng Số kênh phục vụ 100 quầy Thời gian trung bình giữa 2 khách hàng đến 0.002 h Thời gian phục vụ trung bình 0.125 h Lưu lượng hệ thống (λ/μ) 0.6624 Hiệu suất trung bình của hệ thống 66.2% Lượng khách hàng trung bình trong hàng đợi (Lq) 0.00014 khách hàng Lượng khách hàng trung bình trong hệt thống (L) 66.24014 khách hàng Thời gian chờ đợi trung bình của 1 khách hàng (Wq) 0.00000 h Thời gian trung bình của khách hàng trong hệ thống (W) 0.12500 h Xác suất không có khách hàng trong hệ thống (P0) 0.00000 (xác suất hệ thống rảnh) Xác suất tất cả các quầy đều bận 0.01% (tỷ lệ khách hàng phải chờ đợi) Xác suất có ít nhất 1 quầy trống 100.0% (Tỷ lệ khách hàng không phải đợi) Phase 3: Thanh toán Phase thanh toán có mô hình hàng đợi gồm 5 hàng tương ứng với số quầy thanh toán. Thời gian phục vụ trung bình: 225 giây. Không xác định được tham số ở bước này do tốc độ đến bị ảnh hưởng bởi các bước trước. 3.3.3 Mô phỏng bài toán bằng công cụ mô phỏng 3.3.3.1 Xác định mô hình mô phỏng Hình 3. 6- Mô hình thuật toán hoạt động của siêu thị 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ể Số lượng Ghi chú 2. Thực thể lưu trữ 5 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 3. Thực thể hàng đợi 7 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 4. Thực thể thiết bị 5 Thực thể thiết bị là các quầy thanh toán 5. Thực thể bảng 3 Gồm các thực thể bảng lưu thời gian hệ thống 3.3.3.2 Mã hóa chương trình mô phỏng Chương trình mô phỏng được mã hóa với mã nguồn như trong hình 3.6. ; Khởi tạo các biến RMULT 1187 ; thiết lập bộ sinh số ngẫu nhiên First EQU 1 ; Thứ tự quầy thu thông thường Last EQU 4 ; tbl_time_spent TABLE M1,1000,1000,7 ; Thời gian trong hệ thống tbl_lsItems TABLE P$ls_items,10,10,10 ; Số sản phẩm được mua tbl_cust TABLE X$customer,100,50,12; ; Tạo một bảng lưu số khách hàng s_parkC STORAGE 80 ; Bãi xe ô tô s_parkM STORAGE 150 s_trolley STORAGE 100 ; số lượng xe đẩy cho phép s_cart STORAGE 50 ; số giỏ v_time_work VARIABLE 8#60#60 ; Biến thời gian mô phỏng v_items VARIABLE (RN1@96+5) ; Biến ngẫu nhiên số lượng hàng v_pay VARIABLE (RN1@3+1)#40+150 ; Biến lưu hình thức thanh toán tiền thanh toán v_Cash_time VARIABLE (P$ls_items)#2+120 ; Thời gian thanh toán v_choice_time VARIABLE P$ls_items#60 ; Thời gian chọn hàng INITIAL X$customer,0 ; Khởi tạo biến ****************************************** ;Mô phỏng hoạt động gửi xe s_parking TRANSFER .7,,MOTO TRANSFER both,,Lost ENTER s_parkC; ASSIGN transport,1 ;Gán giá trị 1 nếu là Ô tô TRANSFER ,ChoseCarrier MOTO TRANSFER both,,Lost ENTER s_parkM; ASSIGN transport,2 ;Gán giá trị 2 nếu là xe máy ***************************************** ; Hoạt động di chuyển vào ST và chọn giỏ hàng ChoseCarrier ADVANCE 60,40 ;thời gian khách hàng di chuyển vào siêu thị SAVEVALUE customer+,1 ;tăng số lượng người mua hàng lên 1 ASSIGN ls_items,V$v_items ;gán số lượng hàng ngẫu nhiên ASSIGN pay_method,V$v_pay ; Gán các tham biến cho việc thanh toán tiền TEST LE P$ls_items,10,Qs_trolley ; Số lượng lớn hơn 10 lấy xe đẩy GATE SNF s_cart,Qs_trolley ; Kiểm tra số giỏ hàng và xe đẩy còn lại QUEUE cartQueue ; Hàng đợi của giỏ hàng ENTER s_cart ; Lấy giỏ hang DEPART cartQueue ASSIGN Carrier,s_cart ; Gán vật mang hàng là giỏ hàng TRANSFER ,Shopping ; chuyển các yêu cầu từ thời điểm khách vào siêu thị Qs_trolley QUEUE trolleyQueue ; Hàng đợi của xe đẩy ENTER s_trolley ; lấy xe đẩy DEPART trolleyQueue ASSIGN Carrier,s_trolley ; Gán vật mang hàng là xe đẩy ****************************************** ;Hoạt động chọn hàng Shopping ADVANCE V$v_choice_time ;Thời gian mua hàng TEST LE P$ls_items,10,Norm ;số hàng nếu lớn hơn 10 thì chuyển đến quầy thông thường COUNT L v_Condition,First,Last,2,Q ; Kiểm tra quầy thu ngân trống TEST E P$v_Condition,0,Norm ;Nếu khong co quây trong chuyển sang Nomal QUEUE Quick ; Lấy các thông tin thống kê hàng đợi của quầy phục vụ nhanh SEIZE priorityCash DEPART Quick ; Giải phóng hàng đợi ADVANCE V$v_Cash_time ; Lấy thời gian phục vụ ở quầy phục vụ nhanh RELEASE priorityCash LEAVE P$Carrier ;Giải phóng xe đẩy/giỏ hàng TRANSFER ,fin ;chuyển đối tượng đến block FIN ******************************************* ;Quầy thanh toán thông thường Norm SELECT MIN Basic,First,Last,,Q ; Tìm hàng đợi ngắn nhất QUEUE P$Basic SEIZE P$Basic DEPART P$Basic ADVANCE V$v_Cash_time RELEASE P$Basic LEAVE P$Carrier ;Giải phóng xe đẩy/giỏ hàng ******************************************* ; Mô phỏng hoạt động rời siêu thị fin TABULATE tbl_time_spent ; đặt thời gian để mô phỏng TABULATE tbl_lsItems ; Ghi nhận số lượng hàng hóa được mua SAVEVALUE customer-,1 ; giảm số lượng khách hàng 1 đơn vị ADVANCE 60,50 ; khách hàng di chuyển đến bãi đậu xe TEST LE P$transport,1,MOTOLEAVE ; loại xe khách hàng sử dụng LEAVE s_parkC ; Rời khỏi bãi ô tô TERMINATE MOTOLEAVE LEAVE s_parkM ; Rời khỏi bãi xe máy TERMINATE lost TERMINATE ; Rời siêu thị ****************************************** ; Khối sinh sự kiện khách hàng đến GENERATE 50,5,,,1 TRANSFER ,s_parking ****************************************** GENERATE V$v_time_work ; xác định thời gian mô phỏng của hệ thống TABULATE tbl_cust ; Lấy thông tin về số lượng khách đến siêu thị TERMINATE 1 START 1 Kết quả chạy mô phỏng: GPSS World Simulation Report - MartActivity.11.4 Wednesday, November 08, 2017 16:30:11 START TIME END TIME BLOCKS FACILITIES STORAGES 0.000 28800.000 56 5 4 NAME VALUE BASIC 10028.000 CARRIER 10025.000 CARTQUEUE 10026.000 CHOSECARRIER 9.000 CUSTOMER 10020.000 FIN 42.000 FIRST 1.000 LAST 4.000 LOST 51.000 LS_ITEMS 10022.000 MOTO 6.000 MOTOLEAVE 49.000 NORM 35.000 PAY_METHOD 10023.000 PRIORITYCASH 10030.000 QS_TROLLEY 20.000 QUICK 10029.000 SHOPPING 24.000 S_CART 10014.000 S_PARKC 10011.000 S_PARKING 1.000 S_PARKM 10012.000 S_TROLLEY 10013.000 TBL_CUST 10010.000 TBL_LSITEMS 10009.000 TBL_TIME_SPENT 10008.000 TRANSPORT 10021.000 TROLLEYQUEUE 10024.000 V_CASH_TIME 10018.000 V_CHOICE_TIME 10019.000 V_CONDITION 10027.000 V_ITEMS 10016.000 V_PAY 10017.000 V_TIME_WORK 10015.000 LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY S_PARKING 1 TRANSFER 574 0 0 2 TRANSFER 158 0 0 3 ENTER 158 0 0 4 ASSIGN 158 0 0 5 TRANSFER 158 0 0 MOTO 6 TRANSFER 416 0 0 7 ENTER 416 0 0 8 ASSIGN 416 0 0 CHOSECARRIER 9 ADVANCE 574 1 0 10 SAVEVALUE 573 0 0 11 ASSIGN 573 0 0 12 ASSIGN 573 0 0 13 TEST 573 0 0 14 GATE 50 0 0 15 QUEUE 50 0 0 16 ENTER 50 0 0 17 DEPART 50 0 0 18 ASSIGN 50 0 0 19 TRANSFER 50 0 0 QS_TROLLEY 20 QUEUE 523 0 0 21 ENTER 523 0 0 22 DEPART 523 0 0 23 ASSIGN 523 0 0 SHOPPING 24 ADVANCE 573 62 0 25 TEST 511 0 0 26 COUNT 50 0 0 27 TEST 50 0 0 28 QUEUE 33 0 0 29 SEIZE 33 0 0 30 DEPART 33 0 0 31 ADVANCE 33 0 0 32 RELEASE 33 0 0 33 LEAVE 33 0 0 34 TRANSFER 33 0 0 NORM 35 SELECT 478 0 0 36 QUEUE 478 15 0 37 SEIZE 463 0 0 38 DEPART 463 0 0 39 ADVANCE 463 4 0 40 RELEASE 459 0 0 41 LEAVE 459 0 0 FIN 42 TABULATE 492 0 0 43 TABULATE 492 0 0 44 SAVEVALUE 492 0 0 45 ADVANCE 492 2 0 46 TEST 490 0 0 47 LEAVE 138 0 0 48 TERMINATE 138 0 0 MOTOLEAVE 49 LEAVE 352 0 0 50 TERMINATE 352 0 0 LOST 51 TERMINATE 0 0 0 52 GENERATE 574 0 0 53 TRANSFER 574 0 0 54 GENERATE 1 0 0 55 TABULATE 1 0 0 56 TERMINATE 1 0 0 FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY 1 131 0.951 209.164 1 451 0 0 0 4 2 114 0.876 221.313 1 470 0 0 0 4 3 112 0.848 218.119 1 497 0 0 0 4 4 106 0.811 220.438 1 448 0 0 0 3 PRIORITYCASH 33 0.154 134.424 1 0 0 0 0 0 QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY 1 5 4 135 6 2.752 587.033 614.337 0 2 5 4 118 4 2.514 613.473 634.998 0 3 5 4 116 4 2.318 575.620 596.178 0 4 5 3 109 4 2.067 546.034 566.836 0 TROLLEYQUEUE 1 0 523 523 0.000 0.000 0.000 0 CARTQUEUE 1 0 50 50 0.000 0.000 0.000 0 QUICK 1 0 33 24 0.014 12.303 45.109 0 STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY S_PARKC 80 60 0 33 158 1 18.290 0.229 0 0 S_PARKM 150 86 0 69 416 1 50.723 0.338 0 0 S_TROLLEY 100 19 0 83 523 1 65.696 0.657 0 0 S_CART 50 50 0 4 50 1 1.115 0.022 0 0 TABLE MEAN STD.DEV. RANGE RETRY FREQUENCY CUM.% TBL_TIME_SPENT 3582.860 1806.555 0 _ - 1000.000 46 9.35 1000.000 - 2000.000 60 21.54 2000.000 - 3000.000 95 40.85 3000.000 - 4000.000 94 59.96 4000.000 - 5000.000 71 74.39 5000.000 - 6000.000 74 89.43 6000.000 - _ 52 100.00 TBL_LSITEMS 45.986 27.399 0 _ - 10.000 50 10.16 10.000 - 20.000 63 22.97 20.000 - 30.000 61 35.37 30.000 - 40.000 56 46.75 40.000 - 50.000 58 58.54 50.000 - 60.000 44 67.48 60.000 - 70.000 43 76.22 70.000 - 80.000 44 85.16 80.000 - 90.000 40 93.29 90.000 - _ 33 100.00 TBL_CUST 81.000 0.000 0 _ - 100.000 1 100.00 SAVEVALUE RETRY VALUE CUSTOMER 0 81.000 Kết luận rút ra từ báo cáo mô phỏng được kết xuất từ GPSS như trong bảng 3.1. Bảng 3. 8 – Kết quả mô phỏng hoạt động của siêu thị Chỉ tiêu Số lượng Hiệu suất Thời gian mô phỏng 8h Số khách hàng đến siêu thị trong thời gian mô phỏng 574 Số xe ô tô đến 158 Số xe máy đến 416 Số yêu cầu được phục vụ và hiệu suất sử dụng của bãi gửi xe ô tô 158 0.229 Số yêu cầu được phục vụ và hiệu suất sử dụng của bãi gửi xe máy 416 0.338 Số khách hàng đã vào siêu thị nhưng chưa mua hàng 1 Số yêu cầu và hiệu suất sử dụng giỏ hàng được phục vụ 50 0.022 Số yêu cầu và hiệu suất sử dụng xe đẩy hàng được phục vụ 523 0.657 Số khách hàng thực hiện mua hàng 573 Số yêu cầu thanh toán được phục vụ 511 Lượng khách mua dưới 10 món hàng 50 Số khách hàng và hiệu suất sử dụng thanh toán tại quầy 1 131 0.951 Số khách hàng và hiệu suất sử dụng thanh toán tại quầy 2 114 0.876 Số khách hàng và hiệu suất sử dụng thanh toán tại quầy 3 112 0.848 Số khách hàng và hiệu suất sử dụng thanh toán tại quầy 4 106 0.811 Số khách hàng và hiệu suất sử dụng thanh toán tại quầy thanh toán nhanh 33 0.154 Với kết quả tính toán như trên có thể đưa ra một số kết luận về hoạt động của siêu thị như sau: - Số lượng bãi gửi xe máy và ô tô hiện đang cung cấp vượt nhu cầu sử dụng. Khách hàng hoàn toàn không phải chờ đợi để được gửi xe. - Số lượng giỏ hàng và xe đẩy đáp ứng nhu cầu của khách hàng; tuy nhiên tốc độ đến tăng vào các ngày cuối tuần và ngày lễ thì tỷ lệ khách hàng phải chờ đợi xe đẩy tăng lên nên cần tăng số lượng xe đẩy. - Các quầy thanh toán từ số 1 đến số 4 có hiệu suất hoạt động trung bình là 0.876, với lượng khách hàng chờ đợi trung bình là 4 khách hàng. Quầy thanh toán số 5 hoạt động với hiệu suất 0.154, số khách hàng trung bình phải chờ đợi là 0. Thiết kế quầy thanh toán hiện tại của siêu thị phù hợp với nhu cầu khách hàng. 3.3.3.3 Kết luận thu được sau mô phỏng Từ kết quả tính toán trong mục 3.3.2 ta thấy với phase phục vụ thứ 3- dịch vụ thanh toán, không xác định được đúng tốc độ dòng yêu cầu đến cho từng quầy thanh toán (dưới 10 sản phẩm hay trên 10 sản phẩm) do tốc độ này bị chi phối bởi thời gian phục vụ của các bước trước khi thanh toán. Vì vậy, đối với một số bài toán phức tạp với nhiều phase phục vụ trong cùng một hệ thống chỉ có thể sử dụng mô phỏng để tính toán; và 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ả. 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. Tương tự cách tiến hành với mô hình bài toán bãi gửi xe, thực hiện thay đổi thời gian mô phỏng bằng cách cài đặt lại biến thời gian v_time_work lần lượt bằng các giá trị: 16*60*60, 24*60*60, 40*60*60, 80*60*60 sau đó chạy mô phỏng. Đem so sánh kết quả từng trường hợp với lý thuyết. Bảng 3. 9 đưa ra so sánh thời gian phục vụ của các quầy phục vụ với thời gian trung bình tính toán từ lý thuyết (225 giây). Bảng 3. 10. Bảng so sánh thời gian thanh toán trung bình Thời gian mô phỏng 8 giờ 16 giờ 24 giờ 48 giờ Quầy 1 209.164 222.136 223.685 227.322 Quầy 2 221.313 227.015 229.445 227.459 Quầy 3 218.119 223.653 225.355 230.095 Quầy 4 220.438 221.985 225.533 227.091 Quầy 5 134.42 134.512 134.574 134.342 Trung bình tính toán từ mô phỏng 200.6908 205.8602 207.7184 209.2618 Độ lệch 11% 9% 8% 7% Kết luận chương: Trong chương 3, luận văn trình bày hai bài toán điển hình của hàng đợi siêu thị. Bài toán hàng đợi đơn giản M/M/c (bãi đậu xe) và bài toán hàng đợi phức tạp có ảnh hưởng của các yếu tố: độ ưu tiên, kênh phục vụ với kích thước hạn chế và nhiều phase phục vụ (bài toán hoạt động của siêu thị). Trong đó, việc tính toán bằng lý thuyết với bước thanh toán là khó khăn vì bị chi phối bởi thời gian phục vụ ở các bước trước thanh toán nên không xác định được tốc độ đến. Mô phỏng bằng GPSS có thể giải quyết các khó khăn của phương pháp tính toán bằng lý thuyết và đưa ra những kết quả thử nghiệm phù hợp. Việc thực hiện bài toán đã áp dụng quy trình được nêu ở mục 2.5, tuy nhiên do những hạn chế về thời gian nên chưa áp dụng được triệt để quy trình ở bước thu thập dữ liệu như đã đề xuất, nghĩa là dữ liệu của bài toán vẫn là dữ liệu giả định Kết quả mô phỏng của hai bài toán cho thấy hoạt động của mô hình mô phỏng có thể đưa ra những thông số hợp lý; hoàn toàn có thể tham khảo để đưa ra lời khuyên đầu tư hợp lý nhằm nâng cao chất lượng dịch vụ tại các siêu thị, cho dù đó là các hệ thống có nhiều phase phức tạp. 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. 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 (2010), "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, tr. 1. [2] Hà Quang Thụy (2009), “Chương 5. Hàng đợi (Queue),” Slide bài giảng. Tiếng Anh [3] János Sztrik (2005), "Basic Queueing Theory", Budapest University of Technology and Economics. [4] Ivo Adan and Jacques Resing (2015), "Queueing Systems," Department of Mathematics and Computing Science, Eindhoven University of Technology P.O. Box 513, 5600 MB Eindhoven, The Netherlands. [5] Minuteman Software (2009), "GPSS World reference manual," P.O. Box 131 Holly Springs, NC 27540-0131 U.S.A. [6] William Stallings (2014), "Queue system concept" Supplement to Operating Systems. [7] Anthony Igwe, J.U.Onwumere, Obiamaka P. Egbo (2014) “Efficient Queue Management in Supermarkets: A Case Study of Makurdi Town, Nigeria,” European Journal of Business and Management, University of Nigeria, Enugu Campus, Enugu, Nigeria [8] Alan Pilkington, Royal Holloway (2005), GPSS – Getting Started, University of London [9] Andreas Willig (1999), A Short Introduction to Queueing Theory, Technical University Berlin, Telecommunication Networks Group Sekr. FT 5-2, Einsteinufer 25, 10587 Berlin [10] JSKC Priyangika1 and TMJA Cooray (2015) "Analysis of the Sales Checkout Operation in Supermarket Using Queuing Theory," Proceedings of 8th International Research Conference. [11] Leonard Kleinrock(1975) “Queueing Systems – Volume 1 Theory”, John Wiley and Sons New York [12] John D.C. Little and Stephen C. Graves (2005), "Little's Law" Ch.5, Massachusetts Institute of Technology. [13] Robert B.Cooper (1981) “Intro To Queueing Theory”, Elserier North Holland Phụ lục 2.1 - BẢNG CÂU HỎI KHẢO SÁT (Dành cho nhân viên quầy thanh toán) 1. Thời điểm khách hàng đến quầy thanh toán(*) 2. Có khách hàng chờ đợi được phục vụ khi quầy đang thực hiện thanh toán cho khách hàng khác không? (Có tình trạng khách hàng chờ đợi tại quầy phục vụ không) Y/N? Có Không 3. Nếu có thì có bao nhiêu khách hàng chờ đợi? 1 2 3 Số lượng khác:. 4. Cách thức thanh toán của khách hàng? Tiền mặt Thẻ 5. Số quầy thanh toán như hiện nay có đáp ứng nhu cầu của khách hàng? Thừa Vừa đủ Thiếu 6. Thời điểm khách hàng rời khỏi quầy thanh toán (*) Ghi chú: (*): Câu hỏi bắt buộc có phần trả lời để được coi là bảng khảo sát có giá trị. Phụ lục 2.2: BẢNG TỔNG HỢP KẾT QUẢ KHẢO SÁT Khách hàng thứ Thời gian đến Khoảng TG đến của KH tiếp theo Số khách trong hàng đợi Thời điểm rời dịch vụ Thời gian phục vụ 1 16:50:00 0:00:00 2 16:51:00 0:01:00 2 16:51:00 0:01:00 3 16:53:3 0:02:30 3 16:53:00 0:02:00 3 16:55:0 0:02:00 4 16:54:00 0:01:00 4 16:55:0 0:01:00 5 16:55:00 0:01:00 3 16:56:0 0:01:00 6 16:55:00 0:00:00 2 16:56:0 0:01:00 7 16:56:00 0:01:00 1 16:56:4 0:00:45 8 16:56:00 0:00:00 1 16:57:0 0:01:00 9 16:57:00 0:01:00 0 16:59:1 0:02:10 10 16:58:00 0:01:00 2 16:59:0 0:01:00 11 16:59:10 0:01:10 1 16:59:4 0:00:30 12 17:00:00 0:00:50 0 17:01:0 0:01:00 13 17:01:00 0:01:00 0 17:03:0 0:02:00 14 17:03:00 0:02:00 1 17:03:3 0:00:30 15 17:03:00 0:00:00 3 17:03:4 0:00:40 16 17:03:30 0:00:30 2 17:04:0 0:00:30 17 17:04:00 0:00:30 1 17:05:0 0:01:00 18 17:04:00 0:00:00 0 17:05:0 0:01:00 19 17:05:00 0:01:00 0 17:06:0 0:01:00 20 17:07:00 0:02:0 0 17:17:00 21 17:07:00 0:00:00 0 17:09:0 0:02:00 22 17:09:00 0:02:00 1 17:10:0 0:01:00 23 17:10:00 0:01:00 2 17:11:0 0:01:00 24 17:11:00 0:01:00 1 17:12:0 0:01:00 25 17:12:00 0:01:00 2 17:12:5 0:00:50 26 17:12:50 0:00:50 2 17:14:0 0:01:10 27 17:14:00 0:01:10 3 17:14:3 0:00:30 28 17:14:30 0:00:30 3 17:15:0 0:00:30 29 17:15:00 0:00:30 4 17:18:0 0:03:00 30 17:15:00 0:00:00 5 17:16:0 0:01:00 31 17:15:00 0:00:00 2 17:16:0 0:01:00 32 17:16:00 0:01:00 0 17:17:0 0:01:00 33 17:17:00 0:01:00 2 17:17:3 0:00:30 34 17:18:00 0:01:00 0 17:18:3 0:00:30 35 17:18:00 0:00:00 1 17:19:0 0:01:00 36 17:19:00 0:01:00 2 17:20:0 0:01:00 37 17:19:00 0:00:00 0 17:19:3 0:00:30 38 17:20:00 0:01:00 2 17:21:0 0:01:00 39 17:20:00 0:00:00 2 17:21:0 0:01:00 40 17:21:00 0:01:00 2 17:21:4 0:00:40 41 17:21:00 0:00:00 0 17:21:3 0:00:30 42 17:21:00 0:00:00 0 17:23:0 0:02:00 43 17:21:40 0:00:40 1 17:23:0 0:01:20 44 17:23:00 0:01:20 1 17:23:3 0:00:30 17:08:00 0:01:04 17:09 0:01:04 Kết quả tính toán từ khảo sát: Thời gian khách hàng đến trung bình: 0:00:44 giây = 0.73333 phút Tốc độ đến(trong 1 giờ) : 81.818 khách hàng trên giờ Thời gian phục vụ trung bình của 1 khách hàng: 1.0667 phút Thời gian thu thập dữ liệu: 0:33:00 phút