有一家洗车场一次只能为 1 位顾客提供服务。洗车店的目标是让顾客在队列中等待的时间最少，从而让尽可能多的顾客满意。如果可以在 15 分钟内为客户提供服务，他们会很高兴，在一个小时内他们会很高兴，在 1 到 3 小时之间保持中立，在 3 到 8 小时之间生气。 (目标是尽量减少愤怒的人，最大限度地增加快乐的人)。这个问题的唯一警告是每辆车需要不同的时间来清洗和维修，所以我们不能总是以先到先得的方式提供服务，因为我们必须最大限度地提高客户效用。所以它可能看起来像这样:
Customer Line :
Customer1) Task:6 Minutes (1st arrival)
Customer2) Task:3 Minutes (2nd arrival)
Customer3) Task:9 Minutes (3rd)
Customer4) Task:4 Minutes (4th)
Service Line:
Serve Customer 2, Serve Customer 1, Serve Customer 4, Serve Customer 3.
这样一来，没有人排队超过15分钟才上 table 。我知道我应该使用某种形式的优先级队列来实现这一点，但老实说我知道我应该如何为不同的客户提供优先级。我不能优先考虑工作量最少的客户，因为他们可能是最后一个到达的客户(其他人会非常生气)而且我不能只根据时间进行比较，因为第一个人可能有一项任务需要一整天。那么，为了最大程度地提高幸福感，我该如何比较这些客户呢？
干杯
最佳答案
这类似于向调用中心调用电话。当您有黄金和白银客户时，它会变得更有趣。无论如何:
每辆车都有 readyTime(它最早可以清洗的时间，所以它是到达时间 - 每辆车可能不同)和一个 dueTime(清洗的时刻客户生气了，所以 readyTime 后 3 小时)。
然后使用约束求解器(如 OptaPlanner )来确定汽车的顺序 (*)。汽车的顺序(这是一个真正的计划变量)意味着每辆车的 startWashingTime(这是一个影子变量)，因为在您的示例中，如果客户 1 在客户 2 之后订购，并且如果我们从 08:00 开始，我们可以推断客户 1 的 startWashingTime 是 08:03。
那么 endWashingTime 就是 startWashingTime + washingDuration。
然后只需添加 2 个约束并让求解器 solve() 即可:
endWashingTime必须低于dueTime，这是一个硬约束。这是为了没有生气的顾客。endWashingTime必须低于startTime加上 15 分钟，这是一个软约束。这是为了最大限度地提高客户满意度。
(*) 此问题是 NP 完全问题或 NP 难问题，因为您可以将其放松为背包问题。在实践中这意味着:你不能为它编写一个算法来扩展并在合理的时间内找到最佳解决方案。但是约束求解器可以让你接近。
关于algorithm - 如何安排任务，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52397795/