Hello,
i'm kind of new to CPLEX and LP in general. So i'll be very happy if anyone can help me with my schedulingproblem. I want to optimize a schedule for the treatment of goods at a machine. In a first step the goods have only different widths.
The higher the widthdifference of consecutive goods is, the higher the costs are.
I want to model a cost function, which should be minimized. ==> the goods should be sorted by width
As solution i want the optimized order of goods as GanntChart, but i can't find a way to compare the widths of the goods.
I'd be very happy if someone can give me a hint, how i can deal with this problem.
Topic

Re: Scheduling Problem
20120619T07:13:46ZThis is the accepted answer. This is the accepted answer.Hey,
Answering your question without further details is rather complex. For example, which variables are you using in your model? Typically, for scheduling problems, either one of these three variables is chosen:
1. Time indexed. x_{gt}=0,1 : product g is being processed at time t
Usually time indexed formulations perform very well, specially if your time horizon is small or can be partitioned into large intervals, e.g. partioning an horizon of 1 hour into 5 minute segments.
2. Assignment based formulation. x_{gi}=0,1 if product g is the ith job being processed. If you are using multiple machines, you could use: x_{gij}: product g is the ith job being processed on machine j.
3. A flow based formulation: x_{gh}=0,1: product g is processed directly before h. (equivalent: x_{ghj} product g is processed directly before product h on machine j).
Lets assume you chose the 3th option, and you know the width of each product. Lets denote the width of product g width w_g. Then your objective could be: minimize \sum_{g\in G}\sum{h\in {Gg}} (w_gw_h)*x_{gh}
Here G is your set with products.
The above objective is not 100% correct. The one thing you cannot really do is to take the absolute value of a calculation (that is a nonlinear operation which is not possible is linear optimization). So if w_g is smaller than w_h, you have a problem. Nevertheless, this is easily fixed in the above objective by ordering the set G. Since (w_gw_h) only uses constants, you simply make sure they are in the correct order when you write down the objective.
Similar objectives can be created using the other two types of variables. 
Re: Scheduling Problem
20120619T15:53:43ZThis is the accepted answer. This is the accepted answer. JorisK
 20120619T07:13:46Z
Hey,
Answering your question without further details is rather complex. For example, which variables are you using in your model? Typically, for scheduling problems, either one of these three variables is chosen:
1. Time indexed. x_{gt}=0,1 : product g is being processed at time t
Usually time indexed formulations perform very well, specially if your time horizon is small or can be partitioned into large intervals, e.g. partioning an horizon of 1 hour into 5 minute segments.
2. Assignment based formulation. x_{gi}=0,1 if product g is the ith job being processed. If you are using multiple machines, you could use: x_{gij}: product g is the ith job being processed on machine j.
3. A flow based formulation: x_{gh}=0,1: product g is processed directly before h. (equivalent: x_{ghj} product g is processed directly before product h on machine j).
Lets assume you chose the 3th option, and you know the width of each product. Lets denote the width of product g width w_g. Then your objective could be: minimize \sum_{g\in G}\sum{h\in {Gg}} (w_gw_h)*x_{gh}
Here G is your set with products.
The above objective is not 100% correct. The one thing you cannot really do is to take the absolute value of a calculation (that is a nonlinear operation which is not possible is linear optimization). So if w_g is smaller than w_h, you have a problem. Nevertheless, this is easily fixed in the above objective by ordering the set G. Since (w_gw_h) only uses constants, you simply make sure they are in the correct order when you write down the objective.
Similar objectives can be created using the other two types of variables.
So i'll explain further details of my problem to you. I have 1 machine , and 5 goods. The machine handles the goods in a row. So there's no overlaping between the treatment of the 5 goods. The goods have the widths 16,5,9,5,8.
this is my first attempt:
using CP;
int nbgoods = 5;
range allgoods = 1..nbgoods;
int width allgoods = 16,5,9,5,8;
int cost = 2;
/*
Good 1 width : 16
Good 2 width : 5
Good 3 width : 9
Good 4 width : 5
Good 5 width : 8
*/
dvar interval treatmentallgoods size 1;
minimize sum(g in allgoods) sum (h in allgoods: h != g) (width[g]  width[h])* cost * ???;
subject to {
noOverlap(treatment);
}
> JorisK wrote:
>
> Lets assume you chose the 3th option, and you know the width of each product. Lets denote the width of product g width w_g. Then your objective could be: minimize \sum_{g\in G}\sum{h\in {Gg}} (w_gw_h)*x_{gh}
> Here G is your set with products.
>
I also don't undersand what you mean by x_{gh} ? Is it the decision variable ? Is it possible to use intervals ?
And how can i write {Gg}, that CPLEX understands what i mean?
Thank you very much again 
Re: Scheduling Problem
20120620T08:01:20ZThis is the accepted answer. This is the accepted answer. Voigtler
 20120619T15:53:43Z
Hey, thank you very much for your reply. I think the third option fits best for my model, but i hoped i could somehow use intervals as dvar. But i don't really understand how to do it. Is it possible to solve my problem with intervals, or do i have to use integers or something else?
So i'll explain further details of my problem to you. I have 1 machine , and 5 goods. The machine handles the goods in a row. So there's no overlaping between the treatment of the 5 goods. The goods have the widths 16,5,9,5,8.
this is my first attempt:
using CP;
int nbgoods = 5;
range allgoods = 1..nbgoods;
int width allgoods = 16,5,9,5,8;
int cost = 2;
/*
Good 1 width : 16
Good 2 width : 5
Good 3 width : 9
Good 4 width : 5
Good 5 width : 8
*/
dvar interval treatmentallgoods size 1;
minimize sum(g in allgoods) sum (h in allgoods: h != g) (width[g]  width[h])* cost * ???;
subject to {
noOverlap(treatment);
}
> JorisK wrote:
>
> Lets assume you chose the 3th option, and you know the width of each product. Lets denote the width of product g width w_g. Then your objective could be: minimize \sum_{g\in G}\sum{h\in {Gg}} (w_gw_h)*x_{gh}
> Here G is your set with products.
>
I also don't undersand what you mean by x_{gh} ? Is it the decision variable ? Is it possible to use intervals ?
And how can i write {Gg}, that CPLEX understands what i mean?
Thank you very much again
Sorry, from your first message I was under the impression that you wanted to use ILOG Cplex instead of ILOG CP optimizer. Clex is used for linear optimization problems, whereas CP optimizer uses constraint programming. Usually, if you can model a problem as a Mixed Integer Problem, then that is often better/faster than a CP problem. I'm not an expert in ILOG CP, so I'm not sure how to model your problem. There is however a good manual included with ILOG Cplex, including an extensive section on scheduling problems.
Something else :
In your problem, you do not describe any constraints on the processing of goods. Judging from your description, you simply want to order the goods, such that the ordering minimizes the difference in size between consecutive items. This problem can be seen as a traveling salesman problem. Take a simple, complete, undirected graph: each item becomes a vertex, there are edges in between all items. Add a dummy vertex to the graph and add edges between the dummy vertex and all items. Each edge has a cost. An edge between the dummy vertex and an item has cost 0. An edge between two items has a cost which equals the difference in width. Next you want to find a tour, which starts and ends in the dummy vertex and which visits each vertex (item) exactly once, thereby minimizing the length of the tour. This is exactly the TSP problem. Efficient algorithms exist to solve the TSP problem. This problem is easily modeled as a Mixed Integer Problem. Also, if you just need to solve TSP problems, then I would use some special purpose solver, such as Concorde, which is currently the fastest TSP solver. 
Re: Scheduling Problem
20120620T11:06:14ZThis is the accepted answer. This is the accepted answer. Voigtler
 20120619T15:53:43Z
Hey, thank you very much for your reply. I think the third option fits best for my model, but i hoped i could somehow use intervals as dvar. But i don't really understand how to do it. Is it possible to solve my problem with intervals, or do i have to use integers or something else?
So i'll explain further details of my problem to you. I have 1 machine , and 5 goods. The machine handles the goods in a row. So there's no overlaping between the treatment of the 5 goods. The goods have the widths 16,5,9,5,8.
this is my first attempt:
using CP;
int nbgoods = 5;
range allgoods = 1..nbgoods;
int width allgoods = 16,5,9,5,8;
int cost = 2;
/*
Good 1 width : 16
Good 2 width : 5
Good 3 width : 9
Good 4 width : 5
Good 5 width : 8
*/
dvar interval treatmentallgoods size 1;
minimize sum(g in allgoods) sum (h in allgoods: h != g) (width[g]  width[h])* cost * ???;
subject to {
noOverlap(treatment);
}
> JorisK wrote:
>
> Lets assume you chose the 3th option, and you know the width of each product. Lets denote the width of product g width w_g. Then your objective could be: minimize \sum_{g\in G}\sum{h\in {Gg}} (w_gw_h)*x_{gh}
> Here G is your set with products.
>
I also don't undersand what you mean by x_{gh} ? Is it the decision variable ? Is it possible to use intervals ?
And how can i write {Gg}, that CPLEX understands what i mean?
Thank you very much again
Here is a small example with interval variables in CP Optimizer. I changed your cost function to abs(width[g]  width[h]) for illustrative purpose. The actual function can be any expression involving the difference of width between an item and its direct successor in the sequence.
using CP; int nbgoods = 5; range allgoods = 1..nbgoods; int width[allgoods] = [16, 5, 9, 5, 8]; int cost = 2; dvar interval treatment[g in allgoods] size 1; dvar sequence seq in all(g in allgoods) treatment[g] types all(g in allgoods) g; dexpr float deltaw = sum(g in allgoods) abs(width[g]width[typeOfNext(seq, treatment[g], g)]); execute { cp.setSearchPhases(cp.factory.searchPhase(seq)); } minimize cost * deltaw; subject to { noOverlap(seq); }
Let me explain a little bit:
 the interval variables treatment[g] represent the treatment activities for a given good g. Currently, their size (duration) is 1. If in your real problem if you need to model a specific duration and have some additional scheduling constraints on those activities (limited resources, precedence constraints, setuptimes), this type of CP Optimizer model will really be helpful
 the sequence variable seq represents the sequence of treatment activities on the machine. Each activity treatment[g] is associated a type (an index) g. So treatment[1] has type 1, etc.
 there is a noOverlap constraint on this sequence. This states that if treatment[i] is before treatment[j] in the sequence, then treatment[i] must end before the start of treatment[j]
 for a given good g, the difference between the width of g (width[g]) and the width of the interval that is scheduled next to g in the sequence (width[typeOfNext(seq, treatment[g], g)) is used in the cost expression deltaw. See the documentation of expression typeOfNext. Note that when g is last interval in the sequence, we chose g as the value of this expression so that the cost of the last good is 0.
 I added a search phase that tells the engine to focus on fixing the values of the sequence variable seq rather before focusing on finding actual start and end values for the treatment intervals because in this problem, the main decision variable is the order of interval in the sequence, not the actual start/end values. Of course, if the scheduling problem becomes more complex and dominated by scheduling constraints (resources, precedence constraints, ...), this search phase may not be useful.
Philippe the interval variables treatment[g] represent the treatment activities for a given good g. Currently, their size (duration) is 1. If in your real problem if you need to model a specific duration and have some additional scheduling constraints on those activities (limited resources, precedence constraints, setuptimes), this type of CP Optimizer model will really be helpful
 the sequence variable seq represents the sequence of treatment activities on the machine. Each activity treatment[g] is associated a type (an index) g. So treatment[1] has type 1, etc.
 there is a noOverlap constraint on this sequence. This states that if treatment[i] is before treatment[j] in the sequence, then treatment[i] must end before the start of treatment[j]
 for a given good g, the difference between the width of g (width[g]) and the width of the interval that is scheduled next to g in the sequence (width[typeOfNext(seq, treatment[g], g)) is used in the cost expression deltaw. See the documentation of expression typeOfNext. Note that when g is last interval in the sequence, we chose g as the value of this expression so that the cost of the last good is 0.
 I added a search phase that tells the engine to focus on fixing the values of the sequence variable seq rather before focusing on finding actual start and end values for the treatment intervals because in this problem, the main decision variable is the order of interval in the sequence, not the actual start/end values. Of course, if the scheduling problem becomes more complex and dominated by scheduling constraints (resources, precedence constraints, ...), this search phase may not be useful.
Philippe 
Re: Scheduling Problem
20120625T08:55:12ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20120620T11:06:14Z
Hello,
Here is a small example with interval variables in CP Optimizer. I changed your cost function to abs(width[g]  width[h]) for illustrative purpose. The actual function can be any expression involving the difference of width between an item and its direct successor in the sequence.
<pre class="jivepre">using CP; int nbgoods = 5; range allgoods = 1..nbgoods; int width[allgoods] = [16, 5, 9, 5, 8]; int cost = 2; dvar interval treatment[g in allgoods] size 1; dvar sequence seq in all(g in allgoods) treatment[g] types all(g in allgoods) g; dexpr float deltaw = sum(g in allgoods) abs(width[g]width[typeOfNext(seq, treatment[g], g)]); execute { cp.setSearchPhases(cp.factory.searchPhase(seq)); } minimize cost * deltaw; subject to { noOverlap(seq); }
</pre>
Let me explain a little bit:
 the interval variables treatment[g] represent the treatment activities for a given good g. Currently, their size (duration) is 1. If in your real problem if you need to model a specific duration and have some additional scheduling constraints on those activities (limited resources, precedence constraints, setuptimes), this type of CP Optimizer model will really be helpful
 the sequence variable seq represents the sequence of treatment activities on the machine. Each activity treatment[g] is associated a type (an index) g. So treatment[1] has type 1, etc.
 there is a noOverlap constraint on this sequence. This states that if treatment[i] is before treatment[j] in the sequence, then treatment[i] must end before the start of treatment[j]
 for a given good g, the difference between the width of g (width[g]) and the width of the interval that is scheduled next to g in the sequence (width[typeOfNext(seq, treatment[g], g)) is used in the cost expression deltaw. See the documentation of expression typeOfNext. Note that when g is last interval in the sequence, we chose g as the value of this expression so that the cost of the last good is 0.
 I added a search phase that tells the engine to focus on fixing the values of the sequence variable seq rather before focusing on finding actual start and end values for the treatment intervals because in this problem, the main decision variable is the order of interval in the sequence, not the actual start/end values. Of course, if the scheduling problem becomes more complex and dominated by scheduling constraints (resources, precedence constraints, ...), this search phase may not be useful.
Philippe
I've now added weight and thickness of the goods to the model. If i solve the model with 5 goods, solving is done within a few ms.
But if i want to optimize the model with 7 or more goods in the Array, solving takes longer than 1 hour. In the end i want to solve a problem with about 100 goods.
What can i do to solve the problem faster?
Are there any other searchphases i can use ?
I've tried to change the tolerances, but solving took also much too long! 
Re: Scheduling Problem
20120625T10:05:34ZThis is the accepted answer. This is the accepted answer. Voigtler
 20120625T08:55:12Z
Thank you very much.
I've now added weight and thickness of the goods to the model. If i solve the model with 5 goods, solving is done within a few ms.
But if i want to optimize the model with 7 or more goods in the Array, solving takes longer than 1 hour. In the end i want to solve a problem with about 100 goods.
What can i do to solve the problem faster?
Are there any other searchphases i can use ?
I've tried to change the tolerances, but solving took also much too long!
CP Optimizer indeed focuses on computing good solutions rather than computing tight lower bounds or proving optimality. It explains why, even if your model seems not very large, the engine can't prove optimality. You can use a timelimit (or a branch or a fail limit if you want to stop deterministically) to stop the search and access the best solution found so far.
Philippe 
Re: Scheduling Problem
20120626T08:11:15ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20120625T10:05:34Z
Hello,
CP Optimizer indeed focuses on computing good solutions rather than computing tight lower bounds or proving optimality. It explains why, even if your model seems not very large, the engine can't prove optimality. You can use a timelimit (or a branch or a fail limit if you want to stop deterministically) to stop the search and access the best solution found so far.
Philippe
I accidentially changed the timelimit for mathematical programming and not for constraint programming, so this didn't work. But now i've found the right option, so i get a good solution within very short time.
But i've got some other questions:
Is it possible to solve my problem by MP ? Or should i try it with CP ?
The documentation says CP is based on Graph theory and algorithmic. Which algorithms are used and where can i get some further information about them ? 
Re: Scheduling Problem
20120626T08:15:30ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20120625T10:05:34Z
Hello,
CP Optimizer indeed focuses on computing good solutions rather than computing tight lower bounds or proving optimality. It explains why, even if your model seems not very large, the engine can't prove optimality. You can use a timelimit (or a branch or a fail limit if you want to stop deterministically) to stop the search and access the best solution found so far.
Philippe
By the way, is it possible to solve my model by MP or do i have to use CP ?
The documentation says, CP is based on graph theory and algorithmic. Can you tell me which algorithms are used and where i can find further information about them ? 
Re: Scheduling Problem
20120626T14:11:05ZThis is the accepted answer. This is the accepted answer. Voigtler
 20120626T08:15:30Z
Thanks, it worked. I accidentially changed the limits for MP and not for CP, but now i found the right options.
By the way, is it possible to solve my model by MP or do i have to use CP ?
The documentation says, CP is based on graph theory and algorithmic. Can you tell me which algorithms are used and where i can find further information about them ?
I think CP will become interesting if, beside these constraints and objective function on good sequencing you also need to handle other types of scheduling constraints like activity durations, precedence constraints between activities, multiple machines and machine types with limited availability, cumulative resources etc.
If you want to have an idea of the algorithms that are used to solve CP scheduling models in IBM ILOG CPLEX Optimization Studio (using CP Optimizer engine), you can have a look at this paper:
P. Laborie & D. Godard. SelfAdapting Large Neighborhood Search: Application to SingleMode Scheduling Problems. In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), 2007, 276284.
If you want more general information about CP techniques, a good starting point can be the Handbook of Constraint Programming.
Philippe 
Re: Scheduling Problem
20120628T12:23:47ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20120626T14:11:05Z
If the model just consists of what you describe above, that is, finding a sequence for the treatment of goods on a single machine subject to a cost that can be expressed as a sum of transition cost that only depend on pairs of consecutive goods, then as stated by JorisK, it boils down to a TSP problem and you can solve it using MP.
I think CP will become interesting if, beside these constraints and objective function on good sequencing you also need to handle other types of scheduling constraints like activity durations, precedence constraints between activities, multiple machines and machine types with limited availability, cumulative resources etc.
If you want to have an idea of the algorithms that are used to solve CP scheduling models in IBM ILOG CPLEX Optimization Studio (using CP Optimizer engine), you can have a look at this paper:
P. Laborie & D. Godard. SelfAdapting Large Neighborhood Search: Application to SingleMode Scheduling Problems. In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), 2007, 276284.
If you want more general information about CP techniques, a good starting point can be the Handbook of Constraint Programming.
Philippe// Cities int n = ...; range Cities = 1..n; // Edges  sparse set tuple edge { int i; int j; } setof(edge) Edges = {<i,j>  ordered i,j in Cities }; int dist[Edges] = ...;
I've decided to try to describe my problem as TSP. So i had a look in the documentation and found the TSP example.
In my problem i want to calculate my values for the dist[] array before i write them in there.
How is it possible to set dist<1,3> = 5 for example ?
I want to program a forloop which inserts values in the array. Can you tell me how to do it ?
If i try
dist[<1,3>] = 4
i get an error. 
Re: Scheduling Problem
20120628T21:16:26ZThis is the accepted answer. This is the accepted answer. Voigtler
 20120628T12:23:47Z
<pre class="jivepre">// Cities int n = ...; range Cities = 1..n; // Edges  sparse set tuple edge { int i; int j; } setof(edge) Edges = {<i,j>  ordered i,j in Cities }; int dist[Edges] = ...;
</pre>
I've decided to try to describe my problem as TSP. So i had a look in the documentation and found the TSP example.
In my problem i want to calculate my values for the dist[] array before i write them in there.
How is it possible to set dist<1,3> = 5 for example ?
I want to program a forloop which inserts values in the array. Can you tell me how to do it ?
If i try
<pre class="jivepre">dist[<1,3>] = 4
</pre>
i get an error.
dist[Edges] = ...;
Instead, just define it as
dist[Edges];
and then set the value as you did. This should work 
Re: Scheduling Problem
20120630T16:19:05ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20120628T21:16:26Z
Seems in your code you are reading dist from dat file
<pre class="jivepre">dist[Edges] = ...;
</pre>
Instead, just define it as
<pre class="jivepre">dist[Edges];
</pre>
and then set the value as you did. This should work
I always get an syntax errror ! 
Re: Scheduling Problem
20120702T13:07:56ZThis is the accepted answer. This is the accepted answer. Voigtler
 20120630T16:19:05Z
It doesn't work that way.
I always get an syntax errror !
execute { for(e in Edges) if(e.i==3 && e.j==4) dist[e] = 4; }

Re: Scheduling Problem
20120731T10:02:16ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20120702T13:07:56Z
Can you try this one:
<pre class="jivepre">execute { for(e in Edges) if(e.i==3 && e.j==4) dist[e] = 4; }
</pre>using CP; int nbgoods = 5; range allgoods = 1..nbgoods; int width[allgoods] = [16, 5, 9, 5, 8]; * int cost_narrow_broad = 2;* * int cost_broad_narrow = 1;* dvar interval treatment[g in allgoods] size 1; dvar sequence seq in all(g in allgoods) treatment[g] types all(g in allgoods) g; dexpr float deltaw = sum(g in allgoods) abs(width[g]width[typeOfNext(seq, treatment[g], g)]); execute { cp.setSearchPhases(cp.factory.searchPhase(seq)); } minimize cost * deltaw; subject to { noOverlap(seq); }
I modelled a solution as TSP, which works quite good for small problems. But for lager problems the problem is solved to slow. So i want to try it with CP to stop solving after a certain period of time, to get a good, but not optimal solution.
So i want to use the first attempt again. The problem is, that i have to distinguish between a width change from broad>narrow and narrow>broad.
But i have no idea, how to model it.
I hope somebody can give me a hint, how to do it 
Re: Scheduling Problem
20120803T10:59:00ZThis is the accepted answer. This is the accepted answer. Voigtler
 20120731T10:02:16Z
<pre class="jivepre">using CP; int nbgoods = 5; range allgoods = 1..nbgoods; int width[allgoods] = [16, 5, 9, 5, 8]; * int cost_narrow_broad = 2;* * int cost_broad_narrow = 1;* dvar interval treatment[g in allgoods] size 1; dvar sequence seq in all(g in allgoods) treatment[g] types all(g in allgoods) g; dexpr float deltaw = sum(g in allgoods) abs(width[g]width[typeOfNext(seq, treatment[g], g)]); execute { cp.setSearchPhases(cp.factory.searchPhase(seq)); } minimize cost * deltaw; subject to { noOverlap(seq); }
</pre>
I modelled a solution as TSP, which works quite good for small problems. But for lager problems the problem is solved to slow. So i want to try it with CP to stop solving after a certain period of time, to get a good, but not optimal solution.
So i want to use the first attempt again. The problem is, that i have to distinguish between a width change from broad>narrow and narrow>broad.
But i have no idea, how to model it.
I hope somebody can give me a hint, how to do it
many ways are possible, for example, you can modify the objective function as follows:
using CP; int nbgoods = 5; range allgoods = 1..nbgoods; int width[allgoods] = [16, 5, 9, 5, 8]; int cost_narrow_broad = 2; int cost_broad_narrow = 1; dvar interval treatment[g in allgoods] size 1; dvar sequence seq in all(g in allgoods) treatment[g] types all(g in allgoods) g; dexpr float cost = sum(g in allgoods) ( ((width[g]>width[typeOfNext(seq, treatment[g], g)]) * cost_broad_narrow + (width[g]<=width[typeOfNext(seq, treatment[g], g)]) * cost_narrow_broad) * abs(width[g]width[typeOfNext(seq, treatment[g], g)])); execute { cp.setSearchPhases(cp.factory.searchPhase(seq)); } minimize cost; subject to { noOverlap(seq); }
Or you can take the max an not the sum of the cost terms, or you can build an array where indices are all the possible differences of widths, ... Depending on your data, some approaches may be better than others.
Regards,
Olivier