Modelo matemático e busca local aplicados ao problema de otimização de operação de pontes rolantes em um pátio de bobinas de aço.

Abstract

Este trabalho aborda o problema de sequenciamento das movimentações para a retirada de bobinas de aço de tamanhos diversos armazenadas em um pátio com uma ponte rolante e com empilhamento em três camadas. O problema considerado visa determinar o sequenciamento das movimentações para a retirada das bobinas demandadas, das bobinas que bloqueiam bobinas demandadas, e as novas posições para as bobinas que estão bloqueando aquelas que serão retiradas. Um modelo de programação linear inteira (PLI) é utilizado para a obtenção de soluções ótimas em instâncias de tamanho reduzido e uma heurística é proposta para abordar instâncias maiores. A função objetivo busca minimizar o tempo de finalização dos movimentos através da minimização do tempo de movimentação da última bobina. Foram consideradas as duas restrições de empilhamento que garantem a estabilidade do empilhamento de bobinas com tamanhos diferentes. Além disso, foi modelada uma restrição de segurança envolvendo a utilização da terceira camada e foi considerada a configuração de regiões do pátio destinadas a bobinas de tamanhos específicos. A heurística desenvolvida utiliza uma busca local em profundidade, sempre aceitando soluções na vizinhança melhores que a solução atual e utiliza uma estratégia de diversificação para evitar ótimos locais. É desenvolvida uma segunda versão da heurística capaz de gerar menos soluções inviáveis. Como principais contribuições destacamos: a investigação da otimização do problema com restrições de um cenário real, considerando restrições de segurança e configuração do pátio; a formalização do problema em um modelo de programação linear com utilização de empilhamento em 3 camadas, não encontrado na literatura existente; a implementação de duas versões de uma heurística baseada em busca local. Instâncias de tamanho pequeno foram utilizadas para avaliação do desempenho do modelo e da heurística, instâncias de tamanho similar a cenários reais foram utilizadas para avaliação da aplicabilidade da heurística e de seu desempenho em relação a um algoritmo de geração de soluções aleatórias. Percebeu-se que a heurística desenvolvida é capaz de realizar o sequenciamento das movimentações e a definição das posições de destino das bobinas bloqueantes, gerando soluções de boa qualidade em tempo hábil para aplicação industrial.

This work addresses the problem of scheduling movements to remove stored steel coils of different sizes piled up in a warehouse containing one crane and with a three-layers pilling scheme. The problem is to determine the scheduling of the crane movements to retrieve the target coils, the coils that block the target coils, and the new positions for the coils blocking the targets coils. An integer linear programming (ILP) model is used to obtain optimal solutions in small-sized instances, and a heuristic is proposed to be used in bigger instances. The objective function aims to minimize the makespan by minimizing the completion time of the last coil moved. Two stacking restrictions were taking into consideration to ensure the pilling stability of coils with different dimensions. Moreover, a security restriction was developed for the usage of the 3rd layer, and the configuration of areas in the yard designated for coils of specific dimensions was taken into account. The developed heuristic uses a local search always accepting better neighborhood solutions and uses a diversification strategy to avoid local optimal. A second version of the heuristic is developed and is capable of generating fewer inviable solutions. As main contributions, we highlight: the investigation of the optimization of the problem with the restrictions of a real scenario, including safety restrictions and yard configuration; the formalization of the problem with a linear programming model that uses three layers pilling schema, not found in the literature; the implementation of two versions of the local search heuristic. Small-sized instances were used to evaluate the model and heuristic performance, and instances of a size similar to real scenarios were used to evaluate the heuristic’s applicability and performance compared to a random algorithm. It was noticed that the heuristic proposed is capable of scheduling the movements and defining the blocking coils destination, generating good quality solutions in time for industrial usage.