Hàng đợi Markov

Một hàng đợi Markov có các lượt đến theo phân phối Poisson và thời gian phục vụ theo phân phối hàm mũ, làm cho số lượng khách hàng trở thành một chuỗi Markov thời gian liên tục mà trạng thái cân bằng của nó có thể được giải một cách tường minh.

Definition

Một hàng đợi Markov là một hệ thống dịch vụ trong đó khách hàng đến theo một quá trình Poisson và yêu cầu thời gian phục vụ độc lập theo phân phối hàm mũ, do đó số lượng trong hệ thống phát triển như một chuỗi Markov thời gian liên tục sinh-tử với các phân phối trạng thái ổn định và thời gian chờ tường minh.

Scope

Chủ đề này bao gồm ký hiệu Kendall cho các hệ thống hàng đợi, hàng đợi M/M/1 một máy chủ và phân phối dừng hình học của nó, hệ thống M/M/c nhiều máy chủ và hệ thống mất mát, các công thức Erlang B và C, tính ổn định và cường độ lưu lượng, và việc suy ra độ dài hàng đợi trung bình, thời gian chờ, và các đại lượng trong thời gian bận từ quá trình sinh-tử cơ bản.

Core questions

• Hàng đợi M/M/1 phát sinh như một quá trình sinh-tử như thế nào và phân phối dừng của nó là gì?
• Điều kiện nào về cường độ lưu lượng đảm bảo hàng đợi ổn định?
• Độ dài hàng đợi trung bình và thời gian chờ được tính như thế nào, và định luật Little được áp dụng ra sao?
• Nhiều máy chủ và dung lượng hữu hạn làm thay đổi các công thức Erlang như thế nào?

Key theories

Phân phối dừng và tính ổn định của M/M/1

Số lượng trong hàng đợi M/M/1 có phân phối dừng hình học với tham số bằng cường độ lưu lượng, tỷ lệ giữa tốc độ đến và tốc độ phục vụ, và hàng đợi ổn định chính xác khi tỷ lệ này nhỏ hơn một.

Công thức mất mát và trễ của Erlang

Đối với các hệ thống nhiều máy chủ, công thức Erlang B cho xác suất chặn trong hệ thống mất mát và công thức Erlang C cho xác suất chờ trong hệ thống trễ, cả hai đều được suy ra từ các phương trình cân bằng sinh-tử và là trung tâm của việc lập kế hoạch năng lực.

Clinical relevance

Hàng đợi Markov là các mô hình nền tảng để định cỡ các nhóm đường dây điện thoại, nhân sự trung tâm cuộc gọi, trang trại máy chủ và quầy dịch vụ, nơi các công thức Erlang chuyển đổi tải được cung cấp và mức độ dịch vụ mục tiêu thành số lượng máy chủ cần thiết.

History

Erlang đã suy ra các công thức mất mát và trễ cho lưu lượng điện thoại trong khoảng thời gian từ năm 1909 đến 1917, Kendall đã giới thiệu ký hiệu đến/phục vụ/máy chủ có hệ thống và phân tích chuỗi nhúng vào năm 1953, và chuyên luận của Kleinrock vào những năm 1970 đã áp dụng lý thuyết này vào mạng máy tính và truyền thông.

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

M/M/1 có nghĩa là gì?

Trong ký hiệu của Kendall, M đầu tiên biểu thị các lượt đến Markov (Poisson), M thứ hai biểu thị thời gian phục vụ theo phân phối hàm mũ, và 1 biểu thị một máy chủ duy nhất.

Khi nào một hàng đợi Markov ổn định?

Khi cường độ lưu lượng, tốc độ đến chia cho tổng tốc độ phục vụ, nhỏ hơn một; nếu không, hàng đợi sẽ tăng lên vô hạn và không tồn tại phân phối dừng.