Reformulações e relaxação Lagrangiana para o problema de dimensionamento de lotes com várias plantas

Pós-graduação em Matemática - IBILCE

Os problemas de dimensionamento de lotes consistem em determinar, em um horizonte de tempo finito, a quantidade de itens a serem produzidos para os quais há uma demanda a ser atendida e utiliza-se custos de produção, estoque e preparo. Este trabalho aborda o problema de dimensionamento de lotes em um ambiente constitíudo de várias plantas. Cada item pode ser produzido em qualquer planta é possível atender a demanda de uma determinada planta com produção proveniente de uma (ou várias outras) planta(s); para tanto, incorre-se um custo de transferência. Neste trabalho são propostas reformulações para o problema de dimensionamento de lotes com várias plantas, baseadas no problema do caminho mínimo (Shortest Path- SP) e no problema de localização de facilidades (Facility Location- FL). Alguns resultados computacionais são apresentados comparando a formulação original às reformulações apresentadas. Além disso, propôs-se, para uma das reformulações, um método de busca de limitantes inferiores, no qual a relaxação Lagrangiana é aplicada às restrições de demanda e o método do subgradiente é utilizado para atualizar os multiplicadores. A fim de verificar a qualidade dos limitantes obtidos, são apresentados experimentos computacionais com dados da literatura e estes são comparados aos obtidos com o pacote comercial CPLEX

The lot sizing problem consists of determining, in a finite time horizon, the quantity of items to be produced for which there are demands to be met and involve costs of produc-tion, inventory and setup. This work deals with the multi-plant lot sizing problem. Each item can be produced in any plant and the demand of a particular plant can be met using the production from another (or several other) plant(s); to do so, there is a transfer cost. We present reformulations for the classical problem, based on the shortest path problem (SP) and the facility location problem (FL). Some computational results are shown com-paring all formulations presented. Moreover, we propose, for one of the reformulations, a solution method to find lower bounds, where, the Lagrangian relaxation is applied to the demand constraints and the subgradient method is used to update the multipliers. Aiming to verify the quality of the lower bounds, we present computational experiments with data from literature and compare them to those obtained with commercial package CPLEX