Lý thuyết xếp hàng

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

——————————

LÊ THỊ TUYÊN

LÝ THUYẾT XẾP HÀNG

Chuyên ngành: Toán Giải Tích

Mã số: 8460102

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2019

Công trình được hoàn thành tại

Trường Đại học Sư phạm - ĐHĐN

Người hướng dẫn khoa học: PGS.TS. HUỲNH THẾ PHÙNG

Phản biện 1: TS. LƯƠNG QUỐC TUYỂN

Phản biện 2: PGS.TS. NGUYỄN NHỤY

Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ Khoa học họp tại Trường Đại học Sư phạm - ĐHĐN vào ngày

12 tháng 05 năm 2019.

Có thể tìm hiểu luận văn tại

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Hàng đợi là một phần của cuộc sống hàng ngày. Chúng ta phải đứng chờ

tại quầy thu tiền ở siêu thị, chờ để mua vé xem phim, mua vé xe, vé tàu, rút

tiền tại các trạm ATM, lấy thức uống trong quán cà phê, đứng chờ mua xăng

tại trạm xăng, chờ được xử lý tại phòng cấp cứu, máy bay chờ được cất cánh,

hạ cánh, tàu thuỷ chờ được bốc, dỡ hàng hoá tại cảng. . . Trong những mô

hình phục vụ như trên, các khách hàng phải dùng chung tài nguyên, phải chờ

để được phục vụ và đôi khi bị từ chối phục vụ. Trong mọi tình huống, thời

gian chờ là điều mà chúng ta không muốn. Chúng ta phải xác định những

cách để tính thời gian chờ trong giới hạn cho phép. Tất cả các ví dụ trên đã

và đang được nghiên cứu nhờ sử dụng một lý thuyết toán học của các hàng

đợi có tên là lý thuyết xếp hàng (hay lý thuyết phục vụ đám đông).

Lý thuyết xếp hàng liên quan đến nghiên cứu toán học của các hàng đợi

hoặc các dòng chờ. Sự hình thành các hàng đợi là một hiện tượng phổ biến

xảy ra bất cứ khi nào nhu cầu được phục vụ vượt quá khả năng hiện tại để

cung cấp dịch vụ đó. Các quyết định liên quan đến số lượng, khả năng cung

cấp dịch vụ phải được thực hiện thường xuyên. Tuy nhiên, vì thường không

thể dự đoán chính xác khi nào các đơn vị đến để tìm dịch vụ và việc tính

toán cần bao nhiêu thời gian để cung cấp dịch vụ đó thường rất khó. Cung

cấp nhiều đơn vị phục vụ sẽ dẫn đến chi phí quá cao. Ngược lại, nếu không

cung cấp đủ đơn vị phục vụ khiến cho thời gian chờ đợi trở nên quá lâu, mà

điều đó cũng dẫn đến tốn kém theo nhiều nghĩa. Do đó, mục đích cuối cùng

là đạt được một sự cân bằng kinh tế giữa chi phí dịch vụ và chi phí liên quan

đến việc chờ đợi dịch vụ đó. Lý thuyết xếp hàng không giải quyết vấn đề này

một cách trực tiếp; tuy nhiên, nó đóng góp thông tin quan trọng cần thiết

bằng cách dự đoán các đặc tính khác nhau của hàng đợi. Lý thuyết xếp hàng

xác định và tìm các phương án tối ưu để hệ thống phục vụ tốt nhất trên cơ

sở việc xác định được các số đo hiệu năng của các hàng xếp. Ngày nay lý

thuyết xếp hàng còn có nhiều ứng dụng trong các lĩnh vực khác nhau như

mạng máy tính, quản lý xí nghiệp. Ngoài ra lý thuyết xếp hàng cũng còn là

2

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.

Với các ứng dụng thực tiễn như trên, lý thuyết xếp hàng thực sự rất cần

thiết trong mọi lĩnh vực của đời sống xã hội. Vì vậy, được sự đồng ý hướng

dẫn của PGS.TS. Huỳnh Thế Phùng, em chọn đề tài: “LÝ THUYẾT XẾP

HÀNG” cho luận văn thạc sĩ của mình.

2. Mục tiêu của đề tài

Nghiên cứu một số mô hình cơ bản của Lý thuyết xếp hàng thông qua

các quá trình sinh tử khác nhau. Từ đó đề xuất các giải pháp làm cân bằng

giữa chi phí phục vụ và chi phí gây ra do thời gian chờ đợi.

3. Phương pháp nghiên cứu

Luận văn được nghiên cứu dựa trên các phương pháp:

- Nghiên cứu các tài liệu liên quan đến đề tài, bao gồm các tài liệu kinh

điển, tổng hợp và trình bày báo cáo tổng quan.

- Tham khảo, trao đổi với cán bộ hướng dẫn.

4. Đóng góp của đề tài

- Tổng hợp tài liệu để có một báo cáo tổng quan khá đầy đủ về Lý

Thuyết Xếp Hàng cùng các ứng dụng bằng số đối với các mô hình cụ thể.

- Bổ sung các ví dụ, hình ảnh và các chứng minh chi tiết.

5. Cấu trúc luận văn

Ngoài phần mở đầu và kết luận, tài liệu tham khảo, luận văn gồm ba

chương:

- Chương 1: Một số phân phối xác suất cơ bản. Chương này trình bày

sơ lược một số khái niệm và vấn đề liên quan đến xác suất để làm cơ sở cho

chương sau.

- Chương 2: Mô hình xếp hàng cơ bản. Chương này trình bày một số

khái niệm, ký hiệu và ví dụ về Mô hình xếp hàng.

- Chương 3: Mô hình xếp hàng dựa trên quá trình sinh tử. Chương này

là nội dung chính của luận văn, trình bày một số Mô hình xếp hàng cơ bản.

3

CHƯƠNG 1

MỘT SỐ PHÂN PHỐI XÁC SUẤT CƠ BẢN

1.1. PHÂN PHỐI CHUẨN VÀ PHÂN PHỐI NHỊ THỨC

1.1.1. Phân phối chuẩn

Định nghĩa 1.1.1. [1] Biến ngẫu nhiên liên tục X được gọi là có phân phối

chuẩn với tham số µ và σ (−∞ < µ < ∞ và σ > 0) kí hiệu X ∼ N(µ, σ2

)

nếu hàm mật độ xác suất của nó có dạng:

f(x) = 1

σ

√

2π

e

−

(x − µ)

2

2σ

2

, x ∈ R.

Các tham số đặc trưng

- Kỳ vọng toán:E(X) = µ

- Phương sai:V ar(X) = σ

2

.

1.1.2. Phân phối nhị thức

Định nghĩa 1.1.2. [1] Biến ngẫu nhiên rời rạc X được gọi là có phân phối

Bernoulli với tham số p (0 < p < 1) kí hiệu X ∼ Ber(p) nếu hàm xác suất:

p(x; p) = p

x

(1 − p)

1−x

, x ∈ {0, 1}.

Các tham số đặc trưng:

- Kỳ vọng:E(X) = p

1

(1 − p)

0 = p.

- Phương sai: V ar(X) = E(X2

) − E(X)

2 = p − p

2 = p(1 − p).

Định nghĩa 1.1.3. [1] Biến ngẫu nhiên rời rạc X được gọi là có phân phối

theo quy luật nhị thức với tham số n và p (n ∈ N\0, 0 < p < 1) kí hiệu

X ∼ B(n, p) nếu X có hàm xác suất:

p(x; n, p) = C

x

n

p

x

(1 − p)

n−x

, x ∈ 0, 1, 2, ..., n.

Các tham số đặc trưng:

- Kỳ vọng:E(X) = np.

- Phương sai:V ar(X) = np(1 − p).

4

1.2. PHÂN PHỐI POISSON VÀ PHÂN PHỐI MŨ

1.2.1. Phân phối Poisson

Định nghĩa 1.2.1. [1] Biến ngẫu nhiên rời rạc X được gọi là phân phối

Poisson với tham số λ (λ > 0) kí hiệu X ∼ P(λ) nếu tập giá trị của X là

Ω(X) = N = {0, 1, 2, . . .} có hàm xác suất:

p(x; λ) = px =

e

−λλ

x

x!

, x ∈ N.

Các tham số đặc trưng:

- Kỳ vọng: E(X) = λ.

- Phương sai: V ar(X) = λ.

Phân phối Poisson là dạng giới hạn của phân phối nhị thức:

Cho X là biến ngẫu nhiên nhị thức với phân phối xác suất p(x; n, p).

Khi n → +∞, p → 0 và np là hằng số λ, thì p(x; n, p) → p(x; λ).

Thật vậy:

lim

n→∞

p(x; n, p) = lim

n→∞

C

x

n

p

x

(1 − p)

n−x

= lim

n→∞

n!

x!(n − x)!(

λ

n

)

x

.(1 −

λ

n

)

n−x

=

λ

x

x!

lim

n→∞

n!

x!(n − x)!.(1 −

λ

n

)

n

.

1

(1 −

λ

n

)

x

=

λ

x

x!

.e−λ

= p(x, λ).

1.2.2. Phân phối mũ

Định nghĩa 1.2.2. [1] Biến ngẫu nhiên liên tục X được gọi là phân phối

mũ, kí hiệu X ∼ E(λ) nếu X có hàm mật độ xác suất:

f(x, λ) = λe−λx, x > 0

Các tham số đặc trưng:

-Kỳ vọng: E(X) = 1

λ

.

-Phương sai:V ar(X) = 1

λ

2

.

5

1.3. PHÂN PHỐI ERLANG

Định nghĩa 1.3.1. [1] Biến ngẫu nhiên X được gọi là có phân phối Erlang,

kí hiệu Ek với tham số µ và k nếu X là tổng của k biến ngẫu nhiên độc lập

có cùng phân phối mũ với tham số kµ có hàm mật độ:

f(x) = x

k−1

(µk)

k

(k − 1)!e

−kµx, x > 0

.

Khi đó: E(X) = 1

µ

.

6

CHƯƠNG 2

MÔ HÌNH XẾP HÀNG CƠ BẢN

2.1. CẤU TRÚC CƠ BẢN CỦA MÔ HÌNH XẾP HÀNG [3]

2.1.1. Các dạng xếp hàng

Trong cuộc sống hằng ngày, chúng ta thường gặp các trường hợp đứng

chờ để mua vé tàu, vé xe, vé xem phim; chờ được phục vụ tại các nhà hàng,

quán cafe, quầy thức ăn nhanh; xe ô tô trên các xa lộ thu phí; các bệnh nhân

chờ tại phòng cấp cứu của bệnh viện; tàu chờ bốc hàng tại cảng; chờ giao

dịch tại các ngân hàng; ...các trường hợp đó được gọi là các dạng xếp hàng.

Tất cả các trường hợp trên đã và đang được nghiên cứu nhờ sử dụng

một lý thuyết toán học của các hàng đợi có tên là lý thuyết xếp hàng (hay

lý thuyết phục vụ đám đông).

Hình 2.1: Mô hình xếp hàng cơ bản

2.1.2. Các khái niệm cơ bản

Dòng khách hàng đến hệ thống (dòng vào): Là dòng các đối tượng đi

đến hệ thống và đòi hỏi được thoả mãn nhu cầu nào đó. Dòng khách hàng

đến hệ thống là dòng biến cố ngẫu nhiên và tuân theo những phân phối xác

suất như: Phân phối Poisson, phân phối Erlang,. . .

Trạng thái của hệ thống: Là số khách hàng trong hệ thống (bao gồm cả

các khách hàng đang được phục vụ và các khách hàng đang chờ được phục

vụ).

7

Dòng khách hàng chờ phục vụ (hàng chờ): Là tập hợp các khách hàng

sắp xếp theo một trật tự nào đó để chờ được phục vụ. (Tuy nhiên, trong

thực tế cũng có những hệ thống không có hàng chờ).

Chiều dài hàng đợi: Là số khách hàng chờ được phục vụ bằng trạng thái

hệ thống trừ cho số khách hàng đang được phục vụ.

Đơn vị phục vụ: Là những thiết bị, con người hoặc tổ hợp các thiết bị

và con người mà hệ thống sử dụng để phục vụ các khách hàng đến hệ thống.

Thời gian phục vụ: Là thời gian ít nhất mỗi đơn vị phục vụ phải tiêu

hao để phục vụ xong một khách hàng và nó là một đại lượng ngẫu nhiên

tuân theo một qui luật phân phối xác suất nhất định (thường là phân phối

mũ).

Dòng khách hàng đi ra khỏi hệ thống (yêu cầu đã được phục vụ): Là

dòng các khách hàng đi ra khỏi hệ thống, gồm các khách hàng đã được phục

vụ và các khách hàng bị từ chối. Nếu dòng vào là dòng tối giản thì dòng phục

vụ tại mỗi đơn vị phục vụ sẽ là dòng xấp xỉ tối giản.

Nguyên tắc phục vụ của hệ thống: Nó cho biết cách thức khách hàng

được nhận vào và phân bố các khách hàng vào các đơn vị phục vụ. Ngoài

ra nó cũng cho biết trường hợp nào yêu cầu bị từ chối hoặc phải chờ và giới

hạn cho phép của hàng chờ hoặc giới hạn của thời gian chờ.

2.1.3. Các ký hiệu

− Các thuật ngữ:

+ N(t): trạng thái hệ thống tại thời điểm t ≥ 0.

+ Pn(t): xác suất có đúng n khách hàng trong hệ thống tại t ≥ 0.

+ s: số đơn vị được phục vụ (số quầy phục vụ).

+ λn: tốc độ đến trung bình khi có n khách hàng trong hệ thống. Thông

thường λn = λ, ∀n (tốc độ trung bình không phụ thuộc vào trạng thái hệ

thống). 1

λ

là thời gian trung bình giữa hai lần đến của khách hàng. λ không

phụ thuộc vào s.

+ µn: tốc độ phục vụ trung bình khi có n khách hàng trong hệ thống.

Thông thường tốc độ phục vụ trung bình tại một quầy là µ đơn vị thời gian.

µn có phụ thuộc vào s.Lúc đó tốc độ phục vụ trung bình của hệ thống là:

8

µn =







nµ, n ≤ s

sµ, n > s

µn có phụ thuộc vào s.

Hình 2.2: Một số hệ thống xếp hàng cơ bản

+ L: số lượng khách hàng kỳ vọng trong hệ thống xếp hàng =

P

∞

n=0

nPn.

+ Lq: chiều dài hàng đợi ( không bao gồm khách hàng đang được phục

vụ) =

P

∞

n=s

(n − s)Pn.

+ W: thời gian chờ đợi trong hệ thống (bao gồm thời gian phục vụ) cho

từng khách hàng.

+ Wq: thời gian chờ đợi trong hệ thống (không bao gồm thời gian phục

vụ) cho từng khách hàng.

− Mối liên hệ giữa L, W, Lq, Wq.

Giả sử λn = λ với mọi n. Ta có:

L = λW.

Lq = λW q.

Nếu λn không bằng nhau, λ có thể thay thế bằng λ trong các phương

trình.Giả sử thời gian phục vụ trung bình là một hằng số, 1

µ

với mọi n ≥ 1.

Do đó:

W = Wq +

1

µ

.

9

2.2. MỘT SỐ VÍ DỤ CỤ THỂ VỀ MÔ HÌNH XẾP HÀNG

Trong các hệ thống phục vụ như: Bến cảng, khách sạn, nhà hàng, trạm

điện thoại, cửa hàng bán xăng dầu...thường diễn ra 2 quá trình: Quá trình

nảy sinh các yêu cầu và quá trình phục vụ các yêu cầu.

Các ví dụ:

1. Các hệ thống điện thoại: khi số lượng lớn khách hàng quay số để kết

nối đến một trong những đường ra hữu hạn của tổng đài.

2. Trong mạng máy tính: khi mà gói tin được chuyển từ nguồn tới đích

và đi qua một số lượng các nút trung gian. Hệ thống hàng đợi xuất hiện tại

mỗi nút ở quá trình lưu tạm thông tin tại bộ đệm.

3. Hệ thống máy tính: khi các công việc được tính toán và tuyến làm

việc của hệ thống yêu cầu dịch vụ từ bộ xử lý trung tâm và từ các nguồn

khác.

Tuy nhiên, trong quá trình hoạt động của hệ thống do nhiều nguyên nhân

khác nhau thường dẫn đến các tình trạng:

− Khả năng phục vụ của hệ thống không đáp ứng yêu cầu (s quá bé)

do đó kết quả là một số yêu cầu không được phục vụ hoặc phải chờ đợi để

được phục vụ nên cần lắp đặt thêm đơn vị phục vụ dẫn đến chi phí cao.

− Khả năng phục vụ của hệ thống vượt quá yêu cầu (s quá lớn) do đó

kết quả là hệ thống không sử dụng hết năng lực về lao động, vật tư, thiết

bị...nên thừa các đơn vị phục vụ dẫn đến chi phí cao.

Do vậy cần điều chỉnh đơn vị phục vụ(s) phù hợp với yêu cầu để tiết kiệm

chi phí.

2.3. VAI TRÒ CỦA PHÂN PHỐI MŨ TRONG MÔ HÌNH XẾP

HÀNG [3]

Giả sử T là biến ngẫu nhiên chỉ thời gian giữa 2 lần đến (hoặc thời gian

giữa 2 lần phục vụ). T thường có phân phối mũ và hàm mật độ của nó có

dạng:

fT (t) =







αe−αt, t ≥ 0

0, t < 0

10

Hình 2.3: Hàm mật độ xác suất cho phân phối mũ

Hàm phân phối:

P{T ≤ t} =

Z t

0

αe−αsds

= −αe−αs

t

0

= 1 − e

−αt

.

P{T > t} = 1 − (1 − e

−αt) = e

−αt

.

Một số tính chất:

Tính chất 1.fT (t) là hàm giảm chặt.

Tính chất 2. Tính thiếu trí nhớ:

P{T > t + ∆t | T > ∆t} = P{T > t}.

Tính chất 3. Cực tiểu của n biến ngẫu nhiên độc lập có phân phối mũ thì

cũng có phân phối mũ.

Tính chất 4. Quan hệ với phân phối Poisson

Nếu T là biến ngẫu nhiên chỉ thời gian giữa 2 lần đến có phân phối mũ

với hàm mật độ:

fT (t) = αe−αt

,

thì biến ngẫu nhiên X(t) chỉ số khách hàng đến trong khoảng thời gian bằng

t có phân phối Poisson với tham số µ = αt.

Tính chất 5. Với ∆t khá bé thì:

P{T ≤ t + ∆t/T > ∆t} ≈ αt

11

Tính chất 6. Tính bất biến đối với phép gộp và phép tách.

- Phép gộp:

Giả sử có k khách hàng khác nhau, trong đó khách hàng của từng loại

(loại i) đến theo phân phối Poisson với tham số λi(i = 1, 2, ..., n). và sự đến

của mỗi loại khách hàng là độc lập.

Tính chất này nói rằng gộp tổng thể ( sự đến của tất cả các khách hàng

mà không quan tâm đến loại) cũng tuân theo phân phối Poisson, với tham

số λ = λ1 + λ2 + ... + λn. Nói cách khác, phân phối Poisson không bị ảnh

hưởng bởi phép gộp.

- Phép tách:

Giả sử có k khách hàng khác nhau và mỗi khách hàng đến đều có xác

suất xác định là pi của loại i (i = 1, 2, ..., n) với λi = piλ và X

n

i=1

pi = 1.

Tính chất này nói rằng số khách hàng loại i đến cũng tuân theo phân

phối Poisson với tham số λi

. Nói cách khác, phân phối Poisson không bị ảnh

hưởng bởi phép tách.

12

CHƯƠNG 3

MÔ HÌNH XẾP HÀNG DỰA TRÊN QUÁ TRÌNH

SINH TỬ

3.1. QUÁ TRÌNH SINH TỬ [3]

Mô phỏng hệ thống xếp hàng như một quá trình sinh tử.

− Sinh: khi có một khách hàng vào hệ thống.

− Tử: khi có một khách hàng được phục vụ xong và ra khỏi hệ thống.

N(t) là số khách hàng có mặt trong hệ thống tại thời điểm t.

3.1.1. Các giả thiết

Giả thiết 1: Khi N(t) = n phân phối xác suất của thời gian (của T)

cho lần đến tiếp theo của khách hàng là tuân theo phân phối mũ với tham

số λn.

Giả thiết 2: Khi N(t) = n là phân phối xác suất của thời gian (của

T) cho khách hàng tiếp theo ra khỏi hệ thống tuân theo phân phối mũ với

tham số µn.

Giả thiết 3: Tại mỗi thời điểm chỉ có thể có một sinh hoặc một tử xảy

ra.

3.1.2. Sơ đồ của quá trình sinh tử

Hình 3.1: Biểu đồ tỉ lệ cho quá trình sinh - tử