[rules-users] Best model for planning? technicians, airplanes and shifts
Michiel Vermandel
mvermand at yahoo.com
Fri Aug 31 09:07:33 EDT 2012
Hi, me once more.
I guess you figured out by now that I am quite a newbie to Drools (planning).
Problem is I need to write a POC in max 3 to 4 days...
I'm drifting, so please help...
I have written a basic solution for planning plane-maintenance.
I stripped it to it's very basics and it works... if I keep the number of planes, periods and technicians to a very minimum.
I removed all additional constraints like skill matching and availability during a period...
Planning maintenance for 3 planes with each 2 required technicians, 4 available periods and a list of 10 available technicians delivers a solution in about 3 seconds.
Simply increasing the number of technicians per plane from 2 to 3 results in an indefinite solving time (I did not wait longer than a few minutes).
Decreasing the numbers obviously works, at an elapsed time slightly under 3 seconds.
I finally need to plan about 500 plane maintenance jobs (3 to 4 technicians per maintenance job) over 12 available periods with about 400 available technicians..
So there must be something wrong/incomplete in my solution.
What I did:
I have created a planningEntity MaintenanceTask with two planning variables (technician and period) and a simple rule file.
(See all below)
Running this solution thus results in such poor solving time.
Can you please advice me in what I am doing wrong?
Many thanks!!
PlanningEntity (MaintenanceTask .java):
@PlanningEntity(difficultyWeightFactoryClass = TaskDifficultyWeightFactory.class)
public class MaintenanceTask {
private Period period;
private Project project;
private Technician technician;
public MaintenanceTask (Project aProject) {
this.project = aProject;
}
public String getId(){
return project.getId()+"-"+hashCode();
}
@PlanningVariable
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty = "technicians")
public Technician getTechnician() {
return technician;
}
public void setTechnician(Technician aTechnician) {
this.technican= aTechnician;
}
@PlanningVariable
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty = "periods")
public Period getPeriod() {
return period;
}
public void setPeriod(Period aPeriod) {
this.period = aPeriod;
}
public String getPeriodId(){
return period == null ? null : period.getId();
}
public String getProjectId(){
return project == null ? null :project.getId();
}
public MaintenanceTask clone() {
MaintenanceTask clone = new MaintenanceTask (project);
clone.period = this.period;
clone.technician= this.technician;
return clone;
}
}
Project.java
public class Project {
private Plane plane;
public Project(Plane aPlane) {
this.plane = aPlane;
}
public Plane getPlane() {
return plane;
}
public String getId() {
return getPlane().getName();
}
public int getTechnicianLoad(){
return getPlane().getTechnicianLoad();
}
public List<MaintenanceTask> getTasks() {
List<MaintenanceTask> tasks = new ArrayList<MaintenanceTask>();
for (int i = 0; i < getTechnicianLoad(); i++) {
tasks.add(new MaintenanceTask(this));
}
return tasks;
}
}
Technician.java and Period.java are at this moment basically just classes having an getId and getName method, nothing more.
Plane.java has a method getTechnicianLoad that returns the number of required technicians for the maintenance.
This is the config file (basically copy from one of the examples)
<?xml version="1.0" encoding="UTF-8"?>
<solver>
<!-- Domain model configuration -->
<solutionClass>be.axi.planner.domain.MaintenanceSchedule</solutionClass>
<planningEntityClass>be.axi.planner.domain.MaintenanceTask</planningEntityClass>
<!-- Score configuration -->
<scoreDirectorFactory>
<scoreDefinitionType>SIMPLE</scoreDefinitionType>
<scoreDrl>/maintenancePlannerRules.drl</scoreDrl>
</scoreDirectorFactory>
<termination>
<maximumSecondsSpend>700</maximumSecondsSpend>
</termination>
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
<constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType>
</constructionHeuristic>
<localSearch>
<selector>
<moveFactoryClass>org.drools.planner.core.move.generic.GenericChangeMoveFactory</moveFactoryClass>
<!-- GenericChangeMoveFactory is the generic form of RowChangeMoveFactory: -->
<!--<moveFactoryClass>org.drools.planner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveFactoryClass>-->
</selector>
<acceptor>
<solutionTabuSize>1000</solutionTabuSize>
<planningEntityTabuSize>7</planningEntityTabuSize>
</acceptor>
<forager>
<minimalAcceptedSelection>800</minimalAcceptedSelection>
</forager>
</localSearch>
</solver>
this is the rules file:
package org.drools.planner.examples.pas.solver;
dialect "java"
import org.drools.planner.core.score.buildin.simple.SimpleScoreHolder;
import org.drools.planner.core.score.constraint.IntConstraintOccurrence;
import org.drools.planner.core.score.constraint.UnweightedConstraintOccurrence
import org.drools.planner.core.score.constraint.ConstraintType;
import be.axi.planner.domain.MaintenanceTask;
global SimpleScoreHolder scoreHolder;
// ############################################################################
// Hard constraints
// ############################################################################
rule "noMultipleAssignmentsInOnePeriod"
when
$t1 : MaintenanceTask($id : id, $periodId : periodId, $technician : technician )
$t2 : MaintenanceTask(id != $id, periodId == $periodId, technician == $technician)
then
insertLogical(new UnweightedConstraintOccurrence("noMultipleAssignmentsInOnePeriod", $t1, $t2));
end
rule "tasksInSameProjectMustBeInSamePeriod"
when
$t1 : MaintenanceTask($id : id, $periodId : periodId, $projectId : projectId )
$t2 : MaintenanceTask(id != $id, periodId != $periodId, projectId == $projectId)
then
insertLogical(new UnweightedConstraintOccurrence("tasksInSameProjectMustBeInSamePeriod", $t1, $t2));
end
// ############################################################################
// Calculate score
// ############################################################################
rule "hardConstraintsBroken"
when
$occurrenceCount : Number() from accumulate(
$unweightedConstraintOccurrence : UnweightedConstraintOccurrence(),
count($unweightedConstraintOccurrence)
)
then
scoreHolder.setScore(- $occurrenceCount.intValue());
end
Solution file:
package be.axi.planner.domain;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import org.drools.planner.api.domain.solution.PlanningEntityCollectionProperty;
import org.drools.planner.core.score.buildin.simple.SimpleScore;
import org.drools.planner.core.solution.Solution;
public class MaintenanceSchedule implements Solution<SimpleScore>{
private SimpleScore score;
private List<MaintenanceTask> maintenanceTasks;
private List<Period> periods;
private List<Technician> technicians;
public MaintenanceSchedule cloneSolution() {
MaintenanceSchedule clone = new MaintenanceSchedule();
clone.periods = this.periods;
clone.technicians = this.technicians;
List<MaintenanceTask> clonedTasks = new ArrayList<MaintenanceTask>(
maintenanceTasks.size());
for (MaintenanceTask task : maintenanceTasks) {
MaintenanceTask clonedTask = task.clone();
clonedTasks.add(clonedTask);
}
clone.maintenanceTasks = clonedTasks;
clone.score = this.score;
return clone;
}
public Collection<? extends Object> getProblemFacts() {
System.out.println(">>getting problemfacts");
List<Object> facts = new ArrayList<Object>();
facts.addAll(periods);
facts.addAll(technicians);
// Do not add the planning entity's (maintenaceTasks) because that will be done automatically
return facts;
}
public SimpleScore getScore() {
return this.score;
}
public void setScore(SimpleScore aScore) {
this.score = aScore;
if (aScore != null){
System.out.println("Score set to " + aScore.getScore());
}
}
@PlanningEntityCollectionProperty
public List<MaintenanceTask> getMaintenanceTasks() {
System.out.println("getting tasks: #" +maintenanceTasks.size());
return maintenanceTasks;
}
public void setMaintenanceTasks(List<MaintenanceTask> aMaintenanceTasks) {
System.out.println("setting tasks");
this.maintenanceTasks = aMaintenanceTasks;
}
public void setTechnicians(List<Technician> aTechnicians) {
System.out.println("setting Technicians");
this.technicians = aTechnicians;
}
public List<Technician> getTechnicians() {
System.out.println("Getting Technicians: #"+technicians.size());
return technicians;
}
public List<Period> getPeriods() {
System.out.println("getting periods");
return periods;
}
public void setPeriods(List<Period> periods) {
this.periods = periods;
}
}
-----------------
http://www.codessentials.com - Your essential software, for free!
Follow us at http://twitter.com/#!/Codessentials
________________________________
From: Geoffrey De Smet <ge0ffrey.spam at gmail.com>
To: rules-users at lists.jboss.org
Sent: Friday, August 31, 2012 10:54 AM
Subject: Re: [rules-users] Best model for planning? technicians, airplanes and shifts
Op 31-08-12 09:46, Michiel Vermandel schreef:
> Thank you for the response.
> I think I forgot one level of complexity (?):
>
> The moment of maintenance of a plane is not fixed.
>
> We have 12 "periods" per year for maintenance.
> One period every month.
>
> We need to make the planning in such way that the list of planes is
> planned somewhere in these 12 periods.
> But it is not important that a specific plane is maintained at a
> specific period.
> It has though a calendar of unavailability.
>
> So the job (==Shift) of the Task (==ShiftAssignment) has no hard
> constraint on period.
>
> We need to find that combination with the best match between required
> skills for the job and available technicians.
> It's better to plan the job on a later period if at that time a more
> skilled technician is available.
>
> I hope this is a bit clear.
>
> So, given this addition, should I take as planning variables:
>
> 1) Period (List of 12 periods)
> 2) Technician
Good idea
>
> Then use period to check availability on both plane and technician
> (hard-constraint)
I see 3:
- plane availability
- technician conflicts (2 tasks at the same time)
- technician availability
> Then give a better weight on skill-match (soft-constrain)?
yes (and possible others, such as work load, technician desires, ...)
>
> Thank you.
>
> Michiel
>
> -----------------
> http://www.codessentials.com - Your essential software, for free!
> Follow us at http://twitter.com/#!/Codessentials
> ------------------------------------------------------------------------
> *From:* Geoffrey De Smet <ge0ffrey.spam at gmail.com>
> *To:* rules-users at lists.jboss.org
> *Sent:* Friday, August 31, 2012 9:08 AM
> *Subject:* Re: [rules-users] Best model for planning? technicians,
> airplanes and shifts
>
> Op 30-08-12 18:02, mvermand schreef:
> > Hi,
> >
> > I'd like some advice on how to make my model.
> >
> > I need to plan maintenance-schedules for - let's say - airplanes.
> > Constraints are:
> > - planes are only at given moments available for maintenance (when not in
> > the air ;-)
> > - maintenance of a planes requires a number of techniciens (with specific
> > skills).
> > - techniciens have skills and also shifts and vacation.
> >
>
> Sounds like the nurse rostering example in Planner :)
> In nurse rostering, such a Shift has a ShiftDate and a ShiftType.
> The difference is, you need to assign jobs instead of shifts.
>
> > Now, first I tought to make the maintenance of a plane the
> planningEntity.
> > But I did not know how to populate and match the techniciens.
>
> I wouldn't make plane the planningEntity either, it's on the one side of
> the manyToOne relation.
>
> >
> > So, second I tought to make a new Task-class the planningEntity.
> > A Task is a job that needs to be done by a technicien with specific
> skills.
> > Maintaining a plane requires then a number of tasks.
>
> Good idea. In nurse rostering, a Task is called a ShiftAssignment.
> You can generate all Tasks in advance based on the Planes and their jobs
> and the number of technicians needed by each job.
>
> I recommend to make separate Task instances for multiple technicians
> that perform the same job together on the same plane. In nurse rostering
> there are also multiple ShiftAssignments (=tasks) per Shift (=job).
>
> >
> > If I choose this model, I think I'll have to pass two Plannings
> variables to
> > the Task planningEntity:
> > 1) a Maintenance-fact (Plane + Period + list of required tasks) and
>
> I don't think this is a planner variable on the planning entity Task.
> It really defines the Task: what job on what plane (and some of sort of
> requiredTechnicanCountIndex)
>
> > 2) a Technicien-fact (?)
> This is a planning variable.
> You're assigning task to techinicians.
> Each task has exactly 1 technician (because a job has multiple tasks,
> one per required technician).
> Each technician can work on multiple tasks, but the hard/soft
> constraints make sure that it's not at the same time.
>
> >
> > Then I'll need to check if availabity of plane and availability of
> > technicien match and also skill-requirement of task and skills of
> > technicien.
>
> Yep, with constraints
>
> >
> > Do you think this second model is the right one?
> >
> > Will it perform well?
> > => ? matching all combinations of plane availabilty and
> > techniciens-availability and -skills.
>
> It should, see the nurse rostering problem.
> In Planner 5.5.0.Beta1, I would add a filter on the swap move selector
> to prevent it from swapping 2 technicians assigned to different tasks on
> the same job.
>
> https://github.com/droolsjbpm/drools-planner/blob/master/drools-planner-examples/src/main/java/org/drools/planner/examples/curriculumcourse/solver/move/DifferentCourseSwapMoveFilter.javatd
>
> >
> > Thanks in advance
> >
> >
> >
> > --
> > View this message in context:
> http://drools.46999.n3.nabble.com/Best-model-for-planning-tp4019464.html
> > Sent from the Drools: User forum mailing list archive at Nabble.com
> <http://nabble.com/>.
> > _______________________________________________
> > rules-users mailing list
> > rules-users at lists.jboss.org <mailto:rules-users at lists.jboss.org>
> > https://lists.jboss.org/mailman/listinfo/rules-users
> >
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org <mailto:rules-users at lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
_______________________________________________
rules-users mailing list
rules-users at lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20120831/e5d00edd/attachment-0001.html
More information about the rules-users
mailing list