Nesta tese, estudamos o problema de Empacotamento de Bicliques. Um biclique é um grafo bipartido completo. No problema de Empacotamento de Bicliques são dados um inteiro k e um grafo bipartido G e deseja-se encontrar um conjunto de k bicliques, subgrafos de G, dois a dois disjuntos nos vértices, tal que a quantidade total de arestas dos bicliques escolhidos seja máxima. No caso em que k=1, temos o problema de Biclique máximo. Esses dois problemas possuem aplicações na área de Bioinformática. Mantemos neste trabalho um enfoque prático, no sentido de que nosso interesse é resolver instâncias desses dois problemas com tamanho razoavelmente grande. Para isso, utilizamos técnicas de Programação Linear Inteira. Para avaliar os métodos propostos aqui, mostramos resultados de experimentos computacionais feitos com instâncias vindas de aplicações e também com instâncias geradas aleatoriamente. / In this thesis, we study the Biclique Packing problem. A biclique is a complete bipartite graph. In the Biclique Packing problem we are given an integer k and a bipartite graph G and we want to find a set of k vertex disjoint bicliques of G, such that the total number of biclique\'s edges is maximum. When k=1, we have the Maximum Biclique problem. These two problems have applications in Bioinformatics. In this work we keep a practical focus, in the sense that we are interested in solving large size instances of these problems. To tackle these problems, we use Integer Linear Programming techniques. In order to evaluate the methods proposed here, we show results of computational experiments carried out with practical application\'s instances and also with randomly generated ones.

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

O trabalho apresentado nesta dissertação é referente ao estudo da evacuação de pessoas, mais especificamente, a evacuação predial faseada. O objetivo é determinar, para instâncias de até 25 andares, os instantes de liberação de cada grupo de pessoas, a fim de minimizar o tempo total de evacuação do edifício. No entanto, a determinação destes instantes deve considerar o risco ao qual os diferentes grupos estão submetidos, priorizando a evacuação do andar afetado. Além disso, os conflitos de diferentes grupos por espaço nas rotas de evacuação também devem ser evitados, já que, são nessas situações que acontecem grande parte dos acidentes. Para atingir tal objetivo, foi elaborado um modelo matemático de programação linear inteira. Devido à alta complexidade do modelo, fez-se necessária a aplicação de métodos heurísticos para a obtenção de soluções. Dessa maneira, foram desenvolvidas uma heurística de busca baseada em GRASP e uma heurística lagrangeana. Apesar da heurística lagrangeana atestar a qualidade da solução (a partir da comparação do resultado obtido com o limitante inferior), a heurística de busca mostrou-se mais adequada para o problema, pois forneceu resultados de qualidade com pouco esforço computacional. / This dissertation studies the evacuation of people, more specifically, building phased evacuation. The objective of this study is to determine, for buildings of up to 25 floors, in which instants each group of people has to be released, in order to minimize the total evacuation time. Furthermore, the determination of these instants has to consider the risk to which each group of people is submitted, thus the affected floor has to be the first group to be released. In addition, conflicts for space between groups should be avoided, since such situations increase the occurrences of accidents. To achieve this goal, an integer linear programming model was designed. Due to the high complexity of the model, it was necessary to apply heuristics to obtain solutions for some instances. Therefore, a search heuristic based on GRASP and a lagrangian heuristic were developed. Despite the fact that the lagrangian heuristic attests to the quality of the solution (when it is compared to the lower bound), the search heuristic was considered more suitable for this problem because it provided quality results with lower computational efforts.

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

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.

A área crítica para vigilância do espaço aéreo Brasileiro é a Amazônia Legal, cobrindo uma área de aproximadamente 5,08 milhões de quilômetros quadrados. O problema de localizar um dado número de facilidades de vigilância ou localizar um dado número de esquadrões de interceptação para maximizar a área de cobertura em uma definida região geográfica é conhecido na literatura como um Problema de Localização de Máxima Cobertura (Maximum Covering Location Problem - MCLP). O objetivo deste trabalho é apresentar o MCLP, sugerindo novas restrições para adaptá-lo à realidade do problema estudado. Como resultado foi desenvolvida uma metodologia que se mostra flexível para aplicações na situação em estudo e em outras áreas de interesse da Força Aérea Brasileira. Os resultados obtidos no estudo de caso mostram que tal metodologia auxilia o decisor, mostrando a variação com relação à área de cobertura quando se deseja trabalhar com diferentes alcances de missão e restrições impostas às características das localidades de facilidades utilizadas, como por exemplo a bonificação logística, que indica o grau de facilidade operacional de implantação do esquadrão na localidade de facilidade.

Diversas pesquisas e estudos científicos mostram que uma grande porcentagem das pessoas com deficiência é excluída do mercado de trabalho, sobretudo em países em desenvolvimento. Com o intuito de alterar essa realidade, destacam-se, entre outras medidas, a criação de Centros de Trabalho para Deficientes (CTDs). Tais organizações empregam trabalhadores com deficiência em vários setores empresariais, dando-lhes oportunidades iniciais e preparando-os para que possam, mais tarde, ser inseridos no mercado de trabalho convencional. Vários destes centros operam linhas de produção, principal objeto de estudo desta tese. Nosso estudo é situado em uma etapa idealmente posterior aos CTDs, referente à inserção de trabalhadores com deficiência em linhas de produção convencionais. A demanda por estudos neste contexto tem crescido nos últimos anos, devido sobretudo a políticas corporativas de responsabilidade social e exigências legislativas, como a \"Lei das Cotas\", presentes em diversos países. O planejamento da operação de linhas de produção na presença de trabalhadores com deficiência envolve uma série de desafios, devido à heterogeneidade entre trabalhadores, que faz com que o tempo de execução das tarefas seja dependente de cada indivíduo. Nos deparamos, assim, com um problema de dupla alocação, em que as variáveis de decisão determinam as tarefas a serem inseridas em estações e a alocação de trabalhadores para as mesmas, de modo a otimizar alguma medida de eficiência. O balanceamento de linhas de produção convencionais com uma parcela de trabalhadores com deficiência é denominado problema de balanceamento de linhas de produção e integração de trabalhadores (ALWIBP, do inglês: assembly line worker integration and balancing problem), sendo um caso particular do problema de balanceamento de linhas de produção e designação de trabalhadores (ALWABP, do inglês: assembly line worker assignment and balancing problem), cuja ocorrência é mais comum em linhas de CTDs. Nosso objetivo consiste em estudar formas eficientes de proporcionar a integração de trabalhadores com deficiência em linhas convencionais. Para tanto, abordamos variações do ALWIBP que consideram: (i) minimização de diferentes funções objetivo (número de estações ou tempo de ciclo); (ii) linha de produção com leiautes distintos (simples ou em U); (iii) incertezas quanto ao tempo de execução de cada tarefa (abordagem robusta); (iv) estratégias de rotação de tarefas ou alocação de trabalhadores com deficiência na linha com espaçamento regular. Para cada uma destas extensões, foram desenvolvidos formulações matemáticas, métodos de resolução e novos conjuntos de instâncias teste. Experimentos computacionais indicam possibilidades de adaptação de linhas de produção convencionais à inserção de trabalhadores com deficiência, a custos adicionais baixos ou quase nulos. Portanto, este trabalho oferece alternativas para uma maior flexibilidade na integração de pessoas com deficiência, tornando-os tão eficientes quanto qualquer outro trabalhador denominado \"convencional\". / A number of studies show that a large percentage of disabled people are excluded from the labor market, in particular in developing countries. In order to deal with this problem, one can highlight the importance of Sheltered Work Centers for Disabled (SWDs). These organizations employ disabled workers in various corporate sectors, giving them initial opportunities and preparing them so that they can be later integrated into the conventional labor market. Many of these centers operate assembly lines, the main object of study of this thesis. Our study considers an ideally later stage of SWDs, related with the insertion of disabled workers in conventional assembly lines. The demand for studies in this field has grown over the years, due to corporate social responsibility policies and legal requirements such as \"quotas legislations\", present in many countries. Planning the operation of assembly lines with disabled workers involves a series of challenges due to the heterogeneity among workers, which are reflected in task times being worker dependent. This results in a double allocation problem, where decisions must determine both the tasks and the workers to be assigned to the stations, in order to optimize some efficiency measure. The conventional assembly line balancing with a parcel of disabled workers is known as the assembly line worker integration and balancing problem (ALWIBP), being a particular case of the assembly line worker assignment and balancing problem (ALWABP), which occurance is more common in SWDs. Our goal consists in studying efficient ways to promote the integration of people with disabilities in conventional assembly lines. For that, we address ALWIBP variants that consider: (i) minimization of different objective functions (number of stations or cycle time); (ii) different assembly line layouts (simple or U-shaped); (iii) uncertainties on task execution times (robust approach); (iv) job rotation strategies or allocation of disabled workers in the line with regular spacing. For each of these extensions, we develop mathematical formulations, solution methods and new sets of benchmark instances. Computational experiments indicate possibilities for adapting conventional assembly lines to the insertion of disabled workers, at low or close to null additional costs. Therefore, this study offers alternatives ways of increasing exibility in the integration of people with disabilities, making them as efficient as any other conventional worker.

Nesta tese é realizado um estudo de caso em uma indústria química brasileira, no qual busca-se representar características da tomada de decisões para a programação da produção em plantas de bateladas. Para isso, foi proposto um modelo matemático do tipo MIP (Mixed Integer Programming) que considerou a disponibilidade de matérias-primas, múltiplas tarefas produtivas para um mesmo produto, tanques de armazenamento multiproduto, envase de produtos e demanda de produtos a granel e envasados. O objetivo principal desse estudo era permitir a obtenção de soluções compatíveis com a prática da empresa em tempo de processamento viável. A partir desse estudo de caso, foi efetuado um segundo estudo com objetivo de avaliar o desempenho de formulações matemáticas para a resolução de um problema de programação da produção. Foram considerados modelos clássicos das comunidades científicas de pesquisa operacional e de engenharia de sistemas de processo, além de um terceiro modelo desenvolvido a partir de conceitos dessas duas comunidades. Algumas características do estudo de caso não foram retratadas, como o consumo de matérias-primas e o envase dos produtos, porém, foram consideradas duas características comumente observadas em problemas da indústria de processos: bateladas com quantidade produzida flexível e tarefas que produzem mais de um produto. Por fim, um terceiro estudo foi realizado com base no estudo de caso da indústria química brasileira, porém, com um foco decisões mais próximas ao nível tático. Sendo assim, foi considerado apenas o dimensionamento de lotes, sem o sequenciamento da produção. Por outro lado, foram acrescentadas características pertinentes à aquisição de matérias-primas, como custos das matérias-primas e descontos por quantidade adquirida. O objetivo deste último trabalho era avaliar a influência da integração das decisões de dimensionamento de lotes e de aquisição das matérias-primas nos custos da cadeia produtiva durante todo o horizonte de planejamento. / In this thesis we developed a study case in a Brazilian chemical industry, in which the aim was to represent the characteristics of decision-making for production scheduling in batch plants. For this, a mixed integer programming model was proposed to consider the availability of raw materials, multiple productive tasks for the same product, multi-product storage tanks, product packaging and demand for products in bulk and packaged. The main objective of this study was develop a model that is able to obtain solutions that clould be used in practice for this chemical industry in viable processing time. From this study case, a second work was carried out to evaluate the performance of mathematical formulations to solve a problem of production scheduling. Classic models of operational research and process system engineering communities were considered, and a third model was developed from concepts of these two communities. Some features of the case study were not modelled, such as the consumption of raw materials and the product packaging, however, two characteristics usually present in process industries were considered: flexible batch production quantity and multi-product task production. Finally, a third study developed based on the study case of the Brazilian chemical industry, but with focus on decisions more familiar to the tactical level. Thus, only lot sizing was modelled, without production scheduling. On the other hand, features relevant raw material purchasing were included, such as raw material costs and discounts for quantity purchased. The objective of this last work was to evaluate the influence of integrating lot sizing decisions and raw material purchasing decisions in the overall costs of the production chain during the entire planning horizon.

Orientador: Edson Luiz França Senne / Banca: José Roberto Dale Luche / Banca: Luiz Leduino Neto / Resumo: Neste trabalho propõe-se uma abordagem para o Problema de Balanceamento de Linhas de Montagem (do inglês, Assembly Line Balancing Problem - ALBP) para aumentar a eficiência de uma indústria montadora de veículos. O ALBP caracteriza-se como um problema de sequenciamento de tarefas em estações de trabalho classificado como um problema de Otimização Combinatória NP-difícil e, portanto, a solução exata do problema em ambientes reais geralmente implica em elevado custo computacional. Para resolver o ALBP, foram formulados um modelo matemático de otimização inteira mista para obtenção de soluções determinísticas e um modelo estocástico com recurso que considera a incerteza dos tempos de execução das tarefas pelos operadores. A motivação para o desenvolvimento do presente trabalho decorre da observação de interrupções constantes do fluxo de produção nesta indústria, atribuídas às mais diversas naturezas, e que causavam transtornos e elevados níveis de estresse aos trabalhadores. Ambos os modelos, determinístico e estocástico, aumentaram a capacidade de produção de 196 unidades/dia para 245 e 233 unidades/dia, respectivamente. O modelo estocástico aumentou o tempo de ciclo CT em 5,6% quando comparado ao modelo determinístico, embora diminua a capacidade efetiva em 4,8% Porém, não considerar a incerteza no tempo de execução das tarefas pode diminuir a quantidade produzida em até 10,6%. Contrariamente ao entendimento comum em linhas de montagem, este trabalho conclui que reduzir os tem... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work proposes solution approaches to the Assembly Line Balancing Problem (ALBP) to increase the efficiency of a vehicle assembler industry. The ALBP is characterized as a task sequencing in workstations which is classified as a NP-hard Combinatorial Optimization problem and, therefore, the exact solution of the problem in real environments usually implies a high computational cost. In order to solve the ALBP, a mathematical model of mixed integer optimization to obtain deterministic solutions and a stochastic model with resource that considers the uncertainty of the execution times of the tasks by the operators were formulated. The motivation for the development of this work stems from the constant interruptions of the production flow in this industry, attributed to the most diverse natures, which cause disorders and high levels of stress to the workers. The deterministic and stochastic models increased the production capacity from 196 units / day to 245 and 233 units / day, respectively. The stochastic model increased the cycle time by 5.6% when compared to the deterministic model, although it reduced the effective capacity by 4.8%, which is equivalent to 12 vehicles / day. However, not considering the uncertainty in task execution times can decrease the amount produced by up to 10.6% or 26 vehicles / day. Contrary to the most acceptable idea, this work concludes that reducing idle times to minimum levels is detrimental to assembly line productivity. This is due to the ... (Complete abstract click electronic access below) / Mestre

Made available in DSpace on 2016-12-23T14:33:34Z (GMT). No. of bitstreams: 1 dissertacao_ez[1].pdf: 489437 bytes, checksum: d1ab93a940c6981c3ddcdb53466a2f44 (MD5) Previous issue date: 2006-12-04 / An eletric utility must install protection (reclosers and fuses) and sectionalizing (switches) devices in key points of its distribution network to serve its customers with a reliable power supply. Utility boards or similar commissions define measures (reliability indices) to quantify and analize the eletric utility services. The problem addressed in this work is twofold. First, we want to optimize the allocation of reclosers in a distribution network to improve its reliability indices. The Simulated Annealing meta-heuristic was employed and its results were close to the optimal values in the tests performed. Second, we want to improve the effectiveness of a distribution protective design by identifying the type (recloser, fuse or switch) and location of devices to be installed. A Binary Linear Programming model found in the literature was implemented and tested. Its deficiencies leaded to the development of a more complete Binary Nonlinear Programming model and a specific branch-and-bound algorithm to solve it. The solutions proposed in this work allow an eletric utility to project and restructure the protection design of its distribution networks, allowing it to improve the service provided to its consumers. Hence, the company can cut investiments costs and still ensure a better quality of service to its clients, generating economic benefits to both parties. / As empresas responsáveis pelo fornecimento de energia elétrica (concessionárias) devem instalar equipamentos de proteção (religadores e fusíveis) e de seccionamento (chaves) em locais adequados da rede de distribuição para prestar um serviço de boa qualidade. Órgãos reguladores estabelecem métricas (índices de continuidade) para quantificar e analisar o desempenho das concessionárias. O problema abordado neste trabalho pode ser dividido em duas partes. A primeira trata de otimizar a alocação de religadores em uma rede de distribuição, buscando melhorar os índices de continuidade. A meta-heurística Simulated Annealing foi empregada e os resultados obtidos nos testes realizados ficaram muito próximos dos valores ótimos. Na segunda parte, tenta-se determinar a melhor alocação de religadores, fusíveis e chaves de forma simultânea, novamente para melhorar os índices de uma rede de distribuição. Um modelo de Programação Linear Binária proposto na literatura foi implementado e testado. As deficiências identificadas neste modelo motivaram o desenvolvimento de uma nova formulação de Programação Não-linear Binária, mais abrangente, e um algoritmo de branch-and-bound específico para resolver as formulações obtidas com o novo modelo. As soluções propostas neste trabalho permitem que as concessionárias projetem ou reestruturem a proteção das redes de distribuição de energia elétrica de forma a melhorar o serviço prestado aos consumidores. Com isto, as empresas podem diminuir o custo dos investimentos e ao mesmo tempo garantir que os seus clientes serão melhor atendidos, o que gera benefícios econômicos a ambos.