我需要解决工作影响问题，我想找到更有效的算法来解决这个问题。
假设有一些 worker 可以完成多种任务。我们还有一组必须每周完成的任务。每个任务都需要一些时间。每个任务都必须由某人承担。每个 worker 每周必须工作 N 到 P 个小时。
问题的第一部分似乎很适合约束规划算法。
但问题是复杂的:因为一个 worker 可以完成不同的任务，他们也可能有偏好(或愿望)。如果一个人想要满足每个人的所有愿望，那么这个问题就没有解决方案(太多的限制)。
所以我需要一个算法来解决这个问题。如果完美的轮子已经存在，我不想重新发明轮子。
算法必须是公平的(如果可以定义这个词的话)所以例如我应该能够添加一个约束，例如“尝试满足每个人至少一个愿望”。我不确定这个问题是否可以通过此处描述的约束层次结构方法来解决:Constraint Herarchies .事实上，我不确定“公平”和愿望是否可以通过此类算法的有效约束来表达。
有没有约束规划专家给我一些建议？我是否需要使用一些启发式方法而不是使用高效的 CP 算法来开发新的轮子？
谢谢!
最佳答案
您的问题非常复杂，一般解决方案可能需要制定为 linear-integer问题。另一方面，如果您能够放宽某些要求，则可以使用更简单的方法。例如，bipartite matching将允许您安排多个 worker 从事多项工作，甚至可以处理偏好，但无法强制执行一般的“公平”约束。参见例如这个related SO question . Vertex colouring具有执行作业分离约束的有效算法。
其他发贴者提到了simplex和 job shop scheduling . Simplex 是一种优化算法 - 它遍历解决方案空间以寻求最大化某些目标函数。制定目标函数当然可以完成，但并非易事。经典的作业车间调度，如二分匹配，可以模拟问题的某些方面，但不是全部。例如，没有优先约束。有一些扩展版本可以处理一些约束，例如对任务设置时间限制。
如果您对现有的实现感兴趣，Python networkx库有一个实现 this matching algorithm .可能感兴趣的开源时间表程序示例是 Tablix。 .
关于algorithm - 哪些算法)可以解决这个约束规划问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1251079/