如何安排任务

Question

有一个洗车场，一次只能为一个顾客服务。洗车的目的是让尽可能多的顾客排队等候最少的时间。如果顾客能在15分钟内得到服务，他们是快乐的，不到1小时他们是快乐的，1小时到3小时的中立和3小时到8小时的愤怒。(目标是尽量减少愤怒的人，最大化快乐的人)。对这个问题唯一的警告是，每辆车都需要不同的时间来清洗和服务，所以我们不能总是以先到先得的方式服务，因为我们的目标是最大限度地利用客户。所以看起来可能是这样的：

客户线： Customer1)任务:6分钟(第一次到达) Customer2)任务:3分钟(第二次到达) Customer3)任务:9分钟(第3分钟) Customer4)任务:4分钟(第4分钟) 服务线路： 服务客户2，服务客户1，服务客户4，服务客户3。

这样，没有人排队等候超过15分钟才被送达。我知道我应该使用某种形式的优先级队列来实现这一点，但我诚实地知道应该如何对不同的客户给予优先权。我不能以最少的工作量优先考虑客户，因为他们可能是最后一个到达的客户，例如(其他人会非常生气)，而且我不能仅仅根据时间进行比较，因为第一个人的任务可能会占用整个day.So，我如何比较这些客户的目的是最大限度地获得幸福呢？

干杯

Answer 1

这类似于向呼叫中心订购呼叫。当你有了金银客户的时候，它就变得更有趣了。总之：

每辆车都有readyTime (最早可以清洗的时间，所以它的到达时间--对每辆车来说可能不同)和dueTime (顾客生气的时候，在readyTime 3小时之后)。

然后使用约束求解器(如OptaPlanner)来确定cars (*)的顺序。汽车的顺序(这是一个真正的规划变量)意味着每辆车的startWashingTime (这是一个影子变量)，因为在您的示例中，如果客户1是在客户2之后订购的，如果我们在08:00开始，我们可以推断出客户1的startWashingTime是08:03。

然后endWashingTime是startWashingTime + washingDuration。

然后，只需添加2个约束，并让求解器solve()它：

• endWashingTime必须低于dueTime，这是一个很难的限制。这是为了没有愤怒的顾客。
• endWashingTime必须低于startTime加15分钟，这是一个软约束。这是为了最大化快乐的客户。

(*)这个问题是NP-完全的或NP-硬的，因为你可以把它放松到背包问题。在实践中，这意味着:您不能为它编写一个算法，使其扩展并在合理的时间内找到最优解。但是一个约束解决器可以让你接近。