JBoss.org Community Documentation

- Prev

## Chapter 14. Repeated planning

## 14.1. Introduction to repeated 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:

- Unforeseen fact changes: For example: an employee assigned to a shift calls in sick, an airplane scheduled to take off has a technical delay, one of the machines or vehicles break down, ... Use backup planning.

- Unknown long term future facts: For example: The hospital admissions for the next 2 weeks are reliable, but those for week 3 and 4 are less reliable and for week 5 and beyond are not worth planning yet. Use continuous planning.

- Constantly changing planning facts: Use real-time planning.

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 than no plan.

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

## 14.2. Backup 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.

## 14.3. Continuous planning (windowed planning)

Continuous planning is the technique of planning one or more upcoming planning windows at the same time and repeating that process monthly, weekly, daily or hourly. Because time is infinite, there are infinite future windows, so planning all future windows is impossible. Instead, plan only a fixed 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 only immovable planning entities: the planning entities can no longer be changed (they are unable to move), but some of them are still needed in the score calculation, 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-immovable: 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 during the 2 hours before boarding (unless there is no alternative), ...

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.

### 14.3.1. Immovable planning entities

To make some planning entities immovable, simply add an entity `SelectionFilter` that returns `true` if an entity is movable and `false` if it is immovable.

    public class MovableShiftAssignmentSelectionFilter implements SelectionFilter<ShiftAssignment> {

        public boolean accept(ScoreDirector scoreDirector, ShiftAssignment shiftAssignment) {

            ShiftDate shiftDate = shiftAssignment.getShift().getShiftDate();

            NurseRoster nurseRoster = (NurseRoster) scoreDirector.getWorkingSolution();

            return nurseRoster.getNurseRosterInfo().isInPlanningWindow(shiftDate);

        }

    }

And configure it like this:

    @PlanningEntity(movableEntitySelectionFilter = MovableShiftAssignmentSelectionFilter.class)

    public class ShiftAssignment {

        ...

    }

## Warning

Custom `MoveListFactory` and `MoveIteratorFactory` implementations must make sure that they don't move immovable entities.

## 14.4. Real-time planning (event based planning)

To do real-time planning, first combine backup planning and continuous planning with short planning windows to lower the burden of real-time planning.

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 in the solver thread as soon as possible.

    public interface Solver {

        ...

        boolean addProblemFactChange(ProblemFactChange problemFactChange);

        boolean isEveryProblemFactChangeProcessed();

        ...

    }

    public interface ProblemFactChange {

        void doChange(ScoreDirector scoreDirector);

    }

Here's an example:

        public void deleteComputer(final CloudComputer computer) {

            solver.addProblemFactChange(new ProblemFactChange() {

                public void doChange(ScoreDirector scoreDirector) {

                    CloudBalance cloudBalance = (CloudBalance) scoreDirector.getWorkingSolution();

                    // First remove the planning fact from all planning entities that use it

                    for (CloudProcess process : cloudBalance.getProcessList()) {

                        if (ObjectUtils.equals(process.getComputer(), computer)) {

                            scoreDirector.beforeVariableChanged(process, "computer");

                            process.setComputer(null);

                            scoreDirector.afterVariableChanged(process, "computer");

                        }

                    }

                    // Next remove it the planning fact itself

                    for (Iterator<CloudComputer> it = cloudBalance.getComputerList().iterator(); it.hasNext(); ) {

                        CloudComputer workingComputer = it.next();

                        if (ObjectUtils.equals(workingComputer, computer)) {

                            scoreDirector.beforeProblemFactRemoved(workingComputer);

                            it.remove(); // remove from list

                            scoreDirector.beforeProblemFactRemoved(workingComputer);

                            break;

                        }

                    }

                }

            });

        }

## Warning

Any change on the problem facts or planning entities in a `ProblemFactChange` must be done on the instances of the `Solution` of `scoreDirector.getWorkingSolution()`. Note that these are not the same entity instances as in the bestSolution (or therefore your user interface): they are clones.

## Warning

Any change on the problem facts or planning entities in a `ProblemFactChange` must be told to the `ScoreDirector`.

## Note

Many types of changes can leave a planning entity uninitialized, resulting in a partially initialized solution. That's fine, as long as the first solver phase can handle it. All construction heuristics solver phases can handle that, so it's recommended to configure such a `SolverPhase` as the first phase.

In essence, the `Solver` will stop, run the `ProblemFactChange` and restart. Each `SolverPhase` will run again. Each configured `Termination` (except `terminateEarly`) will reset. This means the construction heuristic will run again, but because little or no planning variables will be uninitialized (unless you have a nullable planning variable), this won't take long.

Normally, you won't configure any `Termination`, just call `Solver.terminateEarly()` when the results are needed. Alternatively, you can subscribe to the `BestSolutionChangedEvent`. A `BestSolutionChangedEvent` doesn't guarantee that every `ProblemFactChange` has been processed already, so check `Solver.isEveryProblemFactChangeProcessed()` and ignore any `BestSolutionChangedEvent` fired while that method returns `false`.

- PrevChapter 13. Benchmarking and tweaking
- Top of page
- Front page