Op 31-08-12 15:07, Michiel Vermandel schreef:
> 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.
It probably stopped early because basically all solutions had been seen.

> 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).
you got:
<maximumSecondsSpend>700</maximumSecondsSpend>
so it will run for over 11 minutes.
Turn that to just 60 seconds (or see manual about alternative
termination methods).

The problem is NP-complete, so as you scale up to thousands (and more)
planes/techs/periods, no software (and certainly no human being) can
find the optimal solution in reasonable time (see first chatper in
manual). Planner will find you the best solution in the time you (can)
give it.

> 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@gmail.com>
> *To:* rules-users@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@gmail.com
> <mailto:ge0ffrey.spam@gmail.com>>
>  > *To:* rules-users@lists.jboss.org <mailto:rules-users@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@lists.jboss.org <mailto:rules-users@lists.jboss.org>
> <mailto:rules-users@lists.jboss.org <mailto:rules-users@lists.jboss.org>>
>  >  > https://lists.jboss.org/mailman/listinfo/rules-users
>  >  >
>  >
>  >
>  > _______________________________________________
>  > rules-users mailing list
>  > rules-users@lists.jboss.org <mailto:rules-users@lists.jboss.org>
> <mailto:rules-users@lists.jboss.org <mailto:rules-users@lists.jboss.org>>
>  > https://lists.jboss.org/mailman/listinfo/rules-users
>  >
>  >
>  >
>  >
>  > _______________________________________________
>  > rules-users mailing list
>  > rules-users@lists.jboss.org <mailto:rules-users@lists.jboss.org>
>  > https://lists.jboss.org/mailman/listinfo/rules-users
>  >
>
>
> _______________________________________________
> rules-users mailing list
> rules-users@lists.jboss.org <mailto:rules-users@lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
>
>
> _______________________________________________
> rules-users mailing list
> rules-users@lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>


_______________________________________________
rules-users mailing list
rules-users@lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users