这里是我的第一个问题的延续（Flow店布尔可满足性[多项式时间缩短] ）。

由于什么是错的，我也没成功，知道在什么地方。我问了计算器的主人的帮助下再次：）

对于和行动的是我对现在的：

在我有谁是这样的输入文件：

  3 2
1 1 1
1 1 1
 

     

谁再presents：3的工作，2店（机），并在每个车间（机）每个作业的时间。而且我要为论文的问题，找到最佳C_max值。

因此​​，例如，它应该在输出给这个结果（对不起paint.exe XD）：

所以，读论文的文件，我创建2个结构：资源和谁的问题是这样的：

  typedef结构_resource {

   无符号整型numShop;
   无符号整型numJob;
   无符号整型值;

}资源;

typedef结构_problem {

   无符号整型nbShops;
   无符号整型nbJobs;
   资源**资源;

} 问题;
 

读数是好的，而我在输入文件中的所有信息在我的结构。

我想要改造这个优化问题（找到最佳的解决方案）成为决策问题（这是一个可能的解决方案？），为此，我的目标是把车间作业/流水作业问题转化为SAT问题。

在我的目标是如下：我把C_max的值作为固定的，我创建了一个SAT的问题，我会降低C_max直到SAT解算器说，这个问题无解。上次值与解决方案将是最佳值。

由于@Jens Schauder不，我有一个解决方案的开始。我的布尔变量是这样的： s_1_2_3有一个被使用在机器2，从时间开始的意思资源3

所以，如果我有Ĵ工作，男店，我把我的C_max的值C，我会肯定的：Ĵ* M * C 布尔变量

的问题的，因为现在我的SAT问题是错误的。给出的解决方案是不行的。

下面是我对现在的约束条件：（V表示'或'，另：'和'）

这意味着这份工作，我可以在只有1一时间k店

这意味着商店Ĵ只能处理1个职位空缺的时间k。

这意味着如果该作业的持续时间大于1，它必须是contineous。因此，如果一个变量为真，后等，直到任务的持续时间结​​束时也必须是真实的。

我真的不知道，如果我是对这个问题的提法，或/和，如果我忘了约束。

现在，我心里也车间（流水作业的基本相同，其中的作业必须在每个商店的相同顺序）

对不起，很大的问题，但对于此类问题，最好是所有的细节就知道说些什么。

修改

我会加的3约束上上面的源$ C ​​$ C，或许真的是错了里面，我看不出有什么...

约束N°1：

  / **的工作，我可以在只有1个店一时间k * /
无符号整型writeConstraintOne（问题*问题，无符号整型timeMax，FILE *文件，烧焦forReal）{

无符号整型最后= 0;
unsigned int的最大值= getNbVariables（问题，timeMax）;

为（unsigned int类型I = 0; I＆LT; problem-＆GT; nbShops;我++）{

  为（unsigned int类型L = 0; L＆LT; problem-＆GT; nbShops，L ++）{

    为（unsigned int类型J = 0; J＆LT; problem-＆GT; nbJobs; J ++）{

     为（unsigned int类型T = 0; T＆LT; timeMax;吨++）{

      如果（我== L）继续;

      / **我们拿到的S_i_j_t * /
      unsigned int类型A = getIdOfVariable（的问题，I，J，T，timeMax）;

      / **我们拿到的S_l_j_t * /
      unsigned int类型B = getIdOfVariable（的问题，L，J，T，timeMax）;

      最后++;

      / *这fonction会或计数的子句的数目，
       *或文件中写他们。 * /
      如果（forReal == 1）{

          / *它重新presents -A =＆GT; B * /
          fprintf中（文件 - ％D  - ％D 0 \ N，A，B）;
      }
       }
      }
    }
   }
   返回决赛;
 }
 

约束N°2：

  / **店Ĵ只能处理1的时间k工作。 * /
无符号整型writeConstraintTwo（问题*问题，无符号整型timeMax，FILE *文件，字符forReal）{

无符号整型最后= 0;
unsigned int的最大值= getNbVariables（问题，timeMax）;

为（unsigned int类型I = 0; I＆LT; problem-＆GT; nbShops;我++）{

  为（unsigned int类型L = 0; L＆LT; problem-＆GT; nbJobs，L ++）{

    为（unsigned int类型J = 0; J＆LT; problem-＆GT; nbJobs; J ++）{

     为（unsigned int类型T = 0; T＆LT; timeMax;吨++）{

      如果（j == L）继续;

      / **我们拿到的S_i_j_t * /
      unsigned int类型A = getIdOfVariable（的问题，I，J，T，timeMax）;

      / **我们拿到的S_i_l_t * /
      unsigned int类型B = getIdOfVariable（的问题，I，L，T，timeMax）;

      最后++;

      / *这fonction会或计数的子句的数目，
       *或文件中写他们。 * /
      如果（forReal == 1）{

          / *它重新presents -A =＆GT; B * /
          fprintf中（文件 - ％D  - ％D 0 \ N，A，B）;
      }
       }
      }
    }
   }
   返回决赛;
 }
 

约束N°3：

  / **如果作业的持续时间超过1，它必须contineous。
 *因此，如果一个变量为真，后等，直到持续时间的结束
 *的任务也必须是真实的。 * /
无符号整型writeConstraintThree（问题*问题，无符号整型timeMax，FILE *文件，烧焦forReal）{

无符号整型最后= 0;
unsigned int的最大值= getNbVariables（问题，timeMax）;

为（unsigned int类型I = 0; I＆LT; problem-＆GT; nbShops;我++）{

    为（unsigned int类型J = 0; J＆LT; problem-＆GT; nbJobs; J ++）{

     为（unsigned int类型T = 0; T＆LT; timeMax;吨++）{

     为（无符号​​整数K = 0; K＆LT; problem-个资源[I] [J]。价值-1; k ++）{

      如果（K = = t）的继续;

      / **我们拿到的S_i_j_t * /
      unsigned int类型A = getIdOfVariable（的问题，I，J，T，timeMax）;

      / **我们拿到的S_i_j_k * /
      unsigned int类型B = getIdOfVariable（的问题，I，J，K，timeMax）;

      最后+ = 2;

      / *这fonction会或计数的子句的数目，
       *或文件中写他们。 * /
      如果（forReal == 1）{

          fprintf中（文件 - ％D 0 \ N，B，A）;
          fprintf中（文件 - ％D 0 \ N，A，B）;
      }
       }
      }
    }
   }
   返回决赛;
 }
 

解决方案

有一个错误在头两个公式你给：你缺少一个L = J 1。当然，我不知道，如果这个bug是在code为好。

我想你也缺少约束，上面写着：每个职业都有发生每台机器上至少一次（你只有最多一次部分）

在用于调试这更提示：尝试用最简单的例子是可能的：1机1的工作;携手从那里到2台，1个作业和1机2的工作。

使用2台和三份工作，还有就是多，可以去错。

here is the continuity of my first question (Flow Shop to Boolean satisfiability [Polynomial-time reduction]).

Because something is wrong and I didn't success to know where exactly. I ask for the help of StackOverFlow's masters once again :)

For the sum-up of what I have for now :

I have input file who look like this :

3 2
1 1 1
1 1 1

Who represents : 3 jobs, 2 shops (machines), and the duration of each job on each shop (machine). And I want for theses problems, to find the optimum C_max value.

So for example, it should give in output this result (sorry for paint.exe xD):

So to read theses files, I create 2 structures : Resource and Problem who look like this :

typedef struct _resource {

   unsigned int numShop;
   unsigned int numJob;
   unsigned int value;

} Resource;

typedef struct _problem {

   unsigned int nbShops;
   unsigned int nbJobs;
   Resource** resources;

} Problem;

The reading is okay, and I have all the informations in the input files inside my structures.

I want to transform this optimal problem (find the best solution) into a decision problem (is THIS a possible solution ?) and for this, my goal is to transform the JobShop/FlowShop problem into a SAT problem.

My goal is as follow : I put the value of C_max as fixed, I create a SAT problem, and I will decrease the C_max until the SAT-solver says that the problem has no solution. The last-value with a solution will be the optimal value.

Thanks to @Jens Schauder, I have the beginning of a solution. My booleans variables are like this: s_1_2_3 with the meaning resource one gets used at machine 2 starting from time 3.

So if I have J jobs, M shops and I put my C_max to the value C, I will have for sure : J * M * C booleans variables.

Problem: for now my SAT problem are wrong. The solution given is not okay.

Here are the constraints that I have for now : ( V means 'OR', the other : 'And')

Which means that the job i can be on only 1 shop for a time k

Which means that a shop j can handle only 1 job for a time k.

Which means that if the job has a duration more than 1, it has to be contineous. So if one variable is true, the other after until the end of duration of the task have to be true also.

I'm not really sure if I'm right about the formulation of the problem, or/and if I forgot a constraint.

For now, I mind also Job Shop (Flow Shop is basically the same where the jobs have to be in the same order on every shops)

Sorry for the very big question, but for this kind of problem, it's better to have all the details to know what is it about.

EDIT

I will add the source code of the 3 contraints above, maybe something is wrong inside and I don't see what...

Constraint n°1 :

/** the job i can be on only 1 shop for a time k */
unsigned int writeConstraintOne(Problem* problem, unsigned int timeMax, FILE* file, char forReal) {

unsigned int final = 0;
unsigned int max = getNbVariables(problem,timeMax);

for(unsigned int i = 0; i < problem->nbShops; i++) {

  for(unsigned int l = 0; l < problem->nbShops; l++) {

    for(unsigned int j = 0; j < problem->nbJobs; j++) {

     for(unsigned int t = 0; t < timeMax; t++) {

      if(i == l) continue;

      /** We get the S_i_j_t */
      unsigned int A = getIdOfVariable(problem,i,j,t,timeMax);

      /** We get the S_l_j_t */
      unsigned int B = getIdOfVariable(problem,l,j,t,timeMax);

      final++;

      /* This fonction will or count the number of clauses, 
       * or write them inside the file. */
      if(forReal == 1) {

          /* It represents -A => B */
          fprintf(file,"-%d -%d 0\n",A,B);
      }
       }
      }
    }
   }
   return final;
 }

Constraint n°2 :

/** shop j can handle only 1 job for a time k. */
unsigned int writeConstraintTwo(Problem* problem, unsigned int timeMax, FILE* file, char forReal) {

unsigned int final = 0;
unsigned int max = getNbVariables(problem,timeMax);

for(unsigned int i = 0; i < problem->nbShops; i++) {

  for(unsigned int l = 0; l < problem->nbJobs; l++) {

    for(unsigned int j = 0; j < problem->nbJobs; j++) {

     for(unsigned int t = 0; t < timeMax; t++) {

      if(j == l) continue;

      /** We get the S_i_j_t */
      unsigned int A = getIdOfVariable(problem,i,j,t,timeMax);

      /** We get the S_i_l_t */
      unsigned int B = getIdOfVariable(problem,i,l,t,timeMax);

      final++;

      /* This fonction will or count the number of clauses, 
       * or write them inside the file. */
      if(forReal == 1) {

          /* It represents -A => B */
          fprintf(file,"-%d -%d 0\n",A,B);
      }
       }
      }
    }
   }
   return final;
 }

Constraint n°3 :

/** if the job has a duration more than 1, it has to be contineous. 
 *  So if one variable is true, the other after until the end of duration 
 *  of the task have to be true also. */
unsigned int writeConstraintThree(Problem* problem, unsigned int timeMax, FILE* file, char forReal) {

unsigned int final = 0;
unsigned int max = getNbVariables(problem,timeMax);

for(unsigned int i = 0; i < problem->nbShops; i++) {

    for(unsigned int j = 0; j < problem->nbJobs; j++) {

     for(unsigned int t = 0; t < timeMax; t++) {

     for(unsigned int k = 0; k < problem->resource[i][j].value-1; k++) {

      if(k == t) continue;

      /** We get the S_i_j_t */
      unsigned int A = getIdOfVariable(problem,i,j,t,timeMax);

      /** We get the S_i_j_k */
      unsigned int B = getIdOfVariable(problem,i,j,k,timeMax);

      final+= 2;

      /* This fonction will or count the number of clauses, 
       * or write them inside the file. */
      if(forReal == 1) {

          fprintf(file,"-%d %d 0\n",B,A);
          fprintf(file,"-%d %d 0\n",A,B);
      }
       }
      }
    }
   }
   return final;
 }

解决方案

There is a bug in the first two equation you are giving: you are missing an l != j. Of course I have no idea if this bug is in your code as well.

I think you are also missing a constraint that says: every job has to happen on every machine at least once (you only have the at most once part).

On more hint for debugging this: try it with the simplest examples that are possible: 1 machine, 1 job; and work from there to 2 machines, 1 job and 1 machine 2 jobs.

With 2 machines and three jobs, there is to much that can go wrong.