Matheurísticas para o problema de dimensionamento de lotes com múltiplas plantas

Abstract

This Dissertation presents the lot sizing problem with multiple plants (factories) that produce several types of items, where every plant has a single machine. Each machine has setup time and costs, limited capacity and manufactures all types of items. In these plants, the planning horizon is finite and divided into periods. Besides that, each plant has its own demand. The demands of the items in a plant can be met by any plant, without delay, as the problem allows transfers of production lots among the plants and storage of production, both operations subject to costs. This problem, referred here as PDLCLMP, therefore, aims at defining a production planning to minimize the costs of setup, production, storage and transfers between plants, respecting the available resources and attending the demand previously determined in each plant. Due to the limitations found by recently proposed methods in the literature to find feasible solutions to the problem, in this Dissertation we propose matheuristics to solve the PDLCLMP. Three solution methods are presented: a Lagrangian heuristic; a Lagrangian heuristic hybridized with a meta-heuristic path-relinking; and a kernel search method. Besides these instances, others of large scale were generated and employed in experiments performed in this Dissertation. According to these experiments, both pure Lagrangian heuristic and the hybridized Lagrangian version presented an excelent performance when comparing with the best heuristic from literature. Meanwhile the proposed kernel search method, which had as primary goal to keep the solutions quality found by the CPLEX, however in a inferior computacional time, successfully succeded for the instances with small dimensions.

Esta Dissertação apresenta um estudo do problema de dimensionamento de lotes com múltiplas plantas (fábricas) que produzem diversos tipos de itens, sendo que todas as plantas possuem uma única máquina. Cada máquina possui tempo e custo de preparação, capacidade de produção limitada e produz todos os tipos de itens. Nas plantas, o horizonte de planejamento é finito e dividido em períodos. Além disso, cada planta tem sua demanda. As demandas dos itens em uma planta podem ser atendidas por qualquer uma das plantas, sem atraso, pois admitimos transferências de lotes de produção entre as plantas e estocagem de produção, ambas as operações sujeitas a custos. Esse problema, aqui chamado de PDLCLMP, portanto, visa definir um planejamento de produção de forma a minimizar os custos de preparação, produção, estoque e transporte entre plantas, respeitando os recursos disponíveis e atendendo a demanda previamente estabelecida em cada uma das plantas. Devido às limitações dos métodos atualmente propostos na literatura, para encontrar soluções para esse problema propomos matheurísticas para resolver o PDLCLMP. Três métodos de solução são apresentados: uma heurística Lagrangiana; uma heurística Lagrangiana híbrida com a meta-heurística path-relinking; e um método kernel search. Além dessas instâncias, outras de larga escala foram criadas e empregadas nos experimentos. De acordo com esses experimentos, tanto a heurística Lagrangiana híbrida quanto a sem path-relinking apresentaram um excelente desempenho quando comparadas com a melhor heurística da literatura. Já o método kernel search proposto, que tinha como objetivo manter a qualidade das soluções encontradas pelo CPLEX, porém em tempo computacional inferior, atingiu seu objetivo para as instâncias com pequenas dimensões.