Topic
  • 4 replies
  • Latest Post - ‏2013-10-23T17:15:38Z by 5HNY_Imad_Abdeljaouad
5HNY_Imad_Abdeljaouad
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,

Updated on 2013-10-25T22:19:23Z at 2013-10-25T22:19:23Z by 5HNY_Imad_Abdeljaouad
  • JorisK
    JorisK
    26 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? 

  • 5HNY_Imad_Abdeljaouad
    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,

    Updated on 2013-10-25T22:17:18Z at 2013-10-25T22:17:18Z by 5HNY_Imad_Abdeljaouad
  • JorisK
    JorisK
    26 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
  • 5HNY_Imad_Abdeljaouad
    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.

    Updated on 2013-10-25T22:15:28Z at 2013-10-25T22:15:28Z by 5HNY_Imad_Abdeljaouad