Multi-Elevator Scheduling – điều phối cả dàn thang máy

Ở các toà nhà lớn, ta không chỉ có một thang mà là cả một dàn thang máy. Lúc này bài toán không còn là “thang này nên đi lên hay đi xuống?” nữa, mà là:

• Request ở tầng X, hướng Y nên giao cho thang nào?
• Làm sao để tổng thời gian chờ nhỏ, thang không chạy lung tung, và tránh thang này rảnh trong khi thang kia quá tải?

Multi-Elevator Scheduling là bài toán phân công request cho nhiều thang. Có rất nhiều chiến lược, trong đó hai kiểu trực quan và dễ minh hoạ là:

• Nearest-car: giao request cho thang “phù hợp nhất” (gần nhất, đang đi đúng hướng, sắp đi qua tầng gọi…).
• Sectoring: chia toà nhà thành các vùng tầng, mỗi thang phụ trách một vùng (ví dụ: thang A: 0–5, B: 6–10, C: 11–15).

Bài này là phần chốt series: ta sẽ nhìn nhanh ý tưởng và có một demo nhỏ để trực quan hoá.

1. Nearest-car vs Sectoring – trực giác nhanh

Nearest-car

• Mỗi khi có request mới (tầng + hướng), hệ thống tính một “điểm phù hợp (cost)” cho từng thang:
  • Thang càng gần tầng gọi → cost càng thấp.
  • Thang đang đi cùng hướng và sắp đi qua tầng gọi → ưu tiên hơn.
  • Thang phải quay đầu hoặc đi ngược hướng → phạt thêm.
• Request được giao cho thang có cost nhỏ nhất.

Sectoring

• Toà nhà được chia thành các vùng tầng, mỗi vùng gán cho một thang:
  • Thang A: tầng 0–5.
  • Thang B: tầng 6–10.
  • Thang C: tầng 11–15.
• Request ở tầng nào thì ưu tiên giao cho thang phụ trách vùng đó.
• Giảm đụng độ, mỗi thang “canh” một vùng riêng, dễ suy nghĩ hơn.

Thực tế, các hệ thống lớn còn kết hợp thêm time-of-day, load balancing, thậm chí học máy. Nhưng cho mục đích học thuật + demo trực quan, Nearest-car + Sectoring là combo đủ vui và dễ hiểu.

2. Demo Multi-Elevator Scheduling – 3 thang, 16 tầng

Demo dưới đây mô phỏng:

• Tòa nhà 16 tầng (0–15).
• 3 thang máy: A, B, C – ban đầu đều ở tầng 0.
• Request là hall call: (tầng, hướng) – giống người đứng ở tầng bấm Up/Down.
• Scheduler có 2 mode:
  • Nearest-car: tính cost cho từng thang và gán request.
  • Sectoring: A phụ trách 0–5, B phụ trách 6–10, C phụ trách 11–15.
• Sau khi gán, mỗi thang có một list stops (tầng phải ghé). Mỗi bước mô phỏng:
  • Mỗi thang di chuyển 1 tầng về phía stop gần nhất của nó.
  • Nếu tới đúng một stop → dừng, phục vụ request, xoá stop đó.

Giải thích nhanh cấu trúc code

• floors = 16: tầng 0–15.
• requests: mảng hall call, mỗi phần tử { id, floor, dir, elevator, served }:
  • floor: tầng gọi.
  • dir: "up" hoặc "down".
  • elevator: index thang đã được gán (0=A, 1=B, 2=C) hoặc null nếu chưa gán.
  • served: true nếu request đã được phục vụ.
• elevators: mảng 3 thang, mỗi thang { name, currentFloor, direction, stops, color }:
  • stops: danh sách tầng cần ghé, lấy từ các request đã gán cho thang đó.
• Gán thang – Nearest-car: với mỗi request chưa gán, tính một cost cho từng thang:
  • Cost cơ bản = khoảng cách tầng |currentFloor – floor|.
  • Nếu thang đang di chuyển và request nằm “ngược hướng” → +penalty.
  • Chọn thang có cost nhỏ nhất.
• Gán thang – Sectoring:
  • Mỗi thang có một range (sector) cố định: A: 0–5, B: 6–10, C: 11–15.
  • Request ở tầng nào sẽ ưu tiên thang phụ trách sector đó.
  • Nếu có request nằm ngoài sector (edge case), dùng nearest-car fallback.
• Chạy 1 bước:
  • Với mỗi thang:
    • Xác định stop gần nhất trong stops.
    • Di chuyển lên/xuống 1 tầng theo hướng tới stop đó.
    • Nếu đến đúng stop → phục vụ: đánh dấu các request tương ứng là served = true, xoá stop đó.
• Vẽ:
  • 3 trục thang A/B/C cạnh nhau, mỗi thang một màu cabin riêng.
  • Hall call chưa gán vẽ bên trái (“Waiting”).
  • Hall call đã gán vẽ cạnh shaft thang tương ứng, màu cùng với thang.
  • Request đã phục vụ được tô nhạt đi.