Hey there,

I'm writing on a CP-model for a timetabling-problem. I have to schedule events for classes in a given time-interval. Each event needs resources like a chemie-lab or driving range. It is possible to 'overbook' a resource. For example: in a time-slot 3 events need resource A, but only 2 are available. The objective-function is to minimize the overbooking.

Now I've got:


    forall(s in timeslots){
    forall(r in resources){
         sum(e in events: r in requirement[e]) 
         ((s.start>=startOf(itvs[e]) && s.end<=endOf(itvs[e]) && resourceassignment[e][r] == 1)? requirementNb[e] : 0 )
         <= 
         resourcesNb[r] + conflict[s,r];
      }
    }

This produces way too much constraints. Since itvs[e] and resourceassignment[e][r] are decision variables, I can't use them in a if-clause. In the worst-case I get card(timeslots) x card(resources) x card(events) x 4 constraints. The consequence is, that an instance with 200 events can't be handled by OPL and I get a 'not enough memory'-error.

Do you have any ideas how I could fix this?

Many thanks, André

asked 06 Apr '13, 07:47

andrep's gravatar image

andrep
636
accept rate: 0%

edited 26 Jul '13, 12:20

fbahr's gravatar image

fbahr ♦
4.6k716


You should use cumulative functions in OPL. Set one such cumulative function per resource. This cumulative function will perform the role of the sum over events and requirements in your code snippet, albeit much more efficiently.

link

answered 06 Apr '13, 08:28

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

I tried cumulative functions, but I've got two problems.

  1. I've a set of resources for the events, so I would need a request like
 resourceUsage[r in resources] = sum(e in events: r in requirement[e] && resourceassignment[e][r] == 1) pulse(interval[e], requirementNb[e]);

but that's not working, 'cause resourceassignment is a decision variable. Any suggestions?

(09 Apr '13, 07:59) andrep
1

You should have a look at the scheduling models provided with OPL. Your events should be represented by interval variables on which you apply cumulative functions.

(10 Apr '13, 06:49) jfpuget

I've done that and my events are interval variables. But you're right. With the cumulative functions it is possible to reduce the used memory, but I have to change my objective function.

(10 Apr '13, 11:57) andrep
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×37
×13
×5
×5

Asked: 06 Apr '13, 07:47

Seen: 1,837 times

Last updated: 26 Jul '13, 12:20

OR-Exchange! Your site for questions, answers, and announcements about operations research.