[rules-users] best rule for grouping planning entities?
Reinis
drools at orbit-x.de
Wed Jan 23 16:48:08 EST 2013
Hello Michiel,
Wolfgang Laun pointed me to your question.
I believe we have discussed this type of challenge with Wolfgang during
our drools meet-up some weeks ago.
So far I see two possible causes for your challenge:
1. Your domain problem requires weighted or even Pareto score
calculation (check out drools planner doc "5.1.2. Positive and negative
constraints"). In praxis I often use some function or magic number to
weigh one constraint against another;
2. You indeed might have a score trap. The suggestion of Geoffrey is
correct in this case, but your solution might not. I presume that
gapCount is not sufficient to avoid score trap.
Consider this scenario (where [t] = task and - = time unit)
[t]-----------[t]-[t]-[t]-[t] = 4 (gapCount)
[t]-[t]-[t]-[t]-[t] = 4 (gapCount)
In this case you would have to penalize gaps based on distance between
two tasks.
If you are considering distance, then consider this scenario
[t]-----------[t]-[t]-[t]-[t] = 14 (sum of time units in between)
[t]---[t]----[t]----[t]---[t] = 14 (sum of time units in between)
If this is the case, you can use a function (e.g. power, square-root,
natural logarithm) that penalize the distances in a non-linear way (the
further, the more penalty).
I find that the weighing of the soft constraints is a real PITA not
because of the way drools planner support it, but because of the nature
of the constraint weighing itself.
I hope it helps you to move on with your issue and thanks to Wolfgang
for pointing your message out and recognizing similarity of the problem.
br
Reinis
On 01/23/2013 09:08 AM, Michiel Vermandel wrote:
> Hi,
>
> I need to group a number of entities together and I'm not sure if my
> rule is optimal.
>
> My planning entities represent maintenance tasks on airplanes.
> Every planning entity is a discreet task (check tires, refuel, check
> engines...) but the maintenance of an airplane exists of a number of
> these tasks and they need to be grouped together.
> Every task has a duration depending on its type (checking engine takes
> longer than checking tires).
> The optimal solution is that all tasks of a maintenance are in the
> smallest amount of time (time between start of first task till end of
> last task).
> Though, the smaller the better, at least all tasks should be
> sequential (without gaps between the tasks).
> Dependencies on the tasks are availability of the plain, availability
> of the technicians...
>
> (The rules beneath only check that the tasks are chained together, not
> (yet) that the time span is minimal => I thought to make a
> soft-constraint for that).
>
> First I had this rule:
>
> rule "tasksInSameMaintenanceJobMustBeChained"
> when
> $task : Task( $jobId: jobId )
> not ( Task( jobId== $jobId, id != $task.id,
> ($task.startPeriodId-1) <= endPeriodId && ($task.endPeriodId+1) >=
> startPeriodId ) )
> then // we have a gap!
> insertLogical(new
> IntConstraintOccurrence("tasksInSameMaintenanceJobMustBeChained",
> ConstraintType.NEGATIVE_HARD, Importance.chainedPeriod, $jobId, $task));
> end
>
> After adding this rule I started struggling with what I believe is to
> be a score trap.
> After advice from Geoffrey and reading some more, I thought my rule
> suffered from having a penalty which did not change depending on the
> amount of spread of the tasks.
>
> So I rewrote the task to:
> (I have now put all MaintenanceJobs into the working memory and I
> created a Class TaskSet() which is capable of calculating the nr of
> periods between all tasks of a job = gapCount)
>
> rule "tasksInSameMaintenanceJobMustBeChained"
> when
> $job: MaintenanceJob()
> $taskset : TaskSet( gapCount > 0 )
> from accumulate( $task : Task(jobId== $job.id),
> init( TaskSet taskset = new
> TaskSet(); ),
> action( taskset.addTask( $task ); ),
> reverse( taskset.removeTask( $task
> ); ),
> result( taskset ) );
> then
> insertLogical(new
> IntConstraintOccurrence("tasksInSameMaintenanceJobMustBeChained",
> ConstraintType.NEGATIVE_HARD, Importance.chainedPeriod *
> $taskset.getGapCount(), $job, $taskset));
> end
>
> I see a difference in score but still not optimal and terminated on
> time limit reached.
>
> 1) Is this rule as good as it can be? Or am I creating some issue here?
>
> A Task (planning entity) has 3 different planning variables.
> 2) When I analyze the Trace logging I see that during the first steps
> the 3 variables are switched during moves, but then after a while
> only one of the 3 variables gets changed and the other variables of
> all tasks remain as they are.
>
> Should I conclude something out of that?
>
> This is my local search config:
>
> <localSearch>
> <termination>
> <terminationCompositionStyle>OR</terminationCompositionStyle>
> <maximumSecondsSpend>3600</maximumSecondsSpend>
> <scoreAttained>0hard/0soft</scoreAttained>
> </termination>
> <unionMoveSelector>
> <changeMoveSelector>
> <valueSelector>
> <!-- ** -->
> <planningVariableName>role</planningVariableName>
> </valueSelector>
> </changeMoveSelector>
> <changeMoveSelector>
> <valueSelector>
> <!-- entity var technician:who will execute the
> task -->
> <planningVariableName>technician</planningVariableName>
> </valueSelector>
> </changeMoveSelector>
> <changeMoveSelector>
> <valueSelector>
> <!-- entity var period: when will the plane get
> maintenance -->
> <planningVariableName>period</planningVariableName>
> </valueSelector>
> </changeMoveSelector>
> <swapMoveSelector>
> </swapMoveSelector>
> </unionMoveSelector>
>
> <acceptor>
> <!-- 3 => small amount of planning entities in unit test -->
> <planningEntityTabuSize>3</planningEntityTabuSize>
> </acceptor>
> <forager>
> <minimalAcceptedSelection>1000</minimalAcceptedSelection>
> </forager>
> </localSearch>
>
> (**) entity var role: every maintenance job has one lead task (role ==
> lead), all other tasks in that job must have role = member. The
> technician assigned to the lead task will file the maintenance report.
> One of the constraints (checked in other rule) is that no technician
> should be lead-technician twice in a row on two sequential maintenance
> jobs.
>
> Thanks in advance.
>
> Michiel
> -----------------
> http://www.codessentials.com - Your essential software, for free!
> Follow us at http://twitter.com/#!/Codessentials
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
More information about the rules-users
mailing list