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

Question

我联系您,以便了解"如何将流水车间调度问题转换为布尔可满足性".

我已经为N*N Sudoku,N-queens和Class调度问题做了这样的减少,但是我对如何将Flow shop转换为SAT有一些问题.

SAT问题看起来像这样:

目标是:使用不同的布尔变量,找到每个变量的效果,以使"句子"成立.(如果可以找到解决方案).

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

流水车间调度问题是车间或集团车间的一类调度问题,其中流量控制应能够为每个作业进行适当的排序,并在一组机器或其他资源上进行处理1,2,...,m符合给定的处理订单.

特别是在最小的空闲时间和最少的等待时间的情况下,期望保持连续的处理任务流.

Flow shop调度是作业车间调度的一个特例,其中对所有作业执行所有操作的严格顺序.

流水车间调度也可以应用于计算设计的生产设施.

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

结果是一系列工作将经历每个研讨会,图形结果将如下所示:

所以为了表示flow-shop实例,在输入中我有这样的文件:

2 4
4 26 65 62 
63 83 57 9 

这个文件意味着我有2个商店和4个工作,每个工作的每个工作的持续时间都是.

目标:找到最小化C_max的序列,如果您愿意,可以找到最后一台机器上最后一个作业的结束日期.

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

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

这个问题的下一部分:Flow/Job Shop到布尔可满足性[多项式时间缩减]第2部分

Answer 1

我会这样处理：

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

s_1_2_3因此，您会得到类似于含义资源 1 从第二台 3 开始在机器 2 上使用的变量。

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

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

警告：即使对于小问题，这也会产生大量的布尔表达式。

正如 @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 ...