Research and Development

HISTORY, MILESTONES, FACTS

Solution of Complex Tasks

 

Usually, to solve optimization tasks, including scheduling tasks, we use specialized software called an optimization solver. It is capable of performing a smart search of the status space and finding good or even optimal solutions.

 

There are different types of solvers such as mip/lp solvers, constraint solvers, sat solvers and others. For all of them, it is necessary to find a suitable way of modeling the problem for a specific optimization problem and, if necessary, to add on to the solver. Some well-known solvers are ones such as Gurobi, Cplex or the OR-Tools solver library.

Our Approach

 

As we started developing our platform, it was clear that complex and more extensive tasks required more than the standard solution method, which is assigning a complete task to an optimization solver and waiting for a solution, because these tasks exceeded the possibilities of solvers and technology in relation to memory and time requirements.

Therefore, we used the natural decomposition of the optimization task into subtasks solved at the workstation level, which allows the solution to scale. In practice, this approach reflects the method of production management, where the manager is responsible for certain workstations. This solution enabled us to isolate the effects of sudden changes in production only to certain stations and to preserve the original solution at the other stations.

Our Solution

• Our solution supports both vertical and horizontal directions. Vertical allows sharing of resources between workstations. Horizontal allows simulation of not only the current state, but also subsequent steps, up to the defined goal. 
• The horizontal direction typically involves the possibility of performing the operation at different stations, something that can be advantageous. There is, however, a risk of overloading the last possible station as the result of a past bad decision.

 

• This solution layer is deployed using a multi-agent system. Here, the autonomous SW module (agent) represents a workstation or a group of stations in a specific time interval. The goal is to find the best solution (schedule). Due to the possibility of resource sharing and accepting the operations of other agents, various alternatives must be considered. The result is a combination of non-conflicting solutions of individual agents.

 

• At the same time, communication between agents is a search for an alternative assignment that will allow finding the best solution. The multiagent system replaces classic solvers, e.g. in the preparation of alternatives. One big monolithic task breaks down into smaller solvable sub-tasks. Communication between agents leads to the achievement of the best solution to the original large task.

• The second layer of the solution currently relies on two solvers. The first is the classic constraint solver. For this, in addition to our own search strategy, we have also developed specialized promoters. These serve mainly to support workers. The second solver is CP-SAT from the Or-Tools library. This hybrid solver, using techniques from the CP, MIP, and SAT solvers, largely compensates for the shortcomings of the first solver. Both solvers act as services for the agents of the multi-agent system providing complementary solutions for the submitted tasks. The advantage of this approach is, among other things, cooperation between solvers, in which we can let them solve the same task in parallel and share the solutions found.

 

• CPU performance typically does not allow simultaneous computation of tasks for all stations. During the calculation, additional tasks arising from communication between agents may arise. In addition to additional processing, when the system reacts to the local result just found, we prevent this by also scheduling the calculation itself. This is where the decision is made between which variants we will prefer, hold off, and those we will cancel.

Development of the EPIQA tool

TIMELINE

• 2013 Research

  The beginning of the European research project ARUM from the EU Horizon 2020 program. We get access to representative data in the field of production lines from partner companies Airbus and Iacobucci.

• 2017 Deployment

  Key application for production planning and customization of Airbus aircraft.

• 2018 User Interface

  Deployment of a custom application to define different scenarios and optimize results.

• 2022 Integration

  Introduction of a set of REST APIs for connecting external application systems.

• 2024 Commercial Solution

  EPIQA is brought to market as a product for planning investment units or buildings.