我需要解决一个工作情感问题，我想找到最好的高效算法来解决这个问题。哪个算法可以解决这个约束规划问题？
假设有一些工人可以完成几种任务。我们也有每周必须完成的一系列任务。每项任务都需要一些时间。每个任务都必须由某人来完成。每名工作人员必须每周工作N到P小时。
这个问题的第一部分似乎是约束规划算法的一个很好的候选者。
但是，这是复杂的：因为工人可以做不同的任务，他们也可能有偏好（或愿望）。如果一个人想满足所有人的愿望，那么这个问题就没有解决办法（太多的限制）。
所以我需要一个算法来解决这个问题。如果完美的车轮已经存在，我不想重新发明车轮。
该算法必须公平（如果可以定义这个词），例如我应该能够添加一个约束，如“试图满足每个人至少一个愿望”。我不确定这个问题可以通过这里描述的约束层次结构方法来解决：Constraint Herarchies。事实上，我不确定“公平”和愿望可以通过对这类算法的有效约束来表达。
有没有一个约束编程专家给我一些建议？我是否需要用一些启发式方法开发新车轮，而不是使用高效的CP算法？
谢谢！
您的问题很复杂，一般的解决方案可能需要制定一个linear-integer问题。另一方面，如果您可以放松某些要求，则可以使用更简单的方法。例如，bipartite matching将允许您安排多个工作人员进行多项工作，甚至可以处理偏好，但无法执行一般的“公平性”约束。见例如这related SO question。 Vertex colouring具有强制执行作业分离约束的高效算法。
其他海报已提及simplex和job shop scheduling。 Simplex是一种优化算法 - 它遍历一个寻求最大化某些目标函数的解决方案空间。制定目标函数当然可以完成，但不是微不足道的。经典的作业车间调度，如双向匹配，可以模拟问题的某些方面，但不是全部。例如，没有优先约束。有扩展版本可以处理一些限制，例如在任务上放置时间限制。
如果您对现有的实现感兴趣，Python networkx库的实现为this matching algorithm。可能感兴趣的开源时间表程序的一个例子是Tablix。
这听起来像是job shop scheduling。
我已经完成了时间表，这可以被认为是一种约束规划的形式。您有严格的（不可侵犯的）约束和软约束（如间隔首选项）。
线性整数规划通常在超过30个变量后变得毫无用处，这也可以说是单纯形。
这是针对找到解决方案的启发式算法的特定领域优化。
使用了启发式算法是simmulated annealing，genetic algorithms，metaheuristic算法和类似，但最终的最好的结果是由一个“智能”域中提供定制greedy search算法。
基本上，你可能会得到一些体面的结果，其中一种启发式方法在这里，但主要问题是能够识别问题是否过度约束。
研究的一个很好的开源工具是HeuristicLab。
我同意这里提出的建议。然而，由于商业代码（Xpress，Cplex，Gurobi）或开源（Coin-Or/Cbc），现在几乎解决了非常大的MIP（混合整数编程问题）（远远超过30个变量！此外，诸如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（“接触”页）
大卫
取得联系我