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 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à Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 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 – Hà Nội” cho luận văn tốt nghiệp Thạc sĩ của mình.
Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 Chƣơng 1 CƠ SỞ LÝ THUYẾT VỀ HÀNG ĐỢI 1. Các khái niệm cơ bản 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àng đợi Sự kiện đến Server Sự kiện đi 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 đó. 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. - Dung lƣợng bộ đệm hay dung lƣợng lƣu trữ tại hàng đợi. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 - 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: 1 p ( n) 0 ( x ). 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ũ: p(n) . Phân phối erlang-r ( E 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 hoàn thành: Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 r (r x) e r x p ( x) (r 1)! Phân phối Hypexponential ( H r ): Mỗi giai đoạn trễ trong mô hình E r 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 R R p(n) i i e x ( i ) i i i 1 i 1 Phân phối tổng quát(G-General): p( x) 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ụ. Một số khách hàng đƣợc quyền ƣu tiên hơn những ngƣời khác và đƣợc phục vụ trƣớc. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
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 A - Tốc độ đến của các khách hàng () [3]: = T 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 C bình các khách hàng chuyển qua hệ thống : X = T 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.