5
$\begingroup$

Could you OR whizkids please help me out with this one:

https://stackoverflow.com/questions/61854621/a-good-memoryless-elevator-strategy

Surely somebody has solved this before. How do you classify this problem? A 1D transportation problem? A routing problem? What methods do you recommend for solving it?

Notice that the task isn't given at the outset: People keep arriving all the time pushing buttons saying "come here, I want to go there". Notice also that there is only one elevator.

The object is of course to bring people to their destinations as quickly as possible. The individual shouldn't be trampled down: Each customer must be served within a reasonable time, even if he or she travels in an unusual way.

There are simple evident strategies in common use in old elevators, but they cannot be optimal. I wonder how much room there is for improvement.

First of all I'm looking for a memoryless strategy: The decision should only depend on the current list of orders. The next step will be to explore if you can improve on this by learning from experience.

Improve this question
$\endgroup$
2
  • $\begingroup$ There's an extremely common strategy that uses one bit of memory. Surely you can use that one? $\endgroup$
    – John Dvorak
    May 24 '20 at 8:16
  • $\begingroup$ I do not know how the elevators work. That being said, maybe you could try to solve it as a model based on a parallel machine scheduling problem, trying to minimize the maximum lateness. Each push on the button would be a new variable, a new Job, and its processing, the transporting of the people that are going to its floor or the entering of the person on the elevator (this one maybe having a higher priority, or not, I don't know). $\endgroup$
    – Josa Ferreira
    Feb 12 '21 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.