wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Elevator Algorithm
        
(Message started by: Mike_V on May 19^th, 2004, 2:45pm)

Title: Elevator Algorithm
Post by Mike_V on May 19^th, 2004, 2:45pm

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 .5^K 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.)

Title: Re: Elevator Algorithm
Post by rmsgrey on May 20^th, 2004, 3:28am

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.

Title: Re: Elevator Algorithm
Post by towr on May 20^th, 2004, 3:49am

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?

Title: Re: Elevator Algorithm
Post by rmsgrey on May 20^th, 2004, 4:15am

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