Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd Easton / Integer Programs (IP) are a class of discrete optimization that have been used commercially to improve various systems. IPs are often used to reach an optimal financial objective with constraints based upon resources, operations and other restrictions. While incredibly beneficial, IPs have been shown to be NP-complete with many IPs remaining unsolvable. Traditionally, Branch and Bound (BB) has been used to solve IPs. BB is an iterative algorithm that enumerates all potential integer solutions for a given IP. BB can guarantee an optimal solution, if it exists, in finite time. However, BB can require an exponential number of nodes to be evaluated before terminating. As a result, the memory of a computer using BB can be exceeded or it can take an excessively long time to find the solution. This thesis introduces a modified BB scheme called the Octanary Branching Algorithm (OBA). OBA introduces eight children in each iteration to more effectively partition the feasible region of the linear relaxation of the IP. OBA also introduces equality constraints in four of the children in order to reduce the dimension of the remaining nodes. OBA can guarantee an optimal solution, if it exists, in finite time. In addition, OBA has been shown to have some theoretical improvements over traditional BB. During computational tests, OBA was able to find the first, second and third integer solution with 64.8%, 27.9% and 29.3% fewer nodes evaluated, respectively, than CPLEX. These integers were 44.9%, 54.7% and 58.2% closer to the optimal solution, respectively, when compared to CPLEX. It is recommended that commercial solvers incorporate OBA in the initialization and random diving phases of BB.

This thesis is focused on optimizing the routes which are implemented in our country at night. Goods are transporting between designated central cities. It deals with creating cyclic routs, along which the goods should be effectively transported, with the respect of the cost. The instruction how to create these paths represents a heuristic method for generating cyclic paths. The algorithm uses the results provided by model that is based on a search for multiple product chart. The chart contains the minimum number of vehicles that provide transport and individual amount of transported goods. The principle of this heuristic method is to create cyclic paths in such a way to be able to serve all transportation requirements with the lowest number of reloads. This approach leads to the fact that the direct paths are preferred.

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

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

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.