Esta tese de doutorado apresenta modelos matemáticos de problemas de dimensionamento de lotes para planejamento da produção na indústria de embalagens de vidro, que são essenciais em qualquer cadeia de produção, pois são responsáveis por proteger e conservar os produtos (alimentos e bebidas). Na literatura científica são raros os trabalhos que abordam estudos sobre problemas combinados de dimensionamento de lotes e planejamentos da produção em indústrias de embalagens de vidro. Com a finalidade de preencher esta lacuna, a presente tese tem por objetivo propor modelos inéditos e métodos de resolução aplicáveis em problemas nas indústrias de embalagens de vidro. Dessa forma, propõem-se dois modelos baseados em problemas reais para a construção ou reforma de forno(s), denominados de Problema de Instalação de um Novo Forno e Problema de Instalação de Múltiplos Fornos, que verificam a capacidade de fusão e as configurações das máquinas instaladas. Outros dois modelos são desenvolvidos a partir de estudos de casos referentes ao planejamento e ao controle da produção de ampolas de garrafas térmicas. No primeiro estudo, considera-se o máximo da produção líquida e no segundo, minimiza-se os set-up, sendo que em ambos os casos a realidade de uma fábrica é refletida. A complexidade desses modelos contribui para o uso de métodos heurísticos e meta-heurísticos como técnicas para resolução dos mesmos. No entanto, considera-se também a avaliação da associação desses métodos ao uso de programação matemática. Para isso, modelos matemáticos são propostos dentro do contexto das indústrias consideradas. Desta forma, uma heurística de Filtro Guloso e as meta-heurísticas como o Algoritmo Genético Simples, o Algoritmo Genético Multi-Populacional e o Algoritmo Genético Modificado são utilizados na determinação das variáveis inteiras presentes nos modelos matemáticos. Além disso, utiliza-se um método exato, por meio da ferramenta CPLEX, para determinar as variáveis contínuas. Os estudos são conduzidos a partir de dados fornecidos por indústrias localizadas no Brasil e em Portugal. Portanto, os resultados colaboram com o estado da arte nessa área de pesquisa e com o processo de fabricação industrial de embalagens de vidro. / This doctoral dissertation presents mathematical models of lot-sizing problems for production planning in the glass containers industry, which are essential in any production chain, as they are responsible for protecting and conserving products (food and beverages). In the scientific literature, studies addressing combined problems of batch sizing and production planning in glass containers industries are rare. In order to fill this gap, this thesis aims to propose novel models and resolution methods applicable to problems in the glass containers industry. Thus, we propose two models based on real problems for the construction or remodelling of the furnace (s), called New Furnace Installation Problem and Multiple Furnace Installation Problem, which verify fusibility and configurations of installed machines. We developed two other models from case studies regarding the planning and control of the production of thermos vials. In the first study, we consider the maximum net production; in the second, we minimize the set-up. Both cases reflect the reality of a factory. The complexity of these models contributes to the use of heuristic and metaheuristic methods as techniques for their resolution. However, we also consider the evaluation of the association of these methods with the use of mathematical programming. For this, we propose mathematical models within the context of the considered industries. Thus, a Greedy Filter heuristic and metaheuristics such as the Simple Genetic Algorithm, the Multi-Population Genetic Algorithm and the Modified Genetic Algorithm are used to determine the integer variables present in mathematical models. Besides, we use an exact method from CPLEX tool to determine continuous variables. The studies are conducted from data provided by industries located in Brazil and Portugal. Therefore, the results collaborate with state of the art in this research area and with the industrial glass containers manufacturing process.

Decision-tree induction is one of the most employed methods to extract knowledge from data. There are several distinct strategies for inducing decision trees from data, each one presenting advantages and disadvantages according to its corresponding inductive bias. These strategies have been continuously improved by researchers over the last 40 years. This thesis, following recent breakthroughs in the automatic design of machine learning algorithms, proposes to automatically generate decision-tree induction algorithms. Our proposed approach, namely HEAD-DT, is based on the evolutionary algorithms paradigm, which improves solutions based on metaphors of biological processes. HEAD-DT works over several manually-designed decision-tree components and combines the most suitable components for the task at hand. It can operate according to two different frameworks: i) evolving algorithms tailored to one single data set (specific framework); and ii) evolving algorithms from multiple data sets (general framework). The specific framework aims at generating one decision-tree algorithm per data set, so the resulting algorithm does not need to generalise beyond its target data set. The general framework has a more ambitious goal, which is to generate a single decision-tree algorithm capable of being effectively applied to several data sets. The specific framework is tested over 20 UCI data sets, and results show that HEAD-DTs specific algorithms outperform algorithms like CART and C4.5 with statistical significance. The general framework, in turn, is executed under two different scenarios: i) designing a domain-specific algorithm; and ii) designing a robust domain-free algorithm. The first scenario is tested over 35 microarray gene expression data sets, and results show that HEAD-DTs algorithms consistently outperform C4.5 and CART in different experimental configurations. The second scenario is tested over 67 UCI data sets, and HEAD-DTs algorithms were shown to be competitive with C4.5 and CART. Nevertheless, we show that HEAD-DT is prone to a special case of overfitting when it is executed under the second scenario of the general framework, and we point to possible alternatives for solving this problem. Finally, we perform an extensive experiment for evaluating the best single-objective fitness function for HEAD-DT, combining 5 classification performance measures with three aggregation schemes. We evaluate the 15 fitness functions in 67 UCI data sets, and the best of them are employed to generate algorithms tailored to balanced and imbalanced data. Results show that the automatically-designed algorithms outperform CART and C4.5 with statistical significance, indicating that HEAD-DT is also capable of generating custom algorithms for data with a particular kind of statistical profile / Árvores de decisão são amplamente utilizadas como estratégia para extração de conhecimento de dados. Existem muitas estratégias diferentes para indução de árvores de decisão, cada qual com suas vantagens e desvantagens tendo em vista seu bias indutivo. Tais estratégias têm sido continuamente melhoradas por pesquisadores nos últimos 40 anos. Esta tese, em sintonia com recentes descobertas no campo de projeto automático de algoritmos de aprendizado de máquina, propõe a geração automática de algoritmos de indução de árvores de decisão. A abordagem proposta, chamada de HEAD-DT, é baseada no paradigma de algoritmos evolutivos. HEAD-DT evolui componentes de árvores de decisão que foram manualmente codificados e os combina da forma mais adequada ao problema em questão. HEAD-DT funciona conforme dois diferentes frameworks: i) evolução de algoritmos customizados para uma única base de dados (framework específico); e ii) evolução de algoritmos a partir de múltiplas bases (framework geral). O framework específico tem por objetivo gerar um algoritmo por base de dados, de forma que o algoritmo projetado não necessite de poder de generalização que vá além da base alvo. O framework geral tem um objetivo mais ambicioso: gerar um único algoritmo capaz de ser efetivamente executado em várias bases de dados. O framework específico é testado em 20 bases públicas da UCI, e os resultados mostram que os algoritmos específicos gerados por HEAD-DT apresentam desempenho preditivo significativamente melhor do que algoritmos como CART e C4.5. O framework geral é executado em dois cenários diferentes: i) projeto de algoritmo específico a um domínio de aplicação; e ii) projeto de um algoritmo livre-de-domínio, robusto a bases distintas. O primeiro cenário é testado em 35 bases de expressão gênica, e os resultados mostram que o algoritmo gerado por HEAD-DT consistentemente supera CART e C4.5 em diferentes configurações experimentais. O segundo cenário é testado em 67 bases de dados da UCI, e os resultados mostram que o algoritmo gerado por HEAD-DT é competitivo com CART e C4.5. No entanto, é mostrado que HEAD-DT é vulnerável a um caso particular de overfitting quando executado sobre o segundo cenário do framework geral, e indica-se assim possíveis soluções para tal problema. Por fim, é realizado uma análise detalhada para avaliação de diferentes funções de fitness de HEAD-DT, onde 5 medidas de desempenho são combinadas com três esquemas de agregação. As 15 versões são avaliadas em 67 bases da UCI e as melhores versões são utilizadas para geração de algoritmos customizados para bases balanceadas e desbalanceadas. Os resultados mostram que os algoritmos gerados por HEAD-DT apresentam desempenho preditivo significativamente melhor que CART e C4.5, em uma clara indicação que HEAD-DT também é capaz de gerar algoritmos customizados para certo perfil estatístico dos dados de classificação

Neste trabalho foi estudado um problema de dimensionamento de lotes em uma indústria química brasileira, cujo objetivo era determinar o tamanho dos lotes dos produtos para atender às demandas, minimizando os custos produtivos. Os itens podem ser produzidos em máquinas paralelas distintas, através de diferentes processos, e devem ser armazenados em taques cativos, exclusivos a um produto, ou multipropósitos, compartilhado entre produtos, desde que não simultaneamente. Foram propostos dois modelos matemáticos de programação inteira mista para representar o problema, o primeiro apresentava uma função objetivo compreendendo o preço das matérias-primas consumidas nas reações, os gastos com a estocagem de produtos e o custo de descarte de produtos quando os tanques de armazenamento não tiverem capacidade suficiente para armazená-los, já o segundo estendendo este modelo para considerar custos de preparação de máquina. Experimentos computacionais com os modelos propostos, utilizando instâncias geradas a partir dos dados fornecidos pela empresa, mostraram que o software de otimização empregado foi capaz de resolver poucas instâncias, após uma hora de processamento. Portanto, foram propostas heurísticas construtivas do tipo LP-and-fix e relax-and-fix, além de heurísticas de melhoria do tipo fix-and-optimize. Após serem realizados testes com essas heurísticas, constatou-se que algumas proporcionaram a obtenção de soluções factíveis de boa qualidade, quando comparadas às obtidas pelo software, sendo ainda capazes de resolver um maior número de instâncias / In this dissertation the lot sizing problem in a chemical Brazilian industry was studied, with the goal to determine the products lot size to satisfy the demands, minimizing the production costs. The items can be produced on distinct parallel machines through different processes and then must be stored in exclusive tanks, used by only one product, or multipurpose tanks, when more than one product can use the tank, but not simultaneously. Two models were proposed to represent the problem, the first one aiming to minimize the price of raw material consumed in the reactions, storage product spending and the cost of discarting products when the storage tanks do not have enough capacity to store them, and the second one considering setup cost either. Computational experiments using the proposed models, with instances were generated from the data provided by the company, showed that the used optimization software was able to solve only few instances after processing for one hour. In this dissertation we propose constructives heuristics such LP-and-fix and relax-and-fix, and improving heuristics like fix-and-optimize. After performing the tests with those heuristics, it was found that some of them provided feasible solutions with good quality, when compared to the ones obtained by the software, and they were also able to solve a larger number of instances

Neste trabalho desenvolvemos o estudo da álgebra linear, secções cônicas e aplicações. Apresentamos os conceitos mais importantes da álgebra linear, estudando os espaços vetorias, subespaços vetoriais, matriz de mudança de base, transformações lineares e produto interno. O principal resultado do trabalho é o teorema espectral que fornece ferramentas para se estudar as secções cônicas não elementares, ou seja, aquelas nas quais uma parábola, elipse ou hipérbole são apresentadas com seus eixos não paralelos aos eixos coordenados do plano cartesiano. Uma vez de posse deste teorema é mostrado um processo prático no qual transformamos uma equação ax2 +bxy +cy2 +dx +ey + g = 0 na equação k1 (x\')2 + k2 (y\')2 + (dx1 + ey1) x\' + (dx2 + ey2) y\' + g = 0 sem o termo misto xy, onde após a eliminação deste, podemos deduzir a equação da cônica identificando assim esta curva. Apresentamos exemplos de cônicas com eixos paralelos e não paralelos aos coordenados do plano cartesiano e utilizamos o software geogebra para visualização. Também discutimos algumas aplicações das cônicas como trajetória de corpos celestes (planeta Terra e um cometa), princípio de reflexão da parábola mostrando o porquê das antenas e dos captadores de ondas sonoras serem parabólicos. Demonstramos um teorema que denominei de identificador de uma curva cônica pois com ele é possível classificar a cônica sem realizar o processo prático, apenas para isso identificamos através da equação ax2 +bxy + cy2 +dx + ey +g = 0, quais os valores de a;b e c e feito isto calculamos o discriminante b2 - 4ac, analisamos os sinais e a nulidade, ou seja, se é maior que zero, menor que zero ou igual a zero, assim é possível classificar a cônica. / The paper develops the study of linear algebra, conic sections and applications. I present the most important concepts of linear algebra, studying vector spaces, vector subspaces, base change matrix, linear transformations, internal product. The main result of the work is the spectral theorem, which provides tools to study the non-elementary conic sections, that is, those in which a parabola, ellipse or hyperbola are presented with their axes not parallel to the cartesian planes coordinate axes. Using this theorem we show a practical process in which we transform an equation ax2 +bxy + cy2 +dx +ey +g = 0 into the equation k1 (x\')2 +k2 (y\')2 + (dx1 +ey1) x\' (dx2 + ey2) y\' +g = 0 without the mixed term xy, where after its elimination we can deduce the conic equation thus identifying the curve we are looking for. I present examples of conic with parallel and non-parallel axes to the coordinates of the Cartesian plane and use the geogebra software for visualization. I discuss some applications of the conic as a trajectory of celestial bodies (planet Earth and a comet), principle of reflection of parabola showing why the antennas and sound wave pickups are parabolics. I demonstrate a theorem that I named the identifier of a conic curve, with it it is possible to classify the conic without realizing the practical process only for this. I identify through the equation ax2 +bxy + cy2 +dx + ey + g = 0, what are the values of a;b, and c and, with this done, I compute the discriminant b2 - 4ac and analyze the signs and the nullity, that is, if it is greater than zero, less than zero or equal to zero, therefore is possible to classify the conic.

O Problema da Mochila Compartimentada é uma extensão do Problema da Mochila, em que os itens solicitados são divididos em classes, de modo que a mochila deve ser subdividida em compartimentos, os quais têm capacidades limitadas e são carregados com itens da mesma classe. Além disso, a construção de um compartimento tem um custo fixo e ocasiona uma perda no espaço da mochila. O objetivo consiste em maximizar a soma dos valores dos itens, descontado o custo fixo de inclusão de compartimentos. Neste trabalho, são abordados dois métodos de solução. A primeira abordagem é uma heurística, que consiste na combinação de duas heurísticas da literatura. A segunda abordagem é o método Geração de Colunas, que além de fornecer um novo limitante superior para o Problema da Mochila Compartimentada, ao final do método o problema mestre foi resolvido com as variáveis definidas como inteiras, obtendo uma solução factível. Em ambos os métodos, o modelo não-linear é decomposto em dois modelos lineares, no qual, um gera compartimentos e o outro os seleciona. Os resultados obtidos com as duas abordagens foram comparados com um limitante superior e se mostraram bastante satisfatórios / The Compartmentalized Knapsack Problem is an extension of the classical Knapsack Problem, where the ordered items are partitioned into classes, in such way that the knapsack must be divided into compartments, each one having limited capacity. In addition, the building of a compartment has a fixed cost and involves a loss of the overall capacity. The objective is to maximize the sum of the items utility value, minus the fixed costs of the compartments. This dissertation presents two solving methods. The first approach is a heuristic method, which is a combination of two heuristics from the literature. The second approach is a Column Generation method, that apart from it gives a new upper bound to the Compartmentalized Knapsack Problem, in the end of the method the master problem was solved with the variables defined as integer, that supplies a feasible solution. In both methods, the mathematical non linear model is decomposed into two linear models, one generates the compartments, and the other selects them to compose the knapsack. The results obtained with these two approaches were compared with an upper bound and they showed very efficient

O presente trabalho aborda o sistema logístico usualmente denominado Vendor Managed Inventory (VMI), no qual o fornecedor controla e coordena as decisões de reabastecimento, sendo responsável por manter os estoques de seus clientes dentro de limites fixados de antemão. O modelo proposto incorpora ainda as decisões relativas à produção e manutenção de estoque por parte do fornecedor, além da utilização de frota heterogênea na distribuição, e busca a minimização dos custos totais do sistema. Quatro heurísticas de duas etapas são propostas para a resolução do problema abordado. A primeira etapa, comum a todas as heurísticas, baseia-se em uma heurística recentemente publicada na literatura e fornece uma solução inicial viável, utilizada como ponto de partida para a etapa de melhoria subsequente, na qual é utilizada a metaheurística busca tabu ou busca em vizinhança variável. As heurísticas propostas foram avaliadas em um conjunto de teste, sendo obtidos resultados melhores que os reportados na literatura em todas as instâncias testadas. Dentre as estratégias de solução avaliadas, destaca-se a heurística baseada em busca tabu com diversificação, que demonstrou ser superior às demais heurísticas propostas. Os resultados obtidos indicam ainda que, no caso da frota disponível ser heterogênea, é vantajosa a utilização de uma adaptação do procedimento de obtenção da solução inicial, como forma de privilegiar a utilização de veículos de maior eficiência. / This thesis deals with the logistic system usually called Vendor Managed Inventory (VMI). In this system the supplier controls and coordinates the supply decisions and is responsible for keeping the inventory of each of his clients within predetermined minimum and maximum levels. Heterogeneous fleet and production/stocking decisions at the supplier are considered as well, and the proposed model seeks to minimize the total system cost. Four two-stage heuristics are proposed for this problem. The first stage consists in an adaptation of a heuristic found in the bibliography, which provides an initial viable solution that will be improved in the second stage by means of the metaheuristics tabu search or variable neighborhood search. The proposed heuristics were tested on a set of benchmark instances with improvements found on the best known results in all of the tested instances. The obtained results indicate that the tabu search based heuristic with diversification strategy is clearly superior to the other proposed heuristics and that a better fleet utilization can be obtained in the case of heterogeneous fleet by a simple improvement in the first stage, that favors the selection of more efficient vehicles.

Essa tese foi desenvolvida com vistas a responder ao seguinte problema de pesquisa:as heurísticas e os vieses influenciam o processo decisório dos indivíduos quando confrontados com demonstrações financeiras e contábeis publicadas pelas empresas? Baseando-se na Prospect Theory de Kahneman e Tversky, buscou-se verificar como as heurísticas da ancoragem, representatividade e disponibilidade geravam vieses e influenciavam o modo como os usuários tomam suas decisões utilizando informações de cunho contábil e financeiro. Para tanto, foram submetidos questionários contendo situações de decisão junto aos estudantes de graduação da Faculdade de Economia, Administração e Contabilidade da Universidade de São Paulo e aos analistas profissionais de uma grande instituição financeira brasileira. 369 estudantes e 55 analistas responderam o questionário proposto. Para evitar com que os resultados pudessem não ser confiáveis, nenhum dos respondentes sabiam que o questionário buscava identificar vieses no processo de tomada de decisão. Para os colaboradores, foi exposto que a pesquisa versava sobre o processo de tomada de decisão com base na divulgação de informações contábeis e financeiras, sem fazer qualquer menção ao estudo das finanças comportamentais ou vieses. Os resultados obtidos divergiram quando foram comparados os dois públicos estudados nessa tese: analistas de mercado de capitais e estudantes de uma das melhores faculdades de negócio do Brasil. Os resultados sugeriram que o uso da heurística da ancoragem não se mostrou significativa nem para os analistas e nem para os estudantes. Entretanto, o uso da heurística da disponibilidade se mostrou estatisticamente significativa, assim como a presença da noção de correlação ilusória e o efeito isolamento. Por sua vez, o efeito reflexão e a não observação da regressão à média foram percebidos somente na amostra composta pelos analistas profissionais da instituição financeira. Finalmente, o uso da heurística da representatividade só teve efeito estatístico na presença dos alunos. / This thesis has been developed in order to answer the following research problem: the heuristics and biases influence the decision-making process of individuals when faced with financial and accounting statements published by the companies? Based on the Prospect Theory of Kahneman and Tversky, this research sought to determine how the heuristics of anchoring and adjustment, representativeness and availability generated biases and influenced how users make decisions using accounting and financial nature information. To this end, questionnaires containing decision situations were submitted to undergraduate students of the School of Economics, Business and Accounting of the University of São Paulo and the professional analysts of a large Brazilian financial institution. 369 students and 55 analysts answered the proposed questionnaire. To avoid that the results could not be trusted, none of the respondents knew that the questionnaire sought to identify biases in the decision-making process. It was explained that the survey questionnaire was about the decision-making process based on the disclosure of accounting and financial information, without making any mention of the study of behavioral biases. The results diverged when both public studied were compared in this thesis: capital market analysts and students of one of the best business schools in Brazil. The results suggested that the use of the anchoring and adjustment heuristic was not significant neither for the analysts and neither for the students. However, the use of the availability heuristic was statistically significant, as the presence of the concept of illusory correlation and the isolation effect. In turn, the reflection effect and no observation of regression to the mean were perceived only in the sample of the professional analysts of the financial institution. Finally, the use of the representativeness heuristic only had statistical effect in the student\'s sample.

O problema de dimensionamento de lotes determina um plano de produção que apoia às tomadas de decisões, a médio prazo, em meios industriais. Este plano de produção indica as quantidades de cada item que devem ser produzidas em cada período do horizonte de planejamento, de acordo com um objetivo dado e satisfazendo a demanda dos clientes. Diversos métodos de solução foram propostas na literatura, considerando a dificuldade de solução de algumas classes de problemas e a necessidade de métodos que gerem soluções de alta qualidade em um tempo computacional adequado. Neste trabalho, abordamos heurísticas baseadas na formulação matemática (LP-and-fix, relax-and-fix e fix-and-optimize), uma metaheurística (algoritmo de abelhas) e dois métodos híbridos, utilizados na solução de dois problemas distintos de dimensionamento de lotes multiestá- gio com limitação de capacidade. Consideramos também, a utilização de três formulações da literatura, para verificar a influência de cada uma sobre as abordagens de solução verificadas. Os resultados computacionais demonstraram que os métodos baseados na formulação matemática do problema se mostraram eficientes, mas limitados normalmente a ótimos locais, enquanto os métodos híbridos puderam superar estes ótimos locais, utilizando conceitos da metaheurística algoritmo de abelhas para isto. Além disso, pudemos verificar a influência de uma formulação \"forte\" sobre as soluções geradas pelas abordagens de solução, demonstrando que métodos baseados em relaxação linear conseguem obter maiores vantagens deste tipo de formulação, mas outras abordagens podem ou não obter estas vantagens, dependendo do problema abordado / The lot-sizing problem determines a production plan, which supports the decision making, in the medium term, at the industrial environment. This production plan indicates the amounts of each item to be produced in each period of the planning horizon, according to a given objective and satisfying customer\'s demand. Diverse solution methods have been proposed in the literature, considering the difficulty of solving some problem classes and the need of methods to generate solutions quickly. In this work, we develop matheuristics (LP-and-fix, relax-and-fix and fix-and-optimize), one metaheuristic (bees algorithm) and two hybrid methods, used to solve two different multilevel capacitated lot-sizing problems. We also consider the use of three different formulations of the literature to verify the influence of each one on the solutions approaches. The computational results show that the matheuristics proved to be efficient, but usually limited to local optima, while the hybrid methods could escape from these local optima, using concepts of bees algorithm to do this. Additionally, we test the effect of a tight formulation on the solutions approaches, demonstrating that LP-based heuristics can obtain further advantages from this type of formulation, but other approaches can take these advantages, depending on the problem addressed

The two-dimensional irregular cutting and packing problems (aka nesting problems) have been studied over the past six decades and consist in cutting (packing) convex and non-convex small pieces from (in) large boards without overlapping. There are several variants of this problem that are defined according to the board shapes and the objective of each problem. There are a number of heuristics proposed in the literature to solve irregular cutting and packing problems, but only few mixed-integer programming models. Specifically, these models were developed for the irregular strip packing problem, that consists in packing pieces into a single board with fixed width and length to be minimized. For the other problem variants, there is no exact methods presented in the literature. The main difficulty in solving irregular cutting and packing problems is how to handle with the geometric constraints. These constraints depend on the type of placement of the pieces on the board that can be continuous or discrete. In this thesis, we present two mixed-integer programming models for the irregular strip packing problem in which the pieces can be continuously placed on the board. These models do not demand complex structures to be built. We also present a new dot data structure to store the information on the placement of the pieces and overlapping positions bringing flexibility and efficiency to discrete approaches. Using this structure, a matheuristic is proposed, combining the advantages of the models with discrete and continuous placement positions for the pieces on the board. Furthermore, constraint programming models for several variants of irregular cutting and packing problems are exploited. For some variants, these models are the first modelling representation. A new global constraint is developed to eliminate the overlap among pieces. Computational experiments were conducted to evaluate the developed approaches. / Os problemas de corte e empacotamento de peças irregulares bidimensionais vêm sendo estudados há décadas e consistem em cortar (empacotar) peças menores, convexas e não convexas, a partir de (em) placas maiores de forma a não se sobreporem. Existem diversas variantes deste problema, definidas de acordo com o formato da placa e objetivo de cada problema. Na literatura, muitas heurísticas foram propostas para a resolução dos problemas de corte e empacotamento de peças irregulares, porém, poucos modelos de programação inteira mista podem ser encontrados. Especificamente, estes modelos foram desenvolvidos para o problema de empacotamento em faixa, que consiste em empacotar as peças em uma placa de largura fixa e comprimento a ser minimizado. Para as demais variantes do problema, não existem métodos exatos propostos na literatura. A principal dificuldade na resolução dos problemas de corte e empacotamento de peças irregulares está na manipulação das restrições geométricas. Estas restrições dependem do tipo de posicionamento das peças na placa, que pode ser discreto ou contínuo. Nesta tese, apresentamos dois modelos de programação inteira mista para o problema de empacotamento de peças em faixa, no qual cada peça pode ser alocada de forma contínua na placa. Estes modelos não demandam estruturas complexas para serem construídos. Também apresentamos uma nova estrutura de dados para armazenar informações sobre o posicionamento das peças e as posições de sobreposição, trazendo flexibilidade e eficiência para abordagens discretas. Utilizando esta estrutura, uma matheuristica foi proposta, combinando as vantagens dos modelos com alocação discreta e contínua das peças na placa. Além disso, modelos de programação por restrições para diversas variantes dos problemas de corte e empacotamento de peças irregulares foram explorados. Para algumas variantes, estes modelos são a primeira representação via modelagem. Uma nova restrição global foi desenvolvida para eliminar a sobreposição entre as peças. Experimentos computacionais foram realizados para avaliar as abordagens propostas.

Nos problemas de corte de itens irregulares, temos um conjunto de itens menores que devem ser alocados em objetos maiores (recipientes) de forma que estes estejam inteiramente contidos no recipiente e não se sobreponham. Neste trabalho, resolvemos um problema de corte e empacotamento de uma indústria que confecciona aventais e forros de luva, no qual deseja-se alocar uma lista de itens dentro de recipientes retangulares utilizando a menor quantidade de recipientes possível e minimizando o comprimento utilizado em cada recipiente. Para isto, utilizamos métodos exatos e heurísticos adaptados para o corte de aventais e forros de luva, com o objetivo de obter soluções de alta qualidade. Foram realizados experimentos computacionais que comprovaram a eficiência dos métodos de solução presentes neste trabalho. / In nesting problems, we have a set of small items that must be allocated into larger objects (containers) so that they are fully contained within the container and do not overlap. In this work, an apron and gloves lining industry cutting problem is solved, in which we want to allocate a list of items into rectangular containers using the smallest quantity of containers and minimizing the length used in each container. For this, we used exact and heuristic methods adapted for cutting aprons and glove liners, in order to obtain high quality solutions. Computational tests were performed and they show the efficiency of the solving methods presented in this work.