Master Elevator Scheduling: Classic and Real‑Time Algorithms Explained

As a programmer you might skip overtime to catch a 20:00 movie, only to discover that elevator traffic can turn a ten‑minute walk into a ten‑minute delay, illustrating the everyday frustration of elevator waiting times.

Many office workers and shoppers share this pain, especially when time is critical, prompting programmers to think about optimizing elevator dispatch.

Traditional Elevator Scheduling Algorithms

1.1 First‑Come‑First‑Serve (FCFS)

FCFS processes requests in the order they arrive without optimizing floor search or providing real‑time guarantees. It is fair and simple, ensuring each request is eventually served, but performance degrades under heavy load.

When the request queue length is one or request intervals are large, FCFS has negligible impact on efficiency and is easy to implement.

FCFS serves as a baseline for comparing other algorithms.

1.2 Shortest Seek Time First (SSTF)

SSTF selects the next request that can be reached in the shortest floor‑search time, reducing average response time under heavy load but increasing variance, potentially causing starvation.

1.3 SCAN

SCAN moves the elevator continuously between the lowest and highest floors, serving requests in the current travel direction, which improves efficiency but is non‑real‑time.

All requests aligned with the elevator’s direction are satisfied during a single upward or downward pass, avoiding frequent direction changes.

SCAN’s average response time is longer than SSTF, but its variance is smaller, offering more stable performance.

1.4 LOOK

LOOK improves SCAN by reversing direction as soon as there are no further requests in the current direction, rather than traveling to the extreme floor.

1.5 SATF (Shortest Access Time First)

SATF is similar to SSTF but replaces floor‑search time with passenger access time, accounting for the time passengers spend entering and exiting the elevator.

Real‑Time Elevator Scheduling Algorithms

2.1 Earliest Deadline First (EDF)

EDF selects the request with the nearest deadline, but can cause the elevator to wander between floors, resulting in low throughput.

2.2 SCAN‑EDF

SCAN‑EDF combines EDF for deadline selection and SCAN for tie‑breaking among equal deadlines; its efficiency depends on the number of requests sharing the same deadline.

2.3 Priority Inversion (PI)

PI divides requests into high‑ and low‑priority queues, always serving high‑priority requests first; low‑priority requests are served only when the high‑priority queue is empty.

2.4 FD‑SCAN (Feasible Deadline SCAN)

FD‑SCAN chooses the earliest‑deadline request that can still be met from the current position, then proceeds in that direction, but it may ignore the cost of serving other pending requests.

Advanced Elevator Group Control Research

Beyond basic algorithms, modern elevators employ group‑control techniques powered by AI, fuzzy logic, genetic algorithms, neural networks, and hybrid fuzzy‑neural methods.

Elevator Problem Requirement Analysis

4.1 Initial Elevator State

The example building has 21 floors (including a basement parking level) and two elevators (A and B). Each elevator features 23 internal buttons (open, close, and floor buttons numbered –1, 1‑20) and external up/down call buttons, with specific rules for top and bottom floors.

Door operation time is set to 1 second, passenger loading/unloading to 8 seconds per floor, travel time between adjacent floors to 2 seconds (1 second when passing a floor while moving).

During 02:00‑04:30, if no requests are pending, elevator A rests at floor 14 and elevator B at floor 6. If an elevator reaches –1 floor without requests, it returns to floor 1.

4.2 Basic Elevator Functions

Each elevator has a unique identifier and a real‑time monitor that controls acceleration, deceleration, door operations, and sends emergency signals when faults occur.

4.3 Elevator Button Functions

Internal floor buttons become disabled (gray) after being pressed, indicating the destination floor; they re‑enable once the elevator arrives.

The internal open‑door button opens the doors after the elevator stops at the selected floor.

The internal close‑door button closes doors after a configurable timeout (8 seconds) once all passengers have entered.

External up‑call buttons trigger the elevator to stop and open doors when the elevator is moving upward and reaches the calling floor; down‑call buttons behave analogously for downward travel.

Conclusion

No single algorithm is universally optimal; each solves specific scenarios. Studying these algorithms enriches a programmer’s toolkit and may prove valuable in future technical interviews.