Week 6 - Automatic Scheduler

This blog post is a short tutorial on how to solve the operation theater scheduling problem using the optaplanner library.

The goal is to come up with an optimal scheduling that is defined by a set of constraints. In this case the set of constraints is divided into two parts:

• Hard rules: (e.g.: no overlapping surgeries in the same operation theater at the same time)
• Soft rules: (e.g.: first come first served)

The difference between them, is that hard rules must not be broken, while soft rules should not be broken. Based on the rules a score is calculated and maximized by the solver.

Before I will start to describe the implementation I want to introduce a few terms that will be used later:

• Problem fact
  used to calculate the score, but does not change during planning (e.g. Procedure)
• Planning variable
  In contrast to the problem fact, the value of this variable will be changed by the solver. (surgery start time, operation theater)
• Shadow variable
  Changes its value just as the planning variable. The difference here is that its value is not directly modified by the solver, but calculated depending on a planning variable (surgery end time)
• Planning entity
  It is a POJO that contains the planning variables and thus changes during solving
• Planning solution
  A wrapping class that implements the Solution interface, holds all problem facts and the planning entity.

Code walkthrough:

Planning Entity

To define a planning entity one has to add a class annotation

@PlanningEntity
public class PlannedSurgery {

To define a planning variable, just annotate the corresponding getter method

@PlanningVariable(valueRangeProviderRefs = { "locationRange" })
public Location getLocation() {
	return location;
}

The value range provider reference is a link to a method that returns all possible values of this planning variable

The shadow variable “end” is updated within the setter of the planning variable “start”

public void setStart(DateTime start, boolean calculateEndTime) {
	this.start = start;
	if (calculateEndTime) {
		if (start == null) {
			end = null;
		} else {
			int interventionDuration = surgery.getProcedure().getInterventionDuration();
			int otPreparationDuration = surgery.getProcedure().getOtPreparationDuration();
			DateTime endDate = start.plusMinutes(interventionDuration + otPreparationDuration);
			setEnd(endDate);
		}
	}
}

Planning Solution

In the following code snippet you can see all attributes

@PlanningSolution
public class Timetable implements Solution<HardSoftScore> {

	//problem facts  (don't change value during planning)
	private List<Surgery> surgeries;
	private List<Location> locations; // these are the operation theaters
	private List<DateTime> startTimes;

	//planning entities
	private List<PlannedSurgery> plannedSurgeries;

	private HardSoftScore score;

The Solution interface defines three functions: getter and setter of the score attribute and getProblemFacts

@Override
public Collection<?> getProblemFacts() {
	//planning entities are added automatically -> don't add them here
	List<Object> facts = new ArrayList<Object>();
	facts.addAll(surgeries);
	facts.addAll(locations);
	facts.addAll(startTimes);
	return facts;
}

Make sure that you don’t add the planning entity. Another common mistake is to use facts.add() instead of facts.addAll()

As we defined our planning variables in the planning entity class, we specified a value range provider reference. Now we have to tell optaplanner which function provide these objects. We do that - yes you are right - by using another annotation

@ValueRangeProvider(id = "locationRange")
public List<Location> getLocations() {
	return locations;
}

Defining rules

Now that we have defined all relevant classes we can start writing our business rules. We do that by using Drools rule language - The basic syntax is as follows

rule "This is the rule name"
  
 when
  #conditions
 then 
  #actions
end

Here is one hard constraint. If the when condition is met the hard constraint score is decreased by one.

//Operation Theater occupancy: two PlannedSurgeries in the same Location with overlapping periods
rule "overlappingSurgeriesInSameOperationTheater"
    when
        $left: PlannedSurgery($location: location)
        $right: PlannedSurgery(this != $left, location == $location, isOverlapping($left))
        //prevent the double execution of this rule (AB, BA)
        eval( System.identityHashCode($left) < System.identityHashCode($right))
    then
        scoreHolder.addHardConstraintMatch(kcontext, -1);
end

Now I want to shortly describe how this rule works. When part: On the first line PlannedSurgery is stored in the variable ($left). The dollar sign is not needed, but increases readability. The location attribute of the PlannedEntity that is stored in $left is assigned to the variable $location The second line is true for PlannedSurgeries that are not the same one as in the first line, have the same location and do overlapp (isOverlapping is a function defined in PlannedSurgery) The last line just makes sure that all pairs are only processed once (AB, BA)

Before you can execute the solver you have to configure it (e.g. define the optimization algorithm) You can find a basic configuration here.

Now we are ready to..

start the solver

public void solve() {
	// Build the Solver
	SolverFactory solverFactory = new XmlSolverFactory("/scheduler/solverConfig.xml");
	Solver solver = solverFactory.buildSolver();
	// Load problem
	Timetable unsolvedTimetable = createTimetable();

	// Solve the problem
	solver.setPlanningProblem(unsolvedTimetable);
	solver.solve();
	Timetable solvedTimetable = (Timetable) solver.getBestSolution();

	//set surgeries planned begin and finished attributes
	solvedTimetable.persistSolution(otService);
}

This concluded this basic example.

Stay tuned for future blog posts that will describe how to evolve this solution. You can find the complete code for this tutorial in this commit

References:

Optaplanner