Real-time planning problems, such as airport runway scheduling, have a paradox:
- Optimizing such a planning problem into a usable, good solution takes minutes or even hours (because they are NP-complete).
- The planning facts can change up to a few (milli)seconds before the planning is used.
So by the time the solver finds a good solution to the problem, the problem might have already changed.
Yet, JBoss Drools Planner can handle this. For Drools Planner 5.3, I ‘ve created out-of-the-box support for real-time planning (sources of the prototype are here). Take a look at a demo video:
Real-time planning with Drools Planner: demo video from Geoffrey De Smet on Vimeo.
Log
Here the log of a different run which shows what’s going on:
08:44:44,055 [pool-1-thread-1] INFO Solving with random seed (0).
…
// The solution is feasible after 2450 ms
08:44:46,505 [pool-1-thread-1] INFO Greedy phase ended at step index (199) for best score (0hard/-80090soft).
08:44:46,639 [pool-1-thread-1] INFO Step index (0), …, new best score (0hard/-79840soft), …
…
08:44:52,194 [pool-1-thread-1] INFO Step index (84), …, new best score (0hard/-73820soft), …
// Another thread schedules the computer deleting event, while the Planner thread is solving
08:44:52,246 [AWT-EventQueue-0] INFO Scheduling deleting of computer (Computer 3).
08:44:52,254 [pool-1-thread-1] INFO Step index (85), …, best score (0hard/-73820soft), …
08:44:52,257 [pool-1-thread-1] INFO Done 1 PlanningFactChange(s), new score (0hard/-71520soft), possibly uninitialized. Restarting solver.
…
// The solution is feasible again after 71 ms
08:44:52,317 [pool-1-thread-1] INFO Greedy phase ended at step index (9) for best score (0hard/-75250soft).
08:44:52,374 [pool-1-thread-1] INFO Step index (0), …, new best score (0hard/-74850soft), …
…
08:44:55,666 [pool-1-thread-1] INFO Step index (57), …, new best score (0hard/-70660soft), …
…
Use cases
In the demo I am scheduling computer processes on a grid of computers, but there are plenty of other real-time planning problems, such as:
- Train station track/platform scheduling
- Airplane gate scheduling at the airport
- Hospital emergency room/doktor/patient scheduling
- …
And all of these need to be able to scale in data and constraints, which is no problem for Drools Planner.
