Bài giảng Khoa học dịch vụ - Chương 5: Hàng đợi - Hà Quang Thụy

2016 – Chương 5 - Trang 36
➢  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 phép xếp hàng
❖ Trung tâm chỉnh sửa thiết bị hàng không
Phương trình Chapman-Kolmogorov
KHDV 2016 – Chương 5 - Trang 37
➢ 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.
❖ “hệ thống được giả định hoạt động vô thời hạn thời gian”:
tương đối hợp lý trong thực tế
❖ “hệ thống loại trừ việc “ngừng dịch vụ” vào cuối ngày”: khi
đó 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
❖ (3.9)
❖ (3.10)
❖ Giải (3.9) với P1 theo Po , có
P/trình cân bằng trạng thái ổn định
KHDV 2016 – Chương 5 - Trang 38
➢ 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)
P/trình cân bằng trạng thái ổn định
KHDV 2016 – Chương 5 - Trang 39
➢ 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 phép tính xác suất mọi trạng thái
➢ Tính toán các độ đo cốt lõi
❖ và
Trong đó s là số lượng các phục vụ
P/trình cân bằng trạng thái ổn định
số người đợi để được phục vụ
số người trong hệ thống
KHDV 2016 – Chương 5 - Trang 40
➢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
Cân bằng trạng thái ổn định
KHDV 2016 – Chương 5 - Trang 41
➢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)
Cô lập trạng thái
KHDV 2016 – Chương 5 - Trang 42
➢Công thức (3.11): trình bày mô hình cơ bản
❖ Áp dung cho một loạt bài toán hàng đợi Markov
❖ dò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/μ.
Ứng dụng của mô hình cơ bản
(3.11)
KHDV 2016 – Chương 5 - Trang 43
Mô hình M/M/1
(3.11)
(3.15)
= tốc độ sử dụng
Hình 3.12. Sơ đồ chuyển trạng thái của hàng đợi M/M/1
KHDV 2016 – Chương 5 - Trang 44
Mô hì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 45
Mô hình M/M/1
 <1, chúng ta có
(3.16)
xác suất trạng thái hàng đợi M/M/1
(3.17)
(3.18)
(3.19)
(3.20)
KHDV 2016 – Chương 5 - Trang 46
M/M/1: Thả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
ổn định” ~ “tỷ lệ xuất hiện phải nhỏ thua thực sự tỷ lệ
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 thì thi hành rất tồi: đường cong tại
hình vẽ. 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 47
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 48
M/M/1: Tính toán phương sai
➢Phương sai Var(N)
❖ và
❖ 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 49
M/M/1: Xác suất lượng khách ở hệ thống
Hàm tạo thời điểm (Moment Generating Function: MGF) 
KHDV 2016 – Chương 5 - Trang 50
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 51
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 và 1/20 0.050 (1/25 0.041)
xe ở hệ thống (phải đợi) 3 phút;
KHDV 2016 – Chương 5 - Trang 52
M/M/1: Thời gian chờ
KHDV 2016 – Chương 5 - Trang 53
M/M/1: Thời gian rời khỏi
➢Ví dụ trạm thu phí nhỏ
❖ 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 khỏi tiếp = t/gian xuất
hiện tiếp theo (biến n/nhiên mũ kỳ vọng 1/)+ t/gian
dịch vụ (biến n/nhiên mũ có kỳ vọng 1/ → MGF cho
bắt đầu dịch vụ tiếp theo
❖ Hệ thống : tiếp 1/ và MGF là
❖ (Bảng 3.3) Xác suất thời gian trong hệ thống và thời
gian chờ vượt quá w (với =300, =360):
KHDV 2016 – Chương 5 - Trang 54
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 kỳ 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 gì 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 55
M/M/1: Hàng đợi hữu hạn
➢Nhận xé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 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 ảnh hưởng M lớn
KHDV 2016 – Chương 5 - Trang 56
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ị bỏ đi
❖ Do đó với 1
KHDV 2016 – Chương 5 - Trang 57
M/M/1 hữu hạn với =1
❖ Độ dài hàng đơi là M
KHDV 2016 – Chương 5 - Trang 58
M/M/1 hàng đợi hữu hạn: Nhận xét
➢Nhận xé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ụ), và (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
sỹ: coi là M/M/1 với hàng đợi hữu hạn
❖ “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
một người và hai người có thể chờ
❖ Nếu có người thứ tư thì người đó nhận tín hiệu bận:
không thể vào hàng đợi
KHDV 2016 – Chương 5 - Trang 59
M/M/1 hữu hạn : minh họa cân bằng
➢Các tham số
❖ =0.45, =0.5 và =0.9
❖ Tương ứng: tiếp tân thoại với bệnh nhân 2 phút và dòng xuất hiện
27 người/giờ
❖ Có thể 4/5 bác sỹ
❖ Tăng đường đt hoặc cực đại lượng bác sỹ: 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 và ít người bị loại
KHDV 2016 – Chương 5 - Trang 60
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. Các quầy thanh
toán ở các siêu thị. 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 61
M/M/s: Sơ đồ chuyển trạng thái
Đưa về dạng chuẩn (3.11)
Với điều kiện trạng thái ổn định
Và nhận được
(3.24)
(3.23)
KHDV 2016 – Chương 5 - Trang 62
M/M/s: các tham số đầu ra
➢Nhận xét
❖ (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 và
s+1
❖ 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.
❖ Giả sử cho s=1, có
→
→
(3.16)
(3.20)
KHDV 2016 – Chương 5 - Trang 63
M/M/s: Minh họ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 và t/gian đợi trung bình là hàm của tốc độ
phục vụ /(s)
KHDV 2016 – Chương 5 - Trang 64
M/M/s: Minh họa
KHDV 2016 – Chương 5 - Trang 65
M/M/s ví dụ: nhận xét
➢Một số nhận xé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 nhỏ
❖ Khi tăng tỷ lệ lên quá 0.8 thì 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 phút
❖ =0.95 (+ 9 người nữa/giờ): t/gian đợi thêm 5.75 phút
❖ =0.99: thời gian đợi xấp xỉ nửa tiếng
KHDV 2016 – Chương 5 - Trang 66
M/M/s: thêm quầy check-in (tăng s)
➢ Giả 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 67
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 68
M/M/s: Xác suất đợi
➢Nhận xé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:
❖ Kết hợp hàm khối lượng SX và hàm mật độ SX
❖ Lập bảng xác suất thời gian đợi với =175,1/=2,s=6
(3.25)
KHDV 2016 – Chương 5 - Trang 69
M/M/s sánh với M/M/1
➢M/M/s với  và M/M/1 với /s
❖ Câu hỏi: hàng đợi chung cho s phục vụ có tốt hơn s phục
vụ một hàng đợi riêng
❖ 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 70
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 bỏ tâm lý cho khách hàng: “hàng nhanh hàng chậm”: Loại bỏ
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ử lý xuất nhập cảnh tại sân bay, dòng đợi tại
các khu vui chơi giải trí, và v.v..
KHDV 2016 – Chương 5 - Trang 71
M/M/s: Tính xấp xỉ 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 xỉ 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 xỉ 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 72
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 thì”
❖ 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 73
M/M/ : Các kết quả đầu ra
➢Tính các đầu ra
❖ Công thức (3.27) cho phân bố Poison tham số λ/μ
❖ T/gian ở hệ thống trung bình  t/gian phục vụ trung
bình
❖ 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).
(3.28)
KHDV 2016 – Chương 5 - Trang 74
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 nhỏ: lượng phục vụ = lượng dòng
điện thoại, điện thoại bận khi dòng dùng hết
❖ Sơ đồ chuyển trạng thái
❖ Các tốc độ
❖ (3.29)+(3.11) có (3.30)
❖ Nhận được
(3.29)
 = λ/μ
(3.32) Công thức Erlang thiếu
KHDV 2016 – Chương 5 - Trang 75
M/M/s không đợi: các đầu ra
➢Các giá trị đầu ra
❖ Tính toán tốc độ xuất hiện hiệu quả
❖ Kết quả là: (3.35)
❖ Ví dụ bãi đậu xe nhỏ 10 chỗ, lần đậu trung bình 2 giờ
(= 0.5)
❖ 1/=E(thời gian phục vụ)
KHDV 2016 – Chương 5 - Trang 76
H/đợi không Markov: k/quả quan trọng
➢Giới thiệu
❖ Xuất hiện Poison / mũ (liên xuất hiện): giả thiết phù 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ẫu thuật 105’ → phẫu thuật kết thúc sớm
❖ Phân bố mũ có hệ số biến thiên cao, dịch vụ thông
thường không thể như vậy
❖ Hàng đợi M/G/1 có
❖ Với là t/gian dịch vụ kỳ vọng, σ2 là
phương sai của phân bố t/gian dịch vụ.
❖ Ở đây, giả thiết <1.
 =E(S), E(S)= 1/
(3.37)
KHDV 2016 – Chương 5 - Trang 77
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/M/1 có σ2 =1/2 cho nên
❖ Với M/D/1 có σ2 =0 và có
❖ 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 78
M/Ek/1
➢Tính giá trị đầu ra
❖ Phương sai
❖ 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 nhỏ hơn và biến đổi nhỏ hơn
❖ Khi k → : phân bố t/gian phục vụ tiếp cận phân bố
xác định.
(3.39)
KHDV 2016 – Chương 5 - Trang 79
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
❖ Xác định bài toán: Trước BRT Sau BRT
❖ Số lượng phục vụ ? 1 2
❖ Số lượng hàng đợi ? 1 2
❖ Quá trình xuất hiện ?  0.95 0.05
❖ Quá trình dịch vụ ?  0.67 0.33
❖ 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.