Originally posted by: PatiC

Hello IBM community,

I created a model for solving a flow-shop scheduling problem and reduced the complexity in a first step to a one-machine problem with one operation:

using CPLEX;

tuple Machine {
  key int id;        
  int operationId;     
};

tuple Job {
    key int id;            
    int dueDate;
};

tuple Operation {
  key int id;    
};

tuple WorkingTime {
  key int jobId;        
  key int operationId;
  int workingTime;      
};

{Machine} Machines = {<0,0>};
{Job} Jobs = {<0,5>, <1,6>};
{Operation} Operations = {<0>};
{WorkingTime} WorkingTimes = {<0,0,6>, <1,0,4>};

int K = 10000000;
dvar int+ startingTimes[WorkingTimes];
dvar boolean x[Jobs][Jobs][Operations];
dvar boolean w[Jobs][Operations][Machines];
dvar int+ makespan[Jobs];
dvar int+ tardiness[Jobs];

minimize sum(j in Jobs)(tardiness[j]); // (1)
subject to {
  forall (j in Jobs)  // (2)
    makespan[j] - tardiness[j] <= j.dueDate;
   
  forall (j in Jobs, a in Operations, z in WorkingTimes: z.jobId==j.id && z.operationId == a.id) // (3)
     startingTimes[z] + z.workingTime <= makespan[j];
 
   forall (j in Jobs, a in Operations) // (8)
     sum(m in Machines: m.operationId == a.id) w[j][a][m] == 1;
   
   forall (j in Jobs, a1 in Operations, a2 in Operations: a2.id==1+a1.id,
           z1 in WorkingTimes: z1.jobId==j.id && z1.operationId == a1.id,
           z2 in WorkingTimes: z2.jobId==j.id && z2.operationId == a2.id) // (4)         
     startingTimes[z1] + z1.workingTime <= startingTimes[z2];
           
     forall (j1 in Jobs, j2 in Jobs: j1.id < j2.id, a in Operations,
    z1 in WorkingTimes: z1.jobId==j1.id && z1.operationId == a.id,
    z2 in WorkingTimes: z2.jobId==j2.id && z2.operationId == a.id,
       m in Machines: m.operationId == a.id) {    // (5 and 6)
         K * (w[j1][a][m] - x[j1][j2][a] - 1) + startingTimes[z2] + z2.workingTime * w[j2][a][m]
                    <=  startingTimes[z1];
     K * (w[j2][a][m] + x[j1][j2][a] - 2) + startingTimes[z1] + z1.workingTime * w[j1][a][m]
                     <=  startingTimes[z2];
  }
}
execute {
  for (var j in Jobs) {
      writeln("Tardiness Job " + j.id + " : " + tardiness[j]);
    }
}

After I executed the model, I got the solution 1 using the CPLEX engine (cplex_solution screenshot).

I wondered why both jobs have starting time 0. If I use the CP engine to solve the model, I got the solution 5 (cp_solution screenshot).

With CP engine I got another, I think the right solution 5.

I reduced the complexity by eliminating the decision variable w. Decision variable w models, that Job i with Operation o is solved by Machine m (the value is in both solutions for both jobs 1).
I also reduced the decision variable x, which models that Job1 is scheduled before Job2: 1, otherwise 0. Job1 < Job2.

subject to {
  forall (j in Jobs)  // (2)
    makespan[j] - tardiness[j] <= j.dueDate;
   
  forall (j in Jobs, a in Operations, z in WorkingTimes: z.jobId==j.id && z.operationId == a.id) // (3)
     startingTimes[z] + z.workingTime <= makespan[j];
 
   forall (j in Jobs, a in Operations) // (4)
     sum(m in Machines: m.operationId == a.id) 1 == 1;
   
   forall (j in Jobs, a1 in Operations, a2 in Operations: a2.id==1+a1.id,
           z1 in WorkingTimes: z1.jobId==j.id && z1.operationId == a1.id,
           z2 in WorkingTimes: z2.jobId==j.id && z2.operationId == a2.id) // (5)         
     startingTimes[z1] + z1.workingTime <= startingTimes[z2];
           
     forall (j1 in Jobs, j2 in Jobs: j1.id < j2.id, a in Operations,
    z1 in WorkingTimes: z1.jobId==j1.id && z1.operationId == a.id,
    z2 in WorkingTimes: z2.jobId==j2.id && z2.operationId == a.id,
       m in Machines: m.operationId == a.id) {    // (6 and 7)
         K * (1 - x - 1) + startingTimes[z2] + z2.workingTime
                    <=  startingTimes[z1];
     K * (1 + x - 2) + startingTimes[z1] + z1.workingTime
                     <=  startingTimes[z2];
  }
}
 
But I got the same curious results, with CPLEX engine is the decision variable x = 0. But this can't right, because then x is 0, startingTime[0] must be 4 (subject 6).
When I set x = 0 for subject 6 and 7, I got the right solution with CPLEX engine.

So I don't understand why I get this difference solutions by using CPLEX and CP engine. Why CPLEX engine don't use subject 6 and 7 with x = 0?
Is there a problem in the running configurations?
So can anyone help me with my problem?

Thank you
Patrick

Hi,

can you try with a smaller BIG M like

int K = 100000;

?

Plus generally instead of Big M I would use logical constraints

regards

Originally posted by: PatiC

Hello Alex Fleischer,

I think that was the problem. With a smaller value of int K (eg 100000), I get the right solution.

What do you mean with using logical constraints in this case?

Thank you and best regards

Patrick

Hi,

see http://www.ibm.com/support/knowledgecenter/SSSA5P_12.2.0/ilog.odms.ide.help/Content/Optimization/Documentation/OPL_Studio/_pubskel/globals/eclipse_and_xplatform/ps_opl578.html

regards