A fundamental issue in warehouse operations is the storage location of the products it contains. Placing products intelligently within the system can allow for great reductions in order pick costs. This is essential because order picking is a major cost of warehouse operations. For example, a study by Drury conducted in the UK found that 63% of warehouse operating costs are due to order picking. When orders contain a single item, the COI rule of Heskett is an optimal storage policy. This is not true when orders contain multiple line items because no information is used about what products are ordered together. In this situation, products that are frequently ordered together should be stored together. This is the basis of the correlated storage assignment problem. Several previous researchers have considered how to form such clusters of products with an ultimate objective of minimizing travel time. In this dissertation, we focus on the alternate objective of minimizing multi-zone orders. We present a mathematical model and discuss properties of the problem. A Lagrangian relaxation solution approach is discussed. In addition, we both develop and adapt several heuristics from the literature to give upper bounds for the model. A cyclic exchange improvement method is also developed. This exponential size neighborhood can be efficiently searched in polynomial time. Even for poor initial solutions, this method finds solutions which outperform the best approaches from the literature. Different product sizes, stock splitting, and rewarehousing are problem features that our model can handle. The cyclic exchange algorithm is also modified to allow these operating modes. In particular, stock splitting is a difficult issue which most previous research in correlated storage ignores. All of our algorithms are implemented and tested on data from a functioning warehouse. For all data sets, the cyclic exchange algorithm outperforms COI, the standard industry approach, by an average of 15%.

This thesis consists of two parts: text and programming part. It is divided into seven chapters. Its main goal is to compare heuristics for dynamic traveling salesman problem in a few perspectives. The text part of this thesis theoretically describes heuristic methods and in the programming part are wake up to life via VBA in MS Excel. The results of computational experiments on these heuristic methods are presented in the last chapter. In the first part, the traveling salesman problem and its solution are being described. Characteristic of the modification in a form of dynamic traveling salesman problem follow. Next chapter presents the programming solution chosen heuristics. The final chapter presents experimental results obtain with programmed heuristics.

O setor industrial produtor de papel e celulose tem aumentado sua relevância comercial nas últimas décadas devido à demanda constantemente crescente. O aumento na competitividade do setor gerado pela economia globalizada e a dificuldade de desenvolvimento de bons planos de produção em ambientes produtivos cada vez mais complexos têm motivado a pesquisa por novas e efetivas ferramentas de auxílio à tomada de decisão. Considerando estas dificuldades, abordamos neste trabalho o problema de dimensionamento e sequenciamento de lotes com foco em empresas com processo integrado de produção de celulose e de papel. Trata-se de um problema de planejamento de médio a curto prazo, geralmente com maior enfoque no curto prazo por considerar o planejamento detalhado da produção em horizontes de planejamento que não superam 30 dias. No processo integrado de celulose e papel, foram consideradas as decisões de produção do digestor, evaporador, caldeira de recuperação e de múltiplas máquinas produtoras de papel, além do controle de estoque de produtos intermediários e finais. Modelos matemáticos da literatura foram modificados e estendidos para incorporar características adicionais do problema como, por exemplo, processos com múltiplas máquinas de papel. Além disso, foram desenvolvidas heurísticas construtivas, heurísticas de melhoria, abordagens de solução híbridas baseadas em algoritmos genéticos combinadas com ferramentas comerciais de solução exata, além de combinações entre os métodos. As abordagens desenvolvidas foram testadas computacionalmente e as melhores combinações de métodos foram definidas. De forma geral, os resultados dessas abordagens foram superiores aos obtidos por ferramentas de solução comerciais puras. Ademais, a variação proposta da heurística de melhoria fixe-e-otimize com mudanças na função objetivo se destacou com relação aos demais métodos, obtendo os melhores resultados, independentemente da qualidade da solução inicial utilizada. As principais contribuições desta tese são a apresentação de modelos matemáticos para representar apropriadamente o problema estudado, e o desenvolvimento de métodos de solução efetivos para resolver o problema. / The pulp and paper industry has been increasing the commercial importance in recent decades due to the constant growing demand. The increasing competitiveness of this sector generated by the globalized economy and the difficulty to develop good production plans in complex production environments have motivated the search for new and effective decision support systems. Given these difficulties, in this thesis we address the lot sizing and scheduling problem focused on integrated pulp and paper mills. This is a problem of medium to short term planning, generally more focused on the short term as it covers detailed production schedules in planning horizons which do not exceed 30 days. In these integrated pulp and paper process the production decisions of digester, evaporator, recovery boiler and multiple paper machines are considered, apart from the inventory control of intermediate and final products. Mathematical models known in the literature were modified and extended to incorporate additional features of the problem, such as processes with multiple paper machines. In addition, constructive and improvement heuristics, and hybrid methods based on genetic algorithms combined with a commercial solver were developed, as well as combinations of these solution approaches. The methods developed were computationally tested and the best combinations of methods were defined. Overall, the results of these methods were superior to the solutions obtained by pure commercial solvers. Moreover, the alternative variation proposed of the improvement heuristic fix-and-optimize with exchanges in the objective function surpassed the other methods, obtaining the best results, regardless of the quality of the initial solution used. The main contribution of this thesis are the presentation of mathematical models that appropriately represents the problem under study, and the development of effective solution methods to deal with the problem.

O setor industrial produtor de papel e celulose tem aumentado sua relevância comercial nas últimas décadas devido à demanda constantemente crescente. O aumento na competitividade do setor gerado pela economia globalizada e a dificuldade de desenvolvimento de bons planos de produção em ambientes produtivos cada vez mais complexos têm motivado a pesquisa por novas e efetivas ferramentas de auxílio à tomada de decisão. Considerando estas dificuldades, abordamos neste trabalho o problema de dimensionamento e sequenciamento de lotes com foco em empresas com processo integrado de produção de celulose e de papel. Trata-se de um problema de planejamento de médio a curto prazo, geralmente com maior enfoque no curto prazo por considerar o planejamento detalhado da produção em horizontes de planejamento que não superam 30 dias. No processo integrado de celulose e papel, foram consideradas as decisões de produção do digestor, evaporador, caldeira de recuperação e de múltiplas máquinas produtoras de papel, além do controle de estoque de produtos intermediários e finais. Modelos matemáticos da literatura foram modificados e estendidos para incorporar características adicionais do problema como, por exemplo, processos com múltiplas máquinas de papel. Além disso, foram desenvolvidas heurísticas construtivas, heurísticas de melhoria, abordagens de solução híbridas baseadas em algoritmos genéticos combinadas com ferramentas comerciais de solução exata, além de combinações entre os métodos. As abordagens desenvolvidas foram testadas computacionalmente e as melhores combinações de métodos foram definidas. De forma geral, os resultados dessas abordagens foram superiores aos obtidos por ferramentas de solução comerciais puras. Ademais, a variação proposta da heurística de melhoria fixe-e-otimize com mudanças na função objetivo se destacou com relação aos demais métodos, obtendo os melhores resultados, independentemente da qualidade da solução inicial utilizada. As principais contribuições desta tese são a apresentação de modelos matemáticos para representar apropriadamente o problema estudado, e o desenvolvimento de métodos de solução efetivos para resolver o problema. / The pulp and paper industry has been increasing the commercial importance in recent decades due to the constant growing demand. The increasing competitiveness of this sector generated by the globalized economy and the difficulty to develop good production plans in complex production environments have motivated the search for new and effective decision support systems. Given these difficulties, in this thesis we address the lot sizing and scheduling problem focused on integrated pulp and paper mills. This is a problem of medium to short term planning, generally more focused on the short term as it covers detailed production schedules in planning horizons which do not exceed 30 days. In these integrated pulp and paper process the production decisions of digester, evaporator, recovery boiler and multiple paper machines are considered, apart from the inventory control of intermediate and final products. Mathematical models known in the literature were modified and extended to incorporate additional features of the problem, such as processes with multiple paper machines. In addition, constructive and improvement heuristics, and hybrid methods based on genetic algorithms combined with a commercial solver were developed, as well as combinations of these solution approaches. The methods developed were computationally tested and the best combinations of methods were defined. Overall, the results of these methods were superior to the solutions obtained by pure commercial solvers. Moreover, the alternative variation proposed of the improvement heuristic fix-and-optimize with exchanges in the objective function surpassed the other methods, obtaining the best results, regardless of the quality of the initial solution used. The main contribution of this thesis are the presentation of mathematical models that appropriately represents the problem under study, and the development of effective solution methods to deal with the problem.