Originally posted by: user1234567

Hello, i'm using a mathematical model (milp model) to solve Flexible Jobshop Problem. I get results out of the upper and the lower bounds. For example, in the following data (donnees.DAT) i should get a value between 133, and 157. (LB, UB) = (133, 157). I get the value 198 !!

Please can you help me to know the reason why i get unreasonable objective functions ? Can anyone check my model if it is working correctly ? Thank you in advance.

 

My model:

 

decision variables:

X i,j,k = {1 if machine k is selceted for operation Oij, 0 otherwise}

Y i,j,i',j',k = {1 if operation Oij precedes operation Oi'j' on machine k, 0 otherwise}.

 

The mathematical model:

 

Minimize (x i,j,k , y i,j,i',j',k): Cmax

sum (k∈Mj) X i,j,k = 1, i∈J, j∈Oi (1)

sum (i=1,..n, j=1..rj) X i,j,k <= e i,j,k; k∈Mj (2)

where, for given {x i,j,k}, {y i,j,i',j',k} solves:

 

Minimize (y i,j,i',j',k) Cmax 

sum (i in 1,..,n, j=1,..,rj) y i,j,i',j',k <= 1; i'∈J, j'∈Oi', k∈Mj∩Mj', (3)

sum (i in 1,..,n, j=1,..,rj) y i,j,0,1,k <= 1; k∈Mj∩Mj', (4)

sum (i in 1,..,n, j=1,..,rj) y i,j,i',j',k <= sum (i in 0,..,n, j=1,..,rj) y i',j',i,j,k; i'∈J, j'∈Oi', k∈Mj∩Mj', (5)

 

C i,j,k >= C i',j' + y i,j,i',j',k * (p i,j,k + s i,i',k) - L * (1-sum(k=1,..,m) y i,j,i',j',k); i,i' ∈ J, j,j' ∈ Oi', k∈Mj∩Mj', (6)

C i,j,k >= sum (k∈Mj) C i,j-1,k + sum(i=1,..,n, j=1,..,rj, k=1,..,m) y i,j,i',j',k * (p i,j,k + s i',j',k); i ∈ J, j ∈ Oi, (7)

Ci >= sum (k∈Mj) C i,j,k;  i ∈ J, j' ∈ Oi', k∈Mj∩Mj', (8)

Cmax >= Ci;  i ∈ J, (9)

C i,j,k >= 0;  i ∈ J, j ∈ Oi, k∈Mj. (10)

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: PhilippeLaborie

Hello,

For MIP questions, I suggest you post on the Math Programming forums (ibm.biz/MathProgForums).

Now, for a flexible job-shop problem, using a CP Optimizer model makes sense too, of course.

I see in your attached models (model1 and model2) that you are introducing many integer and boolean variables that are useless in this type of model. For a problem as simple a a flexible jobshop, you only need the interval variables "ops" and "modes" and the "mchs" sequences. The model for the flexible jssp looks like this:

// Position of last operation of job j
int jlast[j in Jobs] = max(o in Ops: o.jobId==j) o.pos;

dvar interval ops  [Ops]; 
dvar interval modes[md in Modes] optional size md.pt;
dvar sequence mchs[m in Mchs] in all(md in Modes: md.mch == m) modes[md];

minimize max(j in Jobs, o in Ops: o.pos==jlast[j]) endOf(ops[o]);
subject to {
  forall (j in Jobs, o1 in Ops, o2 in Ops: o1.jobId==j && o2.jobId==j && o2.pos==1+o1.pos)
    endBeforeStart(ops[o1],ops[o2]);
  forall (o in Ops)
    alternative(ops[o], all(md in Modes: md.opId==o.id) modes[md]);
  forall (m in Mchs)
    noOverlap(mchs[m]);
}

In your case I see that there is a secondary objective that is to maximize the sum of start times, but this expression is just:

sum(o in Ops) startOf(ops[o])

 

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: user1234567

Thank you for your reply. How can i add this expression: maximize sum (o in Ops) startOf (ops [o]). CPLEX cannot handle more than one objective function.

Also, i'm using two models because it's a bilevel problem. The first model should solve the X decision variable used for assignment and the second level should solve the Y, used for scheduling. Otherwise, it cannot be considered as a MILP model if i don't write the mathematical model related to this problem.

Do u have an idea about how to get an optimal solution of the corresponding model ?

Thank you.

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: PhilippeLaborie

I'm lost. 

1- You say that you want to write a MILP model for the problem but the two models you attach are CP models (they start with "using CP").

2- I do not understand why you want to solve the problem in 2 steps (first allocation, then scheduling). 

3- You say "Otherwise, it cannot be considered as a MILP model if i don't write the mathematical model related to this problem". If you want to solve your problem with MILP technology then write a MILP model and solve it with CPLEX. If you want to use CP technology then write a CP model and solve it with CPO. Both models are "mathematical" and both engines are "exact" in the sense that, if they are given enough time, they will find the optimal solution and prove optimality.

4- For classical flexible job-shop, the state-of-the-art is the CP Optimizer model provided in the delivery (in opl/examples/opl/sched_jobshopflex). This model was used in 2015 to close many instances of classical flexible job-shop benchmarks and improve both lower and upper-bounds on many others. See "P. Vilim, P. Laborie, P. Shaw : Failure-directed Search for Constraint-based Scheduling. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 12th International Conference, CPAIOR 2015."

If you need advices to efficiently solve this problem using CP Optimizer, please post to this forum. If you want so solve the problem with a MILP model, use the Math Programming ones. And if the problem is more complex, then could you precise what you are exactly trying to achieve ?

 

 

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: user1234567

Yes that's true. It's a complicated problem. First, i'm using CP because i found it easier to use to solve the MILP model. Also, i was adviced on this forum to use cp optimizer to solve my problem and to use a flow control to solve the bilevel problem. I found many difficulties to write my program using CPLEX. Second, i'm solving this problem in two steps because it's a bilevel problem. This is my thesis Topic and i should solve it. The contraints 1 and 2 are used for assignment (upper level). The lower level for scheduling. The lower level should call the upper level to obtain the assignment. Backwards and forwards should be made between the two files (two steps of assignment and scheduling).

 

I found a difficulty when writing my model using cplex. For example, Minimize Cmax subject to:

forall (i in Jobs, j in Oper)

sum (k in Mchs) X[i][j[k] == 1;

and

forall (i in Jobs, j in Oper)

sum (i in Jobs, j in Oper) X [i][j[k] <= e[i[j[k] ...

How can it be written using CPLEX instead of CP ? and in condition that i get feasible and optimal results ?

You can use some modifications in my program and use cplex instead of cp if it doesn't seem to be very difficult. Thank you.

#ConstraintProgramming-General
#DecisionOptimization