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

Bạn đứng ở tầng 5, bấm nút gọi thang máy – nhưng thang lại đi lên tầng 10 trước rồi mới xuống đón bạn. Thang máy "chậm chạp" hay đang làm đúng theo một thuật toán? Hãy cùng tìm hiểu cách thang máy quyết định nên đi đâu tiếp theo.

Bài thứ mười tám của chuyên mục "Thuật toán trong đời sống": bài toán lập lịch và thuật toán SCAN.

1. Một chút lịch sử

Theo trang lịch sử chính thức của Otis, Elisha Otis bán chiếc thang máy có phanh an toàn đầu tiên năm 1853, và năm 1854 ông trình diễn công khai tại Triển lãm Crystal Palace ở New York: ông cho cắt dây treo, phanh an toàn lập tức giữ thang lại. Từ đó, thang máy trở thành thứ không thể thiếu của các tòa nhà cao tầng.

2. Bài toán: phục vụ các lượt gọi theo thứ tự nào?

Giả sử thang đang ở tầng 5, các lượt gọi lần lượt là: 9, 2, 7, 3, 10, 1, 8. Có hai chiến lược:

• Ai gọi trước phục vụ trước (FCFS): đi 5 → 9 → 2 → 7 → … Nghe công bằng, nhưng thang chạy lên chạy xuống liên tục.
• SCAN – "thuật toán thang máy": đi hết một chiều, đón/trả mọi tầng trên đường, rồi mới quay đầu.

Thuật toán SCAN nổi tiếng đến mức trong giáo trình Hệ điều hành (Silberschatz, Galvin, Gagne), khi dùng để sắp xếp thứ tự đọc dữ liệu trên ổ đĩa cứng, nó còn được gọi là "elevator algorithm" – thuật toán thang máy: đầu đọc chạy từ một đầu đĩa sang đầu kia, phục vụ các yêu cầu trên đường đi.

So sánh FCFS và SCAN

#include <bits/stdc++.h>
using namespace std;
// Tổng số tầng thang máy phải đi khi phục vụ theo thứ tự cho trước
int cost(int start, const vector<int>& order){
    int pos = start, moved = 0;
    for(int r : order){ moved += abs(r - pos); pos = r; }
    return moved;
}
int main(){
    int start = 5;
    vector<int> calls = {9, 2, 7, 3, 10, 1, 8};   // thứ tự bấm nút
    // SCAN: đi lên hết các tầng >= start, rồi quay xuống
    vector<int> up, down;
    for(int r : calls) (r >= start ? up : down).push_back(r);
    sort(up.begin(), up.end());
    sort(down.rbegin(), down.rend());
    vector<int> scanOrder = up;
    scanOrder.insert(scanOrder.end(), down.begin(), down.end());
    cout << "FCFS: " << cost(start, calls) << " tang\n";
    cout << "SCAN: " << cost(start, scanOrder) << " tang, thu tu:";
    for(int r : scanOrder) cout << ' ' << r;
    cout << "\n";
}

def fcfs(start, requests):
    # Phục vụ theo thứ tự gọi (đến trước phục vụ trước)
    pos, moved, order = start, 0, []
    for r in requests:
        moved += abs(r - pos); pos = r; order.append(r)
    return moved, order

def scan(start, requests, going_up=True):
    # Thuật toán SCAN: đi hết một chiều rồi mới quay đầu
    up = sorted(r for r in requests if r >= start)
    down = sorted((r for r in requests if r < start), reverse=True)
    order = up + down if going_up else down + up
    pos, moved = start, 0
    for r in order:
        moved += abs(r - pos); pos = r
    return moved, order

calls = [9, 2, 7, 3, 10, 1, 8]          # các tầng được gọi, theo thứ tự bấm nút
print("FCFS:", fcfs(5, calls))
print("SCAN:", scan(5, calls))

Kết quả chạy:

FCFS: 43 tang
SCAN: 14 tang, thu tu: 7 8 9 10 3 2 1

Cùng 7 lượt gọi, SCAN chỉ phải đi 14 tầng thay vì 43 tầng – tiết kiệm hơn 3 lần thời gian và điện năng. Đây là một ví dụ của chiến lược tham lam có định hướng: không quay đầu khi chưa cần thiết.

Vì sao thang lại lên tầng 10 trước? Nếu thang đang đi lên và còn người cần lên tầng 10, SCAN sẽ hoàn thành chiều đi lên trước. Bạn ở tầng 5 phải chờ thêm một chút, nhưng tổng thời gian của mọi người được giảm.

3. Điều phối theo điểm đến: thang máy hiện đại

Nhiều tòa nhà cao tầng ngày nay không còn nút "lên/xuống" mà có màn hình để bạn nhập tầng muốn đến ngay ở sảnh. Hệ thống sẽ chỉ định bạn đi thang nào:

• Theo KONE, hệ thống điều phối theo điểm đến tính đến tầng cần đến và số người đang chờ, trong khi hệ thống truyền thống chỉ biết hướng lên hay xuống.
• Schindler (hệ thống PORT) và Otis (CompassPlus) đều gom những người đi cùng tầng hoặc tầng gần nhau vào cùng một thang. Các hãng quảng cáo mức cải thiện "lên đến 50%" – đây là số liệu do hãng công bố.

Về mặt thuật toán, đây là bài toán phân nhóm và lập lịch: chia hành khách vào các thang sao cho tổng số điểm dừng ít nhất – khó hơn SCAN rất nhiều vì có nhiều thang và nhiều cách ghép nhóm.

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

• Cùng một tập việc cần làm, thứ tự thực hiện có thể thay đổi chi phí rất nhiều.
• Thuật toán SCAN cần sắp xếp – một lần nữa, sắp xếp là nền tảng của nhiều thuật toán.
• Luôn có đánh đổi giữa công bằng (ai gọi trước) và hiệu quả (tổng quãng đường).

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

• CSES – Elevator Rides (quy hoạch động trên tập con)
• CSES – Tasks and Deadlines (chọn thứ tự làm việc tối ưu)
• Sửa code để thang có thể bắt đầu bằng chiều đi xuống. Khi nào đi xuống trước lại tốt hơn?

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

Bài 19: Đèn giao thông thông minh và luồng cực đại – Tìm nút cổ chai của thành phố

Đọc tiếp: giao thông & luồng cực đại →

← Bài trước: lý thuyết hàng đợiXem tất cả 27 bài →

Nguồn tham khảo

• Otis – Our history
• ASME – Elisha Graves Otis
• LSU CSC4103 – Mass Storage (SCAN, elevator algorithm; theo Silberschatz, Galvin, Gagne)
• KONE – Destination solutions
• Schindler – PORT destination control
• Otis – CompassPlus