技术人员时间窗口调度算法

Question

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

1. 一份具有不同技能的技术人员列表(可能不止一名)。
2. 服务时间窗口(例如 8-12)
3. 在此时间范围内之前安排的所有作业的列表(每个作业都有其所需的技能)

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

最初，我考虑做垃圾箱包装 FFD 变体，我预先装载垃圾箱(技术人员)，并且在寻找垃圾箱来放置工作时，我还会检查技能匹配。作业列表将包含所有以前的作业和新作业(按大小降序排序)，并且代码会因为无法将作业放入任何垃圾箱而停止，或者在所有作业都安排好后完成。

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

• 技术人员:T1(具备技能 S1 和 S2)、T2(具备技能 S2 和 S3)
• 之前的工作:J1(需要技能 S2)，整个时间窗口的持续时间。
• 新工作 J2(需要技能 S1)

可能会发生这样的情况:J1 被分配给 T1，然后 J2 没有地方可以容纳。

因此，我考虑在作业列表中添加第二种排序:作业将按大小降序排序，然后按实际可以完成这些任务的资源数量升序排序。这将使 J2 被首先安排，因为能够执行此操作的技术人员较少。

是否有特定的算法可以解决这个问题，或者我的方法足够好吗？

谢谢

Answer 1

看看Constraint Satisfaction Problems 。你的问题就属于这一类。

此外，要快速回顾问题类和一些玩具示例，请查看 here .

This是幻灯片来源的(公开的)章节。

您需要的约束或多或少如下(以非正式方式编写):

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

然后是关于技术人员和可用时间段的限制，最终是关于技术人员和位置(应该解决问题的位置)的限制。