GoKawiilEveryone has shared the frustration of waiting for an elevator that never seems to arrive. "I pressed the button, why isn't it coming?" you ask. For something as commonplace as elevators, they are far more complex than meets the eye.
Over the course of this article, we'll unravel the mysteries of elevators. The way you push their buttons, and how they push yours.
4 3 2 1 1 x 5 x 25 x
One Car
The simplest elevator algorithm is called SCAN and was patented in 1961. The elevator starts at the lobby and goes all the way to the top floor before reversing and coming back down. It picks up and drops off anybody on the way.
Most of the time you don't actually need to go to the TOP floor. If the elevator goes only as high as requested before reversing, the algorithm is called the LOOK algorithm. This is the algorithm most people know and expect.
4 3 2 1 1 x 5 x 25 x add five calls
Multiple Cars
Here's where the mystery begins. If there are multiple elevators, how do the cars coordinate who picks up who?
In the most basic system, there's a central scheduler that tells each elevator which floors to stop on. When a new request comes in, it's assigned to the closest elevator. As we'll soon see however, we can do better.
... continue reading