Upstairs, downstairs
Years ago when I was teaching the "theory of computation" (you know, with Turing machines, Rice's theorem
and all that stuff) course one weekend a month in another town, one
student had signed up for the course thinking that it would be
"computer literacy 101", having taken no computer courses before that.
What is even scarier was that this guy then actually went to pass this
course fair and square. In that same course there was another guy who,
during one break, told me that he designs elevator software for Kone,
and was looking into using genetic algorithms to come up with optimal
elevator control scemes. That interesting topic never came up later,
but I have occasionally wondered what would be the optimal way of
running a group of elevators.
Back in Finland this wasn't much of an issue, because a typical apartment high-rise building (if you can even call five to eight stories a "high-rise") is divided to separate sections (called "rappu" in Finnish) that have one elevator each. This lone elevator of course immediately goes wherever it is called, so there is no advanced logic or optimization involved or even possible. However, the condo where we now live has 25 stories and a group of four elevators that together serve all floors. Occasionally while waiting on the ground floor I have killed time waiting for the car to arrive by looking at the floor indicators to see what the logic of the elevator control would be. And for all I can tell, it could be a helluva lot better. I mean, what is the point of having four independent elevators, if in practice only one of them will ever be moving at any given time?
For example, it has happened to me countless times that I am waiting on the ground floor, and the elevators at located something like 8-12-15-22. The elevator at 8 starts coming down... and reaches the ground floor... but wait, it continues past G and moves all the way down to B2 (lower parking level) to pick up the people waiting there. Coming up, this elevator will stop once more at B1 (upper parking level) to pick up more people, and only after that the people at G can finally get in an elevator that, to add insult to injury, is sometimes so full of people that not everybody can fit in. And during all this waiting time, the other three elevators have been standing at their original locations 12-15-22, doing nothing. So clearly there is room for serious optimization. For starters, since I would guess that about 35% of all trips start from G and 10% from B1 and B2, the control should automatically try to ensure that there are always one or two elevators around there, by bringing down one empty elevator that is otherwise doing nothing useful.
A related issue that I have occasionally wondered but have never had a chance to observe in practice follows from the logical observation that when the control receives a request from some floor, at some point it internally commits to servicing that request with a particular elevator and no other. No matter how the system is programmed, there must necessarily exist such a moment in code and time. Perhaps this commitment is not finalized until the moment that the elevator arrives and opens its doors, but I could easily see it happening even earlier in a simple system that is less well thought out. So what happens if the control has already internally committed to serve a request using elevator A (instead of B, C or D), but at the floor where the elevator A previously makes a stop, some prankster decides to hold the door open indefinitely? How long would it take for the control to realize that it had better start moving one of the other three cars? In principle, this time would be unlimited, if the system has already internally committed to using the elevator A to service the request.
I would assume that there would be some kind of timeout after which the control replans the requests to elevators, but I could easily see that unless the programmers thought of this unlikely scenario, the control would again decide to use elevator A, especially if it is the closest and coming the right way. Perhaps one night at 3 AM when there isn't any traffic so that we wouldn't annoy other people, we should really try this in practice between two floors and see what the elevators will actually do.
Back in Finland this wasn't much of an issue, because a typical apartment high-rise building (if you can even call five to eight stories a "high-rise") is divided to separate sections (called "rappu" in Finnish) that have one elevator each. This lone elevator of course immediately goes wherever it is called, so there is no advanced logic or optimization involved or even possible. However, the condo where we now live has 25 stories and a group of four elevators that together serve all floors. Occasionally while waiting on the ground floor I have killed time waiting for the car to arrive by looking at the floor indicators to see what the logic of the elevator control would be. And for all I can tell, it could be a helluva lot better. I mean, what is the point of having four independent elevators, if in practice only one of them will ever be moving at any given time?
For example, it has happened to me countless times that I am waiting on the ground floor, and the elevators at located something like 8-12-15-22. The elevator at 8 starts coming down... and reaches the ground floor... but wait, it continues past G and moves all the way down to B2 (lower parking level) to pick up the people waiting there. Coming up, this elevator will stop once more at B1 (upper parking level) to pick up more people, and only after that the people at G can finally get in an elevator that, to add insult to injury, is sometimes so full of people that not everybody can fit in. And during all this waiting time, the other three elevators have been standing at their original locations 12-15-22, doing nothing. So clearly there is room for serious optimization. For starters, since I would guess that about 35% of all trips start from G and 10% from B1 and B2, the control should automatically try to ensure that there are always one or two elevators around there, by bringing down one empty elevator that is otherwise doing nothing useful.
A related issue that I have occasionally wondered but have never had a chance to observe in practice follows from the logical observation that when the control receives a request from some floor, at some point it internally commits to servicing that request with a particular elevator and no other. No matter how the system is programmed, there must necessarily exist such a moment in code and time. Perhaps this commitment is not finalized until the moment that the elevator arrives and opens its doors, but I could easily see it happening even earlier in a simple system that is less well thought out. So what happens if the control has already internally committed to serve a request using elevator A (instead of B, C or D), but at the floor where the elevator A previously makes a stop, some prankster decides to hold the door open indefinitely? How long would it take for the control to realize that it had better start moving one of the other three cars? In principle, this time would be unlimited, if the system has already internally committed to using the elevator A to service the request.
I would assume that there would be some kind of timeout after which the control replans the requests to elevators, but I could easily see that unless the programmers thought of this unlikely scenario, the control would again decide to use elevator A, especially if it is the closest and coming the right way. Perhaps one night at 3 AM when there isn't any traffic so that we wouldn't annoy other people, we should really try this in practice between two floors and see what the elevators will actually do.
".. I am waiting in the ground floor..."
Should be "on the ground floor".
English is reasonably straightforward when it comes to the use of prepositions regarding physical positions.
"to turn the insult to injury"
"Add insult to injury" is the correct idiom.
Posted by Markku | 5:17 PM
Apparently the centre-right alliance has won the parliamentary elections in
Sweden. First Finland wins the Eurovision and now this...
Posted by H-Baari | 5:36 PM
All right, corrected. When I get writing enthusiastically, I don't pay much attention to prepositions, even though I should.
Posted by Ilkka Kokkarinen | 6:29 PM
Did anyone else do a double take upon reading the opening sentence of Ilkka's wikipedia link:
"In computer science, Rice's theorem named after Henry Gordon Rice (also known as The Rice-Myhill-Shapiro theorem after Rice and John Myhill)."
Maybe I will posit Andy's Third Man Theorem, namely "Everyone always forgets the third guy"...e.g. "Pavarotti, Placido Domingo and...um...um...."
Andy
Posted by Anonymous | 9:29 PM
Maybe the elevators are optimized to move as little as possible. That would probably make them last longer before breaking up. Average time between service breaks is probably considerably easier to make statistics about compared to average waiting time. Thus it is probably more important to those who decide which elevator to buy.
Just a theory.
Posted by Anonymous | 2:03 AM