[grishka]

Hm. I've always thought that the algorithm of operation of a single elevator is fairly simple? While passing each floor, if a button of that floor was pressed (is lit up), or if the button of the direction it's going on that floor is pressed, then stop. If the elevator is not in use and someone presses any call button, go to that floor. That's mostly it. At least that's how I have that algorithm in my head.

Now, if there are multiple elevators but a single set of up/down buttons for them on each floor, that's where things get really complex really fast.

[saila]

What if you have, say, a 7 story building and someone on each floor presses the call button at around the same time? Do you send the elevator to each floor based on the time the button was pressed, or do you maybe go to the top floor and pick everyone up on the way down, or do something else? The algorithm probably also needs to consider max weight/occupancy. I think even for a single elevator it's quite complex, assuming you want operation to be both fair and efficient.

[grishka]

I'd assume that it would first go to the floor where the button was pressed first, and subsequently collect everyone in the direction it'll go from there. Because that's actually what I feel some elevators are doing because you wait for one for ages. Some certainly do work like that, but newer ones are probably indeed smarter.

Then there's the curiously simple system that you'd find in Soviet buildings, the kind built out of prefab concrete panels. The elevator doesn't allow to be called while it's in use, period. The call buttons on all floors light up while it's in use, and you have to wait for the light to go out before the button would do anything. The buttons inside also only work with doors open (I think?) and you could only press one at a time. The controller for these is most probably made out of relays or something similar.

[varjag]

Elevators in former Soviet Union (even those installed long after its disintegration) are quite dumb compared to Western and SE Asia installations in tall buildings.

[grishka]

I stayed in a tall hotel in Dubai (not sure how much of Asia UAE is) for a while and it still took a minute or two for an elevator to arrive. Though they were freakishly fast, Russian ones now feel like they're crawling.

[svat]

Yes that's mostly it for such old elevators (see "Elevator algorithm" https://en.wikipedia.org/w/index.php?title=Elevator&oldid=10...), except:

- The elevator has a "home floor" (the lobby/ground floor) that it returns to by default, if it has nothing else to do. (Apparently many elevators do this; see "Up peak" in the linked post or on Wikipedia https://en.wikipedia.org/w/index.php?title=Elevator&oldid=10... .)

- To set up such a discrete event simulation on a computer, you also need to model timing (how much time it takes to open and close doors, to move between floors with acceleration/deceleration, etc), and users (how many arrive at each floor and when, and where they want to go to, how long they wait before giving up).

- So you end up with a fair amount of state (the "up" and "down" call buttons on each floor, the buttons inside the elevator, whether the elevator is going up or down or neither) and control (when to open or close doors: what to do if someone presses a button while the doors are closing, etc).

- The purpose of that section of TAOCP is to show in detail how to use doubly-linked lists to simulate such things on a computer (which here means getting down to the level of memory layout and assembly code: MIX/MMIX). So overall there are ~5.5 pages of describing the algorithm, ~1.5 pages for memory layout etc, ~7 pages of assembly code, and a page of higher-level stuff mentioning programming languages and profilers etc.

I'm aware of two repositories on GitHub that reproduce this simulation in a higher-level language: https://github.com/meatfighter/knuth-elevator (700-odd lines of Go code including comments from TAOCP) and https://github.com/Quuxplusone/KnuthElevator (500-odd lines of C++14 code without the copied comments). (Learned of the latter via https://www.meetup.com/theartofcomputerprogramming/ a meetup for reading TAOCP.)