Bài giảng Lý thuyết xếp hàng và ứng dụng

a 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ác