Originally posted by: dayouwang

Dear all,

I want to solve a scheduling problem with constraint programming, but i met some diffcults with it.

A set of demands must be covered by the resources. Each of the demands, which has a fixed duration and a fixed resource requirement (power), must be covered within time period [rel, due], in which rel is the release time as earliest starting time and due is the deadline as latest finishing time. The price of resource (an step function) is time variant as illustrated in the figure in the attachment.

There is a capacity constraint on resource, which means in a given time period, the total used resource can not exceeds a given value. To finde is a schedule that minimize the total cost of resource usage in the whole time periode.

Given values of demands:

Given values of resource:

time variant price,  capacity constraint with value CapCons in time period [t1, t2]

To find:

dvar interval Demands[d in Demand]  in d.rel .. d.due  size d.duration ;

objective:

minimize sum (d.power * price of resource * d.duration)

constraint:

sum (d.power) <= CapCons  in [t1, t2]

I have tried to use the CumulFunction to describe the time variant price of resource, but it seems that it is difficult to use it in objective, because the price of resource is not fixed.

I will be very gratitude, if somedoby could wirte the code for this problem.

best,

Dayou

Hi,

what you could try is to split each resources r in resources with same cost r1, r2, ... rn.

All r1, rn can help the same way to the work done.

But they do not have the same cost.

regards

Originally posted by: dayouwang

Hey Alex,

Thank you for your answer.

But how can i deal with the case, that a demand  is to be covered between two resources, as illustrated in the figure, demand 1 is covered between two resources with cost 2 and 4 ?

Or with another word: if the time horizon of the resource, which has a cost 5, is only 1 hour, but i do NOT have a demand that has a fixed duration of 1 hour exactly, and all of the demands are uniterruptible.

regards,

Dayou

Hi

if the time horizon of the resource, which has a cost 5, is only 1 hour

then the length of the interval will be one hour and this interval will be optional and if this interval is present then you get 5 more in the cost

regards

Originally posted by: dayouwang

Thank you Alex.

Originally posted by: PhilippeLaborie

Hello,

If I understand well, you have two completely different aspects on the resource:

1- A maximal capacity that constrains the demand activities that can simultaneously execute on the resource. For this constraint, you indeed should use a cumulFunction with alwaysIn constraints to state the maximal energy available on some time windows [t1,t2)

2- The energy cost. This cost does not seem to be related with the number of activities simultaneously executing at a given date, it has no "cumulative" aspect and thus I don't think the cumulFunction is the good concept for that. My understanding is that this cost can be computed individually for each activity a_i and if an activity a_i requiring q_i resource units is schedule to start at s_i and end at e_i, the cost is something like c_i = q_i * sum(t in [s_i..e_i)) Price(t) dt, where sum denotes the integral of the (known) price function over time. I see two possible formulations for that in CPO:

2a- There is a CPO concept that computes the integral of a known stepwise function between the start and the end of an interval variable: the notion of interval size and intensity function. An intensity step function Intensity(t) can be specified when creating an interval variable. Then the relation between the size of the interval variable is constrained to be equal to sum(t in [s_i..e_i)) Intensity(t) / 100. The magic constant 100 is because in fact CPO needs a step function that is always <= 100 (this function represents a percentage) so that Intensity(t) / 100 is in [0,1) and the size is always smaller or equal to the length (end-start) of the interval variable. But in your application you may be able to rescale the time scale so that you get the suitable precision on your price/size values. In this case the cost would be something like c_i=K*q_i*sizeOf(a_i) where K is a scaling factor.

2b- You can compute by yourself the integral of the price function IPrice(t) = sum(u in [0..t)) Price(t) dt, this will be a piecewise linear function. Then you can get the cost of an interval variable a_i by c_i = q_i*(endEval(a_i,IPrice)-startEval(a_i,IPrice)). But be aware that formulation 2a will propagate better because by 2b, you are loosing the correlation between the end and start points.

Hope it helps,

Philippe

Originally posted by: dayouwang

Dear Philippe,

Thank you very much for your answer.

I have also thought of using Intensity(t) to describe the resource with time variant cost.

So, Price(t) is defined as :

dvar interval price in 0..24 intensity P;

P denotes the time variant price signal of resource.

A demand with earliest starting time rel and latest finishing time due and fixed duration,  is defined as:

dvar interval demand [d in Demands] in rel..due size dura;

If we take a look at demand 4 (green) in the figure, a possible processing time period for demand 4 is over the time period, in which the price signal has cost of 7, 4, and 2. We just knew that s_i >= rel and e_i <= due, how should i write the code to calculate the cost for demand 4 in this case?

best,

Dayou

Originally posted by: PhilippeLaborie

No. The intensity is associated with the activities. I meant a model like this:

using CP;

tuple DemandData {
  int rel;
  int due;
  int duration;
  int power;
}

{DemandData} Demand = { 
  <0, 100, 25, 12>,
  <0, 100, 15, 23>,
  <0, 100, 77, 17>,
  <0, 100, 72, 21>,
  <10, 90, 35, 20>
};      

int K = 1000;
stepFunction Price = stepwise { 100->0*K; 20->10*K; 40->20*K; 50->30*K; 70->40*K; 40->60*K; 20->80*K; 10->100*K; 50 };

dvar interval Demands[d in Demand] in d.rel*K .. d.due*K intensity Price; 

cumulFunction PowerDemand = sum(d in Demand) pulse(Demands[d], d.power);

minimize sum(d in Demand) (d.power*sizeOf(Demands[d])/K);
subject to {
  forall (d in Demand) {
    // Length of each demand (end-start) is fixed  
    // Size will define the cost
    lengthOf(Demands[d]) == d.duration*K;
  }
  // Maximal power supply over some time-windows
  alwaysIn(PowerDemand, 0*K,  50*K, 0, 50);   // Max power is 50 over time window [0,50)
  alwaysIn(PowerDemand, 50*K, 100*K, 0, 60);  // Max power is 60 over time window [50,100) ...
}

Philippe

Originally posted by: dayouwang

Dear Philippe,

I prefer to the 2a to formulate the price function using intensity, the only thing that i have not compeletly understood is:

minimize sum(d in Demand) (d.power*sizeOf(Demands[d])/K);

The price function (intensity) does not appear in this objective function, i guess it is because of scalling factor K, but i do not understand how does K work?

In addition, if i want to compare CP with another optimizations methode, for exemple with MILP, to check which methode is more suitable for this scheduling problem, can you please also help me to code it with MILP or some another optimizations methode?

Thanks a lot!!

best,

Dayou

Originally posted by: PhilippeLaborie

Hello Dayou,

The price function appears in the objective function thanks to the term sizeOf(Demands[d]). Ead interval variable Demands[d] is defined with the Price function as intensity function:

dvar interval Demands[d in Demand] in d.rel*K .. d.due*K 
intensity Price;

This means that by definition:

sizeOf(Demands[d]) = sum(t in startOf(Demand[d])..endOf(Demand[d])) { Price(t) dt } / 100

The constant K is only a technical constant that you can choose large enough to have enough precision on the cost as sizeOf(Demands[d]) always is an integer and Price(t) should be between 0 and 100.

As for a MIP model, the most direct one is a so called time-indexed formulation with Boolean variables x_it that describes if an activity a_i starts (or is executing) at a given date t. So its size will depend on how you discretize the time values. The size of the CP Optimizer model does not depend on the time-unit (for instance in the type of model I described, the complexity only marginally depends on the choice of the factor K). So if you have few time points, a MIP model may make sense otherwise it will be very large.

Philippe