Originally posted by: guvenc88

Hello;

I have problem about understanding the meaning of noOverlap.

I have a problem which is very similar to sched_opnshop example in opl.
I have jobs and machines. I have to schedule the jobs as always:). every job has a processing time of p[j] independent from machines.
Furthermore every job has a release date r[j] and due date d[j].(p[j]=d[j]-r[j] fixed job scheduling)(no precedence relationship)

using CP;

dvar interval Xa in jb in m optional in r[a]..d[a] size p[a];//j for jobs m for machines
*dvar sequence jobsa in j in all(b in m) X[a][b];
**dvar sequence machinesb in m in all(a in j) X[a][b];
.....................

subject to
{

• forall(a in j)

noOverlap(jobs[a]);

• forall(b in m)
• noOverlap(machines[b]);

}
I do understand the first constraint. It means for me that "the jobs assigned to same machine can not overlap/coincide or intersect.
Would you please explain me the second constraint?(what I need as second constraint is that it can not be assigned a job to more than 1 machine") But I dont understand how noOverlap does this.It works but I cant understand..

Thanks for your help...
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: GGR

Hi

Two part in the answer

1) The model you have written is a simple case of open shop where all operation have the same size, independent of the machine, let's say that is not the case.

// j jobs of m operations, one per machine (implicitly m machines)

// declarations of all the operations: one intervals variable per jobs and per machines dvar interval X[a in 1..j][b in 1..m] in r[a]..d[a] size p[a];

Each machine is disjunctive (aka unary machine). That is you model it with a noOverlap constraint on the sequence defined by the set of interval variable (the operations) executed on the machine.

That is the purpose of the following code elements:

// declaration of the m machine as m sequence dvar sequence machines[b in 1..m] in all(a in 1..j) X[a][b];   subject to 
{ 
// constraint: disjunctive resource forall(b in 1..m) noOverlap(machines[b]); 
}

Now we have to organize the jobs: a job is a succession of operations you do not know the order of execution. You have to sort the operations of a job such that they cannot be executed at the same time (i.e that are not overlapping). That is the basic usage of a sequence: it constraint to organize in sequence a set of interval variables using a constraint to sort it: the constraint is the noOverlap.

As all the size and the machine are

That is the purpose of the following code elements:

// declaration of the sequence of operation of a job dvar sequence jobs[b in 1..m] in all(a in 1..j) X[a][b];   subject to 
{ 
// constraint: disjunctive resource forall(a in 1..j) noOverlap(jobs[a]); 
}

2) It's seem to me you want that the operations of a job are executed on the same machine you do not know. That is completely different. In the previous sample, you decomposed the jobs on the machine, and now you decompose the jobs in k tasks. Each task are executed by one of the machine.

// declarations of all the tasks: one interval variable per jobs and per tasks dvar interval T[a in 1..j][b in 1..k]; / declarations of all the potential operations: one interval variable per (job, task)
's and per machines dvar interval X[a in 1..j][b in 1..k][c in 1..m] optional in r[a]..d[a] size p[a][b];     
// declaration of the m machine as m sequence dvar sequence machines[c in 1..m] in all(a in 1..j, b in 1..k) X[a][b][c];   subject to 
{ 
// constraint: disjunctive resource forall(b in 1..m) noOverlap(machines[b]); 
}   
// the jobs are sequences of tasks dvar sequence jobs[b in 1..m] in all(a in 1..j) T[a][b]; 
// the tasks   subject to 
{ 
// constraint: disjunctive resource forall(a in 1..j) noOverlap(jobs[a]);   
// constraint sort of the jobs as no overlaping sequence of tasks  forall(a in 1..j) noOverlap(jobs[a]);   
// each task is executed by one machine forall(a in 1..j, b in 1..t) alternative(T[a][b], all (c in 1..m) X[a][b][c];   
}

Note if you need an interval variable for each jobs in order to add extra constraint or objective term than release date due date, you have to use a span constraint

{code}

dvar interval Jhttp://a in 1..j;

subject to {
forall(a in 1..j)
span(J[a], all (b in 1..t) T[a][b];
}

Hope that helps
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: guvenc

Thanks for your plentiful response. I should work more. You really well framed my problem.
Just to be sure I can so say that(I am trying to understand the basic concept to model harder problems:)
1- the jobs assigned(regardless the reason of assignment) to a machine do not intersect owing to "sequence jobs..." and noOverlap constraint
2- a job assigned to a machine will not be assigned again to another machine owing to "sequence machine..."and noOverlap constraint(because what I understand here is that noOverlap behaves like saying "do not create the same machines with same assignements")

Thanks a lot again hope i dont bother you a lot...
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: GGR

1) Yes, we can rephrase by saying the noOverlap constraint on the sequence of jobs possibly executed by the machine is the math model in term of CP Optimizer language for the topology of a unary resource

2) beware, the choice of machine is the purpose of the alternative constraints: a job is assigned to one and only one machine. mathematically, each optional interval variables model the execution of a task on a machine. The alternative constraint tells that only one interval variable is present (that is the one related to the machine that execute the task) and this interval share the same start and end with the interval variable that models the task.

cheers
#ConstraintProgramming-General
#DecisionOptimization