3
$\begingroup$

I have a model for the no-wait flow shop scheduling problem, that utilizes the linear ordering variables, and there is a constraint with big-M. When I implement the model in CPLEX OPL, the model assigns zero to all linear ordering variables. I guess the problem is with the big-M constraint, but I don't know how to fix it.

Here is my implementation of the two main constraints in CPLEX OPL. The variable X[i][j] takes 1 if job j is processed after job i in the sequence. The variable C[i][k] shows the completion time of job i on machine k.

In the second constraint (c2) I put 10000 as the big-M (the same value I use in other solvers). The answer turns out to be infeasible due to constraint 1 (c1), since the solver puts all X variables equal to zero (hence violating c1 since 0 = 1).

int NumofJobs = 2;
int NumofMachines = 3;

range n = 1..NumofJobs;
range m = 1..NumofMachines;
dvar boolean X[n][n];
dvar int+ C[n][m];

int TaskTime[n][m] = [[5,6,3], [2,8,9]];;


 minimize (sum (i in n) (C[i][NumofMachines]));

 subject to {

   forall (i in n)
    forall (j in n: j > i)             
      c1: X[i][j] + X[j][i] == 1;

   forall (i in n)
     forall (j in n: j != i)
        forall (k in m)
          c2: C[i][k] + TaskTime[j][k] <= C[j][k] + 10000 * (1 - X[i][j]);
}

I have implemented the same model in other solvers and the problem is solved without any issue.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

It is numerically safer to use a (small) data-dependent value for $M$. For your case, rewrite as:

C[i][k] + TaskTime[j][k] - C[j][k] <= M[i][j][k] * (1 - X[i][j]);

You want to choose $M_{i,j,k}$ to be a (small) upper bound on the left hand side when $X_{i,j}=0$. A good choice is $$M_{i,j,k} = U_{i,k} + T_{j,k} - L_{j,k},$$ where $U_{i,k}$ is a good upper bound on $C_{i,k}$ and $L_{j,k}$ is a good lower bound (0?) on $C_{j,k}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your help. I agree data-dependent values of M will help in terms of efficiency, however, I am wondering why the model cannot be solved with the fixed value. In the example in the OP, there are only two jobs and three machines, but no particular value for M results in solving the instance. $\endgroup$
    – Mostafa
    Jan 8, 2020 at 3:16
  • 1
    $\begingroup$ To diagnose infeasibility, I recommend fixing the variables from a known solution and seeing which constraints are violated. $\endgroup$
    – RobPratt
    Jan 8, 2020 at 3:20
4
$\begingroup$

with CPLEX 12.10 your model gives a solution with objective 3

If you prefer not to use big M, you could use logical constraints and rewrite

forall (k in m)
          c2: C[i][k] + TaskTime[j][k] <= C[j][k] + 10000 * (1 - X[i][j]);

into

forall (k in m)
          c2b:(X[i][j]==1) => (C[i][k] + TaskTime[j][k] <= C[j][k]);

But even better, within OPL CPLEX I encourage you to have a look at the CPOptimizer solver that could tackle your problem even faster.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Alex. This really helps. I also found out that I can use logical or to rewrite the constraint. Which one do you recommend? $\endgroup$
    – Mostafa
    Jan 9, 2020 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.