Lý thuyết xếp hàng và ứng dụng trong viễn thông

từ chối phục vụ. Lý thuyết quá trình sắp hàng (queueing process) xác định và tìm các phương án tối ưu để hệ thống phục vụ tốt nhất. Trong nửa đầu của thế kỷ 20 lý thuyết sắp hàng đã được ứng dụng để nghiên cứu thời gian đợi trong các hệ thống điện thoại. Ngày nay lý thuyết sắp hàng còn có nhiều ứng dụng trong các lĩnh vực khác nhau như trong mạng máy tính, trong việc quản lý xí nghiệp, quản lý giao thông và trong các hệ phục vụ khác… Ngoài ra lý thuyết sắp hàng cũng còn là cơ sở toán học để nghiên cứu và ứng dụng trong nhiều bài toán kinh tế như đầu tư, kiểm kê, rủi ro của bảo hiểm, thị trường chứng khoán ... Chuỗi Markov là quá trình sắp hàng với thời gian rời rạc đã được xem xét trong giáo trình xác suất thống kê. Quá trình sinh tử cũng là quá trình sắp hàng, trong đó sinh biểu thị sự đến và tử biểu thị sự rời hàng của hệ thống. Đối với lý thuyết sắp hàng ta quan tâm đến các số đo hiệu năng, đó là các giá trị trung bình khi quá trình đạt trạng thái dừng bao gồm: độ dài hàng đợi trung bình của hàng, độ dài hàng đợi trung bình của hệ thống, thời gian đợi trung bình của hàng (trễ của hàng) và thời gian đợi trung bình của hệ thống (trễ của hệ thống). Để tính các đại lượng này ta có thể sử dụng phương pháp giải phương trình tích phân dạng Wiener-Hopf hoặc phương pháp khảo sát chuỗi Markov nhúng. Từ đó suy ra các công thức tính các phân bố ổn định cho các loại hàng M/M/k, M/M/k/N; Công thức tổng quát tính các giá trị trung bình này cho các hàng G/G/1 và công thức cụ thể cho các hàng đặc biệt M/M/1, M/D/1 và M/Ek/1.. Hướng ứng dụng vào viễn thông: Một trong những bài toán quan trọng của lý thuyết chuyển mạch là vấn đề xung đột thông tin, nghẽn mạch hoặc rớt cuộc gọi. Lý thuyết sắp hàng sẽ xác lập phương án tối ưu để khắc phục những vấn đề trên. Ngoài ra lý thuyết sắp hàng cũng được ứng dụng rộng rãi trong các hệ phục vụ khác. II. NỘI DUNG 2.1. KHÁI NIỆM VÀ PHÂN LOẠI QUÁ TRÌNH SẮP HÀNG 2.1.1. Khái niệm quá trình sắp hàng Mô hình tổng quát của lý thuyết sắp hàng là khách hàng đến ở một thời điểm ngẫu nhiên nào đó và yêu cầu được phục vụ theo một loại nào đó. Giả thiết thời gian phục vụ có thể ngẫu nhiên Nguồn vào Phương tiện phục vụ Đầu ra Độ dài hàng đợi Độ dài hàng đợi của hệ thống Các khách hàng đã được phục vụ Các khách hàng yêu cầu và tìm kiếm dịch vụ Quá trình đến Quá trình đến trung gian tn Hàng đợi -Dung lượng: Hữu hạn hoặc vô hạn - Quy tắc phục vụ: FIFO hoặc LIFO Đặt tn là khoảng thời gian giữa 2 lần đến của khách hàng thứ n và thứ n+1. Ta giả định rằng tất cả các tn (n ≥ 1) là độc lập và có cùng phân bố. Vì vậy việc đến của các khách hàng tạo thành 1 hàng kế tiếp nhau với tốc độ đến là . Ta gọi quá trình {tn, n=1,2,…} là quá trình đến. Khách hàng đến hệ thống yêu cầu các server của hệ thống phục vụ. Ta giả sử rằng khách hàng thứ n cần một thời gian phục vụ là (n ≥ 1), tất cả các độc lập và có cùng phân bố. Quá trình được gọi là quá trình phục vụ. Ta cũng giả thiết rằng các thời gian đến trung gian độc lập với thời gian phục vụ. Quá trình sắp hàng được phân loại dựa vào các tiêu chí sau: 1) Phân bố của quá trình đến (input process) 2) Phân bố của thời gian phục vụ (service distribution) 3) Nguyên tắc phục vụ: Các khách hàng đến được sắp xếp vào hàng đợi đến lượt được phục vụ. Để đơn giản ta giả thiết chỉ có một hàng. Tuy nhiên trong nhiều trường hợp có thể mở rộng cho nhiều hàng cùng hoạt động song song. Nếu độ dài hàng có đặt ngưỡng thì các đơn vị đến hàng khi hàng đầy vượt ngưỡng sẽ bị loại. Các khách hàng được chọn để phục vụ theo nguyên tắc "đến trước phục vụ trước" (FIFO), nghĩa là phục vụ cho khách nào đứng đầu hàng. 4) Cơ cấu phục vụ: Một phương tiện phục vụ bao gồm một hay nhiều Server. Các Server có thể kết nối thành chuỗi vì thế mỗi yêu cầu phục vụ được phục vụ theo nhiều cách hoặc lần lượt hoặc song song. 2.1.2.Các yếu tố cơ bản của hệ thống hàng đợi KÊNH PHỤC VỤ Input Dòng tín hiệu đến Output Dòng tín hiệu ra Hàng chờ Hệ thống hàng đợi tổng quát được minh hoạ như trên hình sau. Hình I.2.1. Hệ thống hàng đợi Các yếu tố cơ bản của hệ thống hàng đợi bao gồm: a. Bố trí vật lí của hệ thống Hệ thống hàng đợi có một số dạng bố trí vật lí (phisical layout) như minh hoạ trên hình I.2.2 Single Channel – Single Server (Một kênh phục vụ, một loại dịch vụ) Single Channel – Multi Server (Một kênh phục vụ, nhiều loại dịch vụ) Dịch vụ 1 Dịch vụ 2 Dịch vụ 3 Multi Channel – Single Server (Nhiều kênh phục vụ, một loại dịch vụ) Multi Channel – Multi Server (Nhiều kênh phục vụ, nhiều loại dịch vụ) Dịch vụ 1 Dịch vụ 2 Hình I.2.2. Các dạng hệ thống hàng đợi Trên hình I.2.2, các kênh phục vụ được hiểu là những thiết bị kĩ thuật hoặc con người hoặc những tổ hợp các thiết bị kĩ thuật và con người được tổ chức quản lí một cách thích hợp nhằm phục vụ các yêu cầu / các tín hiệu đến hệ thống. Chẳng hạn, ở các trạm điện thoại tự động, kênh phục vụ là các đường dây liên lạc cùng các thiết bị kĩ thuật khác phục vụ cho việc đàm thoại. b. Nguyên tắc phục vụ Nguyên tắc phục vụ (hay nội quy) của hệ thống là cách thức nhận các yêu cầu vào các kênh phục vụ. Nguyên tắc phục vụ cho biết trường hợp nào thì yêu cầu được nhận vào phục vụ và cách thức phân bố các yêu cầu vào các kênh như thế nào. Đồng thời nguyên tắc phục vụ cũng cho biết trong trường hợp nào yêu cầu bị từ chối hoặc phải chờ và giới hạn của thời gian chờ. Một số nguyên tắc phục vụ thường được áp dụng trong các hệ thống hàng đợi là FIFO (First in first out), LIFO (Last in first out), FCFS (First come first serve), có ưu tiên, không ưu tiên,... c. Các phân phối xác suất của các dòng tín hiệu, dòng phục vụ Số tín hiệu đến trong một khoảng thời gian cũng như thời gian phục vụ từng tín hiệu nói chung là những biến ngẫu nhiên, và do đó, chúng tuân theo các quy luật phân phối xác suất. Các quy luật phân phối xác suất này được thiết lập căn cứ các số liệu thực nghiệm thu thập từ các quan sát, thí nghiệm, hay từ cơ sở dữ liệu sẵn có. Đối với dòng tín hiệu đầu vào, thông thường chúng ta giả sử rằng số tín hiệu đến trong vòng một khoảng thời gian nào đó được ấn định trước (1 phút, 3 phút, 5 phút, 30 phút,...) tuân theo luật phân phối Poisson P(l). Ở đây, tham số l đặc trưng cho số tín hiệu đến (trung bình) trong khoảng thời gian trên. Ví dụ, số khách vào siêu thị (trung bình) là 100 người trong 1 giờ. Có nghĩa là, số khách vào siêu thị là biến ngẫu nhiên X có phân phối Poisson với l = 100. Hoặc, với số cuộc gọi (trung bình) đến tổng đài trong vòng 1 phút là 3 (tín hiệu) thì có X ~ P(3). Một cách chính xác hơn, trong những trường hợp trên, ta có dòng tín hiệu đến là dòng Poisson dừng (còn gọi là dòng tối giản) với các tính chất trên sau: Tính không hậu quả: Một dòng tín hiệu có tính không hậu quả nếu xác suất xuất hiện một số tín hiệu nào đó trong một khoảng thời gian nhất định không phụ thuộc vào việc đã có bao nhiêu tín hiệu đã xuất hiện và xuất hiện như thế nào trước khoảng thời gian đó. Tính đơn nhất: Dòng tín hiệu có tính đơn nhất nếu xét trong khoảng thời gian khá bé thì sự kiện “có nhiều hơn một tín hiệu xuất hiện” hầu như không xảy ra. Về mặt thời gian ta có thể xem dòng tín hiệu có tính đơn nhất nếu thời điểm xuất hiện các tín hiệu không trùng nhau. Tính dừng: Dòng tín hiệu có tính dừng nếu xác suất xuất hiện một số tín hiệu nào đó trong khoảng thời gian t chỉ phụ thuộc vào độ dài của t chứ không phụ thuộc vào điểm khởi đầu của t. 2.1.3. Phân tích hàng đợi: Có các phương pháp phân tích hàng đợi như sau Phân tích giải tích Quá trình mô phỏng Cả hai phương pháp trên Phương pháp giải tích để giải mô hình hàng đợi gồm các bước sau: Bước 1: Phân tích hệ thống, chủ yếu là phân tích bản chất của dòng yêu cầu / tín hiệu đến 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 cho các xác suất trạng thái (xác suất để hệ thống ở một trạng thái nào đó tại thời điểm t). Bước 3: Giải hệ phương trình để tìm các xác suất trạng thái. Từ đó thiết lập các 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 các nhận xét và các quyết định. Phương pháp giải tích thường sử dụng các giả thiết rất chặt chẽ của Toán học về các đặc trưng của hệ thống, vì vậy nó có một số hạn chế nhất định khi giải các bài toán thực tế. Trong khi đó, phương pháp mô phỏng / mô phỏng ngẫu nhiên để giải mô hình hàng đợi được áp dụng cho các bài toán dịch vụ đám đông không giải được bằng công cụ giải tích, nhất là những bài toán liên quan đến hệ thống lớn, bất ổn định, hàm chứa nhiều yếu tố ngẫu nhiên, không tuân theo các giả thiết quá chặt chẽ của Toán học. Trong nhiều trường hợp phương pháp mô phỏng cho ta tiết kiệm được thời gian và chi phí nghiên cứu. Tuy phương pháp mô phỏng chỉ tạo ra các phương án đủ tốt để đánh giá hoạt động của hệ thống chứ không đưa ra được kĩ thuật tìm lời giải tốt nhất, nó tỏ ra rất thành công khi giải quyết nhiều bài toán hàng đợi nảy sinh từ thực tiễn. Các bước cần tiến hành khi áp dụng phương pháp mô phỏng bao gồm: Bước 1: Xác định bài toán hay hệ thống hàng đợi cần mô phỏng và mô hình mô phỏng. Bước 2: Đo và thu thập số liệu cần thiết cần thiết để khảo sát thống kê các số đặc trưng / các yếu tố cơ bản của mô hình. Bước 3: Chạy mô phỏng kiểm chứng (test simulation) mô hình và so sánh kết quả kiểm chứng với các kết quả đã biết được trong thực tế. Phân tích kết quả chạy mô phỏng kiểm chứng, nếu cần thì phải sửa lại phương án đã được đánh giá qua chạy mô phỏng. Bước 4: Chạy mô phỏng để kiểm chứng phương án cuối cùng và kiểm tra tính đúng đắn của mọi kết luận về hệ thống thực tế được rút ra sau khi chạy mô phỏng. Triển khai hoạt động của hệ thống hàng đợi dựa trên phương án tìm được. Từ những phân tích trên đây có thể thấy Lí thuyết xếp hàng còn gọi là Lí thuyết hệ phục vụ công cộng hay Lí thuyết hệ dịch vụ đám đông là lĩnh vực rất quan trọng của Toán ứng dụng / Vận trù học. Nhiều bài toán thực tế trong các lĩnh vực hệ thống dịch vụ, kĩ thuật, … đã được giải quyết thành công nhờ áp dụng phương pháp mô phỏng mô hình hàng đợi. Kết quả phân tích (về phía khách hàng) • Thời gian xếp hàng (trễ hàng đợi) • Tổng trễ (bao gồm trễ hàng đợi và trễ phục vụ ) • Số lượng khách hàng trong hàng đợi • Số lượng khách hàng trong hệ thống (gồm khách hàng chờ và khách hàng đang được phục vụ ) • Xác suất nghẽn mạng (khi kích thước bộ đệm hữu hạn) • Xác suất chờ để phục vụ Kết quả phân tích (về phía hệ người phục vụ) • Khả năng sử dụng server • Khả năng sử dụng bộ đệm • Lợi ích thu được (thông số dịch vụ và các xem xét về kinh tế) • Lợi ích bị mất (thông số dịch vụ và các xem xét về kinh tế) Ta Phân tích hàng đợi sau: tốc độ đến trung bình , thời gian đến trung bình 1/μ tốc độ phục vụ trung bình, thời gian phục vụ trung bình 1/μ Với kích thước của bộ đệm là vô hạn, quy tắc phục vụ là FIFO - Sự kiện A: có 1 sự đến trong t - Sự kiện B: không có sự đến nào trong t - Sự kiện C: có nhiều hơn 1 sự đến trong t Giả sử rằng t→ 0 . Như vậy ta sẽ có: Số lượng sự kiện đến tuân theo phân bố Poisson Định nghĩa luật phân bố Poisson Đồng thời, khoảng thời gian đến (được tính giữa hai sự đến liên tiếp) tuân theo luật phân bố mũ. - Sự kiện A: có 1 sự kiện đi trong t - Sự kiện B: không có sự kiện đi nào trong t - Sự kiện C: có nhiều hơn 1 sự kiện đi trong t Giả sử rằng t →0 Như vậy ta sẽ có: • D là sự kiện của 1 hoặc nhiều sự đến AND với sự kiện của 1 hoặc nhiều sự đi trong khoảng t. Giả sử Pr{D}=0 • Định nghĩa là xác xuất mà hệ thống có N khách hàng tại thời điểm t Từ đó ta có • Ở điều kiện ổn định, khi t→∞, ta có: Tức là xác xuất hệ thống rơi vào một trạng thái nào đó không phụ thuộc thời gian nữa... • Xét trong một khoảng thời gian đủ lớn, số lượng khách hàng lưu trong hệ thống được tính theo công thức: • Số lượng khách hàng lưu trong hàng đợi được tính bằng: •Thời gian một khách hàng lưu lại trong hệ thống bao gồm: -Thời gian chờ xếp hàng -Thời gian phục vụ Hàng đợi Sự kiện đến SERVER Sự kiện đi Giả thiết: -Hệ thống ở trạng thái ổn định tức -Quy tắc phục vụ là FIFO Tổng thời gian lưu trong hệ thống: Tổng thời gian chờ trong hàng đợi: Sự kiện một khách hàng đến phải đợi chính là khi trong hệ thống có ít nhất 1 khách hàng: Đây cũng chính là xác suất hệ thống ở trạng thái bận 2.1.4. Phân loại Kendall Kendall (1951) đã đưa ra ký hiệu A/B/C/K/N/D để mô tả các tham số cơ bản của hệ thống sắp hàng, Thông thường được viết gọn lại dưới dạng A/B/C/K. Ví dụ: M/M/k, G/M/k/N. Trong đó. A Biểu diễn dạng của phân bố thời gian đến trung gian B Dạng phân bố thời gian phục vụ C Số Server K Số lượng vị trí trong hàng đợi N Số lượng khách hàng D Nguyên tắc phục vụ: FIFO, LCFS, SIRO, PNPN.. A và B có thể mang bất kỳ kiểu phân bố sau đây: Ký hiệu Dạng phân bố M Phân bố theo cấp số nhân (Markovian) Phân bố Erlang-k G Phân bố được xét dưới dạng tổng quát D Hằng số ( Deterministic). Cụ thể như sau: * Nếu luật phân bố được xét dưới dạng tổng quát thì A hoặc B lấy ký hiệu G (General). Đôi khi người ta còn ký hiệu GI (general independence). * Nếu quá trình đến là quá trình Poisson, nghĩa là thời gian đến trung gian có phân bố mũ thì A được ký hiệu M (Markovian). Tương tự nếu thời gian phục vụ có phân bố mũ thì B cũng được ký hiệu M . * Nếu thời gian đến trung gian hoặc thời gian phục vụ có phân bố Erlang-k thì A , B được ký hiệu . * Nếu thời gian đến trung gian hoặc thời gian phục vụ là hằng số thì A hoặc B được ký hiệu D (Deterministic). Khi một vài thiết bị phục vụ có dung lượng hữu hạn thì hệ thống chỉ có thể chứa đến khách hàng. Nếu ở trong hàng đã có khách hàng chưa được phục vụ thì khách hàng mới đến sẽ bị từ chối hoặc bị mất. Trong trường hợp này hệ thống được ký hiệu A/B/k /N. 2.1.5. Các số đo hiệu năng Đó là các giá trị trung bình khi quá trình đạt trạng thái dừng bao gồm: độ dài hàng đợi trung bình của hàng, độ dài hàng đợi trung bình của hệ thống, thời gian đợi trung bình của hàng (trễ của hàng) và thời gian đợi trung bình của hệ thống (trễ của hệ thống) 1) Tỉ lệ tới trung bình (λ) Tỉ lệ tới trung bình chỉ ra "số kì vọng các khách hàng tới theo đơn vị thời gian ", được biểu diễn bởi "λ"(lambda). Thời gian tới trung bình có thể thu được bằng việc dùng biểu thức sau. Thời gian tới trung bình = 1 / Tỉ lệ tới trung bình = 1 / λ Chẳng hạn, nếu có 4 lần tới được trông đợi trong một phút, Tỉ lệ tới trung bình (λ) = 4 lần khách hàng tới trong một phút Thời gian tới trung bình = 1/4 phút cho mỗi lần khách hàng tới = 15 giây cho mỗi lần khách hàng tới Tức là, về trung bình khách hàng tới cứ sau mỗi 15 giây 2) Tỉ lệ phục vụ trung bình (μ) Tỉ lệ phục vụ trung bình nghĩa là "số lượng trông đợi các khách hàng được hoàn thành phục vụ theo đơn vị thời gian ", được biểu diễn bởi "μ". Thời gian phục vụ trung bình có thể thu được bằng việc dùng biểu thức sau. Thời gian phục vụ trung bình = 1 / Tỉ lệ phục vụ trung bình = 1 /μ Chẳng hạn, nếu dịch vụ cho 5 khách hàng có thể được hoàn tất trong mỗi phút, Tỉ lệ phục vụ trung bình (λ) = 5 khách hàng một phút Thời gian phục vụ trung bình = 1/5 phút cho mỗi khách hàng = 12 giây cho mỗi khách hàng Tức là,về trung bình phải mất 12 giây để phục vụ một khách hàng. Nếu μ>λ hay 1/μ < 1/λ là đúng trong hệ thống xếp hàng, thì hệ thống này được gọi là trong "điều kiện trạng thái vững vàng ". 3) Cường độ lưu thông (ρ) Cường độ lưu thông biểu diễn cho "phân số trông đợi về thời gian các nguồn phục vụ riêng lẻ bận rộn",được kí hiệu bởi "ρ"(rho). Điều này có thể thu được bằng việc dùng biểu thức sau. Cường độ lưu thông (ρ) = Tỉ lệ tới trung bình / Tỉ lệ phục vụ trung bình = λ/μ = 1/μ/ 1/λ = Thời gian phục vụ trung bình / Thời gian khoảng tới trung bình < 1 Chẳng hạn, nếu có bốn khoảng tới khách hàng trông đợi trong mỗi phút, và việc phục vụ cho 5 khách hàng có thể được hoàn thành trong một phút, Cường độ lưu thông (ρ) = 4/5 =0.8→80% hay 12(sec) / 15(sec) = 0.8→80% Điều này nghĩa là từng nguồn phục vụ đều bận đến 80% thời gian. Cường độ lưu thông nên nhỏ hơn 100%. Bởi vì khi nó bằng hay lớn hơn 100%, thì bao giờ cũng có khách hàngchờ đợi trong hàng đợi. Do đó, trong trường hợp như vậy, những biện pháp nào đó (như phân bổ thêmnguồn phục vụ phụ) nên được tính tới để làm cho nó nhỏ hơn 100%. 4)Độ dài hàng đợi trung bình của hệ thống (Số khách hàng trung bình trong hệ thống) (L) Số khách hàng trung bình trong hệ thống là "số trông đợi về các khách hàng trong hệ thống xếp hàng, kể cả đang đợi phục vụ và hiện đang được phục vụ ", được kí hiệu là L. Chúng ta có thể tính số này từ cường độ lưu thông ρ bằng việc dùng phương trình sau. Số khách hàng trung bình trong hệ thống (L) = cường độ lưu thông / (1- cường độ lưu thông)=ρ/ (1-ρ) Chẳng hạn, nếu 4 khách hàng xuất hiện trong một phút và 5 khách hàng có thể nhận được phục vụ trong một phút,Số trung bình các khách hàng trong hệ thống (L) = 0.8 / (1-0.8) = 4 Điều này chỉ ra rằng về trung bình 4 khách hàng đang trong hệ thống xếp hàng, chờ nhận được phục vụ. 5) Thời gian đợi (chờ) trung bình trong hệ thống (W) Thời gian cần dùng trung bình cho khách hàng trong hệ thống là "thời gian chờ đợi được trông đợi trong hệthống (kể cả thời gian phục vụ)", được kí hiệu bởi W. Số này có thể được tính từ số trung bình các khách hàngtrong hệ thống (L) và tỉ lệ tới trung bình (λ) (hay thời gian khoảng tới trung bình (1/λ)), bằng việc dùngđẳng thức sau: Thời gian cần dùng trung bình cho khách hàng trong hệ thống (W) = số khách hàng trung bình trong hệ thống×(1/tỉ lệ tới trung bình) = L×1/λ = số khách hàng trung bình trong hệ thống × thời gian khoảng tới trung bình Chẳng hạn, nếu 4 khách hàng xuất hiện trong một phút và 5 khách hàng có thể nhận được phục vụ trong một phút,Thời gian cần dùng trung bình cho khách hàng trong hệ thống (W) = 4×1/4 = 1 phútĐiều này nghĩa là thời gian giữa việc khách hàng tới và việc hoàn thành dịch vụ là trung bình một phút.Tồn tại đẳng thức khác cho việc tính thời gian cần dùng trung bình cho khách hàng trong hệ thống (W). Đẳngthức sau tính W như tổng của thời gian phục vụ trung bình (1/μ) và thời gian trung bình cho khách hàng tronghàng đợi (Wq). (Thời gian trung bình cho khách hàng trong hàng đợi (Wq) sẽ được giới thiệu muộn hơn.) Thời gian cần dùng trung bình cho khách hàng trong hệ thống (W) = thời gian trung bình cho khách hàng trong hàng đợi + thời gian phục vụ trung bình = Wq+ 1/μ 6) Độ dài hàng đợi trung bình của hệ thống (Số khách hàng trung bình trong hàng đợi) (Lq) Số khách hàng trung bình trong hàng đợi là "chiều dài hàng đợi dự kiến (loại ra các khách hàng đang được phục vụ)", được kí hiệu bởi Lq. Điều này được tính bằng phương trình sau, dùng số khách hàng trung bình trong hệ thống (L) và cường độ lưuthông (ρ). Số trung bình các khách hàng trong hàng đợi (Lq) = số trung bình các khách hàng trong hệ thống (L) × cường độ lưu thông (ρ) = (cường độ lưu thông) / (1 - cường độ lưu thông) =ρ/ (1-ρ) Chẳng hạn, nếu 4 khách hàng xuất hiện trong một phút và 5 khách hàng có thể nhận được phục vụ trong một phút,số trung bình các khách hàng trong hàng đợi (Lq) = 4×0.8 = 3.2 hoặc/ (1 - 0.8) = 3.2 Điều này chỉ ra rằng về trung bình 3.2 khách hàng là trong hàng đợi, chờ được phục vụ. 7) Thời gian đợi trung bình của hàng (Thời gian trung bình của khách hàng trong hàng đợi) (Wq) Thời gian trung bình của khách hàng trong hàng đợi là "thời gian đợi dự kiến trong hàng đợi (trừ thời gian phục vụ)", được kí hiệu bởi Wq. Điều này có thể được tính từ số trung bình các khách hàng trong hàng đợi (Lq) và tỉ lệ tới trung bình (λ) (haythời gian khoảng tới trung bình (1/λ)), bằng việc dùng phương trình sau. Thời gian trung bình của khách hàng trong hàng đợi (Wq) = số trung bình các khách hàng trong hàng đợi × (1/tỉ lệ tới trung bình) = Lq ×1/λ = số trung bình các khách hàng trong hàng đợi × thời gian khoảng tới trung bình Chẳng hạn, nếu 4 khách hàng xuất hiện trong một phút và 5 khách hàng có thể nhận được việc phục vụ trong một phút, Thời gian trung bình của khách hàng trong hàng đợi (Wq) = 3.2[khách hàng] × (1[phút] / 4[khách hàng]) = 0.8[phút] = 48[giây] Điều này chỉ ra rằng trung bình phải mất 48 giây đối với một khách hàng tới thì nó mới nhận được việc phụcvụ. Dưới đây là các công thức cho lí thuyết hàng đợi có liên quan lẫn nhau. Tính ρ từ λ và μ ρ=λ/μ Tính L từ ρ L =ρ/ (1-ρ) Tính W từ L W = L×(1/λ) Tính Lq từ L Lq= L×ρ Tính Wq từ Lq Wq = Lq ×(1/λ) 2.1.6. Kết quả nhỏ ( Little's result ) Công thức liên hệ giữa độ dài hàng đợi và thời gian đợi ở trạng thái cân bằng L = λW (2.1) Lq=λWq (2.2) trong đó λ là tốc độ đến được định nghĩa như sau: λ=limn→∞E{số khách đến trong khoảng (0;t]t *Kết quả là kết quả nhỏ của định lý Little : Tính trung bình, số lượng khách hàng nằm trong hệ thống được tính bằng tích của tốc độ đến và thời gian phục vụ: Công thức Little: • Ký hiệu: N(t): số lượng khách hàng nằm trong hệ thống tại thời điểm t : số lượng khách hàng đến hệ thống khoảng thời gian (0,t) : số lượng khách hàng rời khỏi hệ thống trong (0,t) : thời gian chiếm dùng của khách hàng i Đẳng thức sau đây đúng vì 2 vế đều biểu diễn diện tích phần màu đậm: Tương đương với: 2.1.7 Quá trình sinh tử (Birth-Death) Trạng thái của hệ thống đượ c biểu diễn bằng số các công việc ntrong một hệ thống Khi có một công việc mới đến thì trạng thái của hệ thống sẽ thay đổi sang n+1, khi có một công việc ra đi thì trạng thái hệ thống sẽ thayđổi sang n-1, ta có lược đồ chuyển tiếp trạng thái là quá trình sinh tử Trong đó , là tốc độ sự kiện đến và đi xét tại trạng thái i pn= λ0λ1…λnμ1μ2…μnp0 ;với pn là xác suất ổn đinh trạng thái n Với một hệ thống dừng và ổn định thì tổng các dòng đi vào một trạng thái bằng tổng các dòng đi ra 2.2. HÀNG M /M / k 2.2.1. Trạng thái ổn định của hàng M /M / k Hàng M /M / k có quá trình đến Poisson, thời gian phục vụ theo phân bố mũ và k Server. Trong trường hợp này chuỗi thời gian liên tục {l(t)}t≥0 với không gian trạng thái {0,1,2,...} là một quá trình sinh tử vô hạn có có tốc độ sinhλi = λ và tốc độ tử μi= min(k,i)μ. * Khi λ> kμ hay cường độ lưu thông (traffic intensity) ρ=λμ>k thì hệ thống không đạt được trạng thái ổn định. Chuỗi l(t) t≥0 không hồi qui (transient). Số các khách hàng trong hệ thống sẽ dần đến vô hạn. * Khi λ = kμ hay ρ = k , chuỗi l(t) t≥0 hồi qui không (null - recurrent), hệ thống cũng không đạt trạng thái ổn định. Số khách hàng trong hệ thống không tiến về một trạng thái nào. Thời gian trung bình để hệ thống xuất phát từ một trạng thái bất kỳ quay về lại trạng thái này là vô hạn. * Khi λ<kμ hay ρ<k , chuỗi l(t) t≥0 hồi qui dương (positive recurrent) và hệ thống đạt được trạng thái ổn định. Nghĩa là khi tốc độ đến nhỏ hơn tốc độ phục vụ tối đa của hệ thống thì số khách hàng ở trong hệ thống có khuynh hướng tiến về không và hệ thống quay trở lại trạng thái 1 nếu có một khách hàng mới đến khi hệ thống đang rỗng. * Tại thời điểm t bất kỳ đặt là khoảng thời gian cho đến khi khách hàng tiếp theo rời khỏi hệ thống. Định lý Burke phát biểu rằng khi t →∞ thì d (t) có phân bố mũ với tham số λ và độc lập với số khách hàng trong hệ thống tại thời điểm t. Nói cách khác, chuỗi giới hạn các khách hàng rời khỏi hệ thống M /M / k là một quá trình Poisson tham số λ (Burke, 1976). 2.2.2. Phân bố dừng của hàng M /M / k Khi λ<kμ hay ρ=λμ<k thì hệ thống đạt trạng thái ổn định có phân bố dừng thoả mãn: pn+1= λ0λ1…λnμ1μ2…μn+1p0= (2.4) Từ điều kiện suy ra (2.5) 2.2.3. Hàng M /M / k / N Đây là hàng có quá trình đến Poisson với tốc độ λ , thời gian phục vụ có phân bố mũ tốc độ μ với k Server. Trạng thái của hệ thống bị giới hạn bởi số lượng N. Khi một khách hàng đến hệ thống thì xảy ra hiện tượng sau: Nếu đã có đủ N khách hàng trong hàng thì lập tức khách hàng này rời khỏi hệ thống còn trường hợp ngược lại thì khách hàng sẽ xếp vào xếp hàng. Như vậy không gian trạng thái của chuỗi lt t≥0 là {0,1,…,N}, đây là một quá trình sinh tử hữu hạn. Chuỗi l(t) chuyển từ trạng thái i đến i +1 khi một khách hàng đến và đổi trạng thái i về i −1 khi một phục vụ vừa hoàn tất. Tốc độ sinh là hằng số λi= λ với mọi i=1,2,…. Tốc độ tửμi= min(k,i)μ Hệ thống đạt trạng thái ổn định với phân bố dừng thoả mãn: (2.6) (2.7) Một vài trường hợp đặc biệt ♦ Khi N →∞ ta có nhận được công thức (2.4)-(2.5) của trường hợp M /M / k. ♦ Khi N = k ta được công thức mất của Erlang (Erlang's loss formula). 2.3. HÀNG G/G/1 Hệ thống có 1 Server, quá trình đến là tổng quát nhưng các thời gian đến trung gian tn độc lập, có cùng phân bố và có kỳ vọng chung là E[t1]. Thời gian phục vụ trong mỗi chu kỳ cũng độclập, cùng phân bố và có kỳ vọng chung E[s1]. Kendall ký hiệu hệ thống này là G/G/1 (cũng cókhi ký hiệu GI /GI /1, ở đây I thay cho independence nghĩa là độc lập). Ta sẽ đưa ra 3 phương pháp để phân tích các trường hợp đặc biệt đối với quá trình sắp hàng G/G/1. - Phương pháp thứ nhất được gọi là phương pháp phương trình tích phân. Phương pháp này đưa bài toán tìm các phân bố giới hạn thời gian đợi của khách hàng thứ n (khi n→∞) về bài toán giải phương trình tích phân dạng Wiener - Hopf. - Phương pháp thứ 2 khảo sát chuỗi Markov nhúng (Embedded Markov Chain). Nếu quá trình đến là Poisson thì chuỗi Markov nhúng được xét là độ dài của hàng tại những thờiđiểm khi có một khách hàng vừa được phục vụ xong. Nếu thời gian phục vụ có phân bố mũ và quá trình đến có phân bố tổng quát thì chuỗi Markov nhúng có được bằng cách kê khai kích thước của hàng tại mỗi thời điểm khi có một khách hàng mới đến. Khi đó quá trình trở thành một chuỗi Markov với cấu trúc đặc biệt. -Phương pháp thứ 3 nghiên cứu các tính chất của biến ngẫu nhiên W(t) là thời gian một khách hàng phải đợi nếu anh ta đến hệ thống tại thời điểm t. Đại lượng này được gọi là thời gian đợi thực sự của khách hàng với giả thiết khách hàng đến hệ thống tại thời điểm t. 2.3.1. Phương pháp phương trình tích phân Ký hiệu: - Wnlà thời gian đợi của khách hàng thứ n (không bao gồm thời gian phục vụ). - snlà thời gian phục vụ khách hàng thứ n . - tnlà thời gian đến trung gian của khách hàng thứ n và thứ n +1. tn = Tn+1-Tn - Tnlà thời điểm khách hàng thứ n đến hệ thống, với giả thiết W0 , s0 ,T0 đều bằng 0. Nghĩa là ta giả thiết rằng người thứ nhất đến tại thời điểm t = 0 và không có ai đứng chờ trước anh ta. Rõ ràng Wn+ snlà khoảng thời gian khách hàng thứ n ở trong hệ thống (thời gian chờ +thời gian phục vụ). Do đó, nếu tn>Wn+ sn thì khi khách hàng thứ n +1 đến sẽ không có ai trong hàng vì vậy thời gian đợi Wn+1= 0 . Trường hợp tn≤Wn+ sn thì thời gian đợi là Wn+ sn− tn. Tóm lại Wn+1= Wn+sn-tn nếu Wn+sn-tn≥0 0 nếu Wn+sn-tn<0 (2.8) Kí hiệu: Un = sn – tn và Z+ = max (Z,0) (2.9) Thì Wn+1 = (Wn+ sn- tn)+ = ( Wn + Un )+ (2.10) Un∞n=1là dãy các biến ngẫu nhiên độc lập, cùng phân bố với U. Giả sử Fn(x)là hàm phân bố của Wnvà g(x) là hàm mật độ phân bố của U. Vì Wn và Un là các biến ngẫu nhiên độc lập, do đó với mọi x ≥ 0: Fn+1x=PWn+1<x=Pmax⁡(Wn+ Un;0)<x=PWn+ Un<x =-∞∞PWn+Un<xUn=y g(y)dy =y≤x Fn(x-y)dy (2.11) Vì người thứ nhất đến hệ thống tại thời điểm t = 0 và không đợi nên F1(x) =1 nếu x≥ 00 nếu x<0 (2.12) Mặt khác: Fn(x) = 0 với mọi x <0, với mọi n = 0,1, 2,...Do đó F1(x) − F2 (x) ≥ 0, ∀x∈ R. Fn(x) - Fn+1(x) =y≤x Fn-1(x-y)- Fn(x-y)g( y)dy Bằng qui nạp ta chứng minh được, với mọi n Fn(x) - Fn+1(x) ≥ 0, ∀x∈R. (2.13) Dãy hàm Fn(x) n=1∞không tăng, không âm nên hội tụ về hàm F(x) ,∀x∈ R. Chuyển qua giới hạn của đẳng thức (2.11) ta được: F (x) =y≤x F(x-y)g(y) dy (2.14) Đặt z= x-y ta được: F (x) = -0∞F(z)G(x-y) dz = F(x)* g(x) (2.15) Định lý 2.1: (i) Với mọi x < 0, F(x) = 0 . (ii) Nếu E[U ] = -∞∞x gxdx ≥ 0, thì F(x) = 0, ∀x∈R< 0 (iii) Nếu E[U ] = -∞∞x g(x)dx<0 thì F(x) là hàm phân bố (là hàm không giảm, liên tục trái và thoả mãn: limx→-∞Fx=0 , limx→∞Fx=1 Định nghĩa 2.1: Thời gian từ lúc một khách hàng rời khỏi hệ thống và hệ thống trở thànhrỗng cho đến khi có một khách hàng tiếp theo đến hệ thống gọi là chu kỳ rỗi của hệ thống. Ký hiệu chu kỳ rỗi thứ n là in . Định lý 2.2: Nếu E[U]<∞ thì hệ thống đạt được trạng thái ổn định và thời gian đợi trung bình trong hàng Wq=E[ U2]-2E[U] - E[ i12]2E[i1] (2.16) trong đó i1 là chu kỳ rỗi đầu tiên. Nhận xét: Nếu ta tính được moment cấp1 và cấp 2 của thời gian rỗi i1 thì công thức (2.16) cho ta tính được thời gian đợi trung bình của hàng Wq. Dựa vào "kết quả nhỏ" (2.1) sẽ cho phép tính được các số đo hiệu năng còn lại L, Lq và W . 2.3.2. HàngM /G/1 Ta giả thiết quá trình đến Poisson tốc độ λ, nghĩa là quá trình đến trung gian tn có phân bố mũ tốc độ λ. Quá trình phục vụ sn được xét một cách tổng quát nhưng giả thiết thời gian phục vụ trong các chu kỳ là độc lập với nhau và có cùng luật phân bố. E [t1]= 1λ, E [t12 ] = 2λ Do đó cường độ lưu thông ρ = E[s1 ]E[t1]=λE [s1 ] ⇒Es1=ρλ, -E [U1 ] = E [t1 - s1 ] = 1λ-ρλ=1-ρλ>0 E[U21]= E[(s1-t1)2]= E[s12] - 2E[s1]1λ +2λ2 = E [s12] + 2(1-ρ)λ2 Mặt khác, vì quá trình đến là Poisson nên khoảng thời gian từ một thời điểm bất kỳ đến lúccó một khách hàng tiếp theo đến hệ thống luôn có phân bố mũ. Do đó thời gian từ lúc một khách hàng rời khỏi hệ thống và hệ thống trở thành rỗng cho đến khi có một khách hàng tiếp theo đến hệthống (chu kỳ rỗi của hệ thống) cũng có phân bố mũ tốc độ λ.Vậy E [i1 ] = 1λ; E [i12] = 2λ2 Thay vào công thức (2.16) của định lý 2.2 ta được công thức Pollaczek - Khinchin (P-K)cho hàng M /G/1. Wq = E s12+2(1-ρ)λ22(1-ρ)λ - 2λ22λ =λ E s122(1-ρ) (2.17) W = Wq + E [s1 ] (2.18) Từ "kết quả nhỏ" (2.1)-(2.2) suy ra các số đo hiệu năng còn lại. 2.3.3. Các trường hợp đặc biệt của hàng M /G/1: 1) Hàng M /M /1: Quá trình đến Poisson với tốc độ đến λ, thời gian phục vụ có phân bố mũ tốc độ μ. E [s1 ] = 2μ ; E s12= 2μ2 ; ρ = λμ (2.19) Wq = 2λμ22(1-λμ) =λμ(μ-λ) (2.20) W= Wq + 1μ = λμ(μ-λ) + 1μ = 1μ(μ-λ) (2.21) L = λW = λμ-λ; Lq= λWq=λ2μ(μ-λ) (2.22) 2) Hàng M / D/1: Quá trình đến Poisson với tốc độ đến λ, thời gian phục vụ không đổi tốc độ μ. E [s1 ]= 1μ ; var [s1 ]= E s12- E [s1 ]2=0 ⇒E s12=1μ2 ; ρ = λμ (2.23) Wq= λμ22(1-λμ)=λ2μ(μ-λ) (2.24) W= Wq + 1μ = λ2μ(μ-λ) + 1μ = 2μ-λ2μ(μ-λ) (2.25) L = λW =λ22μ(μ-λ) + λμ; Lq= λWq=λ22μ(μ-λ) (2.26) 3) Hàng M / Ek /1: Quá trình đến Poisson với tốc độ đến λ, thời gian phục vụ ngẫu nhiên độc lập có cùng phân bố Erlang- k với tốc độ μ. E [s1 ] = 1μ= kλ0 ; var [s1 ]= kλ02 = 1kμ2 ⇒E s12=1kμ2 + 1μ2;ρ = λμ (2.27) Wq= λ(k+1)kμ22(1-λμ)=(k+1)λ2kμ(μ-λ) (2.28) W= Wq + 1μ = (k+1)λ2kμ(μ-λ) + 1μ (2.29) L = λW =(k+1)λ22kμ(μ-λ) + λμ; Lq= λWq=(k+1)λ22kμ(μ-λ) (2.30) Trong công thức trên ta đã sử dụng (6.10) chương 6. Nhận xét: 1. Thời gian đợi trung bình mà một khách hàng phải mất ở hàng đợi là số đo trễ xẩy ra ở hệ thống sắp hàng. Ta có WqM/ D/1≤WqM/ Ek/1≤WqM/ E/1 (2.31) Khi k = 1 : WqM / Ek/1=WqM / M/1 Khi k →∞: limk→∞WqM / Ek/1=.WqM / D/1 2. Xét hệ toạ độ trực chuẩn Oxy. Trên trục hoành ta chọn các hoành độ nguyên k = 1, 2,..., trục tung chọn đơn vị là λμ(μ-λ) thì đồ thị của WqM / Ek/1 là hyperbol k+12k = 1 2 + 1 2k đạt cực đại bằng 1 khi k = 1 và tiệm cận đến 1 2 khi k →∞. 1 2 k λμ(μ-λ) 3. Hệ số λ2μ(μ-λ)lớn nếu λ gần bằng μ. Như vậy khi tốc độ đến gần với tốc độ phục vụthì hàng đợi tăng lên nhanh chóng tỉ lệ nghịch với hiệu số hai tốc độ. 12 2.3.4. Phương pháp chuỗi Markov nhúng áp dụng cho hàng G/M /1 Xét hệ thống sắp hàng có 1 server, các chu kỳ thời gian phục vụ sn độc lập cùng có phân bố mũ tốc độ μ. Quá trình đến là độc lập, tổng quát, có cùng phân bố và thời gian đến trung gian là biến ngẫu nhiên có hàm phân bố H(u). Ta xét chuỗi Markov nhúng là số khách hàng trong hàng tại những thời điểm khi có khách hàng mới đến hệ thống. Gọi q là trạng thái của hệ thống khi có 1 người mới đến và gọi q'là trạng thái sau khi có 1 người tiếp theo đến : q'= q +1−N (2.32) Trong đó N là số khách hàng được phục vụ trong chu kỳ giữa hai lần đến. Vì phân bố mũ có tính chất "không nhớ" nên số khách hàng N được phục vụ trong chu kỳ giữa 2 lần đến chỉ phụ thuộc vào độ dài của khoảng và q mà không phụ thuộc vào phạm vi phục vụ mà khách hiện tại đã được nhận phục vụ. Với các giả thiết này công thức (2.32) xác định chuỗi Markov có xác suất chuyển P= [ pij] thỏa mãn: pij=Pq'= j⎤ q=y=Wn+10 nếu j >i+1 PN=i+1-j nếu i+1≥j ≥1 (2.33) Đặt ak= P{N = k} thì pij=0 nếu j >i+1 ai+1-j nếu i+1≥j ≥1 (2.34) Áp dụng công thức xác suất đầy đủ và từ giả thiết thời gian phục vụ có phân bố mũ với tốc độ μ có thể chứng minh được: ak=0∞e-μuukμkk!dH(u) (2.35) trong đó H(u) là hàm phân bố của chu kỳ đến trung gian. Cuối cùng các xác suất chuyển pi0 ( j = 0 ) là xác suất mà tất cả i người trong hàng đã được phục vụ trước khi có người mới đến. pi0=1-j=1∞pij= 1- a0- a1 -…- ai (2.36) Vậy ma trận xác suất chuyển P=r0a0r1a100a000……0……r2a2r3a3a1a0a2a10….a0….…………… …… …… ….… .... (2.37) trong đó ri= 1−a0 – a1−…−ai. Cường độ lưu thông ρ =1/k=0∞kak Hệ thống đạt trạng thái ổn định khi ρ1 Phân bố dừng Π = [π0 ,π1,π2 ,...] có dạng π = (1−ξ0 )ξ0i ; i = 0,1,2,... (2.38) trong đó ξ0 là nghiệm duy nhất của phương trình f (ξ0 )= ξ0 (0<ξ0<1) với f(ξ)= k=0∞akξk (2.39) Thời gian đợi W Nếu ρ < 1thì hệ thống đạt trạng thái ổn định, khi đó hàm phân bố độ dài của hàng cũng đạt đến phân bố ổn định. Với điều kiện này ta xét thời gian đợi W . Xác suất không phải đợi là r0 = 1−ξ0 . Nếu khách hàng đến và đã có n ≥1 khách hàng ở trong hàng thì anh ta phải đợi với tổng số n lần phục vụ có phân bố độc lập và cùng phân bố mũ trước khi đến lượt anh ta. Ta biết rằng tổng của n phân bố mũ độc lập tham số μ là phân bố Erlang- n tham số μ . Do đó P W<t ⎤ có n người trong hàng=0tunτn-1(n-1)!eμτdτ, n≥1 (2.40) Mặt khác: Pcó n người trong hàng=π=1-ξ 0ξ0n,n≥ 1 (2.41) Áp dụng công thức xác suất đầy đủ ta được W(t) =PW<t =n=1∞PW<t ⎤ có n người trong hàngPcó n người trong hàng.+ π0 =(1-ξ0)0tunτn-1(n-1)!e-μτdτ+(1-ξ0). W(t)=(1-ξ0) + ξ0( 1- e-μt(1-ξ0) ) (2.42) 2.3.5. Các cận trên của thời gian đợi trung bình của hàng Để tính các số đo hiệu năng của hàng ta có công thức (2.16) và "kết quả nhỏ" (2.1)-(2.2). Tuy nhiên trong trường hợp tổng quát chưa có qui tắc tính E[i1] và E[i12] G/G/1 Thay cho công thức tính chính xác người ta tìm các cận trên và cận dưới của chúng. Ở đây người ta nêu một vài cận trên cho Wq Vì số hạng E[i12] E[i1]≥ 0 nên Wq≤ E[U.2] -2E[U] (2.43) Mặt khác ta còn có thể chứng minh được là: −2E[U]Wq ≤ var[U] và − 2E[U] > 0 do đó Wq≤ var[U] -2E[U] (2.44) 3. Khi cường độ lưu thông ρ→ 0 thì thời gian rỗi i1 tiến đến 0. Điều này làm cho E[i12] tiến đến 0 nhanh hơn E[i1]. Do đó [E[i12] E[i1] ] →0 vì vậy (2.45) III.ỨNG DỤNG CỦA LÝ THUYẾT XẾP HÀNG Như đã nói ở trên ứng dụng của lý thuyết sắp hàng còn có nhiều ứng dụng trong các lĩnh vực khác nhau như trong mạng máy tính, trong việc quản lý xí nghiệp, quản lý giao thông và trong các hệ phục vụ khác… Ngoài ra lý thuyết sắp hàng cũng còn là cơ sở toán học để nghiên cứu và ứng dụng trong nhiều bài toán kinh tế như đầu tư, kiểm kê, rủi ro của bảo hiểm, thị trường chứng khoán…. Có thể xem xét mạng viễn thông như một tập hợp các hàng đợi Cấu trúc dữ liệu theo kiểu FIFO Lý thuyết xếp hàng sẽ giúp tính toán các tham số như: Chiều dài trung bình Thời gian đợi trung bình Xác xuất một hàng đợi có chiều dài nào đó Xác suất mất gói Đặc trưng của hàng đợi: Hệ thống có bao nhiêu server? Tốc độ phục vụ của các server này ? Có bao nhiêu vị trí đợi trong hàng đợi? Có bất kỳ quy tắc nội bộ đặc biệt nào không (yêu cầu dịch vụ, mức độ ưu tiên, hệ thống còn rỗi không)? Miêu tả của tiến trình đến (phân bố khoảng thời gian đến) Miêu tả của tiến trình phục vụ (phân bố thời gian phục vụ) Quy tắc phục vụ (FIFO), LCFS, RANDOM) Thời gian rỗi (phân bố thời gian rỗi) Hàng đợi Sự kiện đến SERVER Sự kiện đi Mức độ ưu tiên Mô hình 1. Mô hình xếp hàng một kênh, lượng khách hàng đến tuân theo phân phối Poisson và thời gian phục vụ tuân theo hàm mũ Mô hình 2. Mô hình xếp hàng nhiều kênh, lượng khách hàng đến tuân theo phân phối Poisson và thời gian phục vụ tuân theo hàm mũ Mô hình 3. Mô hình một kênh phục vụ, thời gian phục vụ không đổi Mô hình 4. Mô hình một kênh phục vụ, số lượng khách đến hữu hạn. Ví dụ 1 :Một tổng đài quân sự có một trung kế gọi ra mạng dân sự. Ước tính có trung bình 15 cuộc gọi/giờ (cuộc gọi ra ngoài mạng QĐ). Thời gian trung bình mỗi cuộc gọi là 3 phút Xác định tải trọng của hệ thống Tính % thời gian chờ của hệ thống Tính số lượng cuộc gọi xếp hàng trong hệ thống Tính thời gian trung bình của cuộc gọi trong hệ thống Tính xác suất khi hệ thống phục vụ hết cuộc gọi (call=0) và khi (call=4) Ví dụ 2 : Một đại lý bưu điện có 7 buồng điện thoại. Người ta thống kê được cứ trung bình mỗi ngày có 6,6 khách (trừ T7 và CN). Thời gian phục vụ trung bình là 50min/per. Hãy xác định các chỉ số của hệ thống Bài giải: Ví dụ 3 : Tại cả hàng chăm sóc khách hàng của VinaPhone, người ta thống kê cứ 1 giờ một nhân viên nhận được 8 đơn của 8 người đến để làm dịch vụ viễn thông. Thời gian mỗi cuộc giao dịch là 5 phút. Giả sử giao dịch đến tuân theo phân bố Poisson. a. Tính số lượng giao dịch xếp hàng trung bình? b. Tính thời gian trung bình 1 giao dịch phải ở lại trong của hàng? Bài giải: Ví dụ 4: Áp dụng giải quyết bài toán Bán vé tàu a. Phát biểu bài toán Giả sử dòng khách hàng đến mua vé tại một ga tàu với M quầy phục vụ là dòng Poisson với tham số l = 6 khách hàng/1 phút (điều này cũng có nghĩa là khách hàng đến phòng bán vé với các thời điểm đến tuân theo luật phân phối mũ với tham số l = 6). Ngoài ra, còn biết nguyên tắc phục vụ là FCFS (First come first serve) và thời gian phục vụ tại mỗi quầy có luật phân phối mũ với kì vọng 1/3 (phút). Bài toán đặt ra là: Số quầy hàng tối thiểu là bao nhiêu để khách hàng chờ không trở nên dài vô hạn? Giả sử Nt là số khách hàng đang chờ hay đang được phục vụ tại thời điểm t. Chọn M = 4 và một khách hàng sẽ chờ để được phục vụ nếu Nt ≤ 4, chờ với xác suất 0,5 nếu Nt = 5 và sẽ bỏ đi nếu Nt = 6. Hãy xác định phân phối dừng của quá trình này? Bài toán này có thể áp dụng quá trình sinh tử trong hệ thống xếp hàng dạng M/M/s để giải quyết. b. Hệ thống xếp hàng M/M/s với quá trình sinh-tử - Có tiến trình đến là một tiến trình phân phối Poisson - Hệ thống phục vụ có thời gian dịch vụ là một biến ngẫu nhiên phân phối mũ. s là số trạm phục vụ (server) khách hàng. k, m và q được hiểu là định ngầm nên không cần thể hiện trong ký hiệu. Hệ thống này được xây dựng bằng cách cho tốc độ đến hoặc tốc độ dịch vụ phụ thuộc vào số các khách hàng trong hệ thống. Ta có sơ đồ biểu diễn hệ thống xếp hàng M/M/s như sau: Server Tiến trình Poisson Hàng chờ Server phân phối mũ Hình II.2.1. Sơ đồ biểu diễn hệ thống xếp hàng M/M/s Với mô hình của hệ thống trên ta có lược đồ chuyển trạng thái của mô hình này như sau: Hình II.2.2. Sơ đồ chuyển trạng thái trong quá trình sinh-tử Lược đồ chuyển trạng thái này mô tả quá trình sinh-tử (birth-death). Có nghĩa là nếu xem các trạng thái như là tổng số dân thì nó có thể tăng lên (sinh ra) 1 người hoặc giảm đi (mất đi) một người vào một thời điểm nào đó. Có một số mô hình khác mà có thể thay đổi một số thành viên tại cùng một thời điểm (gọi là các quá trình đến/rời theo lô). Trong bối cảnh của việc đánh giá hiệu năng của các hệ thống thông tin, trạng thái của các hệ thống có thể được xem như là số các gói tin trong một bộ vi xử lí truyền thông, số các cuộc gọi trong một mạng máy tính tổng đài điện thoại, hay là số các tác vụ lưu thông trong máy tính. Quá trình sinh-tử là trường hợp riêng của xích Markov thuần nhất thời gian liên tục, với không gian trạng thái S không quá đếm được S = {S0, S1, S2,..., Sn, …} và ma trận cường độ Q = [qij] có tính chất qij = 0 với |i-j| ³ 2. Điều này có nghĩa là việc chuyển trạng thái trong quá trình sinh-tử chỉ có thể tới “1 đơn vị lên hoặc xuống” (hình II.2.2). Từ trạng thái Sn tại thời điểm t hệ X(t) chỉ có thể chuyển tới một trong các trạng thái Sn+1, Sn hoặc Sn-1. Vì vậy chúng ta có các cường độ chuyển: m0 = l-1 = 0 = q00, qn,n+1 = ln, qn,n-1 = mn và qn,n = -(ln + mn) "n Trong trường hợp ln, mn > 0, "n > 0, theo định lí đã được chứng minh, phân phối giới hạn có thể tìm được bằng cách giải hệ: [p0 p1 p2 p3 …]Q = 0, với ma trận cường độ Q đã biết. Ma trận chuyển vị của Q có dạng: Ta có [p0 p1 p2 p3 …]Q = 0 Û QT[p0 p1 p2 p3 …]T = 0 Û Hay: Do tính chất đặc biệt, như đã phân tích ở trên, của ma trận cường độ Q của quá trình sinh-tử, hệ trên được viết một cách tường minh hơn như sau: Từ đây dễ dàng tìm được pn+1 = (ln/mn+1)pn, "n = 1, 2, 3, … để đi tới công thức tính pi, "i. Với điều kiện , cuối cùng ta có: p0 = 1/(1+. Đặc biệt khi mn = 0, "n, thì quá trình sinh-tử trở thành quá trình sinh thuần khiết (pure birth process). Quá trình sinh thuần khiết với ln = l là quá trình Poisson với tham số l. c. Giải quyết bài toán Trong bài toán đặt ra chúng ta thấy có một quá trình sinh-tử với không gian trạng thái S= {S0, S1, S2,..., Sn, …}, trong đó Sn là trạng thái phòng bán vé có n khách hàng. Các cường độ chuyển là lk = 6 với k = 0, 1, 2,… còn mk = 3k với k ≤ M và mk = 3M với k > M (điều này là do biến cực tiểu của các biến ngẫu nhiên với phân phối mũ độc lập cũng có phân phối mũ với tham số bằng tổng các tham số của phân phối mũ tương ứng). Do lk/mk+1 = 6/3M < 1 (khi k ³ M) nên với M ³ 3 thì: Bởi vậy hàng đợi sẽ không dài vô hạn (nếu trái lại, khi chuỗi phân kì, thì p0 = p1 = p2 = … = 0, nên số khách hàng trong hàng đợi sẽ dần tới một số hữu hạn khi t® ¥ với xác suất bằng 0). Tiếp theo, ta có l0 = l1 = l2 = l3 = l4 = 6, l5 = 3. Theo công thức tính p0 = 1/(1+ ta có ngay p0 = 12/89. Từ đó tính ra p1 = 24/89, p2 = 24/89, p3 = 16/89, p4 = 8/89, p5 = 4/89 và p6 = 1/89. KẾT LUẬN Chúng ta thấy khi cần tiến hành lựa chọn quyết định trong các điều kiện có dòng thông tin lớn đi qua một số hệ thống xử lý thì việc sử dụng lý thuyết hàng chờ tỏ ra có hiệu quả. Trong các điều kiện thực tế thì lý thuyết hàng chờ được áp dụng để giải quyết được rất nhiều bài toán cụ thể. Trong tiểu luận này tôi đã cố gắng áp dụng quá trình sinh-tử của lý thuyết hàng chờ để giải quyết một vấn đề nhỏ trong bài toán bán vé tàu. Tuy nhiên do năng lực còn hạn chế nên nội dung còn nhiều thiết sót. Hi vọng rằng đây sẽ là một lý thuyết có ích cho việc nghiên cứu giải quyết các bài toán trong đời sống. TÀI LIỆU THAM KHẢO 1] Toán chuyên ngành – Học Viện CNBCVT [2] Introduction to Queueing Theory – Robert B.Cooper [3] Queueing Theory - Ivo Adan and Jacques Resing Phần 2: Nghiên cứu quá trình POISSON 1. QUÁ TRÌNH ĐẾM. QUÁ TRÌNH POISSON 1.1. Quá trình đếm. Quá trình đếm rất thường gặp trong thực tế. Giả sử A là biến cố nào đó. Ký hiệu X (t) , t > 0 là số lần biến cố A xuất hiện trong khoảng thời gian từ 0 đến t . Khi đó {X (t), t > 0} được gọi là quá trình đếm. Chẳng hạn ta có những ví dụ sau về quá trình đếm: + A là biến cố khách vào điểm phục vụ nào đó. Khi ấy X (t) là số khách vào điểm phục vụ tính đến thời điểm t . + A là biến cố có cuộc gọi đến một tổng đài nào đó. Khi ấy X (t) là số cuộc gọi đến tổng đài tính đến thời điểm t. Quá trình đếm {X (t); t ≥ 0} có các tính chất đặc trưng sau: 1. X (0) = 0 ; (1.1) 2. X (t) chỉ nhận giá trị là các số tự nhiên; (1.2) 3. X (s) ≤ X (t), 0 ≤ s ≤ t . (1.3) 4. X (s,t] = X (t) − X (s) , 0 ≤ s < t , là số lần biến cố A xảy ra trong khoảng thời gian (s,t] . (1.4) Ta gọi {X (s,t], 0 ≤ s < t} là quá trình điểm ứng với quá trình đếm {X (t); t ≥ 0}. 1.2. Quá trình Poisson Định nghĩa 1.1: Ta nói rằng quá trình {X (t); t ≥ 0} là quá trình Poisson với cường độ λ (hoặc tham số λ) nếu: i) X (0) = 0 ; ii) X (t) chỉ nhận giá trị là các số tự nhiên; iii) {X (t); t ≥ 0} là quá trình có gia số độc lập, tức là, với bất kỳ các gia số là các biến ngẫu nhiên độc lập. iv) Mỗi gia số X (s + t) − X (s) có phân bố Poisson với tham số λt với mọi s ≥ 0, t > 0 . Định lý 1.1: Nếu quá trình đếm {X (t); t ≥ 0} thỏa mãn các điều kiện sau: 1. Có gia số độc lập, tức là ∀m = 2,3,... và với mọi thì các gia số là các biến ngẫu nhiên độc lập, 2. Có gia số dừng, tức là với mọi s > 0. ∀ thì các gia số , có cùng phân bố xác suất. Như vậy luật phân bố chỉ phụ thuộc vào khoảng thời gian và không phụ thuộc thời điểm. 3. Xác suất xuất hiện biến cố A gần đều; tức là tồn tại λ > 0 (tốc độ xuất hiện biến cố A ) sao cho với h > 0 khá bé thì P{X (h) =1} =λh + o(h) . (1.5) Trong đó o(h) là vô cùng bé bậc cao được tính theo công thức: 4. Với h > 0 khá bé thì P{X (h) ≥ 2} = o(h) , (1.6) thì {X (t); t ≥ 0} là quá trình Poisson tham số λ. Ngược lại, quá trình Poisson là quá trình đếm thỏa mãn 4 điều kiện trên. 1.3. Các phân bố liên quan đến quá trình Poisson. Định nghĩa 1.2: Giả sử {X (t); t ≥ 0} là quá trình Poisson đếm số lần xuất hiện biến cố A . 1) Ta ký hiệu W(n) là thời điểm đến (arrival time) (hay thời gian chờ, waiting time) thứ n, đó là thời điểm mà biến cố A xuất hiện lần thứ n Quy ước W0=0 2) Ký hiệu Snlà khoảng thời gian giữa 2 lần đến liên tiếp thứ n đó là khoảng thời gian tính từ thời điểm biến cố A xảy ra lần thứ n-1 đến thời điểm xảy ra biến cố A t lần thứ n. Vậy Sn= Wn- Wn-1 Định lý 1.2: Các thời gian đến trung gian S(1) S(2) ,...S(n) , là các biến ngẫu nhiên độc lập có cùngphân bố mũ tham số λ với hàm mật độ f (1.7) W(n) có phân bố Erlang tham số n,λ với hàm mật độ f (1.8) Đặc biệt W(1) có phân bố mũ. Với mọi 0 < s < t và 0 ≤ k ≤ n (1.9) Chú ý rằng nếu X1, X2,..., Xn là các biến ngẫu nhiên độc lập có cùng phân bố mũ tham số λ thì X = X1 + X2 +….+ Xn có phân bố Erlang tham số n,λ . Do đó có kỳ vọng và phương sai: (1.10) 2. QUÁ TRÌNH POISSON CÓ PHÂN LOẠI Xét quá trình Poisson {X (t);t ≥ 0 với cường độ λ (tương ứng với quá trình đếm số lần xảy ra biến cố A ). Giả sử mỗi khi biến cố A xảy ra thì nó được phân thành hai loại: loại I với xác suất p và loại II với xác suất q = 1− p . Hơn nữa, giả sử sự phân loại biến cố này là độc lập với sự phân loại biến cố kia. Chẳng hạn, khách đến cửa hàng theo quá trình Poisson {X (t);t ≥ 0 } với cường độ λ ,khách được phân làm hai loại: nam với xác suất 1/2 và nữ với xác suất 1/2. Ta ký hiệu X1(t) và X2(t) là quá trình đếm tương ứng với biến cố loại I và biến cố loại II. Rõ ràng là X (t) = X1(t) + X2 (t). Định lý 2.3: Với các điều kiện trên ta có X1(t) và X2 (t) là hai quá trình Poisson với cường độ tương ứng λp và λq. Hơn nữa, hai quá trình này là độc lập. PHÂN BỐ ĐỀU. Giả sử ta có một đoạn thẳng chiều dài bằng t và có n hạt cho trước. Ta rải các hạt lên đoạn thẳng này sao cho vị trí của các hạt trên đoạn này lập thành n biến ngẫu nhiên độc lập có phân bố đều ( mỗi hạt đồng khả năng rơi vào từng điểm). Ta ký hiệu Uk là vị trí của hạt thứ k; k = 1,2,..,n. Theo cách rải của ta thì U1,…,Un là các biến ngẫu nhiên độc lập có cùng phân bố đều với hàm mật độ nếu 0 nếu ngược lại Bây giờ ta sắp xếp lại dãy các vị trí theo thứ tự từ bé đến lớn. Bằng cách ấy ta được dãy , trong đó là bé nhất trong số U1,…Un; tương tự là bé thứ 2 trong số U1,…Un . Ta gọi W1, W2,…,Wn là thống kê thứ tự của phân bố đều trên đoạn (0;t]. Định lý 3.4: Hàm phân bố đồng thời của W1, W2,…,Wn có mật độ là với Định lý 3.5: Giả sử là quá trình Poisson với tham số và W1, W2,…,Wn là các thời gian đến trong quá trình Poisson này. Khi đó, với điều kiện X(t) = n, phân bố đồng thời của W1, W2,…,Wn có mật độ với Ý nghĩa của định lý 3.5 là: Với điều kiện có đúng n biến cố xảy ra trong khoảng thời gian (0;t] thì các thời gian đến là thống kê của phân bố đều trên đoạn (0;t]. 4. QÚA TRÌNH POISSON PHỨC HỢP Định nghĩa 4.3: Giả sử là quá trình Poisson với cường độ >0. Y1,…,Yn dãy các biến ngẫu nhiên độc lập, cùng phân bố và dãy này độc lập với . Khi đó ta gọi là quá trình Poisson phức hợp. Ví dụ: - Các cuộc gọi đến tổng đài là quá trình Poisson và thời gian gọi của mỗi cuộc là dãy các biến ngẫu nhiên độc lập, cùng phân bố và dãy này độc lập với các cuộc gọi đến. Khi đó tổng thời gian của tất cả các cuộc gọi cho đến thời điểm t là một quá trình Poisson phức hợp. Định lý 4.6: Kỳ vọng và phương sai của quá trình Poisson phức hợp: Hàm phân bố trong đó F1(z) là hàm phân bố của Y1 +…+ Yn. Đặc biệt nếu Y1 +…+ Yn có phân bố mũ tham số thì Fn (z) là hàm phân bố Erlang tham số n, µ 5. ỨNG DỤNG CỦA QUÁ TRÌNH POISSON. Quá trình Poisson được áp dụng cho nhiều hiện tượng (có tính rời rạc) (nghĩa là số lần xuất hiện trong một khoảng (thời gian, không gian) cho trước phải là số nguyên 0, 1, 2, 3, ... ) với xác suất để sự kiện (hiện tượng) đó xảy ra là không đổi trong suốt khoảng (thời gian, không gian) Trong lĩnh vực viễn thông, quá trình Poisson được ứng dụng nhiều với mục đích để tính lưu lượng của các dịch vụ mà tổng đài hay các thiết bị viễn thông khác có thể đáp ứng trong 1 khoảng thời gian cụ thể. Từ đó có công tác qui hoạch, chiến lược phát triển mạng. Ví dụ 1: Số xe qua trạm thu phí là quá trình poison với lưu lượng trung bình 200 xe trong 1 giờ. a) Tính xác suất để từ 7h00 đến 8h00 không có bức điện nào. b) Tính phân bố của thời điểm tại đó xe qua trạm đầu tiên sau 8h00. Lời giải: Gọi X(t) là số xe tới trạm trong khoảng thời gian t, theo giả thuyết X(t) là quá trình Poisson với tham số λ= 3. a/ Xác suất để từ 7 giờ đến 8 giờ không có xe nào b/ Phân bố của thời điểm tại đó xe qua trạm đầu tiên sau 8h. . Ví dụ 2: Một trạm điện thoại tự động nhận được trung bình 300 lần gọi trong 1 giờ. a/ Tìm xác suất để trạm đó nhận được đúng 2 lần gọi trong 1 phút cho trước. b/ Tìm xác suất để trạm đó nhận được đúng 5 lần gọi trong 3 phút. c/ Tìm xác suất để trong 3 phút liên tiếp, mỗi phút trạm nhận được nhiều nhất 1 lần gọi. Lời giải: Gọi X là bnn chỉ số lần gọi đến trạm trong khoảng thời gian là 1 phút. Do đó X Poisson với λ = 300/60= 5 a/ P(X=2) = e-552/2!0,09 b/ Gọi Y là số lần gọi trong 3 phút. Y Poisson với λ = 5.3=15 Vậy P(Y=5) = e-15155/5!0,003 c/ P(X1)= 1- P(X=0)= 1- e-5 =1- 0,00674 = 0,99326 P(Trong 3 phút liên tiếp, mỗi phút có ít nhất 1 lần gọi) = P(Phút thứ 1 có1 lần gọi, Phút thứ 2 có1 lần gọi, Phút thứ 3 có1 lần gọi) = (Do tính độc lập và có cùng phân bố Poisson với λ= 5, nên) = P(X1) P(X1) P(X1) = 0,993263 = 0,9799.