UMA HEURÍSTICA BASEADA EM VARIABLE NEIGHBOURHOOD SEARCH PARA O PROBLEMA DE BALANCEAMENTO DE LINHAS DE PRODUÇÃO E DESIGNAÇÃO HIERÁRQUICA DE TRABALHADORES

Vol 53, 2021 - 139780
Pôster
Favorite this paper
How to cite this paper?
Abstract

O problema de Balanceamento de Linhas de Produção e Designação Hierárquica de Trabalhadores (BLPDHT) é altamente presente nas indústrias que realizam produção em larga escala. O problema se resume no escalonamento de trabalhadores em estações para realizarem determinadas tarefas, porém nem todos os trabalhadores estão aptos a executar todas as tarefas e, além disso, deve-se respeitar uma hierarquia predefinida que leva em consideração o nível de experiência de cada trabalhador. Desta forma, quanto mais experiente for o trabalhador, menor será o tempo necessário para que ele execute uma determinada tarefa, e consequentemente o custo de utilização deste trabalhador será mais elevado. O escalonamento deve respeitar o tempo máximo de execução das tarefas por estação, previamente estabelecido. Ainda, deve-se levar em consideração a precedência entre as tarefas nas linhas de produção. O custo total do escalonamento é dado pelo somatório dos custos de cada tipo de trabalhador alocado nas estações. O objetivo do BLPDHT é definir um escalonamento de trabalhadores em estações de trabalho de forma que o custo total das linhas de produção seja minimizado. Pelo fato de o BLPDHT pertencer à classe NP-difícil, encontrar uma solução por métodos exatos pode demandar tempos computacionais proibitivos. Sendo assim, foi desenvolvida uma estratégia heurística, denominada VNS-BLPDHT, baseada no algoritmo Variable Neighbourhood Search (VNS). Como método de busca local foi utilizado o Random Variable Neighbourhood Descent (RVND), para que buscas locais em estruturas de vizinhanças sejam realizadas visando a intensificação da busca por melhores soluções. A heurística VNS-BLPDHT modela as soluções do problema através de dois vetores, um vetor que representa o escalonamento com todas as tarefas que devem ser executadas, separadas por suas estações, e um vetor com trabalhadores que identifica qual o tipo de trabalhador que irá executar as tarefas de cada estação. O VNS-BLPDHT utiliza oito estruturas de vizinhanças responsáveis por modificar as soluções, dentre elas destacamos: a troca de tarefas entre estações e a troca do tipo do trabalhador por estação. Neste trabalho foram utilizadas instâncias disponíveis na literatura e boas soluções foram encontradas para o BLPDHT. A heurística VNS-BLPDHT obteve resultados potencialmente satisfatórios e atingiu o ótimo para 30 de 45 instâncias utilizadas. Ao se comparar os resultados obtidos com os já encontrados na literatura, podemos constatar que ainda existe uma superioridade no tempo de execução pelos métodos já existentes. A maior dificuldade encontrada pelo algoritmo provém das instâncias em que o número de precedência das tarefas é alto, gerando uma maior complicação para dividir as tarefas nas estações sem quebrar a regra de precedência e o tempo máximo de execução por estação.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal de Viçosa - Rio Paranaíba
Track
  • 13 - MH - Metaheuristics
Keywords
BLPDHT
VNS
RVND