Heurística e limites duais para o problema de dimensionamento de lotes e sequenciamento com tempos de preparação dependentes da sequência
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Mauricio Cardoso de Souza
Martin Gomez Ravetti
Thiago Ferreira de Noronha
Martin Gomez Ravetti
Thiago Ferreira de Noronha
Resumo
Este trabalho aborda os Problemas de Dimensionamento de Lotes e Sequenciamento em sistemas de produção monoestágio, que consiste na determinação dos níveis de produção ao longo de diversos períodos de tempo para atender às demandas de produção de um conjunto de produtos. O objetivo do problema é obter um plano que minimize os custos de produção, estoque, atraso e preparação das máquinas, que são oriundos do processo fabril. Considera-se um parque industrial composto por máquinas paralelas não relacionadas com tempos de preparação dependentes da sequência.Um método heurístico é proposto para resolver o problema. A ideia básica do algoritmo consiste em gerar soluções para um problema de dimensionamento não capacitado que considera apenas um recurso e aplicar procedimentos que restabelecem o sequenciamento e as limitações de tempo. Em seguida, essas soluções iniciais viáveis são submetidas a um processo de melhoria baseado na metaheurística Busca Tabu. Para medir a qualidade das soluções, é proposta uma relaxação combinatória da qual se obtém limites duais para o problema. Experimentos computacionais são realizados sobre instâncias geradas artificialmente. São construídos cenários de testes que consideram instâncias de pequeno e grande porte. Os resultados computacionais comprovam tanto a eficiência da heurística quanto do procedimento de geração de limites duais.
Abstract
This work addresses the lot sizing and scheduling integrated problem in single-level manufacturing systems, which consists in determining levels of production over various periods of time to meet production demands for a range of products. The objective of the problem is to get a plan that minimizes production, inventory, backlog and setup costs. We consider an industrial park consisting of unrelated parallel machines withsequence dependent setup times. A heuristic method is proposed to solve the problem. The basic idea of the algorithm is to generate solutions to an uncapacitated lot-sizing problem with only one resource and implement algorithms that restore the scheduling and time constraints. These initial feasible solutions are subjected to a process of improvement based on a Tabu Search metaheuristic. To measure the quality of solutions, we propose a combinatorial relaxation that generates dual bounds for the problem. Computational experiments are performed on random instances. The test scenarios are built to consider instances of small and large sizes. The computational results prove the efficiency of both heuristics as the procedure for generation of dual bounds.
Assunto
Agenda de execução (Administração), Pesquisa operacional, Otimização combinatória, Processamento paralelo (Computadores), Computação, Programação paralela (Computação)
Palavras-chave
método heurístico