Flow Shop 到布尔可满足性 [多项式时间缩减]

我联系您是为了了解“如何将流水车间调度问题”转化为布尔可满足性。

我已经对 N*N 数独、N 皇后和班级调度问题进行了此类简化，但我对如何将流水车间转换为 SAT 有一些问题。

SAT 问题如下所示：

目标是：使用不同的布尔变量，找到每个变量的影响以使“句子”为真。 （如果可以找到解决方案）。

我使用遗传算法创建自己的求解器，能够找到解决方案并证明何时没有解决方案。现在，我尝试解决不同的 NP 问题，例如 Flow Shop。

流水车间调度问题是车间或集团车间的一类调度问题，其中流程控制应能够对每个作业以及在一组机器或其他资源上进行的处理进行适当的排序 1,2,...,m遵守给定的加工指令。

尤其需要以最少的空闲时间和最少的等待时间来维持处理任务的连续流。

流水车间调度是作业车间调度的一种特殊情况，其中对所有作业执行的所有操作都有严格的顺序。

流水车间调度既可以应用于生产设施，也可以应用于计算设计。

(http://en.wikipedia.org/wiki/Flow_shop_scheduling http://en.wikipedia.org/wiki/Flow_shop_scheduling)

结果是一系列将经历每个研讨会的作业，图形结果将如下所示：

因此，为了表示流水作业实例，在输入中我有这样的文件：

2 4
4 26 65 62 
63 83 57 9 

这个文件意味着我有 2 个商店和 4 个作业，以及每个作业在每台机器上的所有持续时间。

目标：找到最小化 C_max 的序列，C_max 是最后一台机器上最后一个作业的结束日期（如果您愿意）。

我的 Flow-Shop 目前非常简单，但我不知道如何将它们形式化，以便创建一个 CNF 文件来执行我的 SAT 求解器。

如果你们中的一个人有一些想法：文章？一个想法的开始？

这个问题的下一部分：Flow/Job Shop 到布尔可满足性 [多项式时间缩减] 第 2 部分 https://stackoverflow.com/questions/29651856/flow-job-shop-to-boolean-satisfiability-polynomial-time-reduction-part-2

我会这样处理：

对于每台机器上每个可能的时间开始的每个资源使用情况，都有一个布尔变量（当然，这要求时间是有限的和离散的，所以我假设是整数）。

所以你会得到像这样的变量s_1_2_3其含义是资源从第二台机器 3 开始在机器 2 上使用。

现在您可以根据这些变量制定各种条件。喜欢：

• 每个资源一次只能在一台机器上使用
• 每台机器一次只能处理一种资源
• 机器步骤必须按顺序发生（机器 1 需要处理资源 x，然后机器 2 才能完成其工作）

警告：即使对于小问题，这也会造成HUGE布尔表达式的数量。

正如 @gwilkins 提到的，您需要将优化问题转换为布尔问题。我会遵循他的方法：找到您愿意接受的最大时间并解决该时间限制（这实际上限制了变量的数量）。

您还可以从应该有解决方案的事物（例如添加的所有作业的时间）和自然下限的事物（最长作业所需的时间）开始，然后通过分割间隔找到最佳解决方案。

再说一次：这可能会表现得非常糟糕，但它应该提供正确的解决方案。

使用此变量制定的约束示例：

机器 1 必须先处理资源 x，然后机器 2 才能完成其作业（假设作业长度为 1）：

(S_x_1_1 and ! S_x_2_1) 
or (S_x_1_2 and ! S_x_2_1 and ! S_x_2_2) 
or (S_x_1_3 and ! S_x_2_1 and ! S_x_2_2 and ! S_x_2_3)
or ...