模拟复杂的工作计划

Question

我有一个真实世界的问题，我正试图表达和自动化。我将其简化和抽象如下：

• 有n个工作场所(P1，P2，…，Pn)。
• 每个地方，Pn都有一把钥匙，Kn。
• 有m个工人(W1，W2，…，Wm)。
• 为了在Pn工作，工人必须持有Kn。
• 每个键都可以由员工持有，也可以留在Exchange，E。
• 工作人员可以随时前往Exchange，以获取一些无人认领的密钥或将一些密钥交给其他人使用。
• 现在，有一个外生的工作时间表，必须完成一个严格的顺序。例如：
  • 2016-04-21 W1必须在P6工作
  • 2016-04-21 W2必须在P3工作
  • **交换所需钥匙**
  • 2016-04-22 W3必须在P3工作
  • 2016-04-22 W2必须在P6工作

• 任何数量的工人都可能不得不在计划的某个时间点在Pn工作，尽管从没有在同一天工作。

我们知道：

• 所有键的起始位置，无论是与工人一起还是在E处
• 每个工人都必须履行的未来工作命令。

所以，我很难模拟这种情况。你能建议我应该考虑的数据结构和算法，以便掌握它，并开始优化每个工人的交换行程吗？

我想把去E的总次数降到最低。第二个目标是确保没有任何工人的旅行次数不成比例。

提前谢谢！！

Answer 1

这个问题在一个关键点上有点模棱两可:我们试图解决哪些元素。我们是在考虑优化资源委派的顺序吗？尽量减少去交易所的旅行？最大限度地提高工作订单吞吐量？

考虑到这一点，我将假设我们可以做任何这些事情的混合，并将答案保持在相当高的水平。

我首先想到的是，这些尝试解决的相互关联的问题主要围绕着依赖关系管理。员工、键和位置可以看作是必须解决的依赖关系，才能完成工作任务。

再到下一个层次，我将看到拓扑排序(https://en.wikipedia.org/wiki/Topological_排序)的适应性。将问题空间建模为一个大图(现代图形数据库也可能是其中一些分析的良好中介)，然后使用各种拓扑排序来解决问题空间的不同方面。

在一个轻微的切线上，这听起来像一个非常有趣的项目。今天，我羡慕你，先生。