2

我需要解决一个工作做作的问题,我想找到最好的有效算法来解决这个问题。

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

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

但这里是复杂的:因为工人可以做不同的任务,他们也可能有偏好(或愿望)。如果一个人想要满足所有人的所有愿望,那么问题就没有解决方案(约束太多)。

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

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

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

谢谢 !

4

4 回答 4

8

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

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

如果你对现有的实现感兴趣,Python networkx库有这个匹配算法的实现。Tablix是一个可能感兴趣的开源时间表程序示例。

于 2009-08-09T12:10:44.733 回答
2

我同意这里提出的建议。然而,由于商业代码(Xpress、Cplex、Gurobi)或开源代码(Coin-Or/Cbc),现在实际上解决了非常大(远远超过 30 个变量!)的 MIP(混合整数规划问题)。此外,OPL Studio、GAMS、AMPL、Flop 等花哨的建模语言允许轻松编写数学模型,而不是使用 API。

您可以利用 NEOS 服务器 ( http://neos.mcs.anl.gov/neos/solvers/index.html ) 尝试非常不同的可用 MIP。您以 AMPL 格式发送模型。尽管 AMPL 是免费的受限版本,但 NEOS 可以处理无限的实例。

CP(COMET / OPL Studio)和本地搜索(COMET)也存在建模语言。

请随时通过我的网站 www.rostudel.com(“联系”页面)与我联系

大卫

于 2009-09-21T12:19:01.893 回答
2

我已经完成了时间表,这可以被认为是约束编程的一种形式。您有硬(不可侵犯)约束和软约束(例如间隔偏好)。

线性整数规划通常在超过 30 个变量后变得无用,这也可以说是单纯形。

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

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

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

HeuristicLab是一个伟大的研究开源工具。

于 2009-08-09T12:48:29.580 回答
0

这听起来像作业车间调度

于 2009-08-09T11:17:29.770 回答