Decision Optimization

Originally posted by: AndyHam

Suppose there are five tasks with a single machine.
The machine consumes huge energy and its price changes hourly. 
hr     price
0~3: $10
3~4: $15
4~6: $12
6~ :  $8
Can you please help me to compute the total energy fee to process the five tasks?
The total cost should be computed as follows: sum(i in 1..5) sizeOf(a[i])*price

using CP;
pwlFunction ETCost = piecewise {10 -> 3; 15 -> 4; 12 -> 6; 8 };
dvar interval a[i in 1..5] size i;
minimize sum(i in 1..5) endEval(a[i], ETCost);

Thanks,
Andy

Originally posted by: PhilippeLaborie

Hi Andy,

I think there are two ways to model it in CP Optimizer.

The most efficient one: if the duration of the task a[i] is known (say, D[i]), you could pre-compute a piecewise linear function C[i](t) that gives the cost of task when started at a date t, that is the sum of the cost function (known) between t and t+D[i]. And then, use a similar model as the one you show, using startEval(a[i],C[i]) as cost to minimize. 

The shortest to implement: in fact you can also exploit the relation between the size and the length of an interval variable (the size is the sum of the intensity step function between the start and end of the interval variable) to represent the total cost. There is a small issue because the size of an interval variable is always smaller than its length, so you would have to rescale the model. Here is an example with your data:

int n = 5;
stepFunction C = stepwise { 0->0; 10->300; 15->400; 12->600; 8 };

dvar interval a[i in 1..n]  in 0..2000 intensity C;

minimize sum(i in 1..n) sizeOf(a[i]);
subject to {
  forall(i in 1..n) {
    lengthOf(a[i]) == 100*i; // Fix length of tasks to their duration value
    startOf(a[i])%100 == 0;  // All tasks must start (and end) at a multiple of the time scale (100)
  }
  noOverlap(a);
}

Originally posted by: AndyHam

Hi Philippe,
Thanks for the advice. I prefer an efficient one so I tried to implement the first method ^^
I have an error in putting the cost values into the piecewise function.
For instance, if we start job 4 at time 4, it will cost $40 (=12+12+8+8).
Would you please tell me my mistake?

using CP;
pwlFunction ETCost[i in 1..5] =piecewise
{{0->10;1->10;2->10;3->15;4->12;5->12;6->8;7->8;8->8;9->8;10->8;11->8;12->8;13->8;8},
{0->20;1->20;2->25;3->27;4->24;5->20;6->16;7->16;8->16;9->16;10->16;11->16;12->16;13->16;16},
{0->30;1->35;2->37;3->39;4->32;5->28;6->24;7->24;8->24;9->24;10->24;11->24;12->24;24},
{0->45;1->47;2->49;3->47;4->40;5->36;6->32;7->32;8->32;9->32;10->32;11->32;32},
{0->57;1->59;2->57;3->55;4->48;5->44;6->40;7->40;8->40;9->40;10->40;40}};
dvar interval a[i in 1..5] size i;
dvar sequence seqMch in  all(i in 1..5) a[i];
minimize sum(i in 1..5) startEval(a[i], ETCost[i]);
subject to {
    noOverlap(seqMch); 
}

 

Originally posted by: PhilippeLaborie

The syntax of piecewise linear functions is described here: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cpo.help/refcppcpoptimizer/html/pwl_and_sw_functions.html#55

You need to pass the slope of every step before the x value: slope -> value.

Here is an example with the last function (size=5):

int T=14;
int C[0..T] = [57, 59, 57, 55, 48, 44, 40, 40, 40, 40, 40, 40, 40, 40, 40 ];
pwlFunction Cost = piecewise(t in 0..T-1) { C[t+1]-C[t]-> t+1; 0}(0,C[0]);

Originally posted by: AndyHam

Thanks for the help.
I put it into the problem.
I confirmed that CP results match with the manual calculation of $141.
I finally understood piecewise and Eval ^^

using CP;
int T=14;
int C[1..5][0..T] =
[
[10,    10,    10,    15,    12,    12,    8,    8,    8,    8,    8,    8,    8,    8,    8],
[20,    20,    25,    27,    24,    20,    16,    16,    16,    16,    16,    16,    16,    16,    0],
[30,    35,    37,    39,    32,    28,    24,    24,    24,    24,    24,    24,    24,    24,    0],
[45,    47,    49,    47,    40,    36,    32,    32,    32,    32,    32,    32,    32,    32,    0],
[57,    59,    57,    55,    48,    44,    40,    40,    40,    40,    40,    40,    40,    40,    0]
];

pwlFunction Cost[i in 1..5] = piecewise(t in 0..T-1) { C[i][t+1]-C[i][t]-> t+1; 0}(0,C[i][0]); 
dvar interval a[i in 1..5] size i;
minimize sum(i in 1..5) startEval(a[i], Cost[i]);
subject to {
     startOf(a[1])==0;
     startOf(a[2])==1;
     startOf(a[3])==3;
     startOf(a[4])==6;
     startOf(a[5])==10;     
}