Red Hat JBoss Resource Planner (part of Red Hat JBoss BRMS, the enterprise product based on the upstream OptaPlanner community project) is the leading open source constraint satisfaction solver. A constraint satisfaction solver is a solving engine build around sophisticated optimization algorithms that allows to plan for optimal use of a limited set of constrained resources.

Every organization faces scheduling problems: assign a limited set of resources, for example employees, assets, time and money, to build products or provide services. Resource Planner optimizes such planning problems to provide an optimal utilization of resources, resulting in higher productivity, less costs and higher customer satisfaction. Use cases include:

  • Vehicle Routing: What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?
  • Employee Rostering: Find an optimal way to assign employees to shifts with a set of hard and soft constraints.
  • Cloud Optimization: What is the optimal assignment of processes to cloud computing resources (CPU, memory, disk)
  • Job Scheduling: Optimise the scheduling of jobs of varying processing times on a set of machines with varying processing power, trying to minimize the makespan.
  • Bin Packing:  pack objects of different volumes into a finite number of bins or containers in a way that minimizes the number of bins used.
  • and many more.

All these problems are, so called, NP-hard problems, which implies that the time required to solve these problems using any currently known algorithm increases very quickly as the size of the problem grows (e.g. adding a destination to a vehicle routing problem, adding a shift to an employee rostering problem). This is one of the principal unsolved problems in computer science today.

As it is impossible to solve these problems, or find the best solution to these problems, in a limited timespan when scaling out, Business Resource Planner uses a set of sophisticated optimization heuristics and meta-heuristics (like Tabu Search, Simulated Annealing and Late Acceptance) to find an optimal solution to these problems.

As said, every organisation has these kind of scheduling problems, and there is a lot to gain from optimising these problems. In the remainder of this post we will walk you through a number of steps to get you started with Business Resource Planner/OptaPlanner to find an optimal solution to your business problem and start increasing productivity, reducing costs and increasing customer satisfaction.

1: Download OptaPlanner

The first step is to download the Business Resource Planner distribution. If you're a Red Hat JBoss BRMS customer, you can download the supported Business Resource Planner from the Red Hat Customer Support Portal. If you're not a Red Hat customer, you can download the enterprise version from JBoss.org, or the community version of the platform from OptaPlanner.org.

2: Read the documentation

Business Resource Planner provides excellent documentation that teaches the basics of resource optimisation by examples, and provides detailed and in-depth explanation of all the techniques, algorithms and configuration options provided by Business Resource Planner.

The documentation can be found here.

3: Start the provided demo's

The Business Resource Planner/OptaPlanner distribution comes with a set of pre-defined examples. The examples provide a graphical client that provides a visual view on the problems being solved.

  1. Unzip the Business Resource Planner or OptaPlanner distribution you've downloaded earlier.
  2. Go to the "examples" directory and execute "runExamples.bat" (Windows) or "runExamples.sh" (Linux & Mac OS X).
  3. Choose one of the examples, for example the "Cloud Balancing" example.
  4. Click on one of the unsolved data-sets in the left-hand-side of the screen. Start with a small data-set, like "4computers-12processes".
  5. Click on the "Solve" button to start solving the problem.
  6. We can see the process being assigned to computers. At the bottom of the screen we can see the "Latest best score", which improves when a better solution is found. Finally, the terminal window in which we've started the examples prints the steps performed by the optimisation algorithms.
  7. Note that an optimal solution is quickly identified (i.e. "0 hard / -7140 soft").
  8. Open a larger data-set, e.g. "200computers-600processes" and re-run the solver. Note that the processes in a larger data-set are constantly re-assigned and the solution constantly improves. Because of the larger problem domain, there are many more combinations of feasible solutions. Business Resource Planner will keep trying to find better solutions as long as we give it more time.

4: Identify the demo equivalent of your optimization problem

One of the characteristics of optimisation problems is that the basic structure of these problems is usually quite similar. As a result, you can probably find a problem provided with the Business Resource Planner examples of which the structure is quite similar to your problem domain and business problem. The exercise is to find the problem provided with the examples that matches your optimisation problem. For example, if your problem is assigning employees to shifts, the Nurse Rostering example would be a good base.

5: Implement your domain model and score rules.

Although the basic structure of the optimisation problems are usually quite similar, the domain model and score rules (the rules that implement the hard and soft-constraints), can (and will) differ a lot. We therefore need to (gradually and incrementally) adapt the domain-model and score-rule to our business domain and problem.

Starting with one of the selected examples in the previous step, import the source-code and rules into your IDE of choice (e.g. Eclipse, IntelliJ). The source code of the demo's can be found in the "examples/sources" directory of the Business Resource Planner/OptaPlanner distribution.

All examples have the following package structure in the "src/main/java" directory:

  • {example}/app
  • {example}/domain
  • {example}/domain/solver
  • {example}/persistence
  • {example}/swingui

The "{example}/domain" package contains the domain model of the problem. It contains the PlanningEntityPlanningVariable and PlanningSolution. Inspect the domain model carefully and gradually adapt it to match your problem domain.

The score-rules, which implement the hard and soft constraint can be found in the "src/main/resources" directory in:

  • {example}/solver

That directory contains 2 files, the "{example}ScoreRules.drl" file which contains the score rules and the "{example}SolverConfig.xml" that provides the Business Resource Planner configuration. Gradually adapt and implement the score-rules which match your business problem, using the provided example rules as a base.

6: Use the Benchmarker to analyse and optimize your solution

Once you've (partially) implemented your business resource problem, it is time to analyse (and optimise) its behaviour. To analyse the performance of your implementation, OptaPlanner provides a Benchmarker. The Benchmarker allows to analyse your current implementation and configuration (e.g. which algorithms are used) for a given data-set.

The Benchmarker allows you to run the solver on a given data-set with a number of different solver configurations (e.g. different optimisation algorithms). The output of the Benchmarker is an HTML file with the analysis of the different solver runs. It provides information like "best score summary", "average calculation count" and the performance of the optimisation algorithms used. This information allows us to choose the best algorithm for the given problem domain and data-set and to improve the implementation of our solution (for example by implementing more sophisticated concepts like custom moves).

Conclusion

Most organisations are faced with complex and hard to solve planning problems. Red Hat JBoss Business Resource Planner and OptaPlanner provide a sophisticated constrain satisfaction solver that give you the possibility to find optimal solutions to these problems, resulting in higher productivity, less costs and higher customer satisfaction

In this post we've provided 6 easy steps to get you started with OptaPlanner and implement your business problem in the leading open-source resource optimisation platform.

 

About the author:

Duncan Doyle is the Technical Marketing Manager for the JBoss BRMS and BPMSuite platforms at Red Hat. With a background in Red Hat Consulting and Services, Duncan has worked extensively with large Red Hat customers to build advanced, open-source, business-rules and business process management solutions.

He has a strong background in technologies and concepts like Service Oriented Architecture, Continuous Integration & Delivery, rules engines and BPM platforms and is a subject matter expert (SME) on multiple JBoss Middleware technologies, including, but not limited to, JBoss EAP, HornetQ, Fuse, DataGrid, BRMS and BPMSuite. When he’s not working on open-source solutions and technology, he is building Lego with his son and daughter or jamming along some 90’s rock-music on his Fender Stratocaster.

Last updated: January 22, 2024