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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:64

Thêm vào BST

Báo xấu

36
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của đề tài là 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. 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. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

ĐẠ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
i 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ả Vũ Tuấn Doanh Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ii 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 2.3.3. Các trƣờng hợp đặc biệt của hàng đợi M/G/1 .......................... 27 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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 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 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iv 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 theo thời gian........................................................................................... 55 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
v 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 Hình 3.5. Sơ đồ thuật toán mô phỏng hàng đợi của siêu thị ......................... 42 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
1 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.lrc.tnu.edu.vn
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.lrc.tnu.edu.vn
3 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à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 đó. 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. - 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.lrc.tnu.edu.vn
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)  .e   x .  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.lrc.tnu.edu.vn
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ụ.  P: Chế độ có ƣu tiên. 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.lrc.tnu.edu.vn
6 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 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.  Dạng biểu diễn khác: Throughput  Y    (n) Pn , (khách hàng /giây), n 1 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 :  Q  n   npn (khách hàng) n 1 Độ đ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 diễn khác. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
7  Q = T 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):  R == (giây) C 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ụ). B - Thời gian phục vụ (S-service time) đƣợc định nghĩa là : S = C 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 B Cách định nghĩa khác : độ hiệu dạng trung bình U = : Đại lƣợng này T 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 - 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 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
8 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ụ Chi tiết về hệ thống phục vụ sẽ đƣợc trình bày cụ thể trong phần 1.1.2. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
9 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: F x   1  e  x (1.1) Trong đó: F ( x) : Hàm phân bố của phân phối mũ - E k : Phân phối Erlang k pha có hàm phân phối: Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
10 e  x ( x ) j k 1 F x   1   (1.2) j 0 j! 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 đó: F ( x) : 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: k F  x    q j (1  e  j x ) x ≥0 (1.3) j 1 Với: F ( x) : Hàm phân bố của phân phối mũ - D : 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
11 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 Dòng vào tiền định là dòng vào trong đó nhƣ̃ng yêu c ầu đến hệ thống 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 Dt , kể từ thời điểm t , phụ thuộc vào t , nghĩa là: e  a ( t , t ) x( Dt )  at , t x (1.6) ! Trong đó: a(t , Dt ) là số trung bình yêu cầu xuất hiện từ t đến Dt . - Dòng vào Poisson dừng: Là dòng vào mà xác suất trong khoảng thời gian Dt , kể từ thời điểm t , có x yêu cầu xuất hiện, không phụ thuộc vào t , nghĩa là: Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
12 e  t x( Dt )  !  (.t ) x  (1.7) Trong đó: λ là cƣờng độ xuất hiện của dòng yêu cầu. Nếu t 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ì t là một đại lƣợng ngẫu nhiên tuân theo luật chỉ số, nghĩa là t có hàm phân bố xác suất dạng: F t   1  e  t (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: F (t ) = 1- e –μt (1.10) Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
13 Và hàm mật độ xác suất có dạng: –μt f (t ) = μe (1.11) Trong đó: μ: Là cƣờng độ phục vụ của kênh phục vụ. F (t ) : Hàm phân bố xác suất. f (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ụ - 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ờ Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
14 - 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à xk (t ) , 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 t chính là tình huống mà trong hệ thống có k yêu cầu đƣợc phục vụ, hay nói cách khác hệ thống đang có k kênh phục vụ đang bận (đang làm việc) và do đó có (n  k ) 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 xk (t ) (k  0,1, 2,...) nào đó tại thời điểm t , có xác suất là một giá trị xác định Pk (t ) . 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 trạng thái khác. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn