Bài 17: Xếp hàng ở siêu thị có thể tính trước? Lý thuyết hàng đợi

Vì sao khi siêu thị chỉ đông hơn một chút, thời gian chờ lại tăng vọt? Vì sao nhiều ngân hàng cho mọi người xếp chung một hàng rồi gọi số? Có cả một ngành toán học trả lời những câu hỏi này: lý thuyết hàng đợi.

Bài thứ mười bảy của chuyên mục "Thuật toán trong đời sống": lý thuyết hàng đợi và mô phỏng.

1. Bắt đầu từ… tổng đài điện thoại

Năm 1908, kỹ sư toán học người Đan Mạch Agner Krarup Erlang vào làm cho Công ty Điện thoại Copenhagen. Ông cần trả lời: cần bao nhiêu đường dây để khách gọi không phải chờ quá lâu? Năm 1909 ông công bố bài báo đầu tiên về chủ đề này, và năm 1917 đưa ra công thức cho xác suất mất cuộc gọi và thời gian chờ. Ngày nay đơn vị đo lưu lượng điện thoại mang tên ông: erlang.

2. Mô hình M/M/1

Ký hiệu do nhà toán học David Kendall đề xuất năm 1953. M/M/1 nghĩa là: khách đến ngẫu nhiên, thời gian phục vụ ngẫu nhiên (cả hai đều "không có trí nhớ" – phân phối mũ), và 1 quầy phục vụ.

• λ (lambda): số khách đến trung bình mỗi phút.
• μ (mu): số khách một quầy phục vụ được mỗi phút.
• ρ = λ/μ: mức độ bận của quầy. Phải có ρ < 1, nếu không hàng sẽ dài mãi.

Thời gian chờ trung bình trong hàng (M/M/1): W_q = λ / (μ(μ − λ)) = ρ / (μ − λ)
Thời gian trung bình trong hệ thống: W = 1 / (μ − λ)

3. Điều bất ngờ: gần 100% là "thảm họa"

Giả sử thu ngân phục vụ trung bình 3 phút/khách (μ = 1/3). Chương trình dưới đây mô phỏng 200.000 khách và so với công thức:

Mô phỏng hàng đợi và so với công thức M/M/1

#include <bits/stdc++.h>
using namespace std;
double simulate(double lam, double mu, int servers, int n = 200000){
    mt19937 rng(1);
    exponential_distribution<double> arrive(lam), serve(mu);
    vector<double> freeAt(servers, 0.0);
    double t = 0, totalWait = 0;
    for(int i = 0; i < n; i++){
        t += arrive(rng);                                   // khách tiếp theo đến
        int k = min_element(freeAt.begin(), freeAt.end()) - freeAt.begin();
        double start = max(t, freeAt[k]);                   // quầy rảnh sớm nhất
        totalWait += start - t;
        freeAt[k] = start + serve(rng);
    }
    return totalWait / n;
}
int main(){
    double mu = 1.0 / 3;                                    // 3 phút / khách
    for(double lam : {0.20, 0.25, 0.30, 0.32}){
        double rho = lam / mu;
        printf("1 quay, tai %.0f%%: cho TB %5.1f phut (ly thuyet %5.1f)\n",
               rho * 100, simulate(lam, mu, 1), rho / (mu - lam));
    }
    printf("2 quay, moi quay tai 90%%: %.1f phut\n", simulate(0.6, mu, 2));
}

import random

def simulate(lam, mu, servers, n=200000, seed=1):
    # lam: khách đến / phút, mu: khách mỗi quầy phục vụ / phút
    random.seed(seed)
    free_at = [0.0] * servers          # thời điểm mỗi quầy rảnh
    t, total_wait = 0.0, 0.0
    for _ in range(n):
        t += random.expovariate(lam)   # khách tiếp theo đến
        k = min(range(servers), key=lambda i: free_at[i])
        start = max(t, free_at[k])     # một hàng chung, ai rảnh trước phục vụ trước
        total_wait += start - t
        free_at[k] = start + random.expovariate(mu)
    return total_wait / n

mu = 1 / 3                             # mỗi khách mất trung bình 3 phút
for lam in [0.20, 0.25, 0.30, 0.32]:
    rho = lam / mu
    w = simulate(lam, mu, 1)
    theory = rho / (mu - lam)          # công thức M/M/1: Wq = rho / (mu - lam)
    print(f"1 quay, tai {rho:.0%}: cho TB {w:5.1f} phut (ly thuyet {theory:5.1f})")
print("2 quay, moi quay tai 90%:", f"{simulate(0.6, mu, 2):.1f} phut")

Kết quả chạy (bản Python; bản C++ dùng bộ sinh ngẫu nhiên khác nên cho số gần tương tự):

1 quay, tai 60%: cho TB   4.5 phut (ly thuyet   4.5)
1 quay, tai 75%: cho TB   8.9 phut (ly thuyet   9.0)
1 quay, tai 90%: cho TB  26.6 phut (ly thuyet  27.0)
1 quay, tai 96%: cho TB  81.9 phut (ly thuyet  72.0)
2 quay, moi quay tai 90%: 12.6 phut

Mức bận của quầy	Thời gian chờ trung bình (lý thuyết)
60%	4,5 phút
75%	9 phút
90%	27 phút
96%	72 phút

Mức bận chỉ tăng từ 60% lên 90% (thêm một nửa) nhưng thời gian chờ tăng 6 lần! Nguyên nhân là mẫu số μ − λ tiến về 0. Khi gần 100%, chỉ vài khách đến dồn dập là hàng dài ra rất lâu mới hết. (Ở mức 96%, kết quả mô phỏng dao động mạnh quanh giá trị lý thuyết – chính sự dao động đó cũng là dấu hiệu của hệ thống quá tải.)

Bài học cho người quản lý: đừng để quầy bận 100% thời gian. Một chút "thời gian rảnh" là cái giá để khách không phải chờ lâu.

4. Một hàng chung hay mỗi quầy một hàng?

Dòng cuối của kết quả: hai quầy, mỗi quầy bận 90%, nhưng khách xếp một hàng chung và quầy nào rảnh thì gọi người tiếp theo → chờ trung bình chỉ khoảng 12–13 phút, chưa bằng một nửa so với 27 phút nếu mỗi quầy một hàng riêng (mỗi hàng riêng giống một hệ M/M/1 độc lập). Mô phỏng của MathWorks cũng cho kết luận tương tự: cấu hình nhiều hàng riêng cho thời gian chờ trung bình dài hơn.

Giáo sư Richard Larson (MIT), được gọi là "Dr. Queue", còn chỉ ra lý do tâm lý: hàng chung bảo đảm sự công bằng – ai đến trước được phục vụ trước, không có cảm giác "chọn nhầm hàng chậm".

5. Định luật Little: công thức đơn giản đến bất ngờ

L = λ · W
Số người trung bình trong hệ thống = tốc độ đến × thời gian trung bình mỗi người ở trong hệ thống.

John Little chứng minh công thức này năm 1961, và nó đúng cho rất nhiều loại hệ thống. Ví dụ: một quán cà phê có trung bình 2 khách đến mỗi phút, mỗi khách ngồi 30 phút → trung bình trong quán có 2 × 30 = 60 khách, cần khoảng 60 chỗ ngồi.

6. Bạn học được gì từ đây?

• Mô phỏng là cách mạnh mẽ để kiểm tra một công thức – hoặc thay thế công thức khi bài toán quá phức tạp.
• Cấu trúc dữ liệu hàng đợi (queue) và hàng đợi ưu tiên (priority queue) chính là "trái tim" của các chương trình mô phỏng sự kiện.
• Trực giác "đông hơn một chút thì chờ lâu hơn một chút" là sai – toán học cho câu trả lời đúng.

Bài tập luyện tập

• CSES – Restaurant Customers (đếm số khách tối đa cùng lúc)
• CSES – Room Allocation (phân phòng bằng hàng đợi ưu tiên – giống bài toán xếp quầy)
• CSES – Tasks and Deadlines

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 18: Thang máy chọn tầng như thế nào? Thuật toán SCAN

Đọc tiếp: thang máy & SCAN →

← Bài trước: số ngẫu nhiênXem tất cả 27 bài →

Nguồn tham khảo

• INFORMS – Agner Krarup Erlang
• John D. C. Little (2011) – Little's Law as Viewed on Its 50th Anniversary, Operations Research
• arXiv 0810.1091 – Tiểu sử David Kendall (có nhắc ký hiệu hàng đợi năm 1953)
• MIT OpenCourseWare 2.854 – M/M/1 queue
• MathWorks – Comparing queuing strategies
• NPR – Richard Larson ("Dr. Queue") về tâm lý xếp hàng