Heurística e limites duais para o problema de dimensionamento de lotes e sequenciamento com tempos de preparação dependentes da sequência

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.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