Topic
  • 15 replies
  • Latest Post - ‏2012-08-03T10:59:00Z by ol
Voigtler
Voigtler
8 Posts

Pinned topic Scheduling Problem

‏2012-06-18T18:15:49Z |
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 scheduling-problem. 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 width-difference 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 Gannt-Chart, 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.
Updated on 2012-08-03T10:59:00Z at 2012-08-03T10:59:00Z by ol
  • JorisK
    JorisK
    5 Posts

    Re: Scheduling Problem

    ‏2012-06-19T07: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 {G-g}} (w_g-w_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 non-linear 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_g-w_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.
  • Voigtler
    Voigtler
    8 Posts

    Re: Scheduling Problem

    ‏2012-06-19T15:53:43Z  
    • JorisK
    • ‏2012-06-19T07: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 {G-g}} (w_g-w_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 non-linear 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_g-w_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.
    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 {G-g}} (w_g-w_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 {G-g}, that CPLEX understands what i mean?

    Thank you very much again
  • JorisK
    JorisK
    5 Posts

    Re: Scheduling Problem

    ‏2012-06-20T08:01:20Z  
    • Voigtler
    • ‏2012-06-19T15: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 {G-g}} (w_g-w_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 {G-g}, that CPLEX understands what i mean?

    Thank you very much again
    Hey,

    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.
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Scheduling Problem

    ‏2012-06-20T11:06:14Z  
    • Voigtler
    • ‏2012-06-19T15: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 {G-g}} (w_g-w_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 {G-g}, that CPLEX understands what i mean?

    Thank you very much again
    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.

    
    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, setup-times), 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
  • Voigtler
    Voigtler
    8 Posts

    Re: Scheduling Problem

    ‏2012-06-25T08:55:12Z  
    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="jive-pre"> 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, setup-times), 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
    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!
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Scheduling Problem

    ‏2012-06-25T10:05:34Z  
    • Voigtler
    • ‏2012-06-25T08: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!
    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 time-limit (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
  • Voigtler
    Voigtler
    8 Posts

    Re: Scheduling Problem

    ‏2012-06-26T08:11:15Z  
    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 time-limit (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
    Thanks!

    I accidentially changed the time-limit 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 ?
  • Voigtler
    Voigtler
    8 Posts

    Re: Scheduling Problem

    ‏2012-06-26T08:15:30Z  
    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 time-limit (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
    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 ?
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Scheduling Problem

    ‏2012-06-26T14:11:05Z  
    • Voigtler
    • ‏2012-06-26T08: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 ?
    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. Self-Adapting Large Neighborhood Search: Application to Single-Mode Scheduling Problems. In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), 2007, 276-284.

    If you want more general information about CP techniques, a good starting point can be the Handbook of Constraint Programming.

    Philippe
  • Voigtler
    Voigtler
    8 Posts

    Re: Scheduling Problem

    ‏2012-06-28T12:23:47Z  
    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. Self-Adapting Large Neighborhood Search: Application to Single-Mode Scheduling Problems. In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), 2007, 276-284.

    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 for-loop 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.
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Scheduling Problem

    ‏2012-06-28T21:16:26Z  
    • Voigtler
    • ‏2012-06-28T12:23:47Z
    <pre class="jive-pre"> // 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 for-loop which inserts values in the array. Can you tell me how to do it ?

    If i try
    <pre class="jive-pre"> dist[<1,3>] = 4 </pre>
    i get an error.
    Seems in your code you are reading dist from dat file

    
    dist[Edges] = ...;
    


    Instead, just define it as

    
    dist[Edges];
    


    and then set the value as you did. This should work
  • Voigtler
    Voigtler
    8 Posts

    Re: Scheduling Problem

    ‏2012-06-30T16:19:05Z  
    Seems in your code you are reading dist from dat file

    <pre class="jive-pre"> dist[Edges] = ...; </pre>

    Instead, just define it as

    <pre class="jive-pre"> dist[Edges]; </pre>

    and then set the value as you did. This should work
    It doesn't work that way.

    I always get an syntax errror !
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Scheduling Problem

    ‏2012-07-02T13:07:56Z  
    • Voigtler
    • ‏2012-06-30T16:19:05Z
    It doesn't work that way.

    I always get an syntax errror !
    Can you try this one:

    
    execute
    { 
    
    for(e in Edges) 
    
    if(e.i==3 && e.j==4) dist[e] = 4; 
    }
    
  • Voigtler
    Voigtler
    8 Posts

    Re: Scheduling Problem

    ‏2012-07-31T10:02:16Z  
    Can you try this one:

    <pre class="jive-pre"> 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
  • ol
    ol
    43 Posts

    Re: Scheduling Problem

    ‏2012-08-03T10:59:00Z  
    • Voigtler
    • ‏2012-07-31T10:02:16Z
    <pre class="jive-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); } </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
    Hello,
    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