[gecode-users] Scheduling constraints

[Vladimír Dusa]

Hello,

sorry, of course I meant preemptive schedule. Thank you for your answer ant
for the link to Le Pape's notes - I will read it too. I have now the Book
"Constraint-based scheduling" (Baptiste, Le Pape, Nuijten), where I found
lot of information about scheduling too.

But my problem is a little bit harder because moreover I need to assign
resource to the task from a given set of alternative resources (these sets
of resources must not be necessarily dijoint). It can be done by splitting
the tasks for each resource from the set of alternative resources and search
schedule with all these acitivities. Whenever the bounds of an splitted
activity turn out to be incoherent, the resource can be simply removed from
the set of possible alternative resources for the activity.

But for the propagating and branching I probably need to create my own
propagater and branch function (or not?). I would ask, if is there some
better documentation how to do this - because it is quite hard to do it only
with gecode documentation generated by doxygen.

Thank you very much

Best regards

Vladimír Duša

-----Original Message-----
From: Mikael 'Zayenz' Lagerkvist [mailto:zayenz at gmail.com]
Sent: Wednesday, March 08, 2006 1:26 PM
To: Vladimír Dusa
Subject: Re: [gecode-users] Scheduling constraints


On 3/8/06, Vladimír Dusa <vdusa at bsa-informatik.ch> wrote:
> I would like to create a program for optimizing elastic non-preemptive
> cumulative schedule. Resources will be first of all people. Any resource
can
> work at any time on more tasks simultaneusly. Activities can be
interrupted
> at any time to let some other activities execute and amount of resource
> assigned to some activity can at any time assume any value between 0 and
> resource capacity. In some defined time interval with fixed length placed
> arbitrary in schedule cannot be the resource capacity exceeded.

I believe you mean "elastic cumulative schedule" here, since
non-preemptive would mean that activities could not be interrupted.


> I found in gecode environment some "Gecode::cumulative" propagator, but no
> example how to use it. If is there no such example, could you give mi a
hint
> how can I learn using scheduling propagators in gecode?

The cumulative(s) constraint in Gecode models non-preemptive
scheduling problems, i.e., where the tasks can not be interrupted, and
the amount of resources used is constant for the whole duration of the
task. There is no specific constraint available in Gecode for elastic
or preemptive problems.

The cumulatives constraint is used in one example in Gecode,
examples/packing.cc, although it is not a good propagator for that
particular application.

If you want to read more about how to model different types of
scheduling-problems with constraint programming, I could recommend
Claude Le Pape's notes from the Summer Course in constraint
programming last year (available at
http://www.math.unipd.it/~frossi/cp-school/lepape.pdf).

Hope this helps
Mikael

--
Mikael 'Zayenz' Lagerkvist, http://www.imit.kth.se/~zayenz/