What if mathematics could solve an operational problem in the programming of machines that work simultaneously – each with a specific and permanent set of tasks? This was the winning idea of the EstudIO Award, granted to INESC TEC researcher Ângelo Soares, at the 23rd Congress of the Portuguese Operational Research Society.
Scenario: a manufacturing unit with several machines performing different tasks, previously allocated, divided into families and dependents (sequentially) among themselves. Problem: the time to prepare the machine for each task will depend on the order in which they are processed, and the resources used in this management are limited, which may cause delays. Solution?
The researcher Ângelo Soares may be very close to solving the problem, with a strategy that achieved a gain of 79.61% compared to the performance of the traditional mathematical model. And he didn’t wait long to receive an award: his work was the best among ten other master’s degree theses at the national level.
“The EstudIO Award represents an initiative to acknowledge academic excellence. In this sense, I was quite honoured to receive this award, among other remarkable works. This recognition proves to be crucial and inspiring for my future path as a researcher”, said Ângelo Soares.
At the base of this work is the adaptation of two mathematical models. One follows the strip-packing approach, exploring the free spaces of the machines and minimising the total time to perform all tasks on all machines, and the other is time-indexed, ensuring that the tasks are distributed over time efficiently. “To reflect the real conditions of the production environment, I proposed a new objective function that aims to minimise the sum of the makespan (time between the beginning of the first task and the completion of the last task) of all machines. Considering that the production systems are continuous, an initial configuration of the machines was introduced, and the mathematical models were adjusted – considering the setups dependent on the sequence of families”, explained the researcher.
Since traditional mathematical methods have some limitations, a new approach was used: the mathematical heuristic. The idea was to shorten the space of solutions to analyse and accelerate the search for the optimal solution, through TS metauheuristics (with warm-start mechanism) and Constructive Heuristics (SCUTR).
The results? The different strategies used in the mathematical heuristic translated into positive results: combining TS and SCTUR managed to improve performance by 79.61%, with an average deviation of only 4.24% for the larger problems. “The TS metaheuristic demonstrated the ability to find the optimal solution and presented a reasonable computational response in problems with up to 32 machines and 100 tasks. The different approaches to mathematical heuristics showed promising results in solving this problem, highlighting the strategy that combines TS and SCTUR heuristics”, he added.
This is a valuable contribution to operational research that could be the beginning of other works in this area.
The researcher mentioned in this news piece is associated with INESC TEC.
News, current topics, curiosities and so much more about INESC TEC and its community!
