Week 8

Harsha and I talked about our project plan and features we want to implement until the end of features. We came up with the following list:

• functionality to adjust automatic scheduling manually
• manually lock surgeries (time is fixed and not changed by the solver once it has been adjusted manually)
• introduce surgery priorities
• assign surgeon (surgical team) to a surgery and make sure that they don’t overlap
• schedule emergencies
• improve automatic scheduler
• develop benchmark tool – to compare performance of different solver configurations

Week 7 - Dependency Issues 2/2

After I hadn’t made any progress comparing openmrs and optaplanner dependencies, I decided to debug the entire optaplanner initialization process in order to find the difference between running standalone and inside openmrs. I found some dissimilarities inside Parser.class. This class should be imported from ecj-3.7.2.jar Again I checked the dependencies of openmrs with the command

mvn dependency:tree

but couldn’t find this particular library in the resulting output. In a next step I wanted to figure out, where Parser.class is loaded from. Therefore I inserted the following code snippet and redeployed my module to openmrs:

Class klass = org.eclipse.jdt.internal.compiler.parser.Parser.class;
URL location = klass.getResource('/' + klass.getName().replace('.', '/') + ".class");
System.err.println(location);

Alternatively you can use the vm option -verbose:class

The output told me that this class has been loaded from:

/home/lukas/.m2/repository/org/eclipse/jdt/core/3.1.1/core-3.1.1.jar

It turned out that the jetty maven plugin imports this library. As a quick fix I updated this plugin inside openmrs-core/webapp/pom.xml and the exception vanished. A better solution would be to force the modules class loader to look for classes in the modules classpath first. I will discuss that on openmrs talk.

Week 7 - Dependency Issues 1/2

The next time an interviewer asks me about one of my hardest bugs, I will tell her the story of my last week.

I was trying to integrate my first optaplanner solution for the operation theater scheduling problem into my openmrs module. The unit and integration tests were working perfectly. The problem began as I tried to invoke the solver from an openmrs webpage. I was confronted with various exceptions regarding slf4j library. I could resolve that by excluding all libraries from optaplanner that are provided by openmrs-core. Confident that I would be able to see some scheduling results in my calendar soon I redeployed my module. To my surprise an ArrayOutOfBoundsException was thrown during compilation of the drl file.

This stacktrace occupied me for several days. I had a look at version numbers of the libraries provided by openmrs and the ones that optaplanner depends on. There was a mismatch and I guessed that this is the reason for this error. After creating a separate project (without openmrs) but the same library versions, I found out that I was wrong. To my surprise it was working.
After comparing all dependencies between openmrs and optaplanner and trying out every configuration I could think of, I haven’t moved forward at all.

To be continued tomorrow…

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

Week 5

I started the last week by setting up the environment for lpsolve and trying to integrate it into the maven build process. Lpsolve is written in C with wrappers for different programming languages. It turned out, that integration was harder to achieve than expected. One has to place the dynamic C libraries into the java.library.path folder in order to load them at runtime. This path is read only and cannot be modified at runtime (=module start time). So the only solution is to install it in advance or copy it into a directory that is specified in the java.library.path. Shortly after I had went for the copying solution and had solved my UnsatisfiedLinkError, I came across the project OptaPlanner that is written entirely in Java and available under the Apache License 2. For me it seems to be more user friendly. The package ships with a lot of examples and the rules in OptaPlanner are specified within a Drool file that is more or less human readable. The rest of the week I developed a webpage that lists all surgeries for a given patient, as well as a webpage for a surgery itself.

For a bit more information on this topic, please see my post on openmrs talk which includes a youtube screencast.