Các thuật toán thang máy (Elevator Algorithms)

1. Bức tranh chung: thang máy đang giải bài toán gì?

Một hệ thống thang máy phải quyết định liên tục:

• Thang nào sẽ phục vụ một yêu cầu (nếu có nhiều thang).
• Đi hướng nào (lên hay xuống) tại mỗi thời điểm.
• Dừng ở những tầng nào theo thứ tự ra sao.

Mục tiêu thường là tối ưu một (hoặc kết hợp nhiều) tiêu chí:

• Giảm thời gian chờ trung bình của hành khách.
• Giảm tổng quãng đường di chuyển (tiết kiệm năng lượng, giảm mòn máy).
• Tránh starvation: có tầng chờ rất lâu nhưng không bao giờ được phục vụ.
• Đảm bảo cảm giác “công bằng” giữa các tầng và các hướng.

Các “thuật toán thang máy” dưới đây chính là những cách khác nhau để ra các quyết định đó.

2. Thuật toán Up/Down cơ bản (Basic Elevator Control)

Đây là mức “cổ điển” nhất: thang máy chọn một hướng và cứ thế đi đến khi hết yêu cầu, rồi quay đầu.

• Khi đang đi lên:
  • Ghé tất cả các tầng có người bấm lên (hoặc có người trong cabin chọn).
  • Bỏ qua các yêu cầu đi xuống ở phía trên (tuỳ cấu hình).
• Khi không còn request nào phía trên:
  • Đổi hướng xuống và làm tương tự với các request phía dưới.

Ưu điểm: dễ cài đặt, dễ debug. Nhược điểm: không tối ưu, có thể “quay đầu vô tội vạ” nếu yêu cầu tới dồn dập.

3. Thuật toán SCAN – “thuật toán thang máy” trong ổ cứng

SCAN thực ra là một thuật toán nổi tiếng trong hệ điều hành để điều khiển đầu đọc ổ cứng HDD, nhưng mô hình y hệt thang máy nên được gọi luôn là Elevator Algorithm.

• Thang chọn một hướng (ví dụ đi lên).
• Đi một mạch đến tầng biên (tầng cao nhất có request / hoặc tầng trên cùng).
• Xử lý tất cả yêu cầu trên đường, không quay đầu giữa chừng.
• Đến biên rồi mới đổi chiều và “quét” ngược lại.

SCAN giúp giảm tình trạng đảo chiều liên tục, đồng thời tránh việc một vài tầng bị “bỏ quên” quá lâu.

4. Thuật toán LOOK – phiên bản “tiết kiệm quãng đường” của SCAN

LOOK giống SCAN nhưng thông minh hơn ở chỗ: thang không đi tới tận biên toà nhà, mà chỉ đi đến tầng có request xa nhất theo hướng hiện tại.

• Nếu đang đi lên và request cao nhất chỉ tới tầng 12, thang không cần lên tới tầng 20 rồi mới quay xuống.
• Khi không còn request nào phía trước theo hướng hiện tại, mới đổi chiều.

Ưu điểm: giảm quãng đường “thừa”, vẫn giữ được tính “quét” đều tầng.

5. Collective Control – kiểu điều khiển thang máy thực tế ở chung cư

Đây là kiểu điều khiển gần với thực tế nhất trong các toà nhà bình thường: bên ngoài có hai nút Up/Down, bên trong cabin có nút cho từng tầng.

• Khi thang đang đi lên:
  • Ghép các request “đi lên” từ các tầng phía trên.
  • Cố gắng phục vụ theo thứ tự từ thấp lên cao, hạn chế quay đầu.
• Khi thang đi xuống:
  • Làm tương tự với các request “đi xuống” phía dưới.

Thuật toán này là nền tảng, sau đó có thể kết hợp thêm nhiều heuristic khác (ưu tiên tầng có người chờ lâu, giới hạn số người, v.v.).

6. Destination Dispatch – hệ thang máy hiện đại phân cụm điểm đến

Ở các toà nhà cao cấp, thay vì bấm tầng trong cabin, bạn nhập tầng ngay ở sảnh. Hệ thống sẽ chỉ định bạn vào thang A/B/C/D sao cho:

• Những người đi các tầng gần nhau đi chung thang.
• Mỗi thang dừng ít tầng nhất có thể.

Ý tưởng:

• Gom các yêu cầu thành các “cluster” theo tầng.
• Gán mỗi cluster cho một thang (hoặc một nhóm thang).
• Giảm số lần dừng, tối ưu throughput toàn hệ thống.

7. Multi-Elevator Scheduling – điều phối nhiều thang cùng lúc

Khi toà nhà có nhiều thang, bài toán trở thành: “gán mỗi yêu cầu cho thang nào?”

Một số chiến lược:

• Nearest-car: gán request cho thang gần nhất (theo vị trí và hướng hiện tại).
• Sectoring: mỗi thang phụ trách một vùng tầng (1–10, 11–20,…).
• Dynamic zoning: vùng tầng của thang có thể thay đổi theo tải và thời điểm (giờ cao điểm, giờ trưa…).

Ở mức phức tạp hơn, người ta còn dùng các thuật toán tối ưu, heuristic, thậm chí học tăng cường (Reinforcement Learning) để điều phối.

8. “Thuật toán thang máy” trong các bối cảnh khác

Điều thú vị là mô hình thang máy xuất hiện ở nhiều nơi khác ngoài… thang máy:

• Ổ cứng HDD: đầu đọc di chuyển giữa các track giống như thang máy di chuyển giữa các tầng.
• Hệ thống phục vụ request theo chiều tăng/giảm: ví dụ API rate limiter, batch job scheduler.
• Robot trong kho hàng nhiều tầng: quản lý hướng di chuyển tối ưu.

Nhiều thuật toán thang máy (SCAN, LOOK, C-SCAN…) được mô tả trong giáo trình Hệ điều hành dưới tên “Disk Scheduling”, nhưng bản chất rất giống bài toán điều khiển thang máy.

9. Sơ đồ định hướng các bài viết con

Để đọc sâu hơn, bạn có thể đi theo thứ tự gợi ý sau (mỗi mục tương ứng với một bài con chi tiết):

• Bài 1: Thuật toán thang máy Up/Down cơ bản – nền tảng của mọi hệ điều khiển thang máy
• Bài 2: Thuật toán SCAN & LOOK – “thuật toán thang máy” trong OS & thực tế
• Bài 3: Collective Control – thang máy chung cư với nút Up/Down hoạt động thế nào?
• Bài 4: Destination Dispatch – tại sao thang máy bảo bạn đi thang A chứ không phải thang B?
• Bài 5: Multi-Elevator Scheduling – điều phối cả dàn thang máy

Mỗi bài con có thể kèm:

• Trực giác & ví dụ minh hoạ (kịch bản: giờ cao điểm buổi sáng, giờ tan ca, v.v.).
• Phân tích ưu/nhược, độ phức tạp, fairness.
• Demo JavaScript: canvas vẽ toà nhà, thang di chuyển, log từng bước ra quyết định.

Đây là bài hub, đóng vai trò “mục lục” cho toàn bộ series thuật toán thang máy. Ở các bài tiếp theo, chúng ta sẽ đi sâu vào từng thuật toán, kèm demo trực quan để thấy rõ cách thang ra quyết định trong các tình huống thực tế.