O planejamento da produção é uma atividade que avalia decisões para um melhor uso dos recursos disponíveis, visando satisfazer aos objetivos produtivos da empresa ao longo de um horizonte de planejamento. Este trabalho enfoca o problema de dimensionamento de lotes com restrições de capacidade (PDLC), que é uma das tarefas centrais envolvidas no planejamento da produção. O PDLC visa determinar o tamanho dos lotes a serem produzidos em períodos de tempo de um horizonte de planejamento. Os PDLC estudados neste trabalho contemplam duas características importantes: a presença de múltiplos itens e a existência de tempos de preparação para as máquinas. Além disso, são consideradas restrições de capacidade e situações onde o atraso para atender a demanda é permitido (backlogging). Alguns dos modelos estudados permitem que a preparação do ambiente de produção para um dado item possa ser mantida de um período para o seguinte, o que propiciaria a economia de até uma preparação a cada período. Esta característica é chamada de preservação de preparação (carry-over). Também existem situações onde a preparação de uma máquina começa em um período e termina no período seguinte. Na literatura, esta característica é chamada de set-up crossover. Este trabalho tem três metas centrais: a) avaliar diferentes configurações do software comercial ILOG CPLEX 11 para a solução dos PDLC estudados; b) estudar a influência na solução dos PDLC quando se acrescenta a possibilidade de atraso na demanda, de preservação de preparação e de set-up crossover; c) aplicar local branching para resolver os problemas estudados. Para resolver as instâncias propostas, foram utilizados o software comercial ILOG CPLEX 11 e um programa em C++ que foi desenvolvido neste trabalho. Foram utilizados exemplos encontrados na literatura para avaliar as propostas, e bons resultados foram obtidos / The production planning is an activity that evaluates the decision for a better use of the available resources, in order to satisfy the productive objectives of the company over a planning horizon. This work focuses on the capacitated lot-sizing problem (CLSP), which is one of the central tasks involved in production planning. The CLSP means to determine the size of the lots to be produced in time periods of a planning horizon. The CLSP studied in this work contemplate two complicating characteristics: the presence of multiple items and the existence of set-up times for the machines. Besides that, capacity constraints and situations where backlog of the demand is allowed are also considered (backlogging). Some of the studied models allow the set-up of the production environment for a given item to be carried over to the next period, which could result in economy of a set-up in each period (carry-over). There are situations where the set-up of a machine starts in one period and crosses over to the next period (set-up crossover). This work has three main goals: a) evaluate different configurations of the commercial software ILOG CPLEX 11 to solve the different kinds of CLSP studied; b) study the influence of the solution of the CLSP when you consider the possibility of backlogging, set-up carry-over and set-up crossover; c) apply local branching to solve the studied problems. To solve the proposed instances, we used the commercial solver ILOG CPLEX 11 and the program in C++ developed in this work. The examples used to test both programs are found in the literature, and good results were obtained

Pessoas portadoras de deficiências encontram enormes dificuldades ao tentarem entrar no mercado de trabalho. De fato, sobretudo em países em desenvolvimento, esta parcela significativa da população representa uma fração ínfima dos trabalhadores empregados. Dentre as iniciativas que tentam reverter este quadro, destaca-se a criação de Centros de Trabalhadores Deficientes (CTDs), empresas sem fins lucrativos que empregam pessoas portadoras de deficiências, geralmente em linhas de produção. Um dos fins últimos dos CTDs é expor os trabalhadores a situações encontradas em uma gama diversa de contextos produtivos, de modo que eles possam, eventualmente, vir a compor o quadro de empresas convencionais. A organização e planejamento da operação de CTDs envolve uma série de dificuldades. Questões ligadas à ergonomia do trabalho ou ao gerenciamento de qualidade, por exemplo, adquirem características particulares neste ambiente. Da mesma forma, problemas clássicos de balanceamento de linhas de produção ganham novas particularidades devido, sobretudo, à enorme heterogeneidade existente entre os trabalhadores. Neste contexto, nos interessamos por problemas referentes ao balanceamento da linha de produção com trabalhadores deficientes, onde se busca obter a maior eficiência produtiva dadas as habilidades específicas de cada trabalhador. De maneira mais precisa, o problema de balanceamento de linhas de produção em CTDs, conhecido na literatura como problema de balanceamento e designação de trabalhadores em linhas de produção (ALWABP, na sigla em inglês) consiste em alocar tarefas e trabalhadores a estações de trabalho, de modo a minimizar o gargalo produtivo e levando em consideração que cada tarefa tem um tempo de duração que depende do trabalhador escolhido para sua execução. Isto dá ao problema um caráter de dupla alocação, aumentando seu caráter combinatório e, consequentemente, sua dificuldade de resolução. Nesta dissertação, estudamos uma variedade de técnicas de resolução do ALWABP. Os objetivos deste estudo são, primeiramente, obter métodos diversos para resolução do problema que sejam eficazes tanto em termos do tempo computacional necessário para sua utilização como em termos da qualidade da solução obtida. Dentre as abordagens propostas e testadas encontram-se versões de algoritmos com diferentes complexidades, indo desde heurísticas construtivas e estratégias de busca monotônica em vizinhança até meta-heurísticas como GRASP e Busca Tabu. A variedade de técnicas desenvolvidas permitiu a resolução de um problema ainda mais complexo que o ALWABP, que consiste em programar a linha para diversos períodos produtivos, levando em consideração a rotação de tarefas entre os trabalhadores. Deste modo, os trabalhadores podem ser expostos ao maior número de tarefas possível (atendendo, assim, o fim de treinamento almejado no ambiente dos CTDs). Para resolução do problema de rotação de tarefas, as técnicas desenvolvidas foram utilizadas em um esquema de otimização híbrido que faz uso de um pool de soluções (obtidas pelos métodos heurísticos) que são integradas através de modelos de otimização linear inteira mista. Os resultados obtidos sugerem que as técnicas desenvolvidas são eficientes e flexíveis para o problema ALWABP e que a sua integração permite a obtenção de soluções eficientes para o problema de rotação de tarefas. Deste modo, esta dissertação propõe um esquema completo para o balanceamento de linhas de produção em CTDs / Disabled workers face enormous difficulties when trying to enter to the labor market. At the present moment, in particular in developing countries, this group constitutes a small portion of the labor force in productive processes. Among the initiatives that attempt to reverse this situation, we highlight the creation of sheltered work centers for the disabled (referred to as SWD henceforth), which are non-profit companies that employ people with disabilities, often in assembly lines. The organization and planning of the operation of a SWD involves a number of challenges. Issues related to ergonomy or production quality management, for instance, acquire particular characteristics in this environment. Likewise, classic assembly lines balancing modeling and solving techniques have to be modified, due to the significant heterogeneity among workers. In this context, we are concerned with problems related to the assembly line balancing with disabled workers, which attempts to achieve the higher production efficiency as possible, given the specific skills of each worker. More precisely, the assembly line balancing problem in SWD, known in the literature as the assembly line worker assignment and balancing problem (ALWABP), consists in assigning tasks and workers to workstations, in order to minimize the bottleneck of the production line while considering that each task duration time depends on the worker chosen for its execution. This double assignment structure leads to a much more complex problem. In this dissertation, we study a variety of techniques for solving the ALWABP. The goals of this study are, first of all, the development of a number of efficient techniques for solving the problem, both in terms of computational time required for their use and in terms of the quality of the obtained solutions. Among the techniques proposed and tested, we have versions of algorithms with different complexities, ranging from constructive heuristics and monotonic neighborhood search strategies to metaheuristics such as Tabu Search and GRASP. The diversity of the developed techniques allowed the resolution of a problem even more complex than the ALWABP, which consists of programming the line for a set of periods, taking into account the rotation of tasks among workers. The objective of this new problem is to propose a solution for a given production period that considers the fact that it might be positive to expose the workers to as many tasks as possible (for training, therapeutical and motivational reasons). In order to solve this job rotation problem, the techniques developed were integrated into a hybrid optimization scheme that uses a pool of solutions (obtained with the heuristic methods) which become inputs of mixed integer linear optimization models. The results suggest that the techniques developed are efficient and flexible to the ALWABP and their integration allows the obtention of efficient solutions to the job rotation problem. Thus, this dissertation proposes a complete scheme for the resolution of the balancing problem in SWD production lines

Problemas de corte de estoque consistem em arranjar peças menores, em tamanhos e quantidades especificados, dentro de peças maiores. Tais problemas têm sido investigados intensamente nas últimas décadas, acrescidos de novas características e novos métodos de solução. Nesta tese abordamos o problema de corte de estoque multiperíodo que surge imerso no planejamento e programação da produção em empresas que têm um estágio de produção caracterizado pelo corte de peças. As demandas dos itens ocorrem em períodos diversos de um horizonte de planejamento finito, sendo possível antecipar ou não a produção de itens. Os objetos disponíveis em estoque não utilizados em um período ficam disponíveis no próximo período, juntamente com novos objetos adquiridos ou produzidos pela própria empresa. Um modelo de otimização linear inteira de grande porte é proposto, cujo objetivo pondera o custo das perdas nos cortes, os custos de estocagem de objetos e itens. O método simplex com geração de colunas foi especializado para resolver a relaxação linear do modelo proposto. Foram realizados experimentos computacionais com problemas de corte de estoque unidimensional e bidimensional. Tais experimentos mostram que ganhos efetivos podem ser obtidos usando-se o modelo de corte de estoque multiperíodo, quando comparado com a solução lote-por-lote, tipicamente utilizada na prática. Porém, na prática, a solução relaxada é de pouca, ou nenhuma, utilidade. Assim, nesta tese, desenvolvemos dois procedimentos de arredondamento da solução do problema multiperíodo, baseado em horizonte rolante, ou seja, determinamos uma solução inteira factível apenas para o primeiro período, a qual será, de fato, implementada. Enfim, concluímos que o modelo para o problema de corte de estoque multiperíodo permite flexibilidade na análise de uma solução a ser implementada e, portanto, é uma ferramenta que permite ao gerente de produção uma visão global do problema para auxiliá-lo na tomada de decisões / Cutting stock problems consist of cutting a set of available stock objects in order to produce smaller ordered items. Such problems have been intensively researched over the last decades, together with additional characteristics and new methods for solving them. In this thesis, we address the multiperiod cutting stock problem, which arises in the production planning and programming in many industries that have a cutting process as an important stage. Ordered items have different due date over a finite planning horizon. An integer linear optimization model of large scale is proposed. The model makes possible to anticipate or not the production of items. Unused objects in inventory in a period become available to the next period, added to new inventory, which are acquired or produced by the own company. The mathematical model\'s objective is to minimize the cost of waste in the cutting process and costs for holding objects and fInal items. The simplex method with column generation was specialized to solve its linear relaxation. Computational experiments were carried out to solve one-dimensional and two-dimensional cutting stock problems. Such experiments showed that the multiperiod model could obtain effective gains when compared with the lot-for-lot solution, which is typically used in practice. However, in practical problems, the fractional solution is useless. So, in this thesis, two rounding procedures are developed to determine integer solutions for multiperiod cutting stock problems. Such procedures are based on a rolling horizon scheme, which roughly means, find an integer solution only for the first period, since this is the solution to be, in fact, carried out. Finally, we conclude that the proposed model for multiperiod cutting stock problems allows flexibility on analyzing a solution to be put in practice. The multiperiod cutting problem can be a tool that provides the decision maker a wide view of the problem and it may help him/her on making decisions

O setor de fundições é importante para a economia, pois produz componentes básicos para muitos outros setores, de modo que seu bom desempenho tem repercussão nos demais. Um modelo de programação inteira mista para uma fundição de mercado de pequeno porte, que visa principalmente minimizar atrasos na entrega dos pedidos, foi proposto na literatura. Neste trabalho é feito um estudo do modelo e é proposta uma nova abordagem, independente de qualquer software comercial, baseada na decomposição do problema em dois subproblemas: o planejamento da produção das ligas e o planejamento da produção dos itens. Ambos foram resolvidos por uma heurística lagrangiana baseada em transferêrencias. Testes computacionais mostraram que a abordagem proposta é capaz de gerar soluções de boa qualidade, em tempo computacional aceitável / The foundry sector is important to the economy as it produces basic components for many other sectors, to such an extent that its performance has a repercussion in other sectors. A recently published mixed integer-programming model for small market-driven foundries, which aims to minimize delays when delivering orders, was proposed in the literature. In this work, a study of this model was undertaken and a new approach is put forward, regardless of any commercial software, based on dealing with the problem in two sub problems: production planning of alloys and production planning of items. Both sub problems were solved by a Lagrangian heuristic based on transfers. Computational tests show that the approach proposed is able to generate solutions of good quality in acceptable computational time

Este texto trata de um dos temas fundamentais no planejamento de produção, o problema de dimensionamento de lotes de um único item. Uma descrição sucinta e informal do problema segue abaixo. Considere um intervalo de tempo dividido em períodos e que a cada período de tempo está associada a demanda de um item. Dados os custos e as eventuais restrições na produção e no armazenamento, determine os períodos em que se produzirá e em que quantidade para que as demandas sejam atendidas com o menor custo possível, respeitando as restrições impostas. Apresentamos aqui resultados sobre a estrutura ótima do problema, sobre complexidade e algoritmos para os casos básicos do problema / This text studies one of the core subjects in production planning, the single-item lot-sizing problem. A brief and informal description of this problem follows below. Considering a time interval split into time periods and that there is a demand of an item associated with each time period. Given production and holding costs and possibly production and holding restrictions, determine in which periods the production must occur and in which quantity, in order to attend the demands with a minimum cost, without violate any restriction. Here, it will be shown some results about the optimal structure of the problem, about the complexity and algorithms for the simpler cases

O conteúdo deste trabalho trata da formulação para solução do problema de otimização estrutural com minimização de massa em estruturas unifilares, sujeitas a restrição de tensão, flambagem das barras isoladas e fadiga. São considerados três casos de otimização: paramétrica, de forma e dimensional. Os problemas de singularidades nas restrições de tensão e flambagem são evitados através de uma formulação que faz uso de programação inteira para solução do problema. Outra singularidade encontrada na otimização topológica é a singularidade na matriz de rigidez da estrutura. Este problema foi evitado através de uma formulação que considera a existência de matriz de rigidez regular como restrição do problema. O método de solução utilizado para resolver problema de otimização é o método dos algoritmos genéticos. As restrições do problema são impostas através da penalização da função objetivo. O método de solução mostrou-se adequado para solução dos problemas estudados. A formulação implementada é validada através da solução de problemas clássicos de otimização estrutural. Os resultados obtidos são comparados com a literatura onde verificou-se a coerência dos mesmos. Após realizar a validação, a formulação é utilizada em um estudo que tem como base uma estrutura real: uma torre de queima de gases (flare) oriundos do processo de extração e armazenagem de petróleo em uma unidade flutuante. Para o problema da torre as restrições foram determinadas com base em critérios de falha estabelecido na norma DNV. A otimização do flare permitiu minimizar a massa da estrutura sem que os critérios de falha fossem violados. Verificou-se que a metodologia proposta é adequada para solução com grande número de restrições e com diversos casos de carregamento. / The purpose of this work is the development of a methodology to solve the structural optimization problem of frame structures subject to stress, buckling of isolated members, and fatigue constraints. Three types of structural optimization problems are considered: sizing, shape and topological. The stress and buckling singularity problems are avoided by an integer design variable formulation, using integer programing to obtain the optimization problem solution. Another issue found in optimization problems is the stiffness matrix singularity. The proposed formulations include the linear system stability as a constraint in the optimization problem. A genetic algorithm is used to solve the general optimization problem. All constraints of the problem are included with a penalization equation. The results show that genetic algorithm is a good approach to solve the proposed formulation. The proposed formulation is tested for solving classical optimization problems. The obtained results are consistent with the literature. A real engineering problem is solved with proposed methodology: a gas burning tower (flare). In this problem, all constraints are based on failure criteria recommended by DNV standards. The structural optimization of this problem shows that structural mass minimization is possible without violating the failure criteria. It is observed that solution methodology deals successfully with problems with multiple constraints and load cases

Nesta dissertação, discute-se o problema de otimização de carteiras de investimento para estratégia passiva de Index Tracking. Os objetivos principais são (i) apresentar um modelo de otimização de Index Tracking e (ii) a solucionar esse modelo com uso do método heurístico de Algoritmos Genéticos (AG) para formação de carteiras com número reduzido de ativos. O índice de referência utilizado é o Ibovespa, para o período de Janeiro/2009 a Julho/2012, com um total de 890 observações diárias de preços. A partir de uma amostra de 67 ativos, são formadas carteiras sem limite de ativos e limitadas a 40, 30, 20, 10 e 05 ativos; os intervalos de rebalanceamento das carteiras são 20, 40 e 60 períodos (dias úteis), ou seja, rebalanceamento mensal, bimestral e trimestral. É verificado que, para essa amostra, não é possível formar carteiras de 20 ou menos ativos via otimização direta com o solver Cplex com menos de 1 hora de processamento e gap abaixo de 5%. Com uso da heurística de Algoritmos Genéticos, são formadas carteiras de 10 e 05 ativos com tempo de processamento em torno de 5 minutos; nesse caso, o gap médio fica abaixo de 10% para ambos os tipos de carteira. E, com tempo de processamento do AG um pouco maior, em torno de 8 minutos, o algoritmo fornece soluções para carteiras de 10 e 05 ativos com gap médio abaixo de 5%. / In this master’s thesis it is discussed the portfolio optimization problem using the passive investment strategy of Index Tracking. The main goals are (i) to present an optimization model for the Index Tracking problem and (ii) to solve this model using the heuristic approach of Genetic Algorithms (GA) to create portfolios with reduced amount of stocks. The benchmark used is the Ibovespa Index (main reference for the Brazilian Stock Market), during the period from January/2009 to July/2012 (using a total of 890 daily stock prices). The sample contains 67 assets, and the model is used to build portfolios without limit in the amount of assets and portfolios limited to 40, 30, 20, 10 and 05 assets; the ranges of time to rebalance the portfolios are 20, 40, and 60 trading days, which means to rebalance monthly, bimonthly and quarterly. The results show that, considering this sample, it is not possible to build portfolios with 20 stocks (or less than 20) through direct optimization using the solver Cplex with computational processing time less than 1 hour and results with gap below 5%. On the other hand, using the Genetic Algorithms heuristic approach, portfolios limited to 10 and 05 stocks are built with computational time close to 5 minutes; for both types of portfolio, the solutions provided by the GA have average gap below 10%. Also, with a computational time slightly bigger, close to 8 minutes, the algorithm provides solutions with average gap below 5% for portfolios limited to 10 and 05 stocks.

Optimization plays an important role in many methods routinely used in statistics, machine learning and data science. Often, implementations of these methods rely on highly specialized optimization algorithms, designed to be only applicable within a specific application. However, in many instances recent advances, in particular in the field of convex optimization, make it possible to conveniently and straightforwardly use modern solvers instead with the advantage of enabling broader usage scenarios and thus promoting reusability. This paper introduces the R Optimization Infrastructure which provides an extensible infrastructure to model linear, quadratic, conic and general nonlinear optimization problems in a consistent way. Furthermore, the infrastructure administers many different solvers, reformulations, problem collections and functions to read and write optimization problems in various formats. / Series: Research Report Series / Department of Statistics and Mathematics

O problema de alocação de aeronaves a voos, ou tail assignment problem (TAP), consiste em determinar qual aeronave realizará cada voo da malha de uma empresa aérea, visando a minimizar o custo total da operação e respeitando diversas restrições de conectividade de voos, permanência de aeronaves no solo, serviços obrigatórios de manutenção, limitações técnicas e desempenho de aeronaves, conexões de passageiros e tripulantes e famílias com diversos modelos de aeronaves. Este trabalho apresenta um modelo matemático exato e um método heurístico para a solução do TAP considerando todas as restrições citadas, o que não ocorre com os modelos encontrados na literatura. Os modelos desenvolvidos, baseados em programação linear inteira e na meta-heurística Busca Tabu, foram aplicados a problemas reais, extraídos da malha de uma empresa aérea brasileira, operadora de 35 aeronaves e cerca de 210 voos diários. Os resultados obtidos são compatíveis com a operação da empresa e apresentam ganhos em relação ao método de alocação de aeronaves utilizado na operação diária. Os tempos de processamento para solução pelo método exato são excessivamente longos, indicando que o método heurístico é mais adequado para a utilização em empresas aéreas, com resultados adequados obtidos em tempos de processamento satisfatórios. / The problem known as Aircraft Assignment or Tail Assignment Problem (TAP) is the problem of assigning flights to each aircraft of an airline\'s fleet, aiming at minimizing the total operating cost while complying with several constraints, such as network connectivity, aircraft time on ground, mandatory maintenance services, aircraft technical restrictions, passengers and crew connections, aircraft performance and aircraft families with more than one type. This work presents a deterministic mathematical model and a heuristic method to solve the TAP considering all constraints listed above, what does not happen with the models found in the literature. The proposed methods, based on mathematical integer programming and on the Tabu Search metaheuristic, were applied to problems obtained from the network of a Brazilian airline, operating 35 aircraft and around 210 daily flights. The results show the models are suitable to solve the problem and savings are observed when compared to the current assignment method. The long processing times intrinsic to the deterministic method show the heuristic method is more suitable for use in airlines, with suitable results obtained at acceptable computational times.

O ambiente produtivo denominado job shop representa empresas manufatureiras com características como: alta variedade de produtos, volume baixo de produção e uma fábrica dividida em áreas funcionais. O problema abordado neste trabalho trata da determinação do programa de produção (scheduling) de cada lote de produtos no ambiente job shop, com a premissa de que cada produto a ser elaborado surge através de um pedido realizado pelo cliente com especificações e particularidades próprias. O objetivo do trabalho é apresentar e examinar de forma detalhada as formulações matemáticas do tipo linear inteira mista (PLIM), encontradas na literatura para o ambiente que consideram a função objetivo do makespan. Além disso, se estabelece uma nova formulação matemática que auxilia a simulação do ambiente. Todas as formulações foram comparadas através de suas dimensões e testes computacionais. Adicionalmente são apresentadas três diferentes estratégias de resolução que permitem a exploração de soluções obtidas através de diferentes metodologias. A primeira estratégia estabelece para cada instância uma solução inicial que promove uma redução do número de combinações a serem avaliadas pelo software, a segunda estratégia combina duas formulações tornando uma formulação unificada, e a terceira estratégia, estabelece um processo que utiliza duas formulações de forma consecutiva compondo um procedimento sistemático. Experimentos computacionais indicam que a formulação com melhor desempenho para o problema de job shop é a formulação de Manne (1960) por obter o melhor limitante superior (upper bound). A formulação proposta apresenta o melhor limitante inferior (lower bound). Todas as formulações melhoram seus resultados através do uso das estratégias propostas. / The operational job shop environment, represents manufacturing companies with high product variety, low volume production and an organization divided into functional areas. The problem addressed in this work determines the production schedule of each batch production, with the premise that each product results from a request made by the client with specifications and its own particularities. The main objective here is to present and to examine in detail the mathematical integer - linear program formulations (MILP) from the literature for the job shop classic environment, which considers the makespan objective. Furthermore, a new mathematical formulation is provided to help with the simulation of the environment. All the formulations were compared by mathematical dimensions and computational tests. In addition, three different strategies are presented to promote the exploration of solutions obtained from new methodologies. The first strategy defines an initial solution for each problem and promotes a reduction of the combination number to be evaluated by the software. The second strategy considers the combination of two mathematical formulations under one objective function. The third strategy establishes a procedure in which two mathematical formulations are used consecutively, creating a systematic procedure. Computational experiments demonstrate that the best formulation for the job shop problem is the Manne (1960) formulation, since it obtains the best upper bound. The proposal formulation obtains the best lower bound. All of the formulations improve their results through the use of the proposed strategies.