Metaheurísticas para o problema de programação de tarefas em máquinas paralelas com tempos de preparação dependentes da sequência e de recursos

Abstract

Os problemas de programação de tarefas em máquinas paralelas são importantes na área de otimização combinatória, pois quase sempre envolvem problemas rotineiros em indústrias de pequeno e grande porte. Este trabalho aborda o problema de sequenciamento de tarefas em máquinas paralelas, com tempos de preparação das máquinas dependentes da sequência e do número de recursos utilizados. A característica deste problema é que o tempo de preparação não é determinado apenas pela máquina e pela sequência das tarefas, mas também pela quantidade de recursos associados, que varia entre um valor mínimo e um máximo. Dada a complexidade combinatória do problema, inicialmente propõe-se um algoritmo baseado na metaheurística GRASP, no qual o parâmetro de aleatoriedade utilizado na fase de construção é auto-ajustado de acordo com as soluções previamente encontradas (GRASP Reativo). Em seguida, propõe-se um algoritmo baseado na metaheurística Iterated Local Search (ILS). Esta metaheurística foi proposta recentemente na literatura e está sendo aplicada satisfatoriamente em diversos problemas de otimização combinatória. Em ambos os algoritmos, é utilizada a estratégia de intensificação baseada na técnica de Reconexão de Caminhos, que explora trajetórias que conectam soluções de alta qualidade encontradas pelos algoritmos. Os resultados obtidos pelos algoritmos propostos são comparados entre si e com os melhores resultados disponibilizados na literatura. A análise e a discussão dos resultados mostram que as metaheurísticas aplicadas, apresentaram resultados satisfatórios, sendo possível melhorar, em média, 9,14%, os resultados da literatura, o que comprova a viabilidade do uso destes algoritmos na resolução de problemas práticos existentes nas indústrias.

The problems of scheduling jobs on parallel machines are important problems of combinatorial optimization. They involve routine problems in industries of small and large. This work addresses an unrelated parallel machine problem with machine and job sequence dependent setup times. The characteristic of this problem is that the amount of setup times do not only depend on the machine and job sequence, but also on a number of resources assigned, which can vary between a minimum and a maximum. Due to the combinatorial complexity of this problem, initially we propose an algorithm based on the GRASP metaheuristic, in which the basic parameter that defines the restrictiveness of the candidate list during the construction phase is self-adjusted according to the quality of the solutions previously found (reactive GRASP). Then, we propose an algorithm based on the Iterated Local Search (ILS) metaheuristic. This metaheuristic was proposed recently in the literature and is being applied successfully to several combinatorial optimization problems. In both algorithms, an intensification strategy based on the path relinking technique is used. This consists in exploring paths between elite solutions found by the algorithms. The results obtained by the proposed algorithms are compared with each other and with the best results available in literature. The analysis and discussion of results obtained with the algorithms, leads us to conclude that the metaheuristics show good performance, it is possible to improve, on average, 9,14% the results of the literature, which demonstrates the feasibility of using these algorithms to solve real problems existing in industries.