Home > Probability Theory, Queueing Theory > Lý thuyết phục vụ đám đông I

Lý thuyết phục vụ đám đông I


Có bạn nào từng nghe nói đến một ngành Toán học thú vị có tên “Lý thuyết phục vụ đám đông” với ứng dụng vô cùng mạnh mẽ trong công nghệ thông tin, viễn thông, kinh tế…. Người nghiên cứu đầu tiên về nó là kỹ sư A.K. Erlang với bài báo vào năm 1909. Nó được hệ thống hóa thành lý thuyết vào khoảng những năm 1920s-1930s với những người đi tiên phong là những nhà Toán học O’Dell, Fry, Pollaczek, Kolmogorov, Khinchin… Đến những năm 1950s-1960s, Lý thuyết phục vụ đám đông hầu như được hoàn thiện về hình hài của nó như một bộ phận liên của Lý thuyết xác suất và Vận Trù học cho hệ thống ngẫu nhiên với những công trình quan trọng của Kendall, Lindley, Morse, Jackson, Gordon, Little, Takacs,…. Từ những năm 1980s-1990s, thì xu hướng áp dụng các công cụ của Giải tích ma trận được khởi xướng bởi Neuts, Lucantoni,… phát triển mạnh mẽ nhằm nghiên cứu các hệ phục vụ đám đông với những điều kiện điều khiển phức tạp.

www.sfu.ca/~pbastani/queue.jpg
Lý thuyết phục vụ đám đông hay lý thuyết hàng đợi – Queueing Theory, nghiên cứu các tính chất đặc trưng của mô hình toán liên quan đến hệ thống ngẫu nhiên như sau: có một hệ thống phục vụ và dòng khách hàng đến, trong đo các khách hàng tới hệ thống phải xếp hàng để đợi được phục vụ, khoảng thời gian đến của khách hàng, và khoảng thời gian phục vụ là những đại lượng ngẫu nhiên.
Có thể thấy những hệ thống như vậy trong thực tế, ví dụ: mạng điện thoại, mạng máy tính, hệ thống tính toán,…
Hệ thống phục vụ đám đông đặc trưng bởi:
+ Luồng khách hàng vào: theo quy luật phân phối nào đó, đi riêng lẻ hoặc theo nhóm,…
+ Thái độ của khách hàng: kiên nhẫn chờ hoặc không kiên nhẫn và bỏ đi với xác suất nào đó,…
+ Thời gian phục vụ: tuân theo quy luật phân phối nào đó
+ Khả năng phục vụ của hệ thống: phục vụ từng người một hoặc theo nhóm
+ Phương pháp phục vụ
– FCFS – First Come First Served.
– LCFS – Last Come First Served.
– SIRO – Service In Random Order.
– PS – Processor shared.
– IS – Infinitive server.
– Static priorities.
– Dynamic priorities.
– Preemption…
+ Phòng đợi: có thể giới hạn hoặc không giới hạn số lượng khách chờ.

Mục đích nghiên cứu của chuyên ngành:
+ Đánh giá tham số hệ thống bằng phương pháp thống kê.
+ Tìm điều kiện dừng của hệ thống.
+ Nghiên cứu các tính chất của hệ thống: xác suất được phục vụ, phân phối của số các yêu cầu ở trong hệ thống, phân phối của thời gian chờ, thời gian lưu trú của khách hàng,…
+ Bài toán điều khiển tối ưu của hệ thống khi sự thất lạc và lưu trú của khác hàng tương ứng với một hàm giá thành nào đó…

Hệ thống có thể được ký hiệu theo Kendall: 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.
Trong đó A, B có thể nhận một trong các phân phối sau
M – phân phối mũ có hàm phân phối F(x)=1-e^{-\lambda x}
E_k – phân phối Erlang k pha có hàm phân phối:
F(x) = 1-\sum_{j=0}^{k-1}\frac{e^{-\lambda x}(\lambda x)^{j}}{j!}.
H_k – phân phối siêu lũy thừa có hàm phân phối F(x) = \sum\limits_{j = 1}^k {q_j (1 - e^{ - \mu _j x} )} ,x \ge 0
D – phân phối tất định, có hàm phân phối $latex F(x)=\left\{\begin{matrix} 1, & \mbox{if }x\ge x_0 \\ 0, & \mbox{if }x PH – phân phối pha
G – phân phối tổng quát
GI – phân phối tổng quát, của các khoảng thời gian vào hoặc phục vụ độc lập nhau.
Xin bắt đầu bằng vài khái niệm cơ bản
1. Phân phối mũ

Đại lượng ngẫu nhiên có phân phối mũ, nếu nó có hàm phân phối F(x) = P\{ \xi < x= 1 - e^{-ax} \} ,\ x \ge 0. Khi đó:
– Kỳ vọng toán học
M\xi  = \int\limits_0^\infty  {xdF(x)}  = \int\limits_0^\infty  {xf(x)dx}  =a^{ - 1}
– Moment bậc i:
M\xi ^i  = \int\limits_0^\infty  {x^i dF(x) = \frac{{i!}}{{a^i }}.}

-Tính mất trí nhớ của phân phối mũ:
P{{\{ }}\xi  \ge {{x + b|}}\xi  \ge {{b\}  = P\{ }}\xi  \ge{{x\} }}

Cho \xi _{{1}} ,\xi _{{2}} ,...,\xi_{{n}} đại lượng ngẫu nhiên độc lập có phân phối mũ với tham số a_1 ,...,a_n tương ứng. Khi đó đại lượng ngẫu nhiên \xi  = \min {{\{ }}\xi _1 {{,}}...{{,}}\xi _n {{\} }} có phân phối mũ với tham số {{a = a}}_{{1}}  + {{a}}_{{2}}  + ... +{{a}}_{{n}} .

Theo tính chất trên ta có

P{{\{ }}\xi  = \xi _i {{\} =}}\frac{{{{a}}_{{i}}}}{{{a}}}Nếu đại lượng ngẫu nhiên \xi có phân phối mũ với tham số a, thì
http://latex.codecogs.com/gif.latex?F(\Delta%20t)%20=%20P\{%20\xi%20%3C%20\Delta%20t%20\}%20=%20a%20\Delta%20t+o(\Delta%20t)
2. Phép biến đổi Laplace-Stieltjes
Phép biến đổi Laplace – Stieltjes của hàm phân phối A(t) của đại lượng ngẫu nhiên \xi là hàm
\alpha (q) = Ee^{ - q\xi }  = \int\limits_0^\infty  {e^{ - qt} dA(t),}
trong đó q – biến phức, {\mathop{\rm Re}\nolimits} q \ge 0. Hàm \alpha (q) gọi là phép biến đổi Laplace – Stieltjes của đại lượng ngẫu nhiên \xi .

Mối quan hệ của nó và phép biên đổi Laplace
\alpha (q) = \int\limits_0^\infty  {e^{ - qt} dA(t) = q\int\limits_0^\infty{e^{ - qt} A(t)dt} }

Đối với hàm phân phối liên tục A(t) trên {\rm{[0;}}\infty {\rm{)}}
i. \int\limits_0^\infty  {e^{ - qt} dA'(t) = q\alpha (q) - qA(0).}
trong đó \alpha (q) là phép biến đổi Laplace – Stieltjes của hàm phân phối A(t).
ii. \alpha _i  = E\xi ^i  = ( - 1)^i \alpha ^{(i)} (q)|_{q = 0}
iii. \text{Var}(\xi)  = E\xi ^2  - (E\xi )^2  = \alpha_2  - (\alpha_1 )^2  = \alpha''(0) - (\alpha' (0))^2 .

3. Xích Markov
Xích Markov là dạng đặc biệt có không quá đếm được trạng thái của quá trình Markov. Ta gọi quá trình ngẫu nhiên \{X_t, t\in I\} nhận giá trị thuộc tập hợp không quá đếm được E là xích Markov nếu với bất kì dãy t_0<t_1<...<t_n<t_{n+1} thuộc I thì
P(X_{t_{n+1}}=j\ | \ X_{t_0}=i_0,....,X_{t_{n}}=i_n) = P(X_{t_{n+1}}=j\ | X_{t_{n}}=i_n) với mọi i_0,...,i_{n},j\in E.

Như thế, một xích Markov được xác định hoàn toàn bằng \eta_i= P(X_0=i) gọi là phân phối ban đầu và các xác suất chuyển p_{ij}(s,t)=P(X_t=j|X_s=i).

Nếu p_{ij}(s,t)= p_{ij}(s+h,t+h) với mọi h thì ta gọi là \{X_t\} là xích Markov thuần nhất, và từ này trở về sau ta ngầm hiểu một chuỗi Markov thì thuần nhất.

Khi đó ta chỉ cần quan tâm tới p_{ij}(t)= P(X_t=j|X_0=i). Ma trận P(t)=(p_{ij}(t))_{i,j\in E} gọi là ma trận xác suất chuyển tại thời điểm t.

Như vậy khi nói đến xích Markov (thuần nhất) \{X_t, t\in I\} nghĩa là ta nói đến bộ đôi \{\eta, P(t)\}.

Trong trường hợp I là tập rời rạc, có thể thay P(t) bằng ma trận một bước chuyển P=(p_{i,j}), trong đó p_{i,j}=P(X_{n+1}=j|X_n=i) Nghĩa là xích Markov rời rạc \{X_n\} xác định bởi \{\eta, P\}.

Một kết quả quan trọng của xích Markov thuần nhất đó là phương trình Chapman-Kolmogorov

P(t+\Delta)=P(t)P(\Delta)
Trong trường hợp rời rạc ta còn có chú ý P(n)=P^n.
Từ phương trình Chapman-Kolmogorov suy ra
\frac{P(t+\Delta)-P(t)}{\Delta}=P(t)\frac{(P(\Delta)-I)}{\Delta}cho \Delta\downarrow 0 ta được P'(t)=P(t)Q, hay P(t)=e^{Qt}=\sum_{n=0}^{\infty} \frac{t^n}{n!}Q^n
Trong đó Q=(q_{i,j})=\lim_{\Delta\downarrow 0} \frac{P(\Delta)-I}{\Delta}, gọi là infinitesimal generator (hay ma trận cường độ chuyển) của chuỗi Markov (X_t)_{t\ge 0}.
Khi đó
q_{ij}=\lim_{\Delta\downarrow 0} \frac{p_{ij}(\Delta)}{\Delta}, i\neq j
q_{ii}=\lim_{\Delta\downarrow 0} \frac{p_{ii}(\Delta)-1}{\Delta}
q_{ij} gọi là cường độ chuyển từ trạng thái i sang trạng j. Chú ý rằng
\sum_{j\in E}q_{ij}=0
tức tổng các phần tử mỗi dòng của Q bằng 0.
4. Renewal theory
Renewal Theory thực ra đã phát triển thành nhánh lý thuyết riêng trong ngành Xác suất. Ở đây không có tham vọng đi sâu xa mà chỉ là nói qua vài tư tưởng có liên quan.

Cho (Z_n)_{n\ge 0} là dãy các biến ngẫu nhiên dương độc lập, giả sử (Z_n)_{n\ge 1} cùng phân phối.
Ta đặt (T_n)_{n\ge 1} sao cho Z_0=T_1, Z_n=T_{n+1}-T_n hay T_{n}=\sum_{i=0}^{n-1}Z_{k}.
T_n gọi là thời điểm renewal thứ n, Z_n gọi là khoảng renewal thứ n

Ta đặt \nu_t=\text{max}\{n\in \mathbb{N}\ :\ T_n\le t\}, t\ge 0, khi đó (\nu_t)_{t\ge0} gọi là quá trình renewal từ (Z_n)
Khoảng ban đầu Z_0 gọi là delay. Nếu giả sử Z_0 cũng cùng phân phối với Z_k, k\ge 1 thì (\nu_t)_{t\ge 0} gọi là ordinary.

i152.photobucket.com/albums/s165/dumb_boy1988/renewal.png
Renewal Theorem.
Cho (\nu_t)_{t\ge 0} là quá trình renewal từ dãy các khoảng renewal (Z_n)_{n\ge1}. Giả sử rằng E(X_0)<\infty, E(Z_k)=\lambda>0, k\ge 1
Thế thì
\lim_{t\to\infty}\frac{E(\nu_t)}{t}=\frac{1}{\lambda}
Tích chập của một hàm phân phối F xác định trên \mathbb{R}_+ với một hàm đo được Lebesgue g:\mathbb{R}_+\to\mathbb{R}_+ bị chặn trên mọi khoảng [0,t], t\ge 0 được kí hiệu bởi
F*g(t)=\int_{[0,t]} g(t-u)dF(u)
Ta đưa ra định nghĩa lũy thừa chập (convolutional power) bằng quy nạp với F^{*1}=F, F^{*n+1}=F^{*}*F.
Giả sử (\nu_t)_{t\ge 0} là một ordinary renewal process, với F(t) là hàm phân phối của khoảng renewal Z_k, k\ge 0 . R(t)=\sum_{n=1}^{\infty}F^{*n}(t) gọi là hàm renewal của (\nu_t)_{t\ge 0}.
Khi đó lấy biến biến đổi Laplace–Stieltjes, ta có \widehat{F}(s)=\frac{\widehat{R}(s)}{1+\widehat{R}(s)}. Điều này có nghĩa là (\nu_t)_{t\ge 0} hoàn toàn có thể xác định một cách duy nhất bởi hàm renewal của nó.
Xét (\nu_t)_{t\ge 0} là một ordinary renewal process, với F(t) là hàm phân phối của khoảng renewal Z_k, k\ge 0 và các thời điểm renewal tương ứng (T_k)_{k\ge 1}. Ta đặt
\mu(t)=\lim_{\Delta\downarrow 0}\frac{P\{ \nu_{t+\Delta}-\nu_t\ge 1\ | \ \nu_t-\nu_0=0 \}}{\Delta}
gọi là cường độ tức thời của (\nu_t)_{t\ge 0}
Khi đó P\{ \nu_{t+\Delta}-\nu_t\ge 1\ | \ \nu_t-\nu_0=0 \}=\mu(t)\Delta+o(\Delta) khi \Delta\downarrow 0.Ta có
F(\tau)=P\{Z_k\le \tau \}=P\{T_{k+1}-T_k\le \tau \}=P\{\nu_{T_k+\tau}-\nu_{T_k}\ge 1\}
F(\tau+\Delta)=P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1\}
=P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1,  \nu_{T_k+\tau}-\nu_{T_k}\ge 1 \} +P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1, \nu_{T_k+\tau}-\nu_{T_k}=0 \}
=P\{ \nu_{T_k+\tau}-\nu_{T_k}\ge 1 \} +P\{ \nu_{T_k+\tau}-\nu_{T_k}=0 \}P\{\nu_{T_k+\tau+\Delta}-\nu_{T_k}\ge 1\ |\ \nu_{T_k+\tau}-\nu_{T_k}=0 \}
=F(\tau)+(1-F(\tau))\left( \mu(\tau)\Delta+o(\Delta) \right)
Cho \Delta\to 0, ta có
F'(\tau)=(1-F(\tau))\mu(\tau)
Giải phương trình vi phân một biến này ta dễ dàng thu được mối quan liên hệ giữa cường độ tức thời của ordinary renewal process hàm phân phối của renewal interval tương ứng
F(t)=1-e^{-\int_0^t \mu(\tau)d\tau}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: