java - 基于时间的资源可用性

Question

我目前正在为处理事件调度的系统开发一个模块。每个事件对象都有一个开始和结束时间戳以及一组所需资源。每个资源的可用数量有限，并且可以同时发生的事件数量也有限制。最终它类似于 session 室预订类型的系统，其中有有限数量的房间、投影仪、椅子等。

目前，我正在遍历当前事件以计算资源利用率和并发事件计数，但是当它运行到数千个事件时，这似乎是一种低效的方法。

谁能推荐一个更有效的方法？

Answer 1

这是一个所谓的 NP-complete问题。随着样本量的增加，寻找一个……比如说“数学上最优”的解决方案可能会变得非常昂贵。您花在……比如说“现实世界”解决方案上的时间取决于您的要求。通过使用一些启发式方法可以找到不太理想的解决方案。

一种启发式:

您可以按某种指标对模块进行排序。比将它们按降序添加到您的池中。从最昂贵的模块开始。添加所有也适契约(Contract)一插槽的模块。之后为剩余的模块打开一个新插槽。等等。