Aplicações de meta-heurísticas na resolução de problemas de sequenciamento de tarefas

Abstract

O sequenciamento de tarefas refere-se ao problema de determinar a sequência de um conjunto de tarefas ou atividades que deve ser realizado, de forma a melhorar algum critério de desempenho, como o tempo total de execução ou a utilização dos recursos disponíveis. Esse problema é comum em áreas como o planejamento da produção, logística e gestão de projetos, onde a alocação eficiente dos recursos e a minimização de custos são essenciais para a eficiência operacional. Este trabalho aborda a aplicação de meta-heurísticas no problema de sequenciamento de tarefas, um desafio relevante nessas áreas, onde a alocação eficiente de recursos é crucial para o desempenho do sistema. O problema, frequentemente complexo devido à grande quantidade de variáveis e à necessidade de otimizar múltiplos critérios, é tratado com o uso de técnicas computacionais avançadas, como algoritmos genéticos, GRASP (Greedy Randomized Adaptive Search Procedure) e Simulated Annealing. O principal objetivo desta pesquisa é aplicar meta-heurísticas para a resolução de problemas de sequenciamento de tarefas, equilibrando a qualidade das soluções com a viabilidade computacional. Para tanto, o trabalho envolve a implementação desses algoritmos em Python, configurados para a minimização da soma ponderada de custos de atraso e adiantamento, considerando tanto problemas com máquinas simples quanto em paralelo. A análise de desempenho se baseia em parâmetros como a qualidade da solução e o tempo de execução, além de um processo de calibração dos parâmetros de cada meta-heurística. Além disso, são apresentados os resultados obtidos por meio da execução de diversos casos de teste, comparando o desempenho das técnicas aplicadas, e discutindo a eficácia das abordagens em diferentes configurações do problema. Com isso, o estudo não só contribui para a compreensão do impacto das meta-heurísticas no sequenciamento de tarefas, mas também propõe alternativas viáveis para situações onde a busca exaustiva pela solução ótima é computacionalmente inviável. As meta-heurísticas destacam-se como ferramentas eficazes para resolver o problemas de sequenciamento de tarefas, apresentando vantagens significativas no tempo computacional, especialmente em instâncias de maior porte. Enquanto o método de programação linear inteira mista (PLIM) é capaz de alcançar soluções ótimas, ele enfrenta limitações quando o tamanho das instâncias aumenta, devido ao elevado custo computacional. Em contrapartida, algoritmos como o Algoritmo Genético, GRASP e Simulated Annealing fornecem soluções de alta qualidade em um tempo significativamente menor, tornando-se alternativas adequadas para cenários em que o PLIM se torna inviável. Esses resultados ressaltam a importância de considerar a relação entre a busca pelo ótimo e eficiência computacional ao selecionar métodos de solução.

Scheduling refers to the problem of determining the sequence of a set of tasks or activities to be performed in order to improve some performance criterion, such as total execution time or the utilization of available resources. This problem is common in areas such as production planning, logistics, and project management, where efficient resource allocation and cost minimization are essential for operational efficiency. This work addresses the application of metaheuristics to the task sequencing problem, a relevant challenge in these fields, where efficient resource allocation is crucial to system performance. The problem, often complex due to the large number of variables and the need to optimize multiple criteria, is tackled using advanced computational techniques, such as Genetic Algorithms, GRASP (Greedy Randomized Adaptive Search Procedure), and Simulated Annealing. The main objective of this research is to apply metaheuristics to solve task sequencing problems, balancing the quality of solutions with computational feasibility. To achieve this, the work involves implementing these algorithms in Python, configured to minimize the weighted sum of tardiness and earliness costs, considering both single-machine and parallel-machine problems. The performance analysis is based on parameters such as solution quality and execution time, along with a calibration process for each metaheuristic’s parameters. Additionally, the results obtained through the execution of various test cases are presented, comparing the performance of the applied techniques and discussing the effectiveness of the approaches under different problem configurations. Thus, the study not only contributes to understanding the impact of metaheuristics on task sequencing but also proposes viable alternatives for situations where exhaustive search for the optimal solution is computationally infeasible. Metaheuristics stand out as effective tools for solving task sequencing problems, offering significant advantages in computational time, especially for larger instances. While the Mixed-Integer Linear Programming (MILP) method can achieve optimal solutions, it faces limitations as instance sizes increase due to high computational costs. In contrast, algorithms such as the Genetic Algorithm, GRASP, and Simulated Annealing provide high-quality solutions in significantly less time, making them suitable alternatives for scenarios where MILP becomes infeasible. These results highlight the importance of considering the relationship between the search for optimality and computational efficiency when selecting solution methods.