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

This dissertation is devoted to the modeling, analysis and development of solution approaches for some optimization-related problems encountered in industrial and manufacturing settings. We begin by introducing a special type of traveling salesman problem called "High Multiplicity Asymmetric Traveling Salesman Problem" (HMATSP). We propose a new formulation for this problem, which embraces a flow-based subtour elimination structure, and establish its validity for this problem. The model is, then, incorporated as a substructure in our formulation for a lot-sizing problem involving parallel machines and sequence-dependent setup costs, also known as the "Chesapeake Problem". Computational results are presented to demonstrate the efficacy of our modeling approach for both the generic HMATSP and its application within the context of the Chesapeake Problem. Next, we investigate an integrated lot-sizing and scheduling problem that is encountered in the primary manufacturing facility of pharmaceutical manufacturing. This problem entails determination of production lot sizes of multiple products and sequence in which to process the products on machines, which can process lots (batches) of a fixed size (due to limited capacity of containers) in the presence of sequence-dependent setup times/costs. We approach this problem via a two-stage optimization procedure. The lot-sizing decision is considered at stage 1 followed by the sequencing of production lots at stage 2. Our aim for the stage 1 problem is to allocate batches of products to time-periods in order to minimize the sum of the inventory and backordering costs subject to the available capacity in each period. The consideration of batches of final products, in addition to those for intermediate products, which comprise a final product, further complicates the lot-sizing problem. The objective for the stage 2 problem is to minimize sequence-dependent setup costs. We present a novel unifying model and a column generation-based optimization approach for this class of lot-sizing and sequencing problems. Computational experience is first provided by using randomly generated data sets to test the performances of several variants of our proposed approach. The efficacy of the best of these variants is further demonstrated by applying it to the real-life data collected with the collaboration of a pharmaceutical manufacturing company. Then, we address a single-lot, lot streaming problem for a two-stage assembly system. This assembly system is different from the traditional flow shop configuration. It consists of m parallel subassembly machines at stage 1, each of which is devoted to the production of a component. A single assembly machine at stage 2, then, assembles products after components (one each from the subassembly machines at the first stage) have been completed. Lot-detached setups are encountered on the machines at the first and second stages. Given a fixed number of transfer batches (or sublots) from each of the subassembly machines at stage 1 to the assembly machine at stage 2, our problem is to find sublot sizes so as to minimize the makespan. We develop optimality conditions to determine sublot sizes for the general problem, and present polynomial-time algorithms to determine optimal sublot sizes for the assembly system with two and three subassembly machines at stage 1. Finally, we extend the above single-lot, lot streaming problem for the two-stage assembly system to multiple lots, but still, for the objective of minimizing the makespan. Due to the presence of multiple lots, we need to address the issue of the sequencing of the lots along with lot-splitting, a fact which adds complexity to the problem. Some results derived for the single-lot version of this problem have successfully been generalized for this case. We develop a branch-and-bound-based methodology for this problem. It relies on effective lower bounds and dominance properties, which are also derived. Finally, we present results of computational experimentation to demonstrate the effectiveness of our branch-and-bound-based methodology. Because of the tightness of our upper and lower bounds, a vast majority of the problems can be solved to optimality at root node itself, while for others, the average gap between the upper and lower bounds computed at node zero is within 0.0001%. For a majority of these problems, our dominance properties, then, effectively truncate the branch-and-bound tree, and obtain optimal solution within 500 seconds. / Ph. D.