judas_iskariot
New Member
Tải Lý thuyết xếp hàng và ứng dụng trong viễn thông
Lý thuyết xếp hàng đã được nghiên cứu và ứng dụng rộng rãi trên thế giới trong nhiều lĩnh vực nghành nghề khác nhau như bưu chính viễn thông, hàng không, đường sắt, kiểm soát lưu lượng giao thông, đánh giá hiệu năng hệ thống máy tính, y tế và chăm sóc sức khỏe, không lưu, bán vé
Trong nhiều hệ thống phục vụ, các khách hàng (costumer) phải dùng chung tài nguyên, phải chờ để được phục vụ và đôi khi bị 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 hay 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 hay 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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
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 hay 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/E k/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 hay 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 hay vô hạn
- Quy tắc phục vụ:
FIFO hay 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 hay lần lượt hay 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 hay con người hay 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 hay 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
Download miễn phí Lý thuyết xếp hàng và ứng dụng trong viễn thông
Lý thuyết xếp hàng đã được nghiên cứu và ứng dụng rộng rãi trên thế giới trong nhiều lĩnh vực nghành nghề khác nhau như bưu chính viễn thông, hàng không, đường sắt, kiểm soát lưu lượng giao thông, đánh giá hiệu năng hệ thống máy tính, y tế và chăm sóc sức khỏe, không lưu, bán vé
Trong nhiều hệ thống phục vụ, các khách hàng (costumer) phải dùng chung tài nguyên, phải chờ để được phục vụ và đôi khi bị 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 hay 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 hay 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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
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 hay 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/E k/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 hay 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 hay vô hạn
- Quy tắc phục vụ:
FIFO hay 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 hay lần lượt hay 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 hay con người hay 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 hay 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