Article URL: https://john.fun/elevators Comments URL: https://news.ycombinator.com/item?id=49124218 Points: 297 # Comments: 104

Everyone 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. 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. 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. How do you actually measure how good an elevator algorithm is? The obvious metric is how long you wait for the elevator to arrive. A very simple measure is "how often does the elevator arrive within 30 seconds?" Or "how often does the elevator arrive within 90 seconds?"