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.

$\endgroup$
5
$\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}$.

$\endgroup$
  • $\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 at 3:16
  • 1
    $\begingroup$ To diagnose infeasibility, I recommend fixing the variables from a known solution and seeing which constraints are violated. $\endgroup$ – Rob Pratt Jan 8 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.

$\endgroup$
  • $\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 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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