JBoss.orgCommunity Documentation

Chapter 11. Repeated planning

11.1. Introduction to repeated planning
11.2. Backup planning
11.3. Continuous planning (windowed planning)
11.4. Real-time planning (event based planning)

The world constantly changes. The planning facts used to create a solution, might change before or during the execution of that solution. There are 3 types of situations:

Waiting to start planning - to lower the risk of planning facts changing - usually isn't a good way to deal with that. More CPU time means a better planning solution. An incomplete plan is better then no plan.

Luckily, the Drools Planner algorithms support planning a solution that's already (partially) planned, known as repeated planning.

Backup planning is the technique of adding extra score constraints to create space in the planning for when things go wrong. That creates a backup plan in the plan. For example: try to assign an employee as the spare employee (1 for every 10 shifts at the same time), keep 1 hospital bed open in each department, ...

Then, when things go wrong (one of the employees calls in sick), change the planning facts on the original solution (delete the sick employee leave his/her shifts unassigned) and just restart the planning, starting from that solution, which has a different score now. The construction heuristics will fill in the newly created gaps (probably with the spare employee) and the metaheuristics will even improve it further.

Continuous planning is the technique of planning one or more upcoming planning windows at the same time and repeating that process every week (or every day). Because time infinite, there are an infinite future windows, so planning all future windows is impossible. Instead we plan only a number of upcoming planning windows.

Past planning windows are immutable. The first upcoming planning window is considered stable (unlikely to change), while later upcoming planning windows are considered draft (likely to change during the next planning effort). Distant future planning windows are not planned at all.

Past planning windows have locked planning entities: the planning entities can no longer be changed (they are locked in place), but some of them are still needed in the working memory, as they might affect some of the score constraints that apply on the upcoming planning entities. For example: when an employee should not work more than 5 days in a row, he shouldn't work today and tomorrow if he worked the past 4 days already.

Sometimes some planning entities are semi-locked: they can be changed, but occur a certain score penalty if they differ from their original place. For example: avoid rescheduling hospital beds less than 2 days before the patient arrives (unless it's really worth it), avoid changing the airplane gate (or worse, the terminal) during the 2 hours before boarding, ...


Notice the difference between the original planning of November 1th and the new planning of November 5th: some planning facts (F, H, I, J, K) changed, which results in unrelated planning entities (G) changing too.

To do real-time planning, first combine backup planning and continuous planning with short planning windows to lower the burden of real-time planning. Don't configure any Termination, just terminate early when you need the results or subscribe to the BestSolutionChangedEvent (the latter doesn't guarantee yet that every ProblemFactChange has been processed already).

While the Solver is solving, an outside event might want to change one of the problem facts, for example an airplane is delayed and needs the runway at a later time. Do not change the problem fact instances used by the Solver while it is solving, as that will corrupt it. Instead, add a ProblemFactChange to the Solver which it will execute as soon as the timing is right.

public interface Solver {

   ...

   boolean addProblemFactChange(ProblemFactChange problemFactChange);

   ...

}
public interface ProblemFactChange {

    void doChange(SolutionDirector solutionDirector);

}

Here's an example:

    public void deleteComputer(final CloudComputer cloudComputer) {
        solver.addProblemFactChange(new ProblemFactChange() {
            public void doChange(SolutionDirector solutionDirector) {
                CloudBalance cloudBalance = (CloudBalance) solutionDirector.getWorkingSolution();
                WorkingMemory workingMemory = solutionDirector.getWorkingMemory();
                // First remove the planning fact from all planning entities that use it
                for (CloudAssignment cloudAssignment : cloudBalance.getCloudAssignmentList()) {
                    if (ObjectUtils.equals(cloudAssignment.getCloudComputer(), cloudComputer)) {
                        FactHandle cloudAssignmentHandle = workingMemory.getFactHandle(cloudAssignment);
                        cloudAssignment.setCloudComputer(null);
                        workingMemory.retract(cloudAssignmentHandle);
                    }
                }
                // Next remove it the planning fact itself
                for (Iterator<CloudComputer> it = cloudBalance.getCloudComputerList().iterator(); it.hasNext(); ) {
                    CloudComputer workingCloudComputer = it.next();
                    if (ObjectUtils.equals(workingCloudComputer, cloudComputer)) {
                        FactHandle cloudComputerHandle = workingMemory.getFactHandle(workingCloudComputer);
                        workingMemory.retract(cloudComputerHandle);
                        it.remove(); // remove from list
                        break;
                    }
                }
            }
        });
    }

In essence, the Solver will stop, run the ProblemFactChange and restart. Each SolverPhase will be run again. Each configured Termination (except terminateEarly) will reset.