Made available in DSpace on 2016-06-02T19:50:14Z (GMT). No. of bitstreams: 1 4071.pdf: 1584989 bytes, checksum: c5d431c41837e054ef8d40a5d71b1e21 (MD5) Previous issue date: 2011-12-09 / Universidade Federal de Minas Gerais / In this research, we study lot sizing problems with decisions on product distribution and, also, problems that integrate lot sizing decisions and product packing in the vehicles (bins). In general, these problems involve a trade-off among production costs, holding costs and distribution costs. The lot sizing problems consider limitations in the production capacity and demand delivery deadline. The distribution decisions are related to the product loading into the unit load device (pallets, containers or trucks). The packing problems may involve one, two or three dimensions relevant to the product loading. The problems are modeled by mathematical programming and solved by the branch-and-cut method of an optimization package, and then, the performance and the results obtained are analyzed. Furthermore, heuristic methods are specifically developed in order to provide an approximate solution for these problems. The heuristic methods are built according to the lagrangian relaxation and ant colony optimization. All the methods are tested and evaluated, regarding the solutions found by the optimization package for the proposed models. / Neste trabalho, são estudados problemas de dimensionamento de lotes de produção com decisões de distribuição dos produtos e, também, problemas que integram decisões de dimensionamento de lotes e empacotamento dos produtos em veículos (bins). Em geral, estes problemas envolvem um balanceamento (trade-off) entre os custos de produção, os custos de estocagem e os custos de distribuição. As decisões de dimensionamento de lotes consideram limitações das capacidades de produção e prazos de entrega da demanda. As decisões de distribuição estão relacionadas ao carregamento e transporte dos produtos dentro dos dispositivos de unitização de carga (paletes, contêineres, carrocerias de caminhão, etc.). O carregamento dos produtos pode envolver uma, duas ou três dimensões relevantes para o empacotamento ou arranjo dos produtos dentro dos veículos. Os problemas estudados são modelados via programação matemática e resolvidos pelo método branch-and-cut de um pacote de otimização, e os desempenhos e resultados obtidos são analisados. Além disso, também são desenvolvidos métodos heurísticos específicos para a resolução aproximada de alguns destes problemas. Os métodos heurísticos são construídos tendo como base a relaxação lagrangiana e a otimização baseada em colônias de formigas. Todos os métodos são testados e avaliados, levando em conta as soluções encontradas pelo pacote de otimização com os modelos propostos.

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms