Lý thuyết hàng đợi là nhánh toán học mô tả những hệ thống có người hoặc việc đến ngẫu nhiên và được phục vụ với tốc độ có hạn: quầy giao dịch, tổng đài, máy chủ xử lý yêu cầu, trạm thu phí. Kết quả quan trọng nhất của nó trái với trực giác: khi quầy bận 80% thời gian, khách đã phải chờ lâu gấp bốn lần thời gian phục vụ; bận 96% thì hàng dài gấp sáu lần mức 80%.
Bài này giới thiệu mô hình đơn giản nhất là M/M/1, tính tay các đại lượng chính cho một quầy giả định, giải thích định luật Little, và so sánh một câu hỏi thực tế: nên có một quầy làm nhanh gấp đôi hay hai quầy tốc độ thường. Lý thuyết này bắt nguồn từ công trình của kỹ sư Đan Mạch Agner Krarup Erlang về tổng đài điện thoại đầu thế kỷ 20.
Mô hình M/M/1 và các giả định của nó
Ký hiệu M/M/1 đọc như sau. Chữ M thứ nhất: khách đến theo quá trình Poisson, nghĩa là khoảng thời gian giữa hai khách liên tiếp có phân phối mũ, các lần đến độc lập với nhau. Chữ M thứ hai: thời gian phục vụ mỗi khách cũng có phân phối mũ. Số 1: có một quầy. Mặc định thêm rằng hàng chờ không giới hạn và khách được phục vụ theo thứ tự đến trước phục vụ trước.
Hai tham số là tốc độ đến trung bình, ký hiệu lambda (λ), tính bằng số khách mỗi giờ, và tốc độ phục vụ trung bình mu (μ), cũng tính bằng khách mỗi giờ. Hệ số sử dụng rho (ρ) bằng λ chia μ, cho biết tỉ lệ thời gian quầy bận. Điều kiện để hàng không dài ra mãi là ρ nhỏ hơn 1, tức khách đến chậm hơn tốc độ quầy xử lý.
Ai từng học xác suất sẽ nhận ra hai phân phối quen thuộc. Phân phối Poisson trả lời câu hỏi trong một giờ có bao nhiêu khách đến; phân phối mũ trả lời câu hỏi phải đợi bao lâu nữa mới có khách tiếp theo. Một tính chất đặc biệt của phân phối mũ là "không nhớ": đã đợi năm phút mà chưa có khách thì thời gian còn phải đợi vẫn có cùng phân phối như lúc mới bắt đầu. Chính tính chất này làm các công thức của M/M/1 gọn đến mức tính tay được.
Giả định phân phối mũ nghe kỹ thuật, nhưng ý nghĩa thực tế là mức dao động khá lớn: có lúc khách dồn đến liền nhau, có lúc vắng; có khách xong trong nửa phút, có khách mất mười phút. Với khách đến, giả định này thường khá sát khi khách là nhiều người độc lập. Với thời gian phục vụ, nó thường phóng đại độ dao động; phần sau sẽ thấy điều đó ảnh hưởng thế nào.
Bốn công thức và một ví dụ tính tay
Với M/M/1 ở trạng thái ổn định, có bốn đại lượng hay dùng. Số khách trung bình trong hệ thống (đang chờ cộng đang được phục vụ) L bằng ρ chia (1 trừ ρ). Số khách trung bình đang chờ Lq bằng ρ bình phương chia (1 trừ ρ). Thời gian trung bình một khách ở trong hệ thống W bằng 1 chia (μ trừ λ). Thời gian chờ trung bình trước khi được phục vụ Wq bằng ρ chia (μ trừ λ).
Ví dụ giả định: một quầy giao dịch phục vụ trung bình mỗi khách 2,4 phút, tức μ bằng 25 khách mỗi giờ. Giờ cao điểm có trung bình 20 khách mỗi giờ. Khi đó ρ bằng 20 chia 25 bằng 0,8; L bằng 0,8 chia 0,2 bằng 4 khách; Lq bằng 0,64 chia 0,2 bằng 3,2 khách; W bằng 1 chia 5 giờ, tức 12 phút; Wq bằng 0,8 chia 5 giờ, tức 0,16 giờ hay 9,6 phút.
Đọc kết quả: phục vụ chỉ mất 2,4 phút nhưng mỗi khách trung bình ở quầy 12 phút, trong đó 9,6 phút là đứng chờ. Người quản lý nhìn vào tỉ lệ bận 80% sẽ thấy quầy "vẫn còn 20% thời gian rảnh", còn khách thấy hàng lúc nào cũng có ba bốn người phía trước. Cả hai cùng đúng, và chênh lệch nhận thức này là lý do hàng đợi đáng được tính bằng toán chứ không bằng cảm giác.
Phép kiểm nhanh: W phải bằng Wq cộng thời gian phục vụ trung bình. Ở đây 9,6 cộng 2,4 bằng 12 phút, khớp.
Đường cong thời gian chờ: tăng vọt khi gần kín việc
Giữ nguyên quầy phục vụ 25 khách mỗi giờ, thay đổi lượng khách đến. Bảng dưới tính theo các công thức trên; thời gian đổi ra phút.
| Khách đến mỗi giờ (λ) | Hệ số bận (ρ) | Số khách trong hệ (L) | Thời gian chờ (Wq, phút) | Tổng thời gian (W, phút) |
|---|---|---|---|---|
| 15 | 0,60 | 1,5 | 3,6 | 6 |
| 20 | 0,80 | 4 | 9,6 | 12 |
| 22 | 0,88 | khoảng 7,3 | 17,6 | 20 |
| 24 | 0,96 | 24 | 57,6 | 60 |
Từ 20 lên 22 khách, lượng khách chỉ tăng 10% mà tổng thời gian tăng từ 12 lên 20 phút. Từ 22 lên 24 khách, thêm chưa tới 10% mà thời gian gấp ba. Thủ phạm là mẫu số (μ trừ λ): khi λ tiến sát μ, hiệu số tiến về 0 và thời gian chờ phình ra không giới hạn.
Hệ quả thực tế: một hệ thống được thiết kế "vừa đủ" công suất cho lượng khách trung bình sẽ có hàng rất dài, vì chỉ cần một biến động nhỏ là đẩy ρ lên sát 1. Dư một ít công suất mang lại lợi ích lớn hơn nhiều so với tưởng tượng. Điều này đúng với quầy giao dịch, với tổng đài và với cả máy chủ xử lý yêu cầu trên mạng.
Định luật Little: một đẳng thức dùng được ở mọi nơi
Năm 1961, John Little công bố chứng minh cho một quan hệ đơn giản: trong một hệ thống ổn định, số đối tượng trung bình trong hệ bằng tốc độ đến trung bình nhân thời gian trung bình mỗi đối tượng ở trong hệ, tức L bằng λ nhân W. Kiểm với ví dụ: 20 khách mỗi giờ nhân 0,2 giờ bằng 4 khách, đúng bằng L ở trên.
Điều đáng giá của định luật Little là nó gần như không phụ thuộc giả định về phân phối, số quầy hay thứ tự phục vụ. Bạn có thể dùng nó cho một quán ăn, một kho hàng, một quy trình duyệt hồ sơ. Ví dụ giả định: một bộ phận nhận trung bình 30 hồ sơ mỗi ngày, và đếm được lúc nào cũng có khoảng 150 hồ sơ đang nằm trong quy trình. Không cần theo dõi từng hồ sơ, bạn biết ngay thời gian xử lý trung bình là 150 chia 30 bằng 5 ngày.
Định luật cũng dùng được theo chiều ngược: muốn rút thời gian xử lý trung bình xuống 3 ngày trong khi lượng hồ sơ đến không đổi, số hồ sơ tồn trong quy trình phải giảm xuống khoảng 90. Mục tiêu "giảm tồn" và mục tiêu "giảm thời gian chờ" thực chất là một.
Một quầy nhanh gấp đôi hay hai quầy thường?
Đặt bài toán. Vẫn 20 khách mỗi giờ. Phương án một: một quầy phục vụ 50 khách mỗi giờ. Phương án hai: hai quầy, mỗi quầy 25 khách mỗi giờ, khách xếp một hàng chung và ai rảnh thì gọi người tiếp theo. Tổng công suất như nhau.
Một quầy nhanh. Đây vẫn là M/M/1 với ρ bằng 0,4. Tổng thời gian W bằng 1 chia (50 trừ 20) giờ, tức 2 phút. Thời gian chờ Wq bằng 0,4 chia 30 giờ, khoảng 0,8 phút.
Hai quầy thường. Mô hình M/M/2 có công thức phức tạp hơn; với hai quầy, tổng thời gian W bằng 1 chia (μ nhân (1 trừ ρ bình phương)), trong đó ρ bằng λ chia 2μ bằng 0,4. Ra W bằng 1 chia (25 nhân 0,84) giờ, khoảng 2,86 phút; trừ thời gian phục vụ 2,4 phút còn thời gian chờ khoảng 0,46 phút.
Kết luận phụ thuộc vào thứ bạn quan tâm. Hai quầy thường cho thời gian đứng chờ ngắn hơn, vì khách hiếm khi phải chờ khi có quầy rảnh. Một quầy nhanh cho tổng thời gian ngắn hơn, vì mỗi lượt phục vụ nhanh gấp đôi. Nếu khách bực nhất là đứng chờ, hai quầy hợp lý hơn; nếu tổng thời gian quan trọng, quầy nhanh tốt hơn. Đây là ví dụ kinh điển cho thấy mô hình không ra quyết định thay bạn mà làm rõ đánh đổi.
Một hàng chung tốt hơn mỗi quầy một hàng. Với cùng số quầy, xếp một hàng chung cho thời gian chờ trung bình thấp hơn và công bằng hơn so với mỗi quầy một hàng riêng, vì không có chuyện một quầy rảnh trong khi quầy bên cạnh dồn khách.
Giảm dao động cũng là giảm thời gian chờ
Công thức M/M/1 giả định thời gian phục vụ dao động rất mạnh. Nếu mỗi khách được phục vụ trong đúng 2,4 phút không sai một giây, mô hình đổi thành M/D/1 và thời gian chờ trung bình chỉ còn một nửa: với 20 khách mỗi giờ, Wq bằng ρ chia (2μ nhân (1 trừ ρ)) bằng 0,8 chia 10 giờ, tức 4,8 phút thay vì 9,6 phút. Công thức tổng quát cho thời gian phục vụ bất kỳ, gọi là công thức Pollaczek–Khinchine, cho thấy thời gian chờ tăng theo độ biến động của thời gian phục vụ.
Bài học ứng dụng: chuẩn hoá quy trình, tách những ca phức tạp sang một quầy riêng, chuẩn bị giấy tờ trước khi đến lượt, tất cả đều làm thời gian chờ giảm dù tốc độ trung bình không đổi.
Khi dùng chatbot để tính hàng đợi, hãy yêu cầu nó ghi rõ mô hình đang dùng và giả định về phân phối. Câu lệnh mẫu: "Với λ bằng 20 khách mỗi giờ, μ bằng 25 khách mỗi giờ, tính L, Lq, W, Wq theo M/M/1, ghi công thức từng đại lượng, rồi kiểm lại bằng định luật Little." Sau đó tự kiểm W bằng Wq cộng 1 chia μ. Với dữ liệu đếm khách thật của cửa hàng hay ngân hàng nơi bạn làm, chỉ đưa con số tổng hợp theo giờ, không đưa thông tin khách hàng. Với hệ nhiều quầy hoặc giả định phức tạp, mô phỏng thường đáng tin hơn một công thức chatbot nhớ không chắc.
Câu hỏi thường gặp
Vì sao quầy chỉ bận 80% mà hàng vẫn dài?
Vì khách đến ngẫu nhiên, có lúc dồn dập có lúc vắng. Thời gian rảnh của quầy rơi vào lúc vắng, không bù được cho lúc dồn. Với mô hình M/M/1, ở mức bận 80% mỗi khách mất trung bình gấp năm lần thời gian phục vụ để đi hết quầy.
Định luật Little có cần giả định khách đến theo Poisson không?
Không. Định luật Little đúng cho hầu hết hệ thống ổn định, bất kể phân phối thời gian đến và thời gian phục vụ, số quầy hay thứ tự phục vụ. Điều kiện chính là hệ thống ở trạng thái ổn định trong khoảng thời gian đang xét.
Khi nào mô hình M/M/1 không còn dùng được?
Khi lượng khách thay đổi mạnh theo giờ, khi khách bỏ về vì hàng dài, khi hàng chờ có giới hạn hoặc thời gian phục vụ ít dao động hơn nhiều so với phân phối mũ. Khi đó cần mô hình khác hoặc mô phỏng.
Hệ số sử dụng nên để ở mức nào là hợp lý?
Không có con số chung, vì phụ thuộc chi phí thêm quầy và mức chờ chấp nhận được. Bảng trong bài cho thấy từ khoảng 80% trở lên, thời gian chờ tăng rất nhanh, nên nhiều hệ thống chủ động giữ công suất dư cho giờ cao điểm.
Có thể dùng lý thuyết hàng đợi cho máy chủ web không?
Có, nguyên lý giống hệt: yêu cầu đến ngẫu nhiên, máy chủ xử lý với tốc độ có hạn. Hiện tượng thời gian phản hồi tăng vọt khi tải gần kín công suất là cùng một cơ chế với hàng dài ở quầy.
Chatbot có tính đúng các bài hàng đợi nhiều quầy không?
Công thức nhiều quầy phức tạp nên chatbot dễ nhớ sai. Hãy yêu cầu nó ghi công thức, tự kiểm bằng định luật Little và quan hệ W bằng Wq cộng thời gian phục vụ, hoặc so với một mô phỏng nhỏ trong bảng tính.