Topic
• 4 replies
• Latest Post - ‏2014-01-06T10:23:03Z by PhilippeLaborie
qtbgo
134 Posts

# Pinned topic how to model this constraint in parellel machine scheduling

‏2014-01-03T00:25:54Z |

Hi, in a simple parellel machine scheduling problem, we have n types of jobs and m machines. Each type of jobs should be processed only by one machine and should be processed continuously. How to model this situation?

One way is to consider all jobs of the same type as a big job, but I would not adopt this, because I will use individual job later.

• qtbgo
134 Posts

#### Re: how to model this constraint in parellel machine scheduling

‏2014-01-04T02:28:33Z
• GGR
• ‏2014-01-03T17:45:56Z

Hi

If I understand well your problem: You have to define one interval variable per type

int n = ... // number of type

tuple operation { int ptime; int type}

{Operation} operations = ... // the set of opertrions

dvar interval opers[o in operations} size o.ptime;

dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

forall (t in 1..n)

span(types[t], all (o in operations: o.type = t) opers[o]);

Then use the interval variable types to model the multi parallel machine problem

ope that helps

Thank you for your help, GGR.

• PhilippeLaborie
117 Posts

#### Re: how to model this constraint in parellel machine scheduling

‏2014-01-06T10:23:03Z
• qtbgo
• ‏2014-01-06T09:56:27Z

Dear GGR, Could you tell me why there is no solution for the following simple model:

using CP;

int n = 3;
int b = 10;
int nQC = 2;
int ScheduleLength = 1000;
int l[1..n] =  [1,2,3];

dvar interval opt_z1[ i in 1..n+nQC][k in 1..nQC] optional in 0..ScheduleLength;

dvar interval y[j in 1..b]  in 0..ScheduleLength ;
dvar interval opt_y[j in 1..b][k in 1..nQC] optional in 0..ScheduleLength;

minimize max(j in 1..b)endOf(y[j]);

subject to {

forall (j in 1..b, k in 1..nQC)
span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1

forall(j in 1..b)
alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2

}

Hello,

If you label the constraints in the model:

```subject to {
forall (j in 1..b, k in 1..nQC)
ct1: span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1
forall(j in 1..b)
ct2: alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2
}
```

The conflict refiner of CP Optimizer tells that a minimal conflicting subset of constraints in the model is: { ct2[4], ct1[4][1], ct1[4][2] }

So :

```ct2[4]:    alternative(y[4], { opt_y[4][1], opt_y[4][2] });
ct1[4][1]: span(opt_y[4][1], {});
ct1[4][2]: span(opt_y[4][2], {});
```

Indeed, because the set of the spanned intervals is empty, interval variables opt_y[4][1] and opt_y[4][2] are necessarily absent. But this is incompatible with the alternative constraint that states that (because y[4] is not optional), one and only one among opt_y[4][1] and opt_y[4][2] should be present.

Philippe

• GGR
83 Posts

#### Re: how to model this constraint in parellel machine scheduling

‏2014-01-03T17:45:56Z

Hi

If I understand well your problem: You have to define one interval variable per type

int n = ... // number of type

tuple operation { int ptime; int type}

{Operation} operations = ... // the set of opertrions

dvar interval opers[o in operations} size o.ptime;

dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

forall (t in 1..n)

span(types[t], all (o in operations: o.type = t) opers[o]);

Then use the interval variable types to model the multi parallel machine problem

ope that helps

• qtbgo
134 Posts

#### Re: how to model this constraint in parellel machine scheduling

‏2014-01-04T02:28:33Z
• GGR
• ‏2014-01-03T17:45:56Z

Hi

If I understand well your problem: You have to define one interval variable per type

int n = ... // number of type

tuple operation { int ptime; int type}

{Operation} operations = ... // the set of opertrions

dvar interval opers[o in operations} size o.ptime;

dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

forall (t in 1..n)

span(types[t], all (o in operations: o.type = t) opers[o]);

Then use the interval variable types to model the multi parallel machine problem

ope that helps

Thank you for your help, GGR.

• qtbgo
134 Posts

#### Re: how to model this constraint in parellel machine scheduling

‏2014-01-06T09:56:27Z
• GGR
• ‏2014-01-03T17:45:56Z

Hi

If I understand well your problem: You have to define one interval variable per type

int n = ... // number of type

tuple operation { int ptime; int type}

{Operation} operations = ... // the set of opertrions

dvar interval opers[o in operations} size o.ptime;

dvar interval types[t in i..n] size sum (o in operations: o.type = t) o.ptime;

forall (t in 1..n)

span(types[t], all (o in operations: o.type = t) opers[o]);

Then use the interval variable types to model the multi parallel machine problem

ope that helps

Dear GGR, Could you tell me why there is no solution for the following simple model:

using CP;

int n = 3;
int b = 10;
int nQC = 2;
int ScheduleLength = 1000;
int l[1..n] =  [1,2,3];

dvar interval opt_z1[ i in 1..n+nQC][k in 1..nQC] optional in 0..ScheduleLength;

dvar interval y[j in 1..b]  in 0..ScheduleLength ;
dvar interval opt_y[j in 1..b][k in 1..nQC] optional in 0..ScheduleLength;

minimize max(j in 1..b)endOf(y[j]);

subject to {

forall (j in 1..b, k in 1..nQC)
span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1

forall(j in 1..b)
alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2

}

• PhilippeLaborie
117 Posts

#### Re: how to model this constraint in parellel machine scheduling

‏2014-01-06T10:23:03Z
• qtbgo
• ‏2014-01-06T09:56:27Z

Dear GGR, Could you tell me why there is no solution for the following simple model:

using CP;

int n = 3;
int b = 10;
int nQC = 2;
int ScheduleLength = 1000;
int l[1..n] =  [1,2,3];

dvar interval opt_z1[ i in 1..n+nQC][k in 1..nQC] optional in 0..ScheduleLength;

dvar interval y[j in 1..b]  in 0..ScheduleLength ;
dvar interval opt_y[j in 1..b][k in 1..nQC] optional in 0..ScheduleLength;

minimize max(j in 1..b)endOf(y[j]);

subject to {

forall (j in 1..b, k in 1..nQC)
span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1

forall(j in 1..b)
alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2

}

Hello,

If you label the constraints in the model:

```subject to {
forall (j in 1..b, k in 1..nQC)
ct1: span(opt_y[j][k], all (i in 1..n: l[i] == j ) opt_z1[i][k]);   //1
forall(j in 1..b)
ct2: alternative(y[j], all(k in 1..nQC ) opt_y[j][k]);  //2
}
```

The conflict refiner of CP Optimizer tells that a minimal conflicting subset of constraints in the model is: { ct2[4], ct1[4][1], ct1[4][2] }

So :

```ct2[4]:    alternative(y[4], { opt_y[4][1], opt_y[4][2] });
ct1[4][1]: span(opt_y[4][1], {});
ct1[4][2]: span(opt_y[4][2], {});
```

Indeed, because the set of the spanned intervals is empty, interval variables opt_y[4][1] and opt_y[4][2] are necessarily absent. But this is incompatible with the alternative constraint that states that (because y[4] is not optional), one and only one among opt_y[4][1] and opt_y[4][2] should be present.

Philippe