哪种算法可以解决这种约束编程问题？

Question

我需要解决工作影响问题,我想找到优选的有效算法来解决这个问题.

假设有些工人可以做几种任务.我们还有一个必须每周完成的任务池.每项任务都需要一些时间.每项任务都必须由某人完成.每个工人必须每周工作N小时.

问题的第一部分似乎是约束编程算法的良好候选者.

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

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

算法必须公平(如果可以定义这个词),例如我应该能够添加一个约束,例如"试着满足每个人至少一个愿望".我不确定这个问题可以通过这里描述的Constraint Hierarchies方法解决:Constraint Herarchies.事实上,我不确定"公平"和愿望可以通过这类算法的有效约束来表达.

是否有约束编程专家给我一些建议？我是否需要使用一些启发式方法开发新的轮子而不是使用有效的CP算法？

谢谢 !

Answer 1

你的问题很复杂,一般的解决方案可能需要将其作为线性整数问题.另一方面,如果您能够放宽某些要求,您可以使用更简单的方法.例如,二分匹配允许您将多个工作程序安排到多个作业,甚至可以处理首选项,但无法实施一般的"公平"约束.参见例如这个相关的SO问题.顶点着色具有用于实施作业分离约束的有效算法.

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

如果您对现有实现感兴趣,Python networkx库可以实现此匹配算法.Tablix是一个可能感兴趣的开源时间表程序的一个例子.