Is Drools suitable for preprocessing a Resource Allocation Problem_

0
votes

I have a quite big resource allocation problem to compute.

I have just discovered Drools and I would like to know if it is a good candidate to work as a preprocessor and generate a list of forbidden allocations, based on some user rules.

The Problem

I have an optimisation engine that can allocate some activities to some resources, while optimizing some KPIs (Key Performance Indicator).

The optimizer takes as input (among others) a list of forbiden allocations that should be generated based on some user-provided rules.

Each forbid rule is an "AND" composition of two rules:

  • One for the activity
  • One for the resource

Each sub rule is itself a list of "AND" tests on some attributes.

Here is the structure of one rule, in Pseudo-Code

Rule1:
    * ActivityRule
      * activity.prop1 == "foo" AND
      * activity.prop2 == "bar" AND
      * ... 
    * ResourceRule
      * resource.prop3 == "foobar" AND
      * resource.prop4 == "NULL" AND
      * ...

Rule2:
   ...

As soon as a pair of [Activity,Resource] matches one rule, it should be sent as output, and not tested again against other rules.

Also, this is important to note that some rules will match very often, while overs will match very rarely (very specific cases).

Performance constraints

Here are some rough hints about the volumetry of the problem :

  • 1000 activities
  • 200 resources
  • 50 rules

I need the forbidden allocations to be generated in under a minute.

The challenge

As far, as I understand, Drools can surely generate those forbidden allocations. the question is : "How smart is he" ?

If I had to write an engine myself for this particular problem, I would make some improvements :

For example, I would not generate all possible allocations (200.000) and then try to apply each rule on it (50 rules x 200.000).

Instead, I would try to match the resources and the activities separately on each rule (each side of the rule), and then assemble the couples that match at least one common rule.

Also, I would add some counter on each rule that would auto increment upon each match, in order to apply first the rules that match often.

Questions

Is the engine of Drools smart enought for that ? Or is he even smarter ?

Do you have an example of Drools being used in a similar problem with success ?

Thanks in advance for your advice.

1
javaoptimizationdrools

1 Answers

0
votes

There's a bug in your calculation: For 1000 activities and 200 resources, you don't have 200*1000 possible allocations but 200^1000 possible allocations (so more than 10^2000 possible allocations). Are you sure your optimization engine scales that much?

Have you looked into doing resource allocation with Drools Planner instead? Drools Planner can handle such allocation sizes and much bigger too. It searches for the best solution (and scales out well) and it uses Drools to calculate the score (= negative of the number of forbidden allocations) for each solution it evaluates.