1

我正在尝试实现一个应用程序来协调多个正在调度独占资源的用户。调度数据必须在具有单个主节点的网络上保持强一致性。预定资源可以是任何东西，从会议室到工作现场的工作人员。

我们假设会议室不能同时安排两个会议，一个工人不能同时在两个工作地点。应用程序的业务逻辑不得允许用户“超量预订”资源。

我不知道如何表示数据，以便如果两个或多个用户同时按计划操作，并且存在冲突，则其中一个更新将中止。

到目前为止，我看到的唯一解决方案是跟踪每个排他性资源的时隙。因此，如果会议室以 5 分钟的间隔使用，并且被安排在上午 9 点到 9 点 30 分，那么上午 9 点到 9 点 30 分对应的 5 分钟时间段都将返回 TRUE，而未安排的时间段将返回 FALSE 或 NULL . 然后，DB 事务会将会议室对象从存储中拉出，检查所有时隙，如果更新与现有时隙冲突，则中止。

但是，这似乎会变得非常大，非常快。也许它可以被垃圾收集？此外，设计的目标之一是支持可变粒度，因此某些对象将按分钟安排，而其他对象可能按天安排，这种数据设计不能很好地支持这一点。

目前，我正在尝试使用 Python 在 Google App Engine 上实现这一点，但我真的很想看到一些更通用的解决方案来解决这个问题。我在谷歌上搜索的所有内容都是安排重复性任务，或执行一次性操作以自动构建优化计划的算法。

4

2 回答 2

3

您只需要跟踪每个排他性资源的开始和结束时间。问题中的数据存储实际上是容易的部分 - 困难的部分是制作查询以查找时间间隔内的冲突。

如果我的逻辑在 21 小时后是正确的，那么下面的伪代码应该检查会议冲突。

# Set up your proposed meeting
proposed.start = <thursday, 1pm>
proposed.end   = <thursday, 2pm>

# Look for meetings that intersect with or straddle proposed meeting
conflicts = <SELECT * FROM meeting WHERE
             meeting.start BETWEEN proposed.start AND proposed.end OR
             meeting.end   BETWEEN proposed.start AND proposed.end OR
             meeting.start <= proposed.start AND meeting.end >= proposed.end>


if conflicts.length > 0:
   # We have a conflict!
于 2009-10-08T04:00:23.830 回答
1

要自动优化学校或大学的时间表（甚至是其他问题），请查看以下 Java 工具：

TimeFinder , UniTime或Drools 求解器

用户交互的问题并不像你解释的那样容易解决，因为可能还有其他违反约束的情况（时间表可能会变得更加复杂）。

首先，我只允许时间表人员访问/更改时间表数据。

其次，我将为每个时间表创建一个独立的解决方案，然后使用上面建议的工具优化这个解决方案。然后可以将解决方案存储到数据库中，并且时间表可以使用它们来进一步优化时间表或与其他解决方案进行比较。

于 2010-01-10T12:26:39.250 回答