哪些算法可以解决这个约束规划问题？

Question

我需要解决工作情感问题，并且我想找到更有效的算法来解决这个问题。

假设有一些工人可以完成多种任务。我们还有一系列必须每周完成的任务。每个任务都需要一些时间。每项任务都必须由专人承担。每个工人每周必须工作 N 到 P 小时。

问题的第一部分似乎是约束规划算法的良好候选者。

但问题就复杂了：因为工人可以执行不同的任务，所以他们也可能有偏好（或愿望）。如果一个人想满足所有人的所有愿望，那么问题就没有解决方案（限制太多）。

所以我需要一个算法来解决这个问题。如果完美的轮子已经存在，我不想重新发明轮子。

该算法必须是公平的（如果可以定义这个词），因此例如我应该能够添加一个约束，例如“尝试满足每个人至少一个愿望”。我不确定这个问题可以通过此处描述的约束层次结构方法来解决： 约束等级. 。事实上，我不确定“公平”和愿望是否可以通过此类算法的有效约束来表达。

有约束规划专家给我一些建议吗？我是否需要开发一个带有一些启发式方法的新轮子，而不是使用高效的 CP 算法？

谢谢 ！

Answer 1

您的问题足够复杂，可能需要将通用解决方案制定为 线性整数 问题。另一方面，如果您能够放宽某些要求，您也许可以使用更简单的方法。例如， 二分匹配 将允许您安排多个工人执行多个工作，甚至可以处理偏好，但无法强制执行一般的“公平”约束。参见例如这 相关SO问题. 顶点着色 具有执行工作分离约束的有效算法。

其他海报也提到了 单纯形 和 车间作业调度. 。Simplex 是一种优化算法 - 它遍历解决方案空间，寻求最大化某些目标函数。制定目标函数当然可以完成，但并不简单。经典的作业车间调度（例如二分匹配）可以模拟问题的某些方面，但不是全部。例如，没有优先级限制。有一些扩展版本可以处理一些约束，例如对任务设置时间限制。

如果您对现有的实现感兴趣，Python 网络x 图书馆有一个实施 这个匹配算法. 。可能感兴趣的开源时间表程序的示例是 塔布利克斯.

Answer 2

我已经制定了时间表，这可以被视为约束规划的一种形式。您有硬（不可侵犯）约束和软约束（例如间隔偏好）。

线性整数规划通常在超过 30 个变量后就变得毫无用处，对于单纯形也是如此。

通过启发式算法的特定领域优化，找到了解决方案。

使用的启发式算法是 模拟退火, 遗传算法, 元启发式的 算法和类似，但最终最好的结果是由定制的“智能”域提供的 贪心搜索 算法。

基本上，您可能会通过这里的一种启发式方法获得一些不错的结果，但主要问题是能够辨别问题何时受到过度约束。

一个很棒的开源研究工具是 启发式实验室.

Answer 3

我同意在这里已经提出了什么。然而，非常大的规模的MIP（混合整数规划问题）（远远超出了30个变量！）的实际解决了目前由于商业代码（随心换，的Cplex，Gurobi）或开源（游戏币或者/ CBC）。此外，花式造型语言，如OPL工作室，GAMS，AMPL，翻牌......让轻松地编写数学模型，而不是使用的API。

可以利用NEOS服务器（ HTTP：//neos.mcs .anl.gov /近地天体/解算器/ index.html的）尝试非常esaily不同的MIP可用。您在AMPL格式发送您的模型。虽然AMPL是作为一个自由有限版本，NEOS可以处理无限实例。

建模语言也存在于CP（COMET / OPL工作室）和本地搜索（COMET）。

随时通过我的网站www.rostudel.com取得联系我（“接触”页）

大卫

Answer 4

这听起来像作业车间调度。