Topic
• 4 replies
6 Posts

# Pinned topic energy scheduling problem

‏2013-10-22T17:45:01Z |

Hi folks,
I am wondering if I can model the following problem with CP:
I have n jobs, each has to run for a known number of timeslots, and each consume a known amount of resource per timeslot. I need to schedule the running times for each job within a fixed interval of timeslots (say 1 to 12), so that the total amount of resource consumed in each timeslot is minimized. Keep in mind that the jobs can be interrupted, meaning that a job can run from timeslot 1 to 2, then from 5 to 6, then from 9 to 11. I am not sure if CP can do that. And if it can, any help would be greatly appreciated (even a small example on how to get started with the model).

PS. I have tried reading and writing the model but I cannot find a way to calculate the resource usage per timeslot !

Thanks,

• JorisK
51 Posts

#### Re: energy scheduling problem

‏2013-10-22T18:36:02Z
hi,

you can probably do what you want in CP. But your problem can be easily modelled as a MIP problem.

x_ij= appliance i runs in time slot j.
y_j= amount of energy consumed in time slot j

d_i= total number of time slots required to run appliance i

Minimize y
\sum_j x_ij=d_i \for all i
y >= \sum_i x_ij \for all j
x_ij boolean
y_j integer

The first constraints states that each appliance must be scheduled in sufficient time slots. The second constraint ensures that variable y records the amount of energy required by the time slot that requires the largest amount of energy.

Btw, I'm not sure whether there are more constraints in your problem, but it seems to me that you can solve this problem to optimality with a simple heuristic?

• 6 Posts

#### Re: energy scheduling problem

‏2013-10-22T18:56:57Z
• JorisK
• ‏2013-10-22T18:36:02Z
hi,

you can probably do what you want in CP. But your problem can be easily modelled as a MIP problem.

x_ij= appliance i runs in time slot j.
y_j= amount of energy consumed in time slot j

d_i= total number of time slots required to run appliance i

Minimize y
\sum_j x_ij=d_i \for all i
y >= \sum_i x_ij \for all j
x_ij boolean
y_j integer

The first constraints states that each appliance must be scheduled in sufficient time slots. The second constraint ensures that variable y records the amount of energy required by the time slot that requires the largest amount of energy.

Btw, I'm not sure whether there are more constraints in your problem, but it seems to me that you can solve this problem to optimality with a simple heuristic?

Hi, I thought about that too but I do have another constraint on the finish time (delay) which is the last timeslot in which the job uses resource. This constraint is straight forward in CP and that's why I wanted to use CP. Do you have any idea how it can be translated into the model you are proposing ?

Thanks,

• JorisK
51 Posts

#### Re: energy scheduling problem

‏2013-10-22T20:05:49Z

Hi, I thought about that too but I do have another constraint on the finish time (delay) which is the last timeslot in which the job uses resource. This constraint is straight forward in CP and that's why I wanted to use CP. Do you have any idea how it can be translated into the model you are proposing ?

Thanks,

I cannot really answer your question without knowing the exact constraint? What constraint do you have on the finish time of an appliance?

Lets say you want to minimize both the amount of energy consumed in a time slot as well as the finish time of your appliances. This you could do using the following model:

x_ij= appliance i runs in time slot j.

y_j= amount of energy consumed in time slot j

c_i=completion time of appliance i

d_i= total number of time slots required to run appliance i

Minimize y + \sum_i c_i
\sum_j x_ij=d_i \for all i
y >= \sum_i x_ij \for all j

c_i >= j * x_ij  \for all i,j

x_ij boolean
y_j integer

c_i integer

If an appliance i needs to be finished before time slot k, simply set all x_ij with j>= k to zero. Avoid adding a constraint like c_i <= k here.

Similarly, you can require that an appliance does not start before a given time slot.

Btw, a very nice text about scheduling with CP optimizer, including a large number of examples: Modeling with IBM ILOG CP Optimizer -

Practical Scheduling Examples
You might need to Google this as IBM's website is quite a maze. Try this link: http://www-01.ibm.com/common/ssi/cgi-bin/ssialias?infotype=SA&subtype=WH&htmlfid=WSW14076USEN
• 6 Posts

#### Re: energy scheduling problem

‏2013-10-23T17:15:38Z
• JorisK
• ‏2013-10-22T20:05:49Z

I cannot really answer your question without knowing the exact constraint? What constraint do you have on the finish time of an appliance?

Lets say you want to minimize both the amount of energy consumed in a time slot as well as the finish time of your appliances. This you could do using the following model:

x_ij= appliance i runs in time slot j.

y_j= amount of energy consumed in time slot j

c_i=completion time of appliance i

d_i= total number of time slots required to run appliance i

Minimize y + \sum_i c_i
\sum_j x_ij=d_i \for all i
y >= \sum_i x_ij \for all j

c_i >= j * x_ij  \for all i,j

x_ij boolean
y_j integer

c_i integer

If an appliance i needs to be finished before time slot k, simply set all x_ij with j>= k to zero. Avoid adding a constraint like c_i <= k here.

Similarly, you can require that an appliance does not start before a given time slot.

Btw, a very nice text about scheduling with CP optimizer, including a large number of examples: Modeling with IBM ILOG CP Optimizer -

Practical Scheduling Examples
You might need to Google this as IBM's website is quite a maze. Try this link: http://www-01.ibm.com/common/ssi/cgi-bin/ssialias?infotype=SA&subtype=WH&htmlfid=WSW14076USEN

Thanks for your prompt response, I really appreciate it.

I looked at your model and it seems to be perfect, although that's not exactly what I am looking for. However, I think I can adjust it to my needs. Thank you for the tutorial too, finding quality information like the link you provided on the website is a nightmare.

I will give it a try and let you know if I need further assistance.