Geoffrey De Smet, the founder of OptaPlanner, and his team demonstrated a real-time planning and scheduling example using OptaPlanner at the 2019 Red Hat Summit keynote. Geoffrey and his team dedicated three blog posts to describe this program. This program and its related blog posts are considered classic works of OptaPlanner in the field of VRP. This series will also be translated into three posts for the enjoyment of ORers, APSers, and Planners.
Currently, I am researching this program and will further analyze it in the future, forming blog posts to share its intricacies.
[Below is the translation]
This year, my team and I gave a keynote speech at the Red Hat Summit. In front of 7,000 people, we demonstrated a real-time scheduling program that can respond in real-time to inputs from the audience via a mobile app. Over the past two months, our team collaborated with other middleware teams under the excellent guidance of Burr Sutter to create this real-time scheduling program. This program integrates multiple technologies, such as accelerometers on Android/iPhone, as well as OpenShift/Kubernetes, Quarkus, KNative, TensorFlow, Kafka/Strimzi, Camel, Node.js, Godot, Infinispan, Drools, and of course, the star of the show, OptaPlanner.
We wrote a simulator to simulate a typical floor production scenario, involving machines on an assembly line. When I first showed this program to my wife, it sparked an interesting conversation:
“Look, dear, this is the example program from the keynote speech that we have been working on for the past two weeks.”
“It looks like a mini-game; are those Mario and Luigi running around?”
“No, those are the machine maintenance workers; it demonstrates how OptaPlanner optimizes their walking time so they can spend more time repairing machines.”
“Are you really going to show this to over 7,000 business people?”
“Of course, the presentation will be spectacular.”
The effect of the program running is as follows:
Currently, there are 10 machines (numbered A to J) that experience wear and tear during operation, which is detected through sensors. With the help of the audience (who installed our app), we simulate the sensors by obtaining data from the accelerometers on their phones. As the saying goes, the more precarious things become, the more fragile they are. When the audience shakes their phones vigorously or makes other shaking motions, the corresponding machines in the program receive damage notifications. (Due to the large number of attendees), each part of the audience sends damage information to the corresponding machine by shaking their phones, causing the health value of that machine to decrease. If a machine’s health value drops to 0, it indicates that the machine has broken down.
At this point, those damaged machines are scheduled for repair before they break down, which is where OptaPlanner comes into play. The program has 2 to 3 maintenance workers to repair these damaged machines, and while the maintenance workers shuttle between machines, all machines continue to lose health (as the audience keeps shaking their phones). When scheduling the machines, deciding the order of repairs is challenging because damage occurs constantly. Fortunately, OptaPlanner helps us schedule these maintenance workers, responding in real-time to changes in machine health, as shown in the video:
(Below, we discuss the specific design of the planning program)
The Challenges of This Planning Problem
The planning objective is simple: do not let the health value of any machine drop to 0%. This seems like a simple constraint, but in fact, it presents two conflicting constraints:
1. Prioritize repairing the machine with the lowest health value, as it has the highest risk of breakdown.
2. Allow the maintenance workers to repair nearby machines as quickly as possible by minimizing their travel paths. The reasons are as follows:
-
a. Maintenance workers need to move between machines in addition to repairing them, so reducing their travel time increases their productivity.
-
b. If only the shortest path constraint is considered, it becomes a TSP problem (Traveling Salesman Problem).
These two constraints compete with each other, each leaning towards different solutions:
The impact of these two constraints on completion time is not very obvious, i.e., how they affect the time needed for maintenance workers to repair all malfunctioning machines at once. The longer the repair time, the lower the productivity:
Therefore, we ultimately need to weigh these two constraints. We assess a penalty score for each damaged machine by multiplying the amount of damage by the duration until that machine is repaired. Thus, the solutions planned by OptaPlanner will avoid increasing the degree of damage to machines as much as possible or minimizing the time the machines remain in a damaged state.
This Is Just a Vehicle Routing Problem (VRP)
In the academic world of operations research, such problems are also known as Vehicle Routing Problems (VRP), where we need some vehicles (e.g., trucks) to be sent to multiple destinations.
As shown in the diagram above, these are essentially the same problem with some differences in constraints.
Currently, OptaPlanner is indeed good at solving optimization problems related to vehicle routing: by achieving a time reduction of 15% or more in overall vehicle operating time, we save hundreds of millions of dollars for some customers each year. At the same time, it also significantly reduces energy consumption of vehicles, thus reducing carbon emissions, which is beneficial for the environment.
To learn more about how OptaPlanner optimizes VRP problems:
https://www.optaplanner.org/learn/useCases/vehicleRoutingProblem.html
Or check out Jiri (another member of the OptaPlanner project) latest demo on VRP problems:
https://github.com/kiegroup/optaweb-vehicle-routing
The demo video is as follows (this video has not yet been translated):
The real challenges in the maintenance worker scheduling program
First, implementing this variant of the vehicle routing problem is not actually complex, but ensuring that the program’s interaction and demonstration run smoothly presents a greater challenge. After all, we cannot risk the program crashing during the demonstration in front of the audience and our CEO, Jim Whitehurst.
-
To learn more about our architecture and integration with all other technologies, read Musa’s article (Part 2: https://www.optaplanner.org/blog/2019/05/09/RHSummit2019Part2.html).
-
To learn more about extension challenges and benchmarks for our simulations and load tests, read Radovan’s article (Part 3: https://www.optaplanner.org/blog/2019/05/09/RHSummit2019Part3.html).
If you want to debug this program yourself, you can download it from the link below and follow the readme instructions for scheduling.
https://github.com/rhdemo/2019-demo4-optaplanner
End.