A presente pesquisa aborda um problema de programação de veículos rico, em que a característica mais importante é a demanda de múltiplas embarcações para atendimento a uma única tarefa. Trata-se de uma aplicação real do setor de apoio marítimo \"offshore\", das embarcações que fazem o reboque e o lançamento de linhas de ancoragem de sondas de perfuração e unidades de produção. Como método de solução, aplicaram-se duas heurísticas com uma abordagem híbrida que incluem uma inserção baseada em programação linear inteira, visando a minimização do custo total da operação, dentro de um tempo de processamento aceitável. / This research deals with a rich vehicle scheduling problem, having as the most important feature the demand of multiple vessels per task. It is a real problem present in the oil industry related to the vessels that undertake the towing and the launching of mooring lines of drilling and production units. As a solution method, two heuristics with a hybrid approach were applied which include an insertion based on integer linear programming, aiming at minimizing the total cost of the operation, within an acceptable processing time.

M.Sc., Faculty of Sciences, University of the Witwatersrand, 2011 / Abstract This dissertation is concerned with discrete global optimization of nonlinear problems. These problems are constrained and unconstrained and are not easily solvable since there exists multiplicity of local and global minima. In this dissertation, we study the current methods for solving such problems and highlight their ine ciencies. We introduce a new local search procedure. We study the rapidly-exploring random tree (RRT) method, found mostly in the research area of robotics. We then design two global optimization algorithms based on RRT. RRT has never been used in the eld of global optimization. We exploit its attractive properties to develop two new algorithms for solving the discrete nonlinear optimization problems. The rst method is called RRT-Optimizer and is denoted as RRTOpt. RRTOpt is then modi ed to include probabilistic elements within the RRT. We have denoted this method by RRTOptv1. Results are generated for both methods and numerical comparisons are made with a number of recent methods.

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.

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

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 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.

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

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