Проблема планирования ресурсов

Question

Я занимаюсь разработкой сайта проката мотоциклов.У меня есть проблема, как решить проблему назначения гостя на мотоцикле эффективным способом.Я знаю, как сделать это «глупо», но я хочу знать, существует ли классический алгоритм, который решает эту проблему.Это та же проблема, что и при назначении гостя на номера в отеле.В этом последнем примере цель состоит в том, чтобы достичь максимальной занятости, никогда не отклоняя резервирование из-за неэффективного планирования.

Я почти уверен, что эта проблема должна быть классической проблемой, которая имеет известное решение.

Спасибо большое.

Answer 1

То, что вас интересует, называется Интервальное планирование . Если предположить, что все резервы имеют одинаковый вес (ни одно из них не является предпочтительным по сравнению с любым другим), вам нужен жадный алгоритм.

Здесь (pdf) есть несколько хороших слайдов по теме.

Как правило, вы хотите сначала запланировать самые ранние бронирования.

Answer 2

Это интервальное планирование, но это онлайн-алгоритм.Если вы хотите читать дальше, вы можете прочитать здесь:

http://www -bcf.usc.edu / ~ dkempe / teach / online.pdf