其中算法（S）可以解决这个约束规划问题？ [英] Which algorithm(s) can solve this constraint programming problem?

问题描述

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

I need to solve a job affectation problem and I would like to find preferably efficient algorithms to solve this problem.

比方说，有一些工人，可以做几种任务。我们也有任务，必须每星期做池。每个任务需要花费一些时间。每个任务必须要采取的某人。每个工人必须到n之间一个p小时，每周工作。

Let's say there are some workers that can do several kind of tasks. We also have a pool of tasks which must be done every week. Each task takes some time. Each task must be taken by someone. Each worker must work between N an P hours a week.

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

This first part of the problem seems to be a good candidate for a constraint programming algorithm.

但这里是复杂：因为工人可以做不同的任务，他们可能也有preferences（或愿望）。如果一个人想满足大家有没有解决的问题（太多的约束）所有的愿望。

But here is the complication: because a worker can do different tasks they may also have preferences (or wishes). If one want to satisfy all wishes for everyone there is no solution to the problem (too many constraints).

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

So I need an algorithm to solve this problem. I don't want to reinvent the wheel if the perfect wheel already exists.

该算法必须是公平的（如果可以定义这个词），因此，例如我应该能够加入像尽量满足每个人至少有一个心愿的约束。我不知道，这个问题可以通过在这里描述的约束层次的方法来解决：约束Herarchies 的。事实上，我不知道，公平和愿望可以为这一类的算法pssed通过有效的约束EX $ P $。

The algorithm must be fair (if one can define this word) so for example I should be able to add a constraint like "try to satisfy at least one wish per people". I'm not sure that this problem can be solved by Constraint Hierarchies methods described here: Constraint Herarchies. In fact I'm not sure that "fairness" and wishes can be expressed by valid constraints for this category of algorithms.

是否有约束规划专家给我一些建议？我需要开发使用高效CP算法的一个新的轮毂与一些启发呢？

Is there a constraint programming expert to give me some advices ? Do I need to develop a new wheel with some heuristics instead of using efficient CP algorithms ?

谢谢！

推荐答案

您的问题是足够复杂，一个通用的解决方案可能需要制定为的线性整数的问题。如果在另一方面，你可以放松有一定的要求，你可以用一个简单的方法。例如，双边匹配将允许您安排多个工人多工作，甚至可以处理preferences，但将无法执行一般的公平的约束。例如参见该<一href="http://stackoverflow.com/questions/1221990/hungarian-algorithm-and-multiple-factors/1222263#1222263">related SO质疑。 顶点着色具有有效的算法执行工作分离制约。

Your problem is complex enough that a general solution will probably require formulating as a linear-integer problem. If on the other hand you are able to relax certain requirements, you may be able to use a simpler approach. For example, bipartite matching would allow you to schedule multiple workers to multiple jobs, and can even handle preferences, but would not be able to enforce general 'fairness' constraints. See e.g. this related SO question. Vertex colouring has efficient algorithms for enforcing job separation constraints.

其他海报也提到单纯和的车间作业调度。单是一个优化算法 - 它遍历解空间寻求最大化某些目标函数。制定目标函数当然可以做到，但就是不平凡。古典作业车间调度，如二分匹配，可以模拟你的问题的某些方面，但不是全部。有没有precedence约束，例如。有扩展版本，可以处理一些约束，例如放置时间界限的任务。

Other posters have mentioned simplex and job shop scheduling. Simplex is an optimisation algorithm - it traverses a solution space seeking to maximise some objective function. Formulating the objective function can certainly be done, but is non-trivial. Classical job shop scheduling, like bipartite matching, can model some aspects of your problem, but not all. There are no precedence constraints, for example. There are extended versions that can handle some constraints, for example placing time bounds on tasks.

如果你有兴趣在现有实现，Python的 networkx 库拥有的这个匹配算法。一个开放源码的时间表计划可能会感兴趣的一个例子是的Tablix 。

If you're interested in existing implementations, the Python networkx library has an implementation of this matching algorithm. An example of an open source timetabling program that might be of interest is Tablix.

这篇关于其中算法（S）可以解决这个约束规划问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！