资源调度问题

Question

我正在开发摩托车租赁网站。我遇到的问题是如何以有效的方式解决客人给摩托车的问题。我知道如何以一种“愚蠢”的方式做到这一点，但我想知道是否有一种经典的算法来解决这类问题。这与将客人分配给酒店客房的问题相同。在这最后一个例子中，我们的目标是通过永不拒绝预约而实现最大占用率，因为调度效率低下。

我很确定这个问题必须是一个已知解决方案的经典问题。

非常感谢。

Answer 1

您感兴趣的内容叫做Interval Scheduling。假设所有预订都具有相同的权重（没有任何优惠比其他任何优惠），您需要一个贪婪算法。

Here (pdf)是关于该主题的一些很好的幻灯片。

基本上，您想先安排最早的结束预订。

Answer 2

这是间隔调度，但它是一个在线算法。如果您想进一步阅读，你可以在这里阅读：

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