[rules-users] [planner] Performance question

[Guilherme Kunigami]

Consider I have a set of N activities with a given start and end times and I
want to assign them to a set of rooms.

One of the main rules is to avoid two activities that have time conflicts,
to be assigned to the same room. I devised three modelling options:

[1] Do it entirely in Java code, checking whether there will be a conflict
before allowing an "Assignment move". This way, all solutions that the
algorithm works with are feasible.

[2] Do it using drools rules, like the following:

rule "Avoid conflicting activities"
when
Assignment($room1: room, $act1: activity, $id : activity.id)
 Assignment(room == $room1, room!= null, $act2 : activity, activity.id >
$id)
eval(Activity.conflict($act1, $act2))
then
insertLogical(new IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,
                10, null));
end

Here I'm using Assignment as the only planning entity. There's an assignment
for each activity and it may point to a room or to null in the case the
activity is not assigned. In the case above, I have a static function that
checks whether two activities conflicts. This way, solutions may be
infeasible but with high penalties the best solution found will eventually
be feasible.

I also thought of a third option, which is to insert a fact "Conflict" for
each pair of conflicting activities in a preprocessing phase. This way we
would end up with:

rule "Avoid conflicting activities"
when
Assignment($room1 : room, $act1: activity, $id : activity.id)
Assignment(room== $room1, room != null, $act2 : activity, activity.id > $id)
Conflict(act1 == $act1, act2 == $act2)
then
insertLogical(new IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,
                10, null));
end

The problem is that there may be up to O(N^2) such objects.

I do not know the rules engine algorithm in depth, so I'd like to know: Is
any of these approaches more efficient than the others?

Thanks!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20111019/dbba421b/attachment.html