2

我正在寻找一种可以执行以下操作的算法（希望是 .net 实现）：我有以下数据：

  1. 一份技术人员名单，每个人都有不同的技能（可能不止一个）。
  2. 服务时间窗口（例如 8-12）
  3. 此时间窗口内所有先前安排的工作的列表（每个都有它所需的技能）

给定一份新工作（具有所需技能），我应该检查新工作是否并分配给任何可用的技术人员（只要他们的技能支持，以前的工作可以在技术人员之间转移）。也不能超过服务时间窗口，因此不能将 1 小时的工作安排在 11:30

最初我考虑做装箱 FFD 变体是我预装了箱子（技术人员），在寻找一个箱子来放置工作时，我也会检查技能匹配。作业列表将包含所有以前的作业和新的作业（按大小降序排序），并且代码停止，因为作业无法放置在任何 bin 中，或者它在所有作业都安排好后完成。

理论上它可以工作，但后来我想到了以下场景：

  • 技术员：T1（具有技能 S1 和 S2）、T2（具有技能 S2 和 S3）
  • 以前的工作：J1（需要技能 S2），整个时间窗口的持续时间。
  • 新工作 J2（需要技能 S1）

可能会发生这样一种情况，即 J1 被分配给 T1，然后 J2 无处安放。

所以我考虑在工作列表中添加第二个排序：工作将按大小降序排序，然后按实际可以执行它们的资源数量升序排序。这将使 J2 排在第一位，因为可以做到这一点的技术人员较少。

是否有解决此问题的特定算法或者我的方法是否足够好？

谢谢

4

1 回答 1

2

看看约束满足问题。您的问题属于该类别。

此外，为了快速回顾问题类和一些玩具示例，请查看此处。

这是幻灯片的来源（公开）章节。

您需要的约束或多或少如下（以非正式方式编写）：

  1. 一个问题需要一套技能来解决。
  2. 一个问题有一个需要解决的时间窗口。
  3. 只有当技术人员具备所有需要的技能时，才能将问题分配给技术人员。
  4. 只有当技术人员的时隙大于或等于解决问题所需的时间时，才能将问题分配给技术人员。

然后是关于技术人员和可用时间段的限制，最终还有关于技术人员和位置（应该解决问题的地方）的限制。

于 2015-04-30T07:52:44.133 回答