[gecode-users] Scheduling constraints

[Mikael 'Zayenz' Lagerkvist]

On 3/8/06, Vladimír Dusa <vdusa at bsa-informatik.ch> wrote:
> 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.

The cumulatives constraint that is available allows one to specify
scheduling problems where the tasks may be allocated to different
machines (governed by the machine-parameter of the constraint). As
said previously though, this is only for non-preemptive problems.

My suggestion would be to first try to do some decomposition of the
problem into the available constraints, even if this leads to a very
inefficient model. This would give you something to compare against
for propagators that you implement yourself.

As for documentation, the doxygen-generated documentation is intended
as a reference, and not a tutorial. Writing some tutorial-like
documentation is definitely on our todo-list. There are two papers in
which important aspects of the Gecode architecture is discussed that I
can recommend, "Views and Iterators for Generic Constraint
Implementations" and "Speeding Up Constraint Propagation", both
available from http://www.gecode.org/publications.html. Apart from
that, I would recommend you to look at the implementation of some
propagator that you are familiar with, and see how it is done.

Hope this helps
Mikael


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