Bài giảng Khoa học dịch vụ - Chương 5: Hàng đợi

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

➢ 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ụ

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

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

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

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

❖ 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ỹ.

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

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

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

cộng cần 4160 lô .

❖ Tuy nhiên, xá c suất tí ch hợp 0.98²⁰= 0.667. Cần 0.98 cho

cả 20 vùng thì mỗi vùng e^ln(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” ²(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” c_X= (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ố

nhất

và xá c suất để X_ilà nhỏ

i=1, 2, …, n.

KHDV 2016 – Chương 5 - Trang 15

Phân bố Erlang

➢Phâ n bố Erlang

❖ 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/.

❖ Ký hiệu E_k() hoặc E_k.

❖ 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

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

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

❖ Một biến ngẫu nhiên có phâ n bố xá c suất E_k-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:

❖ 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

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

❖ Đâ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-p_nvà nó đi tới pha tiếp

theo với xá c suất p_n. Rõ ràng p_k=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 p_nlà 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 p_i(i=1,2, …, k) là

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

❖ Ký hiệu X là H_k(p₁, …, p_k; ₁, …, _k) hoặc H_k.

❖ Hàm mật độ và kỳ vọng

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

❖ Sơ đồ pha

KHDV 2016 – Chương 5 - Trang 20

Bài giảng Khoa học dịch vụ - Chương 5: Hàng đợi - Hà Quang Thụy