Author |
Topic: Elevator Algorithm (Read 1307 times) |
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Elevator Algorithm
« on: May 19th, 2004, 2:45pm » |
Quote Modify
|
Design the most efficient elevator algorithm for two elevators in an N-floor building. Assume that people come and go from and to the first floor N times as often as any other floor. Also, there is a .5K chance that people will choose to take the stairs if they're going up or down exactly K floors. Ignore any increase/decrease in usage due to time of day. We can measure efficiency by average wait time between pushing the button and getting to the desired floor. Is it possible to prove it is the most efficient? (If not, we can just compare average times.) Is it possible to extend to M elevators? Note: I have no great solution to this problem, though I think about it every day at work. (I swear, the building I work in has the stupidest elevators ever.)
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Elevator Algorithm
« Reply #1 on: May 20th, 2004, 3:28am » |
Quote Modify
|
Another consideration is the notion of reliability. If you have a situation where the expected trip is quick, but there's a possibility of spending an arbitrarily long time in transit while the elevator shuttles back and forth, then passengers are going to be less happy than with a system that always takes about the same time, but has a worse average time.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Elevator Algorithm
« Reply #2 on: May 20th, 2004, 3:49am » |
Quote Modify
|
I suppose you would then want to minimize the maximum time a trip takes, rather than minimize the average time. How much room is there in an elevator?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Elevator Algorithm
« Reply #3 on: May 20th, 2004, 4:15am » |
Quote Modify
|
Typically, I'd expect an elevator to hold somewhere in the 10-20 region. Another question is how the time taken varies with the number of floors between stops (and at what point it's too late to decide to stop at a given floor). A "slow" elevator will take approximately linear time to travel, and be able to stop at a moment's notice, while an "express" elevator would be roughly inverse quadratic (accelerate constantly to midpoint, then decelerate constantly to stop) but requires roughly the same number of floors to stop as it has already passed. A real elevator presumably falls somewhere between those two extremes
|
|
IP Logged |
|
|
|
|