Efficient Elevators: Algorithms, Cars and Queues

The latest PBS NOVA episode entitled "Trapped in an Elevator" is based on an actual event that occurred in 1999. Watching it reminded me that elevators (or lift in British english) can be regarded as a queueing system, viz., priority queues, which are also the basis for scheduling algorithms in operating systems and storage devices. A lot of this background can be found in Don Knuth's erudite volumes:

• Vol 1, p.280: elevator simulator program based on doubly-linked lists
  
• Vol 3, p.150: elevator scheduling as priority queues
  
• Vol 3, p.357: tape sorting reformulated as single elevator problem
  
• Vol 3, p.374: disk seeks treated as single elevator problem

[Best wishes for Randall's fiancée]

Real elevators in buildings occupy space. As the buildings have become taller and taller skyscrapers, the volume that would be taken up by elevators becomes prohibitive. The solution is to partition the building with "sky lobbies" that cut the number of elevator-shafts per section in half by keeping the number of shafts per section constant. The other innovation that I hadn't heard of, and is not discussed in Knuth, is the destination dispatch algorithm. Instead of just indicating whether you want to go up or down, you punch in the desired floor number (needs a full keypad) and the elevator does the rest when you enter. For this reason, there are no buttons inside the car: the computers take care of you—unless it's 1999 all over again. That case, however, seems to have been more about human failure than electro-mechanical failure.

Elevator scheduling algorithms are very much still a part of ongoing research. The real limitation for skyscraper elevators is not scheduling algorithms, but the weight of the multiple steel cables required to hall them up and down. In the world's tallest buildings there can be more than 6 miles of cables, weighing around 30 tons. As the NOVA program shows, one possible solution is to eliminate cables by using maglev-style motors.