Bài giảng Khoa học dịch vụ: Chương 5

NHẬP MÔN KHOA HỌC DỊCH VỤ

CHƯƠNG 5. HÀNG ĐỢI

PGS. TS. HÀ QUANG THỤY

HÀ NỘI 09-2018

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐẠI HỌC QUỐC GIA HÀ NỘI

1

Nội dung chương

➢Giới thiệu ➢ Lý thuyết hàng đợi là gì ➢ Độ đo hiệu năng cốt lõi ➢ Một khung cho hàng đợi Markov ➢ Kết quả quan trọng ở hàng đợi không Markov. ➢Giải mô hình hàng đợi số ➢Khi các điều kiện thay đổi theo thời gian

KHDV 2016 – Chương 5 - Trang 2

1. Giới thiệu

❖ Rút tiền tại Ngân hàng hoặc tại ATM ❖ Xếp hàng đợi và có thể khó chịu ❖ Một số dịch vụ “hy vọng” không bao giờ phải đợi: dịch vụ

➢ Giới thiệu

cứu hỏa !, dịch vụ trên Internet v.v. ❖ “Hàng đợi” một dòng “đợi” dịch vụ ❖ Đợi: nảy sinh cả khi tình huống tài nguyên được cho là đủ

➢Một số phân loại hàng đợi

❖ Hàng đợi trong suốt ❖ Hàng đợi không trong suốt ❖ Hàng đợi thiếu yếu tố con người

KHDV 2016 – Chương 5 - Trang 3

Phân tích một số hàng đợi dịch vụ

➢Ví dụ: Phân tích hàng đợi khám bệnh bác sỹ

❖ Lên lịch bác sỹ khám bệnh theo lịch: lịch 18’/bệnh nhân, 2’ nghỉ ngơi cho bác sỹ, lên lịch hẹn theo lịch 20’ từ 8h00 tới 16h40. Hy vọng không ai phải đợi

ngày theo trung bình thời gian bệnh nhân phải đợi ?

❖ Tuy nhiên, không hoàn hảo, kiểm tra bằng mô phỏng 365

❖ Bác sỹ không khám đúng 18’ với mọi bệnh nhân ❖ Bệnh nhân đến sớm hơn lịch ❖ … ❖ Dùng mô phỏng Excel: xuất hiện hàng đợi tới bác sỹ.

❖ “Đợi” bác sỹ trong hàng đợi, lý do:

KHDV 2016 – Chương 5 - Trang 4

Thời gian bác sỹ khám: hai phân bố

➢Hai phân bố thời gian dịch vụ khám một bệnh nhân

❖ Phân bố đều: trong miền [13,23]. Chiều rộng phân bố đều bằng hai lần thời gian kéo dài với xác suất 0.1 mỗi phút

❖ Phân bố tam giác: trong miền [13, 28] với hai lần kéo dài

về sau và một lần kéo dài về trước.

KHDV 2016 – Chương 5 - Trang 5

Thời gian bận rộn bác sỹ khám: pb đều ➢Biến động thời gian bận trung bình: mô phỏng

❖ Nếu thời gian phục vụ 18’: bận 90%, 15’ : bận 75%, 19,5’:

bận 97,5%

❖ Ba độ đo cốt lõi: thời gian đợi trung bình được bác sĩ khám; thời gian đợi trung bình cho người phải đợi; tỷ lệ bệnh nhân phải đợi

❖ tác động của biến thiên và thay đổi thời gian dịch vụ theo thời gian phục vụ bình quân trên thời gian đợi trải nghiệm một bệnh nhân (giả sử mọi bệnh nhân đến đúng vào thời gian dự kiến của họ). Giá trị kéo dài nhỏ

KHDV 2016 – Chương 5 - Trang 6

Thời gian bận của bác sỹ khám: pb đều ➢Biến đổi thời gian bận trung bình

❖ Trái: Ảnh hưởng thời gian phục vụ trung bình và biến đổi thời gian dịch vụ theo tỷ lệ bệnh nhân những ai phải đợi cho dịch vụ với các bệnh nhân đến đúng như dự kiến

❖ Phải: Ảnh hưởng của thời gian dịch vụ trung bình và độ biến đổi thời

gian theo % bệnh nhân phải đợi khi bệnh nhân đến đúng hẹn

❖ “Trung bình” → biến ngầu nhiên thời gian bác sỹ khám. Bệnh nhân phải đợi ngay khi (a) thời gian phục vụ bình quân là ít hơn so khoảng cách xuất hiện các bệnh nhân và (b) các khách hàng đến đúng hẹn.

KHDV 2016 – Chương 5 - Trang 7

Bệnh nhân trễ hẹn: theo phân bố đều

➢Bệnh nhân trễ hẹn

❖ Bệnh nhân đến sớm: đợi do tự bản thân ❖ Bệnh nhân đến trễ: gây đợi cho người khác ❖ Thời gian đợi trung bình trên mọi bệnh nhân nếu bệnh

nhân đồng đều đến trễ 5 phút so với hẹn

KHDV 2016 – Chương 5 - Trang 8

Phân bố thời gian phục vụ tam giác ➢Tác động biến thiên tăng phân bố thời gian phục vụ ❖ Trái: Tương ứng ngay trước: phân bố thời gian phục vụ

tam giác

❖ Thời gian đợi tăng lên dù thời gian phục vụ ít hơn thời gian bệnh nhân xuất hiện. Khả năng xuất hiện nhỏ tới 31,5’ với trung bình 19’ với kéo dài 6’.

❖ Phải: Thời gian đợi trung bình đối với bệnh nhân phải đợi.

Ít hài lòng nhất

KHDV 2016 – Chương 5 - Trang 9

Ví dụ 2: Xác định số chỗ đậu xe

➢ Xác định số chỗ đậu xe ở một trung tâm mua sắm

❖ Ví dụ giúp mô hình hóa hàng đợi ❖ Xe xuất hiện theo “quá trình Poisson” với 1200 chiếc/giờ

(trung bình 20 xe/phút).

❖ Mỗi người ở lại trung tâm mua sắm 3 giờ. ❖ Nên xây bao nhiêu lô đậu xe để 98% chắc chắn đủ ?

➢ Phân tích sơ bộ

❖ 1200 xe/giờ và 3 giờ  cần 3600 chỗ ? ❖ 1200 xe/giờ song với 50% tình huống lớn hơn 1200 xe/ giờ. Nếu chỉ có 3600 chỗ: 50% trường hợp không đủ chỗ. ❖ Phải chăng là 6000 ? Phải chăng là 7000 để 98% khả năng đủ chỗ ? Không đơn giản. Xem phân bố Poisson ❖ Nếu xe xuất hiện phân bố Poisson và ở lại 3 giờ thì có giá

trình trung bình 3600 xe.

KHDV 2016 – Chương 5 - Trang 10

Ví dụ 2: Xác định số chỗ đậu xe (2) ➢ Số lượng chỗ đậu xe cho một trung tâm mua sắm ➢ Phân tích sơ bộ

❖ Xe xuất hiện phân bố Poisson và ở lại 3 giờ thì có giá trị trung bình 3600 xe. Tương đương phân bố chuẩn với trung bình 3600 và độ lệch b/phương trung bình 60.

❖ Cơ hội 2% biến n/nhiên phân bố chuẩn có giá trị cao hơn 2 độ lệch. Xác suất 98%: số xe  3600+ 2*60=3720 (Thực tế 3723 p/bố Poisson). Số dự trữ nên là 3,4% khi 3600 tb.

➢Phân tích thêm

❖ Đến – đi ra khỏi bãi đậu xe là lý tưởng: hê thống tiên tiến

❖ Phân thành 20 vùng. Tương tự mỗi vùng 180 chỗ thì tổng

mới giúp khách hàng xác định lô rỗng.

cộng cần 4160 lô.

❖ Tuy nhiên, xác suất tích hợp 0.9820 = 0.667. Cần 0.98 cho cả 20 vùng thì mỗi vùng eln(0.98)/20=0.99899. Cần 223 lô cho mỗi vùng

KHDV 2016 – Chương 5 - Trang 11

2. Một số kiến thức bổ túc về xác suất

➢Biến ngẫu nhiên

❖ Biến ngẫu nhiên là biến nhận giá trị về biến đổi cơ hội/từ kết quả một thực nghiệm thống kê; dùng chữ cái in hoa

❖ Mỗi giá trị của biến ngẫu nhiên có một xác suất cơ hội

❖ Kỳ vọng “expected value” E(X) biến ngẫu nhiên X, ❖ Phương sai “variance” 2(X), độ lệch chuẩn “standard

deviation” (X)

❖ X biến ngẫu nhiên dương, hệ số biến thiên “coecient of

variation” cX= (X)/E(X)

KHDV 2016 – Chương 5 - Trang 12

Biến ngẫu nhiên rời rạc/liên tục

➢Biến ngẫu nhiên rời rạc ❖ Cho X biến ngẫu nhiên ❖ X nhận giá trị đếm được (hữu hạn/vô hạn): biến ngẫu

nhiên rời rạc.

❖ Ví dụ: biến ngẫu nhiên tương ứng mặt “sấp”/”ngửa” ở trên khi tung đồng xu: biến ngẫu nhiên rời rạc (S. N). Tung liền hai lần (SS, SN, NS, NN)

❖ Tung viên xúc sắc sáu mặt có 6 giá trị …. ❖ Bảng phân bố xác suất: Theo từng giá trị

➢ Biến ngẫu nhiên liên tục ❖ X nhận giá trị liên tục ❖ Ví dụ: Biến ngẫu nhiên lốc xoáy xảy ra ở một vị trí trong

không gian hai chiều là biến liên tục.

KHDV 2016 – Chương 5 - Trang 13

Một số phân bố xác suất thông dụng

➢Phân bố hình học

❖ Cho X là biến ngẫu nhiên rời rạc “giá trị nguyên” ❖ X có phân bố hình học với tham số p là

❖ Các đặc trưng

➢ Phân bố Poisson (đề cập bài toán khu để xe)

❖ Cho X là biến ngẫu nhiên rời rạc ❖ X có phân bố Poisson với tham số  là

❖ Các đặc trưng

KHDV 2016 – Chương 5 - Trang 14

Phân bố mũ

➢Phân bố mũ

❖ Cho X là biến ngẫu nhiên liên tục dương ❖ X có phân bố mũ với tham số  và hàm mật độ là

❖ Các đặc trưng

❖ Tính chất “quên” (không nhớ “memoryless property”): x>0, t>0:

có nghĩa là kỳ vọng phía sau t vẫn là 1/.

❖ Nếu X1, X2, …, Xn là các biến ngẫu nhiên phân bố mũ độc lập thì min (X1, X2, …, Xn) một biến ngẫu nhiên phân bố mũ với tham số và xác suất để Xi là nhỏ nhất i=1, 2, …, n.

KHDV 2016 – Chương 5 - Trang 15

Phân bố Erlang

➢Phân bố Erlang

❖ Ký hiệu Ek() hoặc Ek. ❖ Hàm phân bố xác suất

❖ Hàm mật độ xác suất (đạo hàm của phân bố xác suất

❖ Cho X là biến ngẫu nhiên liên lục trong miền t>0 ❖ X có phân bố Erlang-k (k=1,2, …) với kỳ vọng k/ nếu như X là tổng của k biến ngẫu nhiên độc lập có cùng phân bố mũ với kỳ vọng 1/.

theo t)

❖ : tham số cỡ (kích thước), k: tham số hình dạng

KHDV 2016 – Chương 5 - Trang 16

Phân bố Erlang

➢Sơ đồ “pha” của biến ngẫu nhiên Erlang

❖ Hàm mật độ của phân bố k-Erlang với kỳ vọng 1 và

phương sai k

KHDV 2016 – Chương 5 - Trang 17

Phân bố Erlang

➢Các đặc trưng

❖ Phân phối phù hợp “convenient” khi kết hợp hai phân

❖ Một biến ngẫu nhiên có phân bố xác suất Ek-1,k() nếu X với xác suất p (tương ứng, 1-p) tổng của k-1 (tương ứng k) biến ngẫu nhiên độc lập với cùng kỳ vọng 1/. Mật độ xác suất của biến ngẫu nhiên này:

phối Ek-1 và Ek với cùng tham số cỡ: Ek-1,k.

kết hợp chạy từ 1/k tới 1/(k-1).

❖ với 0  p  1. ❖ Khi p chạy từ 0 tới 1 hệ số biến thiên của phân bố Erlang

❖ Đây là biến ngẫu nhiên tương đối phổ biến

KHDV 2016 – Chương 5 - Trang 18

Biến ngẫu nhiên phân bố kiểu pha

➢Khái niệm

❖ Các phân bố trước đây là trường hợp đặc biệt của phân

bố kiểu pha (phase-type distribution).

❖ Phân bố Coxi: Biến ngẫu nhiên X có phân bố Coxi bậc k nếu nó đi qua hầu hết k pha phân bố mũ. Độ dài kỳ vọng của pha n là n, n=1,2, …, k. Nó bắt đầu từ pha 1, sau pha n nó kết thúc với xác suất 1-pn và nó đi tới pha tiếp theo với xác suất pn. Rõ ràng pk=0. Với phân bố Cosi-2 thì hệ số biến thiên  0.5.

❖ Biến ngẫu nhiên X có phân bố Erlang kết hợp bậc k nếu nó với xác suất pn là tổng của n phân bố mũ với cùng một kỳ vọng 1/.

KHDV 2016 – Chương 5 - Trang 19

Biến ngẫu nhiên phân bố siêu mũ

➢Phân bố Hyperexponential distribution

❖ X là biến ngẫu nhiên liên tục t>0 ❖ X có phân bố siêu mũ với các xác suất pi (i=1,2, …, k) là

biến ngẫu nhiên có phân bố mũ với kỳ vọng 1/i.

❖ Hệ số biến thiên cX  1.

❖ Ký hiệu X là Hk(p1, …, pk; 1, …, k) hoặc Hk. ❖ Hàm mật độ và kỳ vọng

❖ Sơ đồ pha

KHDV 2016 – Chương 5 - Trang 20

3. Lý thuyết hàng đợi ➢ Mở đầu

❖ Sự chậm trễ xảy ra ngay cả với hệ thống đặc trưng trung

bình cho biết không xuất hiện hàng đợi

❖ Sử dụng mô phỏng: (i) tốn kém thời gian lập trình viên + thời gian máy tính; (ii) đầu ra mô phỏng là thời gian đợi trung bình, tỷ lệ khách hàng đợi – biến ngẫu nhiên phụ thuộc sự không chắc chắn. Câu hỏi cốt lõi nên là: cần bao nhiều dòng ? Cái gì nên cắt cho cỡ dự kiến đạt chất lượng dòng ? Bao nhiêu dòng dịch vụ đầy đủ nên khởi tạo; (iii) Nếu chạy ít mô phỏng không đủ minh họa xu thể !  Lý thuyết hàng đợi là sự thay thế tốt !

➢ Sơ bộ

❖ Kết nối toán học với hàng đợi/dòng chờ (waiting lines) ❖ Có hai tiếp cận cơ bản: (i) Mô hình dựa trên xấp xỉ dòng lỏng (Newell, 1971): khung xác định hàng đợi, đặc biệt hữu ích trong phân tích hàng đợi mà tỷ lệ đến trung bình vượt tốc độ phục vụ bình quân trong thời gian dài gian; (ii) phân tích hàng đợi xác suất: một khung ngẫu nhiên hàng đợi, hữu ích nhất trong phân tích hàng đợi mà tỷ lệ xuất hiện ít hơn tỷ lệ dịch vụ trong thời gian dài.

KHDV 2016 – Chương 5 - Trang 21

Lý thuyết hàng đợi ➢ Mở đầu

❖ Lý thuyết hàng đợi (xác định/ngẫu nhiên) đòi hỏi các đầu vào ❖ Cần đặc trưng hóa : (i) Quá trình xuất hiện cũng như (ii)

Quá trình dịch vụ

➢ Đầu vào cho mô hình hàng đợi

a) Mô tả cách thức khách hàng xuất hiện vào hệ thống. Quá trình xuất hiện (arrival process). Chú ý đặc biệt: phân bố xuất hiện khách hang theo thời gian

b) Mô tả cách thức khách hàng được phục vụ. Quá trình phục vụ (service process). Chú ý đặc biệt: (i) ước lượng trung bình và độ lệch bình phương trung bình thời gian cần để phục vụ một khách hàng; (ii) phân bố xác suất thực sự của thời gian cần để phục vụ khách hàng

c) Số lượng phục vụ d) Số lượng cực đại khách hàng có thể đi vào hệ thống

KHDV 2016 – Chương 5 - Trang 22

Đầu vào hàng đợi (2) ➢Đầu vào cho mô hình hang đợi

e) Kích thước xâu (pool) khách hàng f) Cách thức mà khách hàng đợi được chọn để phục vụ.

Quy tắc phục vụ (service discipline)

➢Giải thích

❖ Các đầu vào a), b), c) luôn cần. Kendal phát triển lưu ý

quá trình phục vụ tương ứng,

❖ Z là sơ nguyên (có thể ) chỉ số lượng phục vụ

chuẩn cho các đầu vào này X/Y/Z: ❖ X và Y là các chữ cái được dung để mô tả quá trình xuất hiện và

hiện Poisson,

❖ Ek: Phân bố Erlang-k. Phân bố Erlang-1 là phân bố lũy thừa, phân bố Erlang-k là tống k các phân bố lũy thừa phân tán xác định độc lập

❖ X và Y để mô tả phân bố xác suất được dung trong mô hình hóa thời gian xuất hiện và thời gian phục vụ khách hàng: ❖ M: Phân bố lũy thừa (Exponential Distribution), tương ứng với xuất

KHDV 2016 – Chương 5 - Trang 23

Đầu vào hang đợi ➢Phân bố xác suất được sử dụng

❖ HE: Phân bố mũ (Hyperexponential distribution) ❖ D: Xác định ❖ G, GI: Phân bố tổng quát với trung bình và độ lệch hữu hạn. GI thường dung cho xuất hiện và ghi chú độc lập tổng quát, G thường được dung cho thời gian dịch vụ. Trong cả hai trường hợp thì giả thiết : thời gian xuất hiện và thời gian phục vụ là các biến ngẫu nhiên độc lập.

➢Ví dụ

❖ M/M/1: Một dòng phục vụ đơn, phân bố t/gian xuất hiện Poisson, phân bố thời gian phục vụ phân tán lũy thừa. ❖ M/Ek/1: phục vụ đơn, Posson xuất hiện, phân bố thời

gian phục vụ Erlang-k

❖ M/M/s: như M/M/1 song s máy phục vụ ❖ M/G/: M, phân bố thời gian phục vụ tổng quát, vô hạn

máy

KHDV 2016 – Chương 5 - Trang 24

Hàng đợi Markov

➢Giới thiệu

thừa)

❖ Xuất hiện Poisson (hoặc thời gian xuất hiện phân bố lũy

❖ Phục vụ: thời gian xuất hiện phân bố lũy thừa ❖ Markov: Phân bố lũy

thừa có tính không nhớ (memoryless) làm đơn gián mô hình hóa hang đợi, không cần biết khách hang cuối đến là bao lâu.

➢ Tập tối thiểu các output

❖ Số lượng trung bình trong hệ thống (hang đợi, dòng, phục

vụ)

❖ Số lượng trung bình ở trong hang đợi (đợi để phục vụ) ❖ Thời gian trung bình trong hệ thống hoặc trong hang đợi ❖ Một số đầu ra quan tâm khác: thời gian trung bình khách ở hang đợi/hệ thống, phân bố thời gian giữa xuất phát từ hang đợi

KHDV 2016 – Chương 5 - Trang 25

4. Độ đo hiệu năng cốt lõi

➢Định nghĩa các độ đo

❖ L: Số lượng trung bình khách hàng trong hệ thống,

❖ Lq: số trung bình khách hàng đợi để được phục vụ,

❖ Wq: thời gian trung bình trong hàng đợi để được phục vụ,

❖ W: thời gian trung bình trong hệ thống,

❖ : tốc độ xuất hiện trung bình,

❖ 1/: thời gian phục vụ trung bình.

❖ : tốc độ phục vụ trung bình,

KHDV 2016 – Chương 5 - Trang 26

Độ đo bổ sung

❖ : số người xuất hiện tại hệ thống trong thời

❖ ❖

➢Độ đo bổ sung a (t) gian [0, t], d (t) : số người rời hệ thống trong thời gian [0, t], N (t) : số người đang ở trong hệ thống tại thời điểm t. Lưu ý rằng N (t) = a (t) - d (t).

KHDV 2016 – Chương 5 - Trang 27

Các độ đo bổ sung

➢Tích lũy và trung bình

❖ Tổng số tích lũy phút-người trong khoảng [0,t]

❖ Thời gian đợi trung bình trong khoảng [0,t]: l(t)/(a(t)=W (t)

và số trung bình trong hệ thống là l(t)/t = L (t)

(3.1)

❖ . ❖ Lấy giới hạn khi t→ :

KHDV 2016 – Chương 5 - Trang 28

Luật nhỏ và liên quan

➢Luật nhỏ

L = W (3.2)

❖ Số lượng trung bình khách hàng trong hệ thống bằng tích của tốc độ xuất hiện trung bình với thời gian trung bình trong hệ thống.

Ls= Ws = 1/, với Ls: số lượng người trung bình

(3.3) ❖ Tương tự có Lq = Wq

trong dịch vụ và Ws: thời gian phục vụ trung bình.

➢ Thời gian tổng cộng

(3.4)

❖ W = Wq + 1/ ❖ thời gian trung bình trong hệ thống bằng tổng thời gian trung bình dành cho đợi dịch vụ bắt đầu cộng với thời gian phục vụ trung bình.

KHDV 2016 – Chương 5 - Trang 29

5. Khung đối với hang đợi Markov

➢Khái niệm quá trình Markov

❖ Quá trình Markov: một QT ngẫu nhiên mà xác suất có điều kiện thuộc một trạng thái bất kỳ tại một thời điểm tương lai “khi cho trạng thái hiện tại và trạng thái quá khứ” bằng xác suất ở trạng thái đó trong tương lai khi cho “chỉ trạng thái hiện tại”. ❖ lịch sử quá khứ của hệ thống không cung cấp thông tin bất kỳ

mà cần thiết để dự đoán trạng thái tương lai.

❖ trạng thái hệ thống thường được mô tả: số lượng khách hàng trong hàng đợi (mặc dù ở một số hệ thống tiên tiến hơn: mô tả khác nhau trạng thái hệ thống cần thiết)

KHDV 2016 – Chương 5 - Trang 30

Khung hàng đợi Markov

➢Đặt vấn đề

❖ Phát triển một khung chung phân tích hàng đợi Markov ❖ Phân bố mũ là phân bố không nhớ

❖ Ví dụ, nếu thời gian DV pb mũ với trung bình 15 phút; khách hàng hiện tại đã được phục vụ 12 phút (thậm chí 20 phút) không cho biết gì về thời gian khách hàng trong dịch vụ: giá trị trung bình vẫn là 15 phút

❖ Quá trình xuất hiện và quá trình dịch vụ đều không nhớ

KHDV 2016 – Chương 5 - Trang 31

H/đợi Markov: Tính chất phân bố mũ

➢Một số tính chất bổ sung phân bố mũ

o((t)2) là các số hạng bậc (t)2 hoặc nhỏ hơn.

❖ Quá trình xuất hiện Poisson với tốc độ xuất hiện  ❖ Xác suất không xuất hiện trong thời đoạn ngắn t

❖ Với t nhỏ, ta có:

❖ Xác suất của hai hay nhiều sự kiện trong một thời gian đủ

ngắn về cơ bản là 0 và có thể bỏ qua.

xác suất không hoàn thành là 1-t

❖ Tương tự với quá trình phục vụ: Trong khoảng t nhỏ,

KHDV 2016 – Chương 5 - Trang 32

Phát triển các phương trình

➢ Giả thiết tốc độ xuất hiện, tốc độ dịch vụ

❖ Phụ thuộc vào số lượng người trong hệ thống ❖ Thời gian

➢ Cụ thể

❖ n(t): (Poisson) tỷ lệ xuất hiện n người trong hệ thống tại thời

điểm t

(3.5)

❖ μn(t): tỷ lệ phục vụ với n người trong hệ thống tại thời điểm t ❖ Pi(t) là xác suất ở trạng thái i tại thời điểm t: ❖ ❖ và

KHDV 2016 – Chương 5 - Trang 33

H/đợi Markov: Thiết lập phương trình

(3.5)

➢

❖ Xác suất trong trạng thái 0 không có một người ở hệ thống

hàng xuất hiện

❖ Xác suất mà hệ thống hiện có một khách và người đó hoàn thành dịch

vụ trong thời gian rất ngắn..

❖ Xác suất ở trạng thái i với thời gian ngắn hiện tại là tổng:

❖ xác suất mà hệ thống hiện đang ở trạng thái i-1 và có 1 khách hàng xuất

hiện trong một thời gian ngắn

❖ xác suất mà hệ thống hiện đang ở trạng thái i và không có khách xuất hiện

hoặc hoàn tất dịch vụ trong khoảng thời gian ngắn.

❖ xác suất mà hệ thống hiện đang ở trạng thái i + 1 và có một khách hoàn thành dịch vụ

trong khoảng thời gian ngắn

trong một thời gian rất ngắn từ hiện tại là tổng: ❖ xác suất mà hệ thống đang ở trạng thái 0 hiện tại và không có khách

KHDV 2016 – Chương 5 - Trang 34

H/đợi Markov: Thiết lập phương trình

➢Biến đổi (3.5) và (3.6)

❖ Đưa Pi(t) về bên trái và chia cho t

❖ Lấy giới hạn khi cho t → 0: ❖ (3.7)

❖ (3.8)

❖ Phương trình Chapman-Kolmogorov

KHDV 2016 – Chương 5 - Trang 35

Phương trình Chapman-Kolmogorov

➢  trạng thái của một hàng đợi Markov

❖ Cung cấp các tỷ lệ về các xác suất thay đổi trạng thái như

hàm theo thời gian

❖ Chưa đề cập số lượng phục vụ theo thời gian ❖ Ngầm định giả định có khả năng vô hạn trạng thái

➢ Phương trình (3.8)

❖ Có thể chỉnh đơn giản khi có hữu hạn trạng thái ❖ Đại lượng hữu hạn = số cư dân được phục vụ ở hệ thống ❖ Trung tâm cuộc gọi với hữu hạn các dòng ❖ Trung tâm đậu xe không cho phép xếp hàng ❖ Trung tâm chỉnh sửa thiết bị hàng không

KHDV 2016 – Chương 5 - Trang 36

P/trình cân bằng trạng thái ổn định

➢ Mối quan tâm chính từ lý thuyết hàng đợi

❖ Ước tính dài hạn hiệu năng trung bình hệ thống ❖ Cần giả định: tỷ lệ xuất hiện và tỷ lệ phục vụ không phụ

thuộc thời gian: i(t)=i và μi(t) = μi : t.

tương đối hợp lý trong thực tế

❖ “hệ thống được giả định hoạt động vô thời hạn thời gian”:

❖ “hệ thống loại trừ việc “ngừng dịch vụ” vào cuối ngày”: khi

(3.9) (3.10)

đó tốc độ xuất hiện giảm tới 0. ❖ Cho thêm Pi(t)= Pi và dPi(t)/dt=0. ❖ Viết lại (3.8) và (3.9) theo các giả định trên ❖ ❖ ❖ Giải (3.9) với P1 theo Po , có

KHDV 2016 – Chương 5 - Trang 37

P/trình cân bằng trạng thái ổn định

➢ Trình bày các phương trình

(3.9) (3.10)

❖ ❖ ❖ Giải (3.9) với P1 theo Po , có ❖ Giải (3.10) với I = 1 có

❖ hoặc

❖ Tổng quát hóa (3.11)

❖ Chứng mình tổng quát hóa (xem Daskin)

KHDV 2016 – Chương 5 - Trang 38

P/trình cân bằng trạng thái ổn định

➢ Kết hợp phương trình

❖ Tổng quát hóa (3.11)

❖ Với điều kiện (3.13)

cho phép tính xác suất mọi trạng thái

➢ Tính toán các độ đo cốt lõi

số người trong hệ thống

số người đợi để được phục vụ

❖ và Trong đó s là số lượng các phục vụ

KHDV 2016 – Chương 5 - Trang 39

Cân bằng trạng thái ổn định

➢Hình 3.9 ➢ Hai phương trình (3.9), (3.10) trạng thái ổn định

❖ i , i là các tỷ lệ thông lượng chuyển trạng thái lên/xuống ❖ Tại trạng thái ổn định tỷ lệ ra khỏi vòng tròn = tỷ lệ vào

như phương trình trên đây

KHDV 2016 – Chương 5 - Trang 40

Cô lập trạng thái

➢Hình trái: Cô lập trạng thái: xác suất dòng vào, ra như nhau (xung quanh trạng thái j) ➢ Hình phải: Ở mọi điểm cắt

❖ Tốc độ mạng ở điểm cắt bất kỳ = 0 ❖ Công thức (3.14) tỷ lệ trái = tỷ lệ phải. ❖ Tính Pj+1 theo Pj lại trở về (3.12)

KHDV 2016 – Chương 5 - Trang 41

Ứng dụng của mô hình cơ bản

(3.11)

➢Công thức (3.11): trình bày mô hình cơ bản ❖ Áp dung cho một loạt bài toán hàng đợi Markov ❖ dòng xuất hiện: quá trình Poisson (có nghĩa là lần liên đoạn liên xuất hiện được phân bố mũ) với tốc độ  cho mỗi đơn vị thời gian

❖ thời gian phục vụ: các biến ngẫu nhiên độc lập, phân bố giống nhau, hàm mũ với tham số μ, hoặc thời gian phục vụ 1/μ.

KHDV 2016 – Chương 5 - Trang 42

Mô hình M/M/1

(3.11)

Hình 3.12. Sơ đồ chuyển trạng thái của hàng đợi M/M/1

(3.15)

= tốc độ sử dụng

KHDV 2016 – Chương 5 - Trang 43

Mô hình M/M/1

➢Tốc độ sử dụng

❖ Tốc độ sử dụng: cao bao nhiêu phục vụ được sử

dụng.

❖ Ví dụ văn phòng bác sĩ: tốc độ sử dụng được tính = tốc độ xuất hiện ( = 3 bệnh nhân mỗi giờ) lần thời gian phục vụ trung bình (theo giờ)

❖ Trường hợp t/gian dịch vụ trung bình là 15 phút = 0,25 giờ. Tốc độ sử dụng = 0,75 = 3 *0,25. Với bệnh nhân xuất hiện mỗi 20 phút (3/giờ) và thời gian phục vụ trung bình 15 phút: bác sĩ bận 75 % thời gian, tốc độ sử dụng.

KHDV 2016 – Chương 5 - Trang 44

Mô hình M/M/1

 <1, chúng ta có

(3.16)

xác suất trạng thái hàng đợi M/M/1

(3.17)

(3.18)

(3.19)

(3.20)

KHDV 2016 – Chương 5 - Trang 45

M/M/1: Thảo luận

➢Thảo luận

❖ Điều kiện  <1 để có (3.16)-(3.20) “điều kiện trạng thái tỷ lệ

ổn định” ~ “tỷ lệ xuất hiện phải nhỏ thua thực sự dịch vụ”

❖ Nếu  1 hàng đợi phát triển không giới hạn ! ❖ Các phương trình (3.17)-(3.20) tỷ lệ 1/(1- ). ❖ Khi  tiếp cận 1 thì thi hành rất tồi: đường cong tại hình vẽ. Hệ thống dịch vụ tốt <0.8, dịch vụ giảm dần 0.8<<0.9, giảm rất nhanh khi 0.9<.

KHDV 2016 – Chương 5 - Trang 46

M/M/1: Ví dụ

➢Trạm thu phí

❖ Tốc độ trung bình 360 xe (người)/giờ hoặc 1 xe/10 giây ❖ 300 xe/giờ (=5/6~0.833): trung bình 60 giây qua trạm ❖ Tăng thêm 10% (330 xe/giờ: 0.917): 2 phút qua trạm ❖ Tăng thêm 15% (345 xe/giờ: 0.958): 4 phút qua trạm.

Công dân khiếu nại?

KHDV 2016 – Chương 5 - Trang 47

M/M/1: Tính toán phương sai

➢Phương sai Var(N)

❖

và

❖ Như vậy

❖ = =

❖ Dẫn đến phương sai, độ lệch chuẩn tăng khi  gần 1.0

❖ Độ lêch chuẩn (cột 5) cao hơn đôi chút số khách trung

bình trong hệ thống (cột 3)

KHDV 2016 – Chương 5 - Trang 48

M/M/1: Xác suất lượng khách ở hệ thống

Hàm tạo thời điểm (Moment Generating Function: MGF)

KHDV 2016 – Chương 5 - Trang 49

M/M/1: Thời gian hệ thống

➢Hàm tạo thời điểm vô điều kiện của thời gian chờ

❖ Đây chỉ là MGF của phân bố mũ với tham số (1-). Hàng đợi M/M/1 FCFS, thời gian là phân bố siêu mũ

❖ có được

KHDV 2016 – Chương 5 - Trang 50

Ví dụ

➢Ví dụ trạm thu phí nhỏ (tiếp) ❖ 300 xe/giờ hay 5 xe/phút ❖ Bảng trước cho biết thời gian đợi 60 giây ❖ Bảng dưới cho thấy: 1/80.135 (1/90.113) xe ở hệ thống (phải đợi)  2 phút và 1/200.050 (1/25 0.041) xe ở hệ thống (phải đợi)  3 phút;

KHDV 2016 – Chương 5 - Trang 51

M/M/1: Thời gian chờ

KHDV 2016 – Chương 5 - Trang 52

M/M/1: Thời gian rời khỏi

➢Ví dụ trạm thu phí nhỏ

❖ Xác suất đợi 3 phút là 0.041: cứ 25 xe có một xe đợi

3 phút

❖ Nếu hệ thống rỗng: t/gian rời khỏi tiếp = t/gian xuất hiện tiếp theo (biến n/nhiên mũ kỳ vọng 1/)+ t/gian dịch vụ (biến n/nhiên mũ có kỳ vọng 1/ → MGF cho bắt đầu dịch vụ tiếp theo

gian chờ vượt quá w (với =300, =360):

❖ Hệ thống : tiếp 1/ và MGF là ❖ (Bảng 3.3) Xác suất thời gian trong hệ thống và thời

KHDV 2016 – Chương 5 - Trang 53

M/M/1: Rời khỏi tiếp (2)

➢MGF vô điều kiện thời gian rời khỏi tiếp

❖ Thời gian liên-rời khỏi

là hàm mũ hay quá trình rời

khỏi là Poison với kỳ vọng  tương tự như xuất hiện ❖ Không ngạc nhiên: Tốc độ xuất hiện trung bình = tốc độ rời trung bình “cái gì vào hàng đợi sau thời gian dài phải đi ra”

❖ Ngạc nhiên: Phân bố rời khỏi giống như phân bố quá

trình vào hàng đợi

KHDV 2016 – Chương 5 - Trang 54

M/M/1: Hàng đợi hữu hạn

➢Nhận xét

❖ Công thức L rất lộn xộn: L biến đổi quá theo M và  (tốc độ sử dụng) ❖ Bảng cho một số điểm quan trọng: ❖ Khi M tăng thì L tiếp cận như một M/M/1 vô hạn ❖ Không yêu cầu <1; khi >1 thì không áp dụng M/M/1 song vẫn tính

được cho hàng đợi hữu hạn

❖ Khi <1: tác động M không lớn; khi >1 ảnh hưởng M lớn

KHDV 2016 – Chương 5 - Trang 55

M/M/1 hữu hạn: 1

➢Tính W

❖ Tính W:cần tốc độ xuất hiện hiệu quả (effective arrival) ❖ Lưu ý: Khi số khách = M, mọi khách hàng mới bị bỏ đi

❖ Do đó

với 1

KHDV 2016 – Chương 5 - Trang 56

M/M/1 hữu hạn với =1

❖ Độ dài hàng đơi là M

KHDV 2016 – Chương 5 - Trang 57

M/M/1 hàng đợi hữu hạn: Nhận xét

➢Nhận xét hàng đợi cỡ hữu hạn

❖ Có sự cân bằng giữa: (i) tăng tỷ lệ khách xuất hiện được phục vụ (giảm số khách xuất hiện song không thấy cơ hội được phục vụ), và (ii) giảm t/gian đợi trung bình trong hệ thống

❖ Ví dụ, hệ thống điện thoại đơn gian tại văn phòng bác

sỹ: coi là M/M/1 với hàng đợi hữu hạn

một người và hai người có thể chờ

❖ “Hữu hạn” : số đường điện thoại tới văn phòng; ❖ ví dụ tiếp tân có 3 đường điện thoại: Tiếp tân thoại với

❖ Nếu có người thứ tư thì người đó nhận tín hiệu bận:

không thể vào hàng đợi

KHDV 2016 – Chương 5 - Trang 58

M/M/1 hữu hạn : minh họa cân bằng

➢Các tham số

❖ =0.45, =0.5 và =0.9 ❖ Tương ứng: tiếp tân thoại với bệnh nhân 2 phút và dòng xuất hiện

27 người/giờ ❖ Có thể 4/5 bác sỹ ❖ Tăng đường đt hoặc cực đại

lượng bác sỹ: thời gian trung bình

trong hệ thống tăng.

❖ Vì sao thêm đường dt: thời gian chờ dt của bệnh nhân tăng ? Nhiều

người có thể đợi tiếp tân và ít người bị loại

KHDV 2016 – Chương 5 - Trang 59

Hàng đợi M/M/s

➢Giới thiệu

❖ Hàng đợi đa phục vụ: s phục vụ giống hệt nhau ❖ Thời gian xuất hiện Poison, phục vụ mũ ❖ Có hai cách hàng đợi cho hệ thống này ▪ (i) cách 1: khách hàng ở hàng đợi ứng với mỗi phục vụ và ở đó từ xuất hiện tới hoàn tất. Các quầy thanh toán ở các siêu thị. Tập s hàng đợi với xuất hiện /s ▪ (ii) cách 2 (quan tâm): chỉ một hàng đợi và người đợi ở đầu hàng được phục vụ khi có phục vụ rỗi tiếp theo. Cách hoạt động check-in của hãng hàng không

KHDV 2016 – Chương 5 - Trang 60

M/M/s: Sơ đồ chuyển trạng thái

Đưa về dạng chuẩn (3.11)

(3.23)

Với điều kiện trạng thái ổn định

Và nhận được

(3.24)

KHDV 2016 – Chương 5 - Trang 61

M/M/s: các tham số đầu ra

➢Nhận xét

s+1…

❖ (3.24): tg đợi trung bình Lq dễ nhận hơn so với L ❖ L yêu cầu hai dạng xác suất trạng thái (3.23): 0-s và

❖ Lq : chỉ cần sử dụng dạng thứ hai. ❖ Có Lq: theo (3.2)-(3.4):

để tính ba tham số còn lại.

→

(3.16)

→

(3.20)

❖ Giả sử cho s=1, có

KHDV 2016 – Chương 5 - Trang 62

M/M/s: Minh họa

➢Hàng đợi check-in hàng không

❖ S=6 quầy check-in,

t/gian phục vụ tb =0.5 (1/= 2 phút): mỗi quầy phục vụ trung bình 30 khách trong một giờ

❖ Với 6 phục vụ: đòi hỏi <1:   <180=30*6 ❖ Bảng minh họa hiệu năng hệ thống: t/gian trung bình và t/gian đợi trung bình là hàm của tốc độ phục vụ /(s)

KHDV 2016 – Chương 5 - Trang 63

M/M/s: Minh họa

KHDV 2016 – Chương 5 - Trang 64

M/M/s ví dụ: nhận xét

➢Một số nhận xét

❖ Bảng cho thấy t/gian ở hệ thống (L) luôn hơn t/gian

đợi (Lq) 2 phút

❖ Tỷ lệ sử dụng  0.8: t/gian đợi là rất nhỏ ❖ Khi tăng tỷ lệ lên quá 0.8 thì t/gian đợi tăng đột biến ❖ =0.8: t/gian đợi < 1 phút ❖ =0.9 (thêm 18 người/giờ): t/gian đợi thêm 2.5 phút ❖ =0.95 (+ 9 người nữa/giờ): t/gian đợi thêm 5.75 phút ❖ =0.99: thời gian đợi xấp xỉ nửa tiếng

KHDV 2016 – Chương 5 - Trang 65

M/M/s: thêm quầy check-in (tăng s)

➢ Giả sử tốc độ vào 175 người giờ

❖ =175/180 = 0.9722 ❖ Bảng cho hiệu năng hệ thống khi thêm quầy check-in ❖ Khi bổ sung quầy: giảm thời gian đợi rất nhanh và chỉ

cần bổ sung một quầy (s=7)

KHDV 2016 – Chương 5 - Trang 66

M/M/s: Xác suất đợi

➢Tính toán

❖ Xác suất phải đợi: mọi quầy check-in đều bận

❖ Nếu một khách xuất hiện nhìn thấy n+s người trong hệ thống: khách phải đợi n+1 người hoàn tất dịch vụ (có 01 phục vụ rỗi) ❖ T/gian giữa các thời điểm hoàn tất dịch vụ là phân bố mũ theo tham số s, hàm tạo thời điểm khách hàng được phục vụ khi khách hàng xuất hiện có n+s người ở hệ thống. Tạo thời điểm

KHDV 2016 – Chương 5 - Trang 67

M/M/s: Xác suất đợi

➢Nhận xét

❖ Biểu diễn trên: hàm tạo thời điểm của một phân bố mũ

với tham số s-  phân bố t/gian đợi M/M/s:

(3.25)

❖ Kết hợp hàm khối lượng SX và hàm mật độ SX ❖ Lập bảng xác suất thời gian đợi với =175,1/=2,s=6

KHDV 2016 – Chương 5 - Trang 68

M/M/s sánh với M/M/1

➢M/M/s với  và M/M/1 với /s

vụ một hàng đợi riêng

❖ Câu hỏi: hàng đợi chung cho s phục vụ có tốt hơn s phục

❖ Trong mọi trường hợp hiệu năng M/M/s tốt hơn s M/M/1 ❖ Tăng tốc độ xuất hiện: thời gian đợi tăng lên ❖ Với 0.972: lượng khách trong M/M/s (38.2) nhiều hơn M/M/1 (35) song khách chỉ đợi 11.1 phút so với 70 phút.

KHDV 2016 – Chương 5 - Trang 69

M/M/s đối sánh M/M/1

➢Tiếp tục

❖ Như trên: Hiệu năng M/M/s tốt hơn ❖ loại bỏ tâm lý cho khách hàng: “hàng nhanh hàng chậm”: Loại bỏ

bất bình đẳng: người đến sau được phục vụ trước

❖ Ứng dụng rộng rãi trong hoạt động check-in các hãng hàng không, kiểm tra an ninh sân bay, xử lý xuất nhập cảnh tại sân bay, dòng đợi tại các khu vui chơi giải trí, và v.v..

KHDV 2016 – Chương 5 - Trang 70

M/M/s: Tính xấp xỉ hiệu năng

➢Xác suất cho trạng thái rỗng

❖ Công thức tính toán M/M/s là kết hợp “phức tạp” ❖ Công thức tính Po ❖ Tính hiệu năng (với =/(s))

❖ Công thức xấp xỉ tốt, ví dụ ❖ M/M/5 với λ = 500 xuất hiện mỗi giờ và 1/=30 giây (hoặc 1/=30/3600 =1/120 giờ). t/gian đợi trong hàng đợi: C/xác 22.4 s; xấp xỉ 23.0 s

❖ M/M/9 tốc độ xuất hiện gấp đôi, cx 34.2 giây, xx 34.4 s

KHDV 2016 – Chương 5 - Trang 71

M/M/

➢Giới thiệu

❖ Xuất hiện Poison, phục vụ mũ, “vô hạn” phục vụ ❖ “tự phục vụ” ❖ Ví dụ: internet băng thông tốc độ cao “phục vụ tức thì” ❖ Ví dụ: “cứu hỏa” ❖ Sơ đồ chuyển trạng thái

❖ Các tốc độ: λn = λ; n = n ❖ Thay thế vào (3.11) có ❖ Kết hợp điều kiện chuẩn nhận được

(3.27)

KHDV 2016 – Chương 5 - Trang 72

M/M/: Các kết quả đầu ra

➢Tính các đầu ra

❖ Công thức (3.27) cho phân bố Poison tham số λ/μ

(3.28)

bình

❖ T/gian ở hệ thống trung bình  t/gian phục vụ trung

❖ Wq = W-1/, t/gian đợi dịch vụ trung bình là 0 ❖ Tương tự: Lq = 0. ❖ phân bố trạng thái ổn định của khách hàng ở hàng đợi M/G/: phân bố t/gian phục vụ trung bình 1/μ và phương sai hữu hạn, cũng theo (3.27) và lượng trung bình trong hệ thống theo (3.28).

KHDV 2016 – Chương 5 - Trang 73

M/M/s không đợi

➢Giới thiệu

❖ Mô hình M/M/s không có hàng đợi ▪ Ví dụ: bãi đậu xe, không có chỗ đợi cho xe vào bãi ▪ Trung tâm cuộc gọi nhỏ: lượng phục vụ = lượng dòng

điện thoại, điện thoại bận khi dòng dùng hết

❖ Sơ đồ chuyển trạng thái

(3.29)

(3.30)

 = λ/μ

(3.32) Công thức Erlang thiếu

❖ Các tốc độ ❖ (3.29)+(3.11) có ❖ Nhận được

KHDV 2016 – Chương 5 - Trang 74

M/M/s không đợi: các đầu ra

➢Các giá trị đầu ra

❖ Tính toán tốc độ xuất hiện hiệu quả

❖ Ví dụ bãi đậu xe nhỏ 10 chỗ, lần đậu trung bình 2 giờ

❖ Kết quả là: (3.35)

(= 0.5)

❖ 1/=E(thời gian phục vụ)

KHDV 2016 – Chương 5 - Trang 75

H/đợi không Markov: k/quả quan trọng

➢Giới thiệu

❖ Xuất hiện Poison / mũ (liên xuất hiện): giả thiết phù hợp ❖ Quá trình phục vụ: Thường không phân bố mũ ! ❖ Phục vụ có nhớ: Phẫu thuật thường 90’, bệnh nhân đang

❖ Phân bố mũ có hệ số biến thiên cao, dịch vụ thông

phẫu thuật 105’ → phẫu thuật kết thúc sớm

thường không thể như vậy

(3.37)

❖ Hàng đợi M/G/1 có =E(S), E(S)= 1/ ❖ Với là t/gian dịch vụ kỳ vọng, σ2 là

phương sai của phân bố t/gian dịch vụ.

❖ Ở đây, giả thiết <1.

KHDV 2016 – Chương 5 - Trang 76

M/G/1

➢Một số kết quả tính toán

❖ Thời gian đợi trước dịch vụ

(3.38)

❖ Với M/D/1 có σ2 =0 và có

❖ Với M/M/1 có σ2 =1/2 cho nên

❖ t/gian đợi ở hàng đợi cho hệ thống phục vụ đơn với t/gian phục vụ xác định là chính xác một nửa t/gian đợi trong hàng đợi cho một hệ thống tương tự với t/gian dịch vụ phân bố mũ

❖ t/gian phục vụ bị thiệt hại.

KHDV 2016 – Chương 5 - Trang 77

M/Ek/1

➢Tính giá trị đầu ra

❖ Phương sai

(3.39)

❖ T/gian đợi trước khi phục vụ giảm khi hoặc k tăng hoặc t/gian phục vụ nên nhỏ hơn và biến đổi nhỏ hơn ❖ Khi k → : phân bố t/gian phục vụ tiếp cận phân bố

xác định.

KHDV 2016 – Chương 5 - Trang 78

Phân luồng đường theo hàng đợi

➢Giới thiệu

❖ Giao thông Hà Nội: Hiện trạng ❖ Một vài “đề xuất giải pháp” ➢ Tiếp cận lý thuyết hang đợi

Trước BRT Sau BRT 2 2

1 1  

0.95 0.05 0.67 0.33

❖ Xác định bài toán: ❖ Số lượng phục vụ ? ❖ Số lượng hàng đợi ? ❖ Quá trình xuất hiện ? ❖ Quá trình dịch vụ ? ❖ Các ràng buộc liên quan ? Trong nhiều giờ trong ngày tốc độ xuất hiện thực sự từ 0.8  - 1.2. Phân tích tình trạng trước và sau BRT, vấn đề sau BRT và đề xuất giải pháp.