Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-07-01Bitstream added on 2014-06-13T18:30:54Z : No. of bitstreams: 1 carretero_mm_me_sjrp.pdf: 795127 bytes, checksum: 64b07e80db6689945e91fc1c317deb3c (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Em alguns setores, o planejamento da produção envolve dois aspectos: o dimensionamento do tamanho dos lotes e a programação da produção (sequenciamento dos lotes). O primeiro problema consiste em determinar o tamanho dos lotes de produção de cada item a ser produzido em uma ou mais máquinas em cada período ao longo de um horizonte de planejamento finito. O segundo problema consiste em encontrar a ordem em que os lotes devem ser produzidos em um dado conjunto de máquinas. Estes dois aspectos do planejamento da produção podem ser tratados de forma independente: em um estágio é resolvido o problema de dimensionamento dos lotes e no outro, realizado antes ou depois, é resolvido o problema de seqüenciamento. No entanto, uma tendência recente na literatura são trabalhos que apresentam modelos matemáticos que capturam simultaneamente as relações entre os dois problemas. Na literatura pode-se encontrar modelos integrados que incluem restrições de eliminação de subrotas, propostas para o Problema do Caixeiro Viajante (PCV), para formular as restrições de sequenciamento. No entanto, alguns dos modelos propostos usam restrições de ordem polinomial que fornecem uma relaxação linear fraca. O objetivo desse trabalho é avaliar o uso de inequações válidas, propostas na literatura, para obtenção de formulações mais fortes para o problema integrado de dimensionamento e sequenciamento da produção. Resultados computacionais usando exemplares aleatórios e exemplares da literatura mostram que as reformulações propostas são eficientes para cenários em que o modelo original não é eficiente. / Often, the production planning involves the lot sizing and scheduling of items. The first problem is to determine the lot size of each item to be produced in one or more machines in each period over a finite planning horizon. The second problem is to find the order in which the items will be produced. These two aspects of the production planning can be treated independently: in one stage the lot sizing problem is solved, and in the other, that can be executed before or after, the scheduling problem is solved. A recent trend in the literature is to propose mathematical models that capture the relationships between these two problems. In the literature one can find integrated models that include subtour elimination constraints, proposed for the Traveling Salesman Problem, to formulate the scheduling decisions. However, in some of these models, constraints of polynomial order, that provides a weak linear relaxation, are used.The purpose of this study is to evaluate the use of valid inequalities proposed in the literature to obtain stronger formulations to the lot and scheduling problem. Computational results using random instances and instances from the literature show that the proposed formulations have a better performance in scenarios where the original model is not efficient.

Orientador: Maria do Socorro Nogueira Rangel / Banca: Alistair Clark / Banca: Silvio Alexandre de Araujo / Resumo: Em alguns setores, o planejamento da produção envolve dois aspectos: o dimensionamento do tamanho dos lotes e a programação da produção (sequenciamento dos lotes). O primeiro problema consiste em determinar o tamanho dos lotes de produção de cada item a ser produzido em uma ou mais máquinas em cada período ao longo de um horizonte de planejamento finito. O segundo problema consiste em encontrar a ordem em que os lotes devem ser produzidos em um dado conjunto de máquinas. Estes dois aspectos do planejamento da produção podem ser tratados de forma independente: em um estágio é resolvido o problema de dimensionamento dos lotes e no outro, realizado antes ou depois, é resolvido o problema de seqüenciamento. No entanto, uma tendência recente na literatura são trabalhos que apresentam modelos matemáticos que capturam simultaneamente as relações entre os dois problemas. Na literatura pode-se encontrar modelos integrados que incluem restrições de eliminação de subrotas, propostas para o Problema do Caixeiro Viajante (PCV), para formular as restrições de sequenciamento. No entanto, alguns dos modelos propostos usam restrições de ordem polinomial que fornecem uma relaxação linear fraca. O objetivo desse trabalho é avaliar o uso de inequações válidas, propostas na literatura, para obtenção de formulações mais fortes para o problema integrado de dimensionamento e sequenciamento da produção. Resultados computacionais usando exemplares aleatórios e exemplares da literatura mostram que as reformulações propostas são eficientes para cenários em que o modelo original não é eficiente. / Abstract: Often, the production planning involves the lot sizing and scheduling of items. The first problem is to determine the lot size of each item to be produced in one or more machines in each period over a finite planning horizon. The second problem is to find the order in which the items will be produced. These two aspects of the production planning can be treated independently: in one stage the lot sizing problem is solved, and in the other, that can be executed before or after, the scheduling problem is solved. A recent trend in the literature is to propose mathematical models that capture the relationships between these two problems. In the literature one can find integrated models that include subtour elimination constraints, proposed for the Traveling Salesman Problem, to formulate the scheduling decisions. However, in some of these models, constraints of polynomial order, that provides a weak linear relaxation, are used.The purpose of this study is to evaluate the use of valid inequalities proposed in the literature to obtain stronger formulations to the lot and scheduling problem. Computational results using random instances and instances from the literature show that the proposed formulations have a better performance in scenarios where the original model is not efficient. / Mestre

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.