Mô hình phục vụ đám đông

Chia sẻ: Lê Viết Sơn | Ngày: | Loại File: DOCX | Số trang:10

Thêm vào BST

Báo xấu

108
lượt xem 12
download

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

Mô tả hệ thống phục vụ.Chúng ta có thể mô tả hệ thống phục vụ đám đông bằng phương pháp hộp đen hoặc phương pháp hộp trắng

Chủ đề:

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

Lưu

Nội dung Text: Mô hình phục vụ đám đông

Chương VI: MÔ HÌNH PHỤC VỤ ĐÁM ĐÔNG I.Các đặc trưng cơ bản của hệ thống phục vụ đám đông 1 .Sơ đồ chung của hệ thống phục vụ đám đông Trong nhiều trường hợp bài toán ứng dụng sơ đồ có dạng sau: Có một dòng yêu cầu các hệ thống xếp thành hàng , các thiết bị của hệ thống phục vụ các yêu cầu,các yêu cầu đi ra khỏi hệ thống trong dạng như dòng vào. Công việc của hệ thống đó là hoàn thành các yêu cầu đi tới vào những thời điểm nói chung là ngẫu nhiên, tạo nên dòng vào của hệ thống. Mỗi yêu cầu sẽ được bắt đầu phục vụ ngay bởi một trong các thiết bị rỗi.Nếu tất cả các thiết bị đều đang bận phục vụ thì yêu cầu hoặc bị bãi bỏ hoặc phải xếp hàng. Các yêu cầu đã qua đã qua phục vụ tạo thành dòng ra thường được gọi là yêu cầu rời khỏi hệ thống, không phụ thuộc vào chúng đã được phục vụ hay không. Sở dĩ có những yêu cầu không được phục vụ vì có những khách hàng sốt ruột không muốn hàng. Yêu cầu Hàng chờ Dòng được phục vụ ***** [*****] *****  Yêu cầu không thỏa mãn 2.Phân loại các dòng vào: Để tang tính hiệu quả, người ta thường giới hạn việc nghiên cứu bằng việc xét các dòng vào sau đây: Dòng vào là dòng các yêu cầu đến hệ thống phục vụ, đòi hỏi được thoả mãn một yêu cầu nào đó: Ví dụ: Khách hàng đến một cửa hàng siêu thị để mua hàng, các đơn vị quân đội chờ qua phà để vượt sông, các khí tài chờ để được sửa chữa, bảo dưỡng v.v. - Tại các thời điểm khác nhau, các yêu cầu đến hệ thống phục vụ là 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 luật phân bố xác suất nào đó, do vậy nó có nhiều loại dòng vào. ở giáo trình này chúng ta chỉ xét 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 Poát xông. 1. Dòng vào tiền định: Các yêu càu đi đến hệ thống tại các thời điểm cách đều nhau một khoảng bằng a. Rõ ràng là hàm phân bố sự kéo dài của các khoảng thời gian giữa các thời điểm liên tiếp của việc đi tới các yêu cầu có dạng F (x) = ; 0
hợp việc áp dụng nó sẽ cho kết quả một cách nhanh chóng và hiệu quả. Nhưng thường trong việc giải các bài toán của lý thuyết phục vụ đám đông các yêu cầu đã kể ra không được thực hiện. Chẳng hạn dòng các hành khách đi vào hệ thống tàu điện ngằm phụ thuộc vào thời gian của một ngày đêm.Dòng các yêu cầu về xem văn nghệ nói chung không phải là mức bình thường theo qui luật (có thể cùng một lúc xuất hiện ở cửa bán vé 2 hoặc 3 yêu cầu). Vì vậy dòng vào có khi được cho bởi một đặc trưng tổng quát hơn quá trình Poisson. 1.3 Kênh phục vụ: Tập hợp một số điều kiện vật chất(thiết bị, thông tin) có chức năng thỏa mãn một loại yêu cầu nào đó gọi là kênh phục vụ. Các thiết bị phục vụ(các kênh) của hệ thống được chia ra thành các hệ một kênh và nhiều kênh.Ta giả thiết rằng tất cả các thiết bị của nhiều kênh hoàn hoàn toàn đồng nhất và làm việc không phụ thuộc nhau giữ vẫn nhịp độ phục vụ và việc kéo dài xếp hàng của đám đông không làm ảnh hưởng đến chúng. Ta xét phân bố lũy thừa(mũ) của thời gian phục vụ ℥ bởi thiết bị F(t)=P= 1- (1.3) Trong đó: v là đại lượng hằng số, tỷ lệ nghịch với thời gian trung bình phục vụ ( t= ), hoặc v bằng trung bình số các yêu cầu được thiết bị phục vụ trong 1 đơn vị thời gian. Chú ý: công thức 1.3 không phụ thuộc vào việc nó đã kéo dài trong bao lâu Phân loại các hệ thống phục vụ Trong các bài toán phục vụ đám đông xuất hiện cả vấn đề kỷ luật xếp hàng. Nếu trong hệ thống không có xếp hàng thì yêu cầu đến được phục vụ ngay bởi bất cứ thiết bị nào. Khi có xếp hàng thì có các dạng khác nhau của ky luật xếp hàng. Đơn giản và tự nhiên nhất phục vụ theo thứ tự xếp hàng là “ai đến trước thì được phục vụ trước” nhưng có thể xảy ra trường hợp có sự ưu tiên của một vài yêu cầu so với các yêu cầu khác, nghĩa là chúng được phục vụ không theo xếp hàng,chẳng hạn điện thoại giữa các thành phố được ưu tiên hơn điện thoại trong thành phố. Vì dòng vào các yêu cầu và thời gian phục vụ chúng là ngẫu nhiên nên có thể xảy ra tình huống là tất cả các thiết bị trong hệ thống đều bận.Trong trường hợp này yêu cầu hoặc bị xóa bỏ( rời khỏi hệ thống) hoặc xếp vào hàng. Các hệ thống loại thứ nhất gọi là hệ thống với các từ chối, các hệ thống loại thứ hai gọi là hệ thống chờ đợi. Ví dụ: hệ thống có chờ đợi là các đơn vị phục vụ sinh hoạt. Các hệ thống có chờ đợi được phân chia theo cách tổ chưc xếp hàng: Các hệ thống với thời gian chờ đợi không hạn chếcuar các yêu cầu Các hệ thống mà đối với chúng sự xếp hàng bị giới hạn bởi chỗ xếp hàng. Các hệ thống với thời gian chờ đợi hữu hạn, hoặc ngẫu nhiên 5, Trạng thái của hệ thống 1. Trạng thái hệ thống và quá trình chuyển trạng thái Trạng thái của hệ thống phục vụ, ký hiệu là (t), là khả năng kết hợp dòng vào và dòng Ta gọi tập hợp hay một số đặc trưng mà trên cơ sở đó có thể phân biệt sự tồn tại của hệ thống trong những tình trạng khác nhau tại một thời điểm là trạng thái của hệ thống , kí hiệu là (t) Việc hệ thống tồn tại ở một trạng thái cụ thể là một biến cố ngẫu nhiên nên tương ứng với mỗi trạng thái có một giá trị xác xuất gọi là xác suất trạng thái của hệ thống, kí hiệu là (t) Sau một thời gian hệ thống có thể chuyển từ trạng thái (t) đến trạng thái (t + ) nhờ sự tác động của các yếu tố ngẫu nhiên nào đó. Ta gọi xác suất
của sự kiện đó là xác suất chuyển trạng thái. Ta kí hiệu cường độ của dòng biến cố làm cho hệ thống chuyển từ (t) đến (t + ) là (t). 2. Sơ đồ trạng thái và hệ phương trình trạng thái Người ta dung một sơ đồ mô tả toàn bộ các trạng thái và quá trình chuyển trạng thái của hệ thống: Nhờ sơ đồ chuyển đổi đổi trạng thái có thể thiết lập hệ phương trình trạng thái cho phép xác định các xác suất trạng thái. Đạo hàm bậc nhât theo thời gian của xác xuất trạng thái (t) bằng tổng của một số số hạng;Mỗi số hạng là tích của cường độ dòng biến cố với xác suất trạng thái (dấu + nếu mũi tên đi tới, dấu – ngược lại) =(t) - (t) Với điều kiện chuẩn là =1 Điều kiện chuẩn thể hiện tập hợp (t) là một nhóm đầy đủ các biến cố, tức là tại một thời điểm hệ thống phải tồn tại ở một và chỉ một trạng thái nói trên. 3. Quá trình hủy và sinh – lời giải của hệ phương trình trạng thái a – Sơ đồ trạng thái của quá trình hủy sinh Trong hệ thống phục vụ đám đông sẽ xét sau đây ta gặp các sơ đồ chuyển trạng thái mà trong đó mỗi trạng thái chỉ có thể chuyển qua lại với các trạng thái kế nó ( trừ trạng thái đầu tiên và kế nó ). Sơ đồ có dạng sau: (t) (t) (t) (t) (t) (t) (t) (t) Ta gọi quá trình như vậy là quá trình hủy và sinh. b.Hệ phương trình trạng thái: Với sơ đồ trạng thái trên, nên ta có hệ phương trình trạng thái: =+ =- + + ………………………………………………………………………………………………… ……………………….. =- ++ Với điều kiện chuẩn là : Trong trường hợp hệ dừng ta có hệ phương trình sau: 0= +
0= - + + ………………………………………………………………………………………………… …………………………………..(1.1) 0= - + + ………………………………………………………………………………………………… ……………………………………………….. Với điều kiện chuẩn là: c.Lời giải của hệ (1.1) Nếu đặt = + Thì hệ (1.1) trở thành: Nghiệm cảu hệ là Từ đó â có thể đưa ra công thức tính các xác suất như sau: Công thức này sẽ được sử dụng làm giảm nhẹ việc giải hệ phượng trình trạng thái các hệ thống phục vụ công cộng trình bày trong chương này. Trong đó và , (v là con số trung bình các yêu cầu được một thiết bị hay kênh phục v). Nếu đặt là số thiết bị cần thiết để phục vụ thì (1.2) 1.6. Các tiêu chuẩn chất lượng của hệ thống phục vụ đám đông: Bài toán cơ bản của lý thuyết phục vụ đám đông là xác định tính hiệu quả của hệ thống phục vụ. Hiệu quả hoạt động của hệ thống phục vụ được đặc trưng bởi một số lớn các tiêu chuẩn chất lượng khác nhau: -Xác suất phải loại yêu cầu trong hệ thống phục vụ (xác suất từ chối) ký hiệu là : = (1.3) -Xác suất của sự kiện là việc phục vụ các yêu cầu trong hệ thống bị bận k thiết bị. -Con số trung bình các thiết bị bận (1.4) -Con số trung bình các thiết bị rỗi (1.5) -Hệ thống rỗi (bỏ trống) của các thiết bị (1.6) -Hệ số bận của các thiết bị (1.7) -Luật phân bố thời gian chờ đợi (cho các hệ thồng với xếp hàng không giới hạn). - Thời gian chờ đợi trung bình của các yêu cầu trong hàng cho đến lúc bắt đầu được phục vụ. -Xác suất của sự kiện mà thời gian lưu lại của yêu cầu trong hàng không kéo dài quá một đại lượng xác định. - Luật phân bố chiều dài của hàng - Độ dài trung bình của hàng M - Xác suất của sự kiện số yêu cầu trong hàng lớn hơn một số nào đó.
- Toàn bộ giá chờ đợi (bỏ trống) của các yêu cầu và các máy rỗi trong một đơn vị thời gian: . Trong đó: : giá chờ đợi cảu một yêu cầu trong một đơn vị thời gian; :giá trị một máy rỗi trong một đơn vị thời gian 2.Hệ thống phục vụ đám đông có từ chối cổ điển (Hệ thống ERLANGO) 1. Mô tả hệ thống Hệ thống phục vụ đám đông có n kênh phục vụ, năng suất các kênh bằng nhau và bằng v, dòng yêu cầu đến hệ thống là dòng Poisson dừng mật độ Thời gian phục vụ 1 yêu ʎ . cầu của kênh tuân theo quy luật số mũ. Nguyên tắc phục vụ của hệ thống như sau: mỗi yêu cầu đến hệ thống gặp lúc có ít nhất một kênh rỗi thì được nhận vào phục vụ tại một kênh rỗi bất kỳ, ngược lại thì bị từ chối và phải đi ra khỏi hệ thống. 2.Quá trình thay đổi trạng thái và sơ đồ trạng thái của hệ thống a.Trạng thái: Gọi là trạng thái hệ thống có k kênh bận tại thời điểm t(k=1,2,….,n) Chú ý: Chế độ phục vụ của hệ thống Erlango số kênh bận cũng chính là số yêu cầu đang được phục vụ tại t. b.Sơ đồ chuyển trạng thái: ʎ ʎ ʎ ʎ v 2v (k-1)v kv ʎ ʎ ʎ ʎ (k+1)v (k+2)v (n-1)v nv Sơ đồ thiết lập trên cơ sở phân tích tính chất của các dòng Poisson dừng như sau: -Nhờ tính đơn nhất của dòng yêu cầu mà khi hệ thống ở trạng thái nó chỉ có thể chuyển đến trạng thái , không thể chuyển thẳng đến trạng thái . - Nhờ tính không hậu quả của các dòng biến cố nêu trên mà cường độ của các dòng biến cố không phụ thuộc vào trạng thái của hệ thống khi nó tác động đến. - Với tính chất dừng ta có mật độ dòng yêu cầu không đổi, cũng như vậy mật độ dòng phục vụ chỉ phụ thuộc vào số kênh đang phục vụ. - Những phân tích trên cũng ứng dụng cho việc lập sơ đồ chuyển trạng thái của các hệ thống thống tương tự, vì vậy với các hệ thống sau ta sẽ không ngắc lại. 3 Hệ phương trình trạng thái và các xác suất trạng thái 0=+ 0= …………………………………………………………… (2.1) 0= 0= Với điều chỉnh chuẩn là: Đặt từ (1.2)ta có: (2.2)
Thay vào điều kiện chuẩn ta có: (2.3) Ký hiệu P( là xác suất đại lượng ngẫu nhiên phân phối Poisson nhận giá trị k và R( là xác suất tích lũy tương ứng ta có: Từ đó : = (2.4) Các giá trị P( và R( được tính trong bảng giá trị phân phối Poisson(Xem bảng 1) 4.Các chỉ tiêu đánh giá hoạt động của hệ thống Đới với hệ thống này các chỉ tiêu cơ bản đánh giá hệ thống là: *Xác suất hệ thống có n kênh rỗi (nghĩa là số kênh phục vụ = 0): *Xác suất hệ thống có n kênh bận (hay xác suất một yêu cầu đến hệ thống bị từ chối ): Đây cũng là hiệu suất lý thuyết tối đa của hệ thống *Xác suất phục vụ(xác suất 1 yêu cầu đến hệ thống được nhận phục vụ) là , đó là tỷ lệ các đối tượng được hệ thống tiếp nhân và phục vụ. *Số kênh bận trung bình(hay số yêu cầu trung bình có trong hệ thống): = == = *Số kênh rỗi trung bình: *Hệ số bận(rỗi): III.Hệ thống chờ với độ dài hàng chờ và thời gian hạn chế 1. Mô tả hệ thống Hệ thống phục vụ có n kênh phục vụ, năng suất các kênh bằng nhau và bằng v, dòng yêu cầu đến hệ thống là dòng Poisson dừng mật độ ʎ .Thời gian phục vụ 1 yêu cầu của kênh tuân theo qui luật số mũ. Nguyên tắc phục vụ: Một yêu cầu đến hệ thống gặp lúc ít nhất có 1 kênh rỗi thì được nhận phục vụ cho đến thỏa mãn tại 1 trong các kênh rỗi đó. Ngược lại nếu tất cả các kênh đều bận thì xếp hàng chờ bé hơn m. Cần xác định các chỉ tiêu phân tích hệ thống. 2 Quá trình thay đổi trạng thái và sơ đồ trạng thái của hệ thống a.Trạng thái: Ta quan tâm đến hiệu quả phục vụ của hệ thống vì vậy đặc trưng được chọn để xác định trạng thái là số kênh bận tại mỗi thời điểm. Gọi là trạng thái hệ thống có k kênh bậntại thời điểm t (k=1,2,….,n) là trạng thái hệ thống có n kênh bận và s yêu cầu chờ tại thời điểm t (s=1,2,….,m). b.Sơ đồ chuyển trạng thái Sơ đồ được thiết lập trên cơ sở phân tích tính chất của các dòng Poisson như đã nói ở hệ thống Erlango. c.Hệ phương trình trạng thái và các xác suất trạng thái 0=+ 0=
……………………………………………………………………………….. 0= ………………………………………………………………………………… (3.1) 0= …………………………………………………………………………………… 0= …………………………………………………………………………………… 0= Với điều kiện chuẩn là: . Đặt . Từ (3.1) ta có với k < n (3.2) Từ điều kiện chuẩn ta tính được: (3.3) với k (3.4) Nếu thì bằng yêu cầu phục vụ tang không hạn chế theo thời gian. Sau đây ta sẽ giả sử . Ta dẫn ra 1 vài đặc trưng của hệ thống với sự chờ đang xét với điều kiện chế độ làm việc được thiết lập. Xác suất để mọi thiết bị đều bận phục vụ và có s yêu cầu trong hàng được tính như sau: khi s > 0 (3.5) q === (3.6) Công thức (3.6) nhận một dạng đặc biệt đơn giản cho hệ thong phục vụ đám dông mọt thiết bị: q= . Độ dài trung bình của hàng M= (3.7) Con số trung bình k các yêu cầu có mặt trong hệ thống (hoặc đang được phục vụ, hoặc ở trong hàng bằng: K= (3.8) Con số trung bình các thiết bị rỗi: (3.9) Luật phân bố độ dài chờ đợi của yêu cầu cho tới khi được phục vụ cho bởi công thức: P (3.10) Độ dài trung bình cuả thời gian chờ đợi: (3.11) Thời giant rung bình toàn bộ của sự có mặt trong hệ thống rõ rang là tổng của các thời gian trung bình chờ đợi được phục vụ và thời gian phục vụ: (3.12) Phương sai của đại lượng ngẫu nhiên được tính theo công thức: D (3.13) Thời giant rung bình bị mất (xóa) trên sự chờ đợi bởi các yếu tố đi đến hệ thống trong khoảng thời gian T bằng: = (3.14)
IV.Các bài toán phục vụ trong các hệ thống hỗn hợp 1 .Các hệ thống với thời gian chờ đợi trung bình hạn chế trong hàng *Điều kiện: -Có dòng vào các yêu cầu với mật độ ʎ đi tới hệ thống gồm n thiết bị có năng suất như nhau. -Thời gian phục vụ của thiết bị cho mỗi yêu cầu là một đại lượng ngẫu nhiên tuân theo luật phân bố lũy thừa với tham số v= Trong đó: là thời gian trung bình cần thiết để phục vụ yêu cầu. -Nếu lại có một yêu cầu mới đến mà các thiết bị đều bận thì nó tự xếp vào hàng và chờ phục vụ. Thời gian lưu lại hàng là ngẫu nhiên và tuân theo luật phân bố lũy thừa mũ với tham số Trong đó: :thời gian chờ đợi trung bình. Nếu yêu cầu có trong hệ thống một thời gian : mà không nhận được phục vụ thì nó rời khỏi hệ thống. Vì vậy tham số có thể coi là mật độ trung bình của các rời khỏi hệ thống. Các sự phụ thuộc đối với hệ thống n thiết bị(kênh phục vụ) trong việc xác định các đại lượng đặc trưng cơ bản của hệ thống dẫn ra dưới đây: 1.Xác suất để mọi thiết bị tự do (rỗi )khỏi sự phục vụ: (4.1) Trong đó: 2.Xác suất để k thiết bị của hệ thống bị bận: 0 (4.2) 3.Xác suất để cả n thiết bị của hệ thống đều bận và s yêu cầu chờ phục vụ: S (4.3) 4.Xác suất của sự từ chối yêu cầu: (4.4) 5.Con số trung bình các yêu cầu chờ phục vụ: (4.5) 6.Con số trung bình các thiết bị bận phục vụ: (4.6) 7.Hệ số bận của các thiết bị: (4.7) 8.Con số trung bình của các thiết bị tự do (rỗi): (4.8) 9.Hệ số của sự rỗi (bỏ trống) các thiết bị: (4.9) 10.Xác suất để một yêu cầu bất kỳ đến hệ thống là được phục vụ: (4.10) Chú ý:Việc tiến hành tính toán theo các công thức này tỏ ra cồng kềnh vì vậy đẻ đơn giản cho việc tính toán ở cuối cuốn sách có nêu ra bảng để tính và khi với 3 cái vào . Ngoài ra đẻ tính công thức gần đúng ta có thể thay các tổng vô hạn bởi:
(4.11) (4.12) Các cái vào thường xét trong các khoảng sau: 1.1 1.1 2 Hệ thống với hạn chế thời gian có mặt của yêu cầu trong hệ thống Hệ thống này có đặc trưng là không phụ thuộc vào việc yêu cầu được phục vụ hay phải xếp hàng, nó sẽ rời khỏi hệ thống nếu thời gian ó mặt của yêu cầu trong hệ thống là ngẫu nhiên tuân theo luật phân bố lũy thừa với tham số V= Trong đó: thời gian trung bình có mặt của yêu cầu trong hệ thống. Các xác suất các trạng thái của hệ thong tin được diễn tả bởi hệ các phương phương trình vi phân sau: …………………………………………………………………………………………………… ………………… 1 …………………………………………………………………………………………………… ………………… ; (4.13) Đối với trường hợp dừng nghĩa là khi t thì hệ phương trình vi phân (4.13)trở thành hệ các phương trình đại số ta có: -+( =0 1 =0 (4.14) …………………………………………………………………………………………………… ………………… =0 Khi giải các phương trình (4.14) ta sẽ nhận được các công thức đẻ các định các xác suất c ủa trạng thái hệ thống phục vụ đám đông: k; (4.15) s (4.16) Trong đó . Xác suất được xác định theo điều kiện chuẩn hóa: Và bằng:
(4.17) Xác suất phục vụ một yêu cầu bất kì có thể được xác định như là tích kỳ vọng toán học của con số các yêu cầu tới tỷ số các mật độ phục vụ trên các yêu cầu đến hệ thống: (4.18) Từ đó tính được xác suất từ chối phục vụ theo công thức: = 1- (4.19) Sau một loạt các biến đổi công thức (4.19) có thể viết dưới dạng: (4.20)