流水车间到布尔可满足性[多项式时间减少] [英] Flow Shop to Boolean satisfiability [Polynomial-time reduction]

问题描述

我为了得到一个想法上与您联系如何改造一个流水车间调度问题变成了布尔可满足性。

I contact you in order to get an idea on "how to transform a flow shop scheduling problem" into a boolean satisfiability.

我已经做了这样减少了A N * N的数独，一个N皇后与一类调度问题，但我对如何在流水车间改造成SAT一些问题。

I already done such reduction for a N*N Sudoku, a N-queens and a Class scheduling problem, but I have some issue on how to transform the flow shop into SAT.

一个SAT问题是这样的：

a SAT problem looks like this :

的目标是：用不同的布尔变量，以找到每一个变量的做作，以使句子如此。 （如果找到一个解决方案是可能的）。

The goal is : with different boolean variables, to find an affectation of every variable in order to make the "sentence" true. (If finding a solution is possible).

创建我自己的求解器遗传算法能够找到一个解决方案，以证明时，有没有。而现在，我尝试在不同的NP-问题，如流水车间。

I create my own solver with genetic algorithm able to find a solution and to prove when there is none. And now, I try it on different NP-problems, like Flow Shop.

流水车间调度问题是一类排序问题的研讨会或小组店在流量控制应能进行适当的顺序为每个作业和处理上的一组计算机或其他资源1,2，... ，米符合给定的处理命令。

Flow shop scheduling problems are a class of scheduling problems with a workshop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1,2,...,m in compliance with given processing orders.

尤其是处理任务的连续流动的维持希望以最小的空闲时间和最小的等待时间。

Especially the maintaining of a continuous flow of processing tasks is desired with a minimum of idle time and a minimum of waiting time.

流水车间调度车间作业计划的一种特殊情况，还有就是在所有的工作进行严格的顺序排列的所有操作。

Flow shop scheduling is a special case of job shop scheduling where there is strict order of all operations to be performed on all jobs.

流水作业排序可能也适用于生产设施，以计算设计。

Flow shop scheduling may apply as well to production facilities as to computing designs.

（ http://en.wikipedia.org/wiki/Flow_shop_scheduling ）

和结果是一个序列的工作谁去通过每一个车间和图形化的结果将是这样的：

and the result is a sequence of jobs who will go through every workshop and the graphical result will look like this :

因此​​，要重新present流水作业情况下，输入我有这样的文件：

So to represent flow-shop instances, in input I have files like this :

2 4
4 26 65 62 
63 83 57 9 

该文件意味着我有2个商店和4工作岗位，每个工作岗位上的每个机器上的所有的持续时间。

This file means that I have 2 shops and 4 jobs, with all the duration time of each jobs on each machines.

目标：找到谁尽量减少C_max，最后一台机器上的最后一个作业的结束日期，如果你preFER序列

The goal : to find the sequence who minimize the C_max, the end-date of the last job on the last machine if you prefer.

我的流水作业是现在很简单，但我不知道如何将它们以创造一个CNF文件，求解后执行我的SAT正规化。

My Flow-Shop are really simple for now, but I have no idea how to formalize them in order to create a CNF file to execute my SAT solver after.

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

If one of you has some idea : article ? beginning of an idea ?

下一部分的这个问题：<一href="http://stackoverflow.com/questions/29651856/flow-job-shop-to-boolean-satisfiability-polynomial-time-reduction-part-2">Flow/Job店布尔可满足性[减少多项式时间]第2部分

Next part of this question : Flow/Job Shop to Boolean satisfiability [Polynomial-time reduction] part 2

推荐答案

我想接近它是这样的：

您在每个机器对每个资源的使用开始在每一个可能的时间布尔变量（当然需要的时间是有限的，离散的，所以我认为整数）。

You have a boolean variable for each resource usage start at each possible time at each machine (of course that requires that the time is limited and discrete, so I'd assume integers).

所以，你得到像 s_1_2_3 变量有一个被使用在机器2，从第二个3起的意义的资源。

So you get variables like s_1_2_3 with the meaning resource one gets used at machine 2 starting from second 3.

现在你可以制定你的这些变量方面的各种条件。像：

Now you can formulate you various conditions in terms of these variables. Like:

• 每个资源可以只用在一台机器在时间
• 每台机器可以一次只处理一个资源
• 在机器步骤都发生在顺序（机器1需要处理资源X，前机2可以做的工作）

警告：即使是小问题，这将创建一个巨大量的​​布尔EX pressions

Warning: Even for small problems this will create a HUGE amount of boolean expressions.

由于@gwilkins提到你需要转换的优化问题转化为一个布尔问题。而且我按照他的方法：找到一个最大的时候，你愿意接受并解决该时间限制（这实际上限制了变量的数目）。

As @gwilkins mentioned you need to transform the optimization problem into a boolean Problem. And I'd follow his approach: find a maximum time you are willing to accept and solve for that time limit (which actually limits the number of variables).

您也可以开始与东西，应该有一个溶液（像的所有作业的时间加）和东西是一个自然下限和通过分割间隔找到最优解（所需的最长的作业的时间）。

You can also start with something that should have a solution (like the time of all jobs added) and something that is a natural lower limit (the time needed for the longest job) and by splitting the interval find the optimal solution.

再次：这将可能进行真正可怕的，但它应该提供正确的解决方案

Once again: this will probably perform really awful, but it should provide the correct solution.

实例制定这个变量的约束：

Example for a constraint formulated with this variables:

机1具有处理资源的X光机2之前，可以做自己的工作（假设作业长度为1）：

Machine 1 has to process resource x before Machine 2 can do its job (assuming the job has length 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 ...

这篇关于流水车间到布尔可满足性[多项式时间减少]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！