Geoffrey De Smet is the OptaPlanner lead. Geoffrey has posted 16 posts at DZone. You can read more from them at their website. View Full User Profile

Solving Planning Problems: Introducing the Drools Solver

08.17.2008
| 20113 views |
  • submit to reddit
Planning problems are everywhere! Have you ever moved houses and needed to fit all your belongings into a moving truck? Usually you put all the big stuff in first, and then cram the little stuff in between. But what is bigger? A tall, thin closest or a wide one-person couch? Maybe you could have stacked your stuff better so you didn't need to pay for that extra moving truck?

Have you ever wondered about how they schedule trains? They need to minimize the commune between any 2 relevant train stations, while complying to their resource limits: train sizes, train speed, physical location of train sets, employee working hours, employee qualifications, occupancy of train station platforms, weekly maintenance, ...

Did you ever try to plan a meeting, just to find that on the one day that all participants can attend, all meeting rooms are occupied? Or there's no available beamer?

The world is full of planning problems.

In this article I'll focus on solving a very simple lesson schedule:

  • A school has teachers, student groups and a bunch of lessons (which combine 1 teacher with 1 student group). Those lessons need to fit into a limited number of timeslots.
  • The goal is to avoid conflicts: a teacher can't teach 2 lessons in the same timeslot and a student group can't attend 2 lessons in the same timeslot either.

Size does matter

A planning problem has a score function, which determines the score for any possible solution we can construct. Based on that score, we can compare solutions and determine the optimal solution. There is usually only 1 optimal solution, but the number of possible solutions is huge.

For example, let's take a medium school with 30 student groups, 40 teachers and 33 timeslots. Each student group has a lesson in each timeslot, which makes 990 lessons. In how many distinct ways can those 990 lessons be scheduled into 33 timeslots? In other words, how many possible solutions does it have? Well, this example has 33 ^ 990 or a little over 2e1503 possible solutions. Yes, for a medium school, that number is a 2 with 1503 zero's behind it!

Calculating the score of a single solution can take quite some time, as every teacher and student group needs to checked on conflicts with any other teacher or student group. Due the sheer size of the search space and real-world time constraints, it normally suffices to find a “good enough” solution, better than those of human planners.

Planning algorithms

There are different ways to solve a planning problem:

  • Random: There's no overarching entity which plans the system. For example, traffic is solved almost randomly: everyone just picks their route and departure time as they please. If you ever drove through a major city, once during rush hour and once an hour after rush hour, you know this is nowhere near optimal.

  • Exhaustive: Through brute force every possible solution is evaluated to determine the optimal solution. In practice this simply doesn't work: if we could evaluate a billion possible solutions each millisecond, it would still take over 6e1483 years to evaluate all the possible solutions for our medium school. Even smart exhaustive algorithms, such as branch and bound, take ages.

  • Deterministic: The resources are put into the planning based on simple rules. The solution is far from optimal, but it's sometimes “good enough”. For example, patients in a clinic are treated in a FIFO queue (first come, first serve), but emergency patients get moved to the front of the queue. In our lesson schedule example, we could schedule one lesson at a time by assigning it a timeslot that doesn't already have a lesson with the same teacher or student group. However, we will more then likely end up with lessons that can't be assigned.

  • Metaheuristic: The algorithm wades through the possible solutions in an intelligent manner and remembers the best solution it encounters. It decides which solutions to visit, guided by the score of the already encountered solutions. There are various metaheuristic algorithms, such as tabu search, simulated annealing, ant colony optimization, genetic algorithms, ... For example, a greedy algorithm starts from a random solution and evaluates every solution that moves 1 lesson to a different timeslot, and it takes the best of those solutions as the new solution to continue from.

In practice, it's usually recommended to start with a deterministic algorithm and improve upon that solution with a metaheuristic algorithm.

Introducing Drools Solver

Drools Solver is an open source Java library to help you solve planning problems, by using metaheuristic algorithms. The API isn't completely stable yet, but there's already a full manual and 5 extensive examples available.

Score calculation

Drools Solver uses the Drools rule engine for score calculation, which greatly reduces the complexity and effort to write very scalable constraints in a declarative manner. In our lesson schedule example, we could implement a teacher conflict like this:

rule "multipleLessonsPerTeacherPerTimeslot"
when
$l : Lesson($id : id, $t : teacher, $ts : timeslot);
exists Lesson(id > $id, teacher == $t, timeslot == $ts);
then
insertLogical(new UnweightedConstraintOccurrence(
"multipleLessonsPerTeacherPerTimeslot", $l
));
end

Notice how the rule to detect student group conflicts isn't mixed into this one: it's completely separated. And because the rules don't define how they should be detected, it's left up to the Drools rule engine to use for-loops, hash tables or something much more efficient (like a ReteOO network).

Tabu search

Drools Solver supports several algorithms to find a solution in a limited amount of time. Currently its supports hill climbing, several forms of tabu search, simulated annealing and great deluge. A tabu search configuration for our lesson schedule example with a time limit of 5 minutes, looks like this:

<localSearchSolver>
<scoreDrl>.../lessonScheduleScoreRules.drl</scoreDrl>
<finish>
<maximumSecondsSpend>300</maximumSecondsSpend>
</finish>
...
<accepter>
<completeSolutionTabuSize>1000</completeSolutionTabuSize>
</accepter>
</localSearchSolver>

You can easily switch to the simulated annealing metaheuristic by changing a few lines in the configuration. There's even a benchmarker utility which you can use to play out different configurations against each other and determine the best one for your use case.

Getting started

Want to know more about Drools Solver? Take a look at the manual or run the examples of the download package. Your feed back is always welcome on the Drools user mailing list.

About the author

Geoffrey De Smet is the main developer of Drools Solver. He finished 4th in the International Timetabling Competition 2007's examination track with an early version of Drools Solver.

Published at DZone with permission of its author, Geoffrey De Smet.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Peter Karussell replied on Sun, 2008/08/17 - 6:19am

Hi Geoffrey!

[quote]In our lesson schedule example, we could implement a teacher conflict like this[/quote]

Could you explain this specific rule definition (for the teacher conflict) in more detail?

It is a new language for me. I know that the documentation for this is here, but I need examples ;-)

And what does 'this score rule will fire once' mean? (I found this in the drools-solver docs)

Regards,
Peter.

Geoffrey De Smet replied on Sun, 2008/08/17 - 10:25am in response to: Peter Karussell

The multipleLessonsPerTeacherPerTimeslot rule looks for a pattern in the when side:

  $l : Lesson($id : id, $t : teacher, $ts : timeslot);

which is any lesson, for which

   exists Lesson(id > $id, teacher == $t, timeslot == $ts);

there exists a lesson which a higher id, of the same teacher, in the same timeslot.

If then is the case, then

  insertLogical(new UnweightedConstraintOccurrence(...));

it logically insert a fact that that has occured.
By logically inserting it, the rule engine will automatically remove it when the rule pattern no longer applies for it.

 

Tim Boudreau replied on Mon, 2008/08/18 - 4:41am

For example, let's take a medium school with 30 student groups, 40 teachers and 33 timeslots. Each student group has a lesson in each timeslot, which makes 990 lessons. In how many distinct ways can those 990 lessons be scheduled into 33 timeslots? In other words, how many possible solutions does it have? Well, this example has 33 ^ 990 or a little over 2e1503 possible solutions. Yes, for a medium school, that number is a 2 with 1503 zero's behind it!

Well, 15 of the 40 teachers are parents of preschoolers.  They need morning slots due to day-care constraints.  3 of the teachers are having extra-marital affairs with five of the other teachers (well, one in common).  7AM is fine for them, but they're not going to give up that lunch hour of bliss, so they're after morning slots too.  Then there's the brilliant english teacher who is a wretched drunk by night, but nonetheless brilliant if you catch him after noon.  Maybe we'll pencil him in to teach history too?

 Somehow I think no algorithm is going to nail this all down optimally...

 But it looks good on paper or as a thesis project. 

 -Tim 

Chris Wash replied on Mon, 2008/08/18 - 10:15am in response to: Tim Boudreau

Somehow I think no algorithm is going to nail this all down optimally...

But it looks good on paper or as a thesis project.

Sounds like a calculator for Operations Research.  Its usefulness increases as you can make sure that someone is following the rules you use to constrain the system.

Geoffrey De Smet replied on Mon, 2008/08/18 - 10:36am in response to: Tim Boudreau

[quote=tim]

Somehow I think no algorithm is going to nail this all down optimally...

[/quote]

Actually, in Drools-Solver, adding constraints is easy and scalable. For example:

[quote=tim]

Well, 15 of the 40 teachers are parents of preschoolers.  They need morning slots due to day-care constraints

[/quote]

rule "parentOfPreschoolersWantMornings"  
when
$t : Teacher(parentOfPreschooler == true);
$ts : Timeslot(startingHour >= 12)
Lesson(teacher == $t, timeslot == $ts);
then ...
end

[quote=tim]

3 of the teachers are having extra-marital affairs with five of the other teachers (well, one in common).  7AM is fine for them, but they're not going to give up that lunch hour of bliss, so they're after morning slots too. 

[/quote]

rule "giveTeachersWithAffairSameOffTimesInTheMorning"  
when
$male : Teacher();
$female : Teacher(affairWith == $male);
$ts : Timeslot(startingHour < 12);
Lesson(teacher == $male, timeslot == $ts);
not Lesson(teacher == $female, timeslot == $ts);
then ...
end

[quote=tim]

Then there's the brilliant english teacher who is a wretched drunk by night, but nonetheless brilliant if you catch him after noon.

[/quote]
rule "drunkWantsAfternoons"  
when
$t : Teacher(drunk == true);
$ts : Timeslot(startingHour < 12)
Lesson(teacher == $t, timeslot == $ts);
then ...
end

 

Of course, Drools Solver supports weighting those constraints (for example 1 broken preschooler constraint is 100 times the weight of 1 broken drunk constraint) and the difference between hard and soft constraints.

Kuni Katsuya replied on Mon, 2008/08/18 - 12:30pm

brilliant response! :)

Alberto Izagirre replied on Tue, 2009/09/15 - 4:49am

I would like to know the feasibility of using drools to palletize problems, i.e. problems where a set of products from a store muss pu in a pallet, in particular problems where many constraints or rules are needed. Also, I would like to know if other drools users have tried to solved this type of problems using drools.

 Sincerely yours:

 Alberto Izagirre

CIS & Electr. Departm

University of Mondragon

20500 Mondragon, Spain

email: aizagirre@eps.mondragon.edu

 

Geoffrey De Smet replied on Wed, 2009/11/11 - 8:01am

Aizagirre, are you talking about a bin-packaging problem (2D or 3D knapsack problem) with many extra constraints?

 Drools Solver is very suited for bin-packaging problems. Someone on the drools user list already used Drools Solver for a 2D knapsack problem if I recall correctly.

Slikrek Slikrek1 replied on Wed, 2009/11/18 - 2:41am

HI Geoffrey, Which package can be used for Patient Admission Scheduling .. please could you put the link and the package name ? Best Regards Slikrek

Alberto Izagirre replied on Mon, 2009/11/30 - 10:54am in response to: Geoffrey De Smet

We are presently trying the 2D case of the rectangle-picking problem. Lets suppose that I have a 2D pallet whose width is 1000 mm, and its height is 1000 mm. Suppose let´s say that we have 6 boxes of 200 x 300 mmxmm, other 6 boxes of 200 x 200 mmxmm and other 6 boxes of 300x100 mmxmm. A square can be put only above another square, i.e. it is a simulation of a 3D pallet in 2D, where the first boxes are put on the floor and the rest on top of the other ones. I have seen the solution of the nqueens problems where the NQueensMoveFactory is a list of all posible moves from the original solution. This can be impractical in our case, as the number of possible moves can be too large. What I think is that the 2D rectangle picking problem can be implemented doing a iterative search, e.g. trying to put first one of the 18 boxes (actually one of the 3 types), and then trying to put the rest of the boxes one at the time. PD> I have seen the implementation of the itc2007.curriculumcourse, and it seems that you have 3 types of move factories LectureSwitchMoveFactory PeriodChangeMoveFactory and RoomChangeMoveFactory, and their corresponding Movers. This example looks more difficult to understand, and we would like to know if a similar strategy can be used for the 2D rectangular-packing. Our main idea would be to allow only the boxes at left or right corners only if underneath is a flat surface that supports at least 75% of their surface. Example: ------------- | |-------------- | | | ---------------------------- I can put a box in: ---------------- | | ----------------- | |------------- | | | ---------------------------- Any help suggestions are always welcomed: Thanks again, Alberto Izagirre

Geoffrey De Smet replied on Sat, 2010/02/13 - 9:32am

Slikrek, Patient Admission Scheduling is the org.drools.planner.examples.pas package (I originally used the full name as the package name, but the path name was too long for fellow developers on windows vista...).

Aizagirre, such questions are welcome on the drools user mailing list, which you can access by a web interface (nabble.com) too. In the ref manual 5.1.0 M2 I 'll try to include an example on how to configure a custom selector (although a smart MoveFactory might already suffice in your case).

Drools Solver has been renamed to Drools Planner. The website is:

http://www.jboss.org/drools/drools-planner.html

 

Chetan Satya replied on Tue, 2010/05/11 - 5:46am

Hey Geoffrey,

I am thinking of using Drools Planner in my application.
I have an examination timetabling problem with variable exam durations and a large number of test centers.
I developed a sample application to evaluate the usability of the Drools Planner before jumping to the actual production usage.
I developed a scheduler that schedules 20 candidates into 20 seats in the odd seats first manner (seat numbers 1,3,5,7,9..19 first and 2,4,6,8..20 later).

Now I want to use it in my application.
What stable version of drools planner can I use?
I did not find any maven repository for a drools-planner-core artifact.
My Sample application was done using 5.1.0.SNAPSHOT.
I obviously cannot use a snapshot for a production application.

Please advise.

Chetan.
(chetanhs247@gmail.com)

Geoffrey De Smet replied on Fri, 2010/12/03 - 7:52am in response to: Chetan Satya

5.1.0 has been released a few months ago

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.