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

Question

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

我已经针对N * N数独，N皇后和班级调度问题进行了这种归约，但是我对如何将流水车间转换为SAT存在一些问题。

SAT问题看起来像这样：

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

我使用遗传算法创建了自己的求解器，能够找到解决方案并证明何时没有解决方案。现在，我在Flow Shop等其他NP问题上进行尝试。

流水车间调度问题是车间或小组车间的一类调度问题，在流水车间中，流控制应允许对每个作业进行适当的排序，并在一组机器或其他资源上进行处理1,2，... ，m符合给定的加工订单。

特别是希望以最少的空闲时间和最少的等待时间来保持连续的处理任务流。

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

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

（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 to Boolean satisfiability [Polynomial-time reduction] part 2

Answer 1

我会这样处理：

您在每个机器的每个可能时间都有一个用于每个资源使用的布尔变量（当然，这要求时间是有限且离散的，所以我假设是整数）。

因此，您获得像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 ...

Answer 2

我正在使用c＃;我通过以下if语句处理该结果：（EndTime = StartTime + Duration）

Answer 3

首先阅读此页：https://en.wikipedia.org/wiki/Job_shop_scheduling