[JAVA] Plan optimization "utilization image" with AI that understands the reason for the result
Author: Takashi Takahisa, Hitachi, Ltd.
Introduction
In this article, I posted [Red Hat Decision Manager](https://www. We will introduce a concrete model case and utilization image about the features of planning optimization using redhat.com/en/technologies/jboss-middleware/decision-manager). If you have not read the above article, we recommend that you read it first.
Post list:
- Plan optimization with AI that understands the reason for the result
- Plan optimization "utilization image" with AI that understands the reason for the result (this post)
Model case (equipment inspection plan)
In this model case, we will optimize the annual inspection plan for large equipment.
background
For the following reasons, we will systematize the inspection planning work that was carried out manually. ・ As the number and types of equipment to be inspected increased, it took a long time to make a plan. -Since it is a large device, the inspection cost per unit is high, and by increasing the number of return days (inspection interval) within the permissible range, a significant cost reduction can be expected. (In the conventional manual planning, it was difficult to consider the restrictions to be observed, and efficiency could not be considered.)
Outline of the plan
The list of equipment to be inspected for the current year and the related data used in the optimization calculation are input, and the inspection start date and inspection area (where the inspection is performed) of each equipment are calculated and output. The number of inspection days for each device type shall be predetermined. Inspections can only be conducted on weekdays. It is not possible to inspect multiple devices at the same time in one inspection area.
Constitution
In this model case, it is implemented with the following configuration.
Constraints / Evaluation Index (Excel Rule)
In this model case, the following constraints are set.
■ Absolute constraints (constraints that you definitely want to keep) -Limitation on the number of simultaneous inspections per day: Only x units can be inspected per day. -Limited number of days: The inspection must be done within x days from the last inspection end date. ■ Consideration constraints (constraints that you want to keep as much as possible) -Consideration of the number of simultaneous inspections during the busy season: For devices of a specific classification, we want to keep the number of devices to be inspected during the busy season within x. -Consideration of inspection system for the same device: For devices of the same type, the inspection start date should be x days or more. ■ Evaluation index (index for calculating better combinations) -Maximization of regression days: The larger the number of regression days (inspection interval), the better. (To reduce inspection costs & downtime) -Work leveling for each month: Level the number of inspections for each device type in each month.
** Excel rules **
■ About priority adjustment between rules Priority is defined by level + weighting factor, and the result is evaluated as a score value for each level. It is evaluated in order from the highest level score value (Hard in the above example), and if the high level score value is the same, it is evaluated by the next level score value, and the combination with the best score value is the optimum solution. I will. In this example, two levels, Hard and Soft, are used in order to optimize the degree of compliance with the consideration constraint and the evaluation index while always observing the absolute constraint.
In this example, there are two levels, Hard and Soft, but it can be three or more. If you want to prioritize compliance with consideration constraints over improvement of evaluation indicators, rather than comprehensively evaluating the degree of compliance with consideration constraints and improvement of evaluation indicators, set consideration constraints to Medium level. It can be achieved by doing.
The weight factor is the priority adjustment factor for rules of the same level. In this example, the weighting factor is specified as an integer, but you can specify a BigDecimal type value. For example, you can specify values such as "12.345" and "0.02". Increase the weight factor for high priority rules, but also consider the base value of the score for each rule. For example, the absolute constraint # 1 is based on the number of units that exceed the inspection number limit, and the absolute constraint # 2 is based on the number of days that exceeds the limit number of days. I'm making it bigger. In the case of absolute constraints, we always want to keep it, so we don't have to be very conscious of the weighting coefficient of the Hard level, but this time, when input data that is difficult to keep comes, we can detect both on average. Adjusted in consideration. Soft level weighting factors need to be considered and determined in order to make a good plan. However, you can change it at any time, so you can specify a rough value at first.
Input data
The equipment to be planned and master data are received as input data. By receiving the threshold of the constraint rule as input data, it is easy to change it later. Since it would be too long to list all the input data, I will list it as an excerpt (there are some other master data to refer to).
** Device data to be inspected **
| Device type | Device name | Last inspection end date |
|---|---|---|
| A | A01 | 2017/9/15 |
| A | A02 | 2017/4/20 |
| … |
** Definition data **
| Key | value |
|---|---|
| Limitation on the number of simultaneous inspections per day | 5 |
| Maximum number of days | 900 |
| … |
** Inspection days data **
| Device type | Inspection days |
|---|---|
| A | 16 |
| B | 16 |
| … |
Business application
In this model case, we implemented input data reading, evaluation processing of some constraint conditions referenced from constraint rules, calling of optimization calculation of Red Hat Decision Manager, output of optimization calculation result, output of score data, etc. I am creating a business application. The most important and difficult AI optimization calculation itself is performed by Red Hat Decision Manager, so the number of steps in the business application is 1.2Ks, which is a simple implementation.
Optimization Calculation (Red Hat Decision Manager)
The optimization calculation of Red Hat Decision Manager is performed by repeatedly executing the following processes (1) to (3). (1) Generate a combination of each device and inspection start date & inspection area (2) Calculate the score of the constraint condition / evaluation index defined as an Excel rule for the generated combination. (3) Compare the score value of this combination with the score value of the combination of the past optimal solutions, and set the better one as the optimal solution.
Here, the algorithm for generating the combination of (1) and the repetition time (calculation time) of (1) to (3) are defined in the Red Hat Decision Manager configuration file. The optimum calculation time and algorithm settings depend on the amount of data, the number of constraints / evaluation indexes, etc., but in this model case, the following settings are used. Initial solution generation algorithm: First Fit Local search algorithm: Late Acceptance Optimization calculation time: 60 seconds
Definition contents of this optimization algorithm
<termination>
<secondsSpentLimit>60</secondsSpentLimit>
</termination>
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
</constructionHeuristic>
<localSearch>
<acceptor>
<lateAcceptanceSize>80</lateAcceptanceSize>
</acceptor>
<forager>
<acceptedCountLimit>1</acceptedCountLimit>
</forager>
</localSearch>
■ About optimization algorithm Red Hat Decision Manager's optimization algorithms are based on a combination of initial solution generation algorithms and local search algorithms. The initial solution generation algorithm generates the first combination, and the local search algorithm generates the second and subsequent combinations.
The initial solution generation algorithm uses First Fit, which is the easiest to use this time. If you want to improve performance, consider using other algorithms such as First Fit Decreasing, which allows you to prioritize the combination of initial solutions.
The local search algorithm uses Late Acceptance this time because it is highly scalable, it is easy to find the optimum solution, and it is easy to tune. Other well-known algorithms such as Tabu Search and Simulated Annealing are also supported, and we will consider them as needed.
For Late Acceptance, you only need to fix the acceptedCountLimit to 1 (4 in some cases) and tune only the lateAcceptanceSize. Also, for lateAcceptanceSize, the larger the specified value, the larger the number of combinations to be targeted and the longer it takes to solve the problem, but the higher the maximum score tends to be. Therefore, the value is adjusted according to the scale of the input data (in this case, the number of devices to be inspected, the number of candidate dates for inspection start date, the number of inspection areas) and the calculation time. Even if the input data is different each time, you can use it by dynamically setting the value specified for lateAcceptanceSize according to the scale of the input data.
Tabu Search needs to be tuned by combining two parameters, and the range of specified values also needs to be tuned in a larger range than Late Acceptance.
Simulated Annealing is a specified value of tuning parameter, and it is necessary to consider the score of the constraint rule in addition to the scale and calculation time of the input data. It needs to be reviewed.
Red Hat Decision Manager's planning optimization features are based on an OSS called OptaPlanner. If you would like to see a list of algorithms and detailed specifications available in Red Hat Decision Manager, please refer to the OptaPlanner User Guide.
■ About calculation time and score convergence The longer the calculation time, the better the result, but over time the score will converge and hardly improve. Decide how much time you want, taking into account your target score (degree of optimization) and performance requirements. In addition to the simple end of calculation, the calculation can be completed when a specific score is reached, the calculation ends when the score does not improve for a certain period of time, and the calculation ends when any of multiple end conditions is met.
** Example of time lapse and score convergence **
Result data
-The optimization result data is the data to which the inspection start date and inspection area are assigned to the equipment to be inspected. -For inspection areas, we prepare as many inspection areas as the number of simultaneous inspections per day, and assign which inspection area each device uses. -For the inspection end date, the value automatically calculated from the inspection start date and the number of inspection days is output. -For the number of regression days, the value automatically calculated from the inspection start date and the previous inspection end date is output.
** Result data (excerpt) **
| Device type | Device name | Inspection start date | Inspection end date | Inspection area | Regression days |
|---|---|---|---|---|---|
| E | E09 | 2019/4/25 | 2019/5/24 | 5 | 735 |
| A | A07 | 2019/4/26 | 2019/5/24 | 4 | 599 |
| … |
** Visualized result data (excerpt) **
Score information data (reason for results)
This is the data that outputs the degree of compliance with the constraints and the evaluation by the evaluation index as a score. The score this time is a deduction method for all rules, and the closer it is to 0, the better the evaluation. In this business application, it is output to an Excel file.
** Summary sheet **
** Rule + device unit sheet (excerpt) **
** Rule + plan start date sheet (excerpt) **
Image of utilization of score information data (reason for results)
Confirmation that it is working as expected
The absolute constraint and the consideration constraint are in the "summary sheet" above, and the score is "0hard / 0soft", which shows that there is no violation (protected).
For evaluation index # 1, "-(limit days-regression days)" * "Excel rule weighting factor 1" is used as the score value. Looking at the "Rule + Device Unit Sheet (Excerpt)" above, the value in the "Score" column and the value in "Limited Days-Regression Days" are "0hard / -109soft" and "109" in every row. You can see that they match and are working properly.
For evaluation index # 2, the score value is "-(total number of devices / 12-number of devices in the current month) ^ 2" * "Excel rule weighting factor 100" for devices of the same device type. The fraction of the division is rounded to the first decimal place. Looking at the "Rule + Plan Start Date Sheet (Excerpt)" above, the value in the "Score" column matches the value calculated by the above formula in every row, and it is working correctly. I understand. Example:-(13/12 --1) ^ 2 * 100 =-(1.08333 ... --1) ^ 2 * 100 =-(1.1 --1) ^ 2 * 100 =-(0.1) ^ 2 * 100 =- 0.01 * 100 = -1 ⇒ Matches "0 hard / -1.00 Soft".
Problem detection of input data and constraints
Depending on the content of the input data, the constraints may never be met and planning may not be possible. For example, the following cases. ・ Develop an inspection plan for FY2019 (after April 1, 2019). ・ The last inspection end date is 2016/3/1. -The maximum number of days for absolute constraint # 2 is 900 days. In such cases, even if the inspection start date is planned to be the earliest on April 1, 2019, the absolute restrictions cannot be observed and the plan cannot be made. (It is possible that the planned year, the previous inspection date, and the maximum number of days have been set incorrectly.) Score information data makes it easier to spot these issues because you can quickly see which data is violating.
** Score information (summary sheet) when the limit days are violated **
** Score information when the limit number of days is violated (rule + device unit sheet (excerpt)) **
Comparison with past plans
You can compare the scores of the past plan and the new plan to see if the plan is better than the past plan. By using the business application created for normal optimization calculation and Excel rules as they are and specifying the planned data as the input data, the score information of the past plan can be output. The planned data is the input data (inspection target device data) plus the planned "inspection start date" and "inspection area" values.
** Configuration of score information output of planned data **
** Planned data of past plans **
| Device type | Device name | Last inspection end date | Inspection start date | Inspection area |
|---|---|---|---|---|
| A | A01 | 2017/9/15 | 2019/4/22 | 1 |
| A | A02 | 2019/4/26 | 2019/7/25 | 1 |
| … |
** Past plan score information data **
** Score information data for new plans by Red Hat Decision Manager **
In this example, all the constraints are met in both the past plan and the new plan, but the score of the evaluation index is better in the new plan, and it can be seen that the plan is more efficient.
Also, if you adjust the weight of the Soft score by cost, you can quantitatively judge how much cost reduction was achieved from the improved score. For example, if the cost is reduced by 20,000 yen per Soft score due to the reduction of the number of inspections by maximizing the number of return days and the reduction of additional inspection costs such as overtime pay by work leveling, (Past plan score-New plan score) * (Cost reduction cost per Soft score) = (10426 - 6979) * 2 = 3447 * 2 = 6894 It can be estimated that "the cost was reduced by 68.94 million yen compared to the past plan".
By comparing the scores of the past plan and the new plan in this way, it is possible to quantitatively judge how optimized it is. Also, in the unlikely event that the past plan has a better score, you will be aware that there are specifications that have not been taken into consideration, and that there are issues such as calculation time and algorithm tuning.
in conclusion
In this article, we introduced an image of using AI-based plan optimization to understand the reason for the results. By utilizing the score information data that is the reason for the result, it is possible to quantitatively judge how much optimization has been performed and improve it so that better optimization can be performed. I hope you will consider using it.