[rules-users] performance issue in planning and scheduling application

[Co Nijn]

Hi,

I’m interested in the application of Drools in the planning and scheduling
domain. In a planning application a planner can take planning decisions and
the system will determine all consequences of the planning decision
automatically and provides immediate visual feedback of these consequences.
For example, suppose that we have a number of machines and a number of jobs
and each job must be allocated to one of the machines; the objective is to
minimize the completion time of the latest job. In this case, there are two
types of planning decision: allocating a job to a machine and sequencing the
jobs on each machine.

I’ve been experimenting for a while to employ Drools 5.0 to determine the
consequences of the planning decisions. Many business rules in the planning
and scheduling domain are in fact calculations that express the
(declarative) dependency of an attribute of an object on the attributes of
one or more other objects. For the machine scheduling problem we have the
following business rules:

   - A Job must be allocated to one Machine.
   - A Machine can process at most one Job at a time.
   - The completion time of an Allocation is equal to the start time of the
   Allocation plus the processing time of the Job.
   - An Allocation must not start before the release date of the Job
   - An Allocation must be completed before or at the due date of the Job.

These rules can be formulated in Drools, for example:

rule "BR-ALLOCATION.COMPLETION_TIME"

                when

                               $job : Job($procTime : procTime)

                               $allocation : Allocation($startTime :
startTime, job == $job)

                then

                               $allocation.setCompletionTime($startTime +
$procTime);

end



Unfortunately my approach does not scale very well. I guess that this is
related to the way in which RETE works by keeping all possible pairs of Jobs
and Allocations in memory, although each Job is associated (object
reference) with at most one Allocation. Is there any which in which Drools
can take advantage of the fact that a Job has an explicit reference to an
Allocation? Do you have any suggestions on how to improve the performance?

In planning and scheduling applications it is not uncommon to have up to a
million objects in the working memory.

Regards,

Robin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20090605/5e912e49/attachment.html