Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Neste trabalho, apresentamos um estudo sobre o problema de dimensionamento de lotes com múltiplas plantas, múltiplos itens e múltiplos períodos. As plantas têm capacidade de produção limitada e a fabricação de cada produto incorre em tempo e custo de preparação de máquina. Nosso objetivo é encontrar um plano de produção que satisfaça a demanda de todos os clientes, considerando que a soma dos custos de produção, de estoque, de transporte e de preparação de máquina seja a menor possível. Este trabalho tem duas contribuições centrais. Primeiramente, propomos a modelagem do problema de dimensionamento de lotes com múltiplas plantas utilizando o conceito de localização de facilidades. Para instâncias de pequena dimensão, os testes computacionais mostraram que a resolução do problema remodelado apresenta, como esperado, resultados melhores que o modelo original. No entanto, seu elevado número de restrições e de variáveis faz com que as instâncias de maiores magnitudes não consigam ser resolvidas. Para trabalhar com instâncias maiores, propomos um método híbrido (math-heurística), que combina o método relax-and-fix, com a restrição de local branching. Testes computacionais mostram que o método proposto apresenta soluções factíveis de boa qualidade para estas instâncias / In this work, we present a study about the multi-plant, multi-item, multi-period lot-sizing problem. The plants have limited capacity, and the production of each item implies in setup times and setup costs. Our objective is to find a production plan which satisfies the demand of every client, considering that the sum of the production, stocking, transport and setup costs is the lowest possible. This work has two main contributions. Firstly, we propose the multi-plant lot-sizing problem modeling using the facility location concept. For small dimension problems, computational tests showed that the remodeled problem resolution presents, as expected, better results than the original model. However, the great number of restrictions and variables make bigger instances to be intractable. To work with the bigger dimension instances, we propose a hybrid method (math-heuristic), which combines the relax-and-fix method and the local branching restriction. Computational tests show that the proposed math-heuristic presents good quality feasible solutions for these instances

Dans cette thèse, nous étudions deux problèmes de planification de production motivés par des applications du monde réel. Tout d'abord, un problème de planification de production pour un projet de fabrication de vêtements est étudié et un outil d'optimisation est développé pour le résoudre. Deuxièmement, une version restreinte du problème de dimensionnement du lot de capacité avec des configurations dépendantes de la séquence est explorée. Diverses formulations mathématiques sont développées et une analyse de complexité est effectuée pour donner une première analyse du problème. / In this thesis, we study two production planning problems motivated by challenging real-world applications. First, a production planning problem for an apparel manufacturing project is studied and an optimization tool is developed to tackle it. Second, a restricted version of the capacitated lot sizing problem with sequence dependent setups is explored. Various mathematical formulations are developed and complexity analysis is performed to offer a first glance to the problem.

Quality is an important measurement within a semiconductor manufactory. Due to the fact that yield is directly affected by quality of the manufacturing process, in this paper a quality based scheduling approach will be presented which compares different methods like dispatching, MIP and CP, regarding different objectives. To test the different used methods a benchmark model of a semiconductor manufactory is build up. Here a lithography work center is used in detail where the rest of the fabrication is only build up as a delay station. With this model the repeatability for the example of a lithography step is investigated. Thereby in this investigation it is assumed, that each lithography tool has an offset which is transferred to the structure. Now the quality of a product should be best, if the offset from one layer to the next layer is minimized.

In this dissertation, we address three different combinatorial optimization problems (COPs), each of which has specific real-life applications. Owning to their specific nature, these problems are different from those discussed in the literature. For each of these problems, we present a mathematical programming formulation, analyze the problem to determine its useful, inherent structural properties, and develop an efficient methodology for its solution by exploiting these properties. The first problem that we address is the course timetabling problem encountered at Virginia Tech. The course timetabling problem for a university is a difficult problem and has been studied by many researchers over the years. As a result, a plethora of models and approaches have been reported in the literature. However, most of these studies have focused on applications pertaining to course scheduling for a single or at most few departments of a university. The sheer size of the university-wide timetabling problem that we address, involving thousands of courses to be scheduled in hundreds of classrooms in each semester, makes it a challenging problem. We employ an appropriate decomposition technique that relies on some inherent structural properties of the problem both during the modeling and algorithmic development phases. We show the superiority of the schedules generated by our methodology over those that are currently being used. Also, our methodology requires only a reasonable amount of computational time in solving this large-size problem. A facility layout problem involving arbitrary-shaped departments is the second problem that we investigate in this dissertation. We designate this problem as the arbitrary-shaped facility layout problem (ASFLP). The ASFLP deals with arranging a given set of departments (facilities, workstations, machines) within the confines of a given floor space, in order to optimize a desired metric, which invariably relates to the material handling cost. The topic of facility planning has been addressed rather extensively in the literature. However, a major limitation of most of the work reported in the literature is that they assume the shape of a department to be a rectangle (or even a square). The approach that relies on approximating an arbitrary-shaped department by a rectangle might result in an unattractive solution. The key research questions for the ASFLP are: (1) how to accurately model the arbitrary-shaped departments, and (2) how to effectively and efficiently determine the desired layout. We present a mixed-integer programming model that maintains the arbitrary shapes of the departments. We use a meta-heuristic to solve the large-size instances of the ASFLP in a reasonable amount of time. The third problem that we investigate is a supply chain scheduling problem. This problem involves two stages of a supply chain, specifically, a manufacturer and one or more customers. The key issue is to achieve an appropriate coordination between the production and distribution functions of the manufacturer so as to minimize the sum of the shipping and job tardiness costs. We, first, address a single customer problem, and then, extend our analysis to the case of multiple customers. For the single-customer problem, we present a polynomial-time algorithm to solve it to optimality. For the multiple-customer problem, we prove that this problem is NP-hard and solve it by appropriately decomposing it into subproblems, one of which is solvable in polynomial time. We propose a branch-and-bound-based methodology for this problem that exploits its structural properties. Results of an extensive computational experimentation are presented that show the following: (1) our algorithms are efficient to use and effective to implement; and (2) significant benefits accrue as a result of integrating the production and distribution functions. / Ph. D.

No description available.

The goal of harvest scheduling is to produce a practical operations schedule that can be implemented in the field by operational foresters and maximizes all values. The resulting harvest units need to represent a close approximation to what will be done operationally and while emulating natural disturbance regimes and topographic boundaries. using flow direction surfaces. Two methods of meeting spatially acceptable harvest units through a heuristic algorithm and a mixed integer programming method. A factor analysis was conducted on both to determine the statistical significance between 3 forest characterizations and mean financial and shape index indicators. Mixed integer programming had higher cash flows and net present values per hectare and the heuristic method had higher net present value per cubic meter at the 95% level of significance.

Major cyber attacks against the cyber networks of organizations has become a common phenomenon nowadays. Cyber attacks are carried out both through the spread of malware and also through multi-stage attacks known as hacking. A cyber network can be represented directly as a simple directed or undirected network (graph) of nodes and arcs. It can also be represented by a transformed network such as the attack graph which uses information about network topology, attacker profile, and existing vulnerabilities to represent all the potential attack paths from readily accesible vulnerabilities to valuable target nodes. Then, interdicting or hardening a subset of arcs in the network naturally maps into deploying security countermeasures on the associated devices or connections. In this dissertation, we develop network interdiction models and algorithms to optimally select a subset of arcs which upon interdiction minimizes the spread of infection or minimizes the loss from multi-stage attacks. In particular, we define four novel network connectivity-based metrics and develop interdiction models to optimize the metrics. Direct network representation of the physical cyber network is used as the underlying network in this case. Two of the interdiction models prove to be very effective arc removal methods for minimizing the spread of infection. We also develop multi-level network interdiction models that remove a subset of arcs to minimize the loss from multi-stage attacks. Our models capture the defenderattacker interaction in terms of stackelberg zero-sum games considering the attacker both as a complete rational and bounded rational agents. Our novel solution algorithms based on constraint and column generation and enhanced by heuristic methods efficiently solve the difficult multi-level mixed-integer programs with integer variables in all levels in reasonable times.

Cybersecurity has become an increasingly important concern for both military and civilian infrastructure globally. Because of the complexity that comes with wireless networks, adversaries have many means of infiltration and disruption of wireless networks. While there is much research done in defending these networks, understanding the robustness of these networks is tantamount for both designing new networks and examining possible security deficiencies in preexisting networks. This dissertation proposes to examine the robustness of wireless networks on three major fronts: the physical layer, the data-link layer, and the network layer. At the physical layer, denial-of-service jamming attacks are considered, and both additive interference and no interference are modeled in an optimal configuration and five common network topologies. At the data-link layer, data transmission efficacy and denial-of-sleep attacks are considered with the goal of maximizing throughput under a constrained lifetime. At the network layer, valid and anomalous communications are considered with the goal of classifying those anomalous communications apart from valid ones. This dissertation proposes that a thorough analysis of the aforementioned three layers provides valuable insights to robustness on general wireless networks.

[pt] A propagação de influências tem sido objeto de extensos estudos devido a seu importante impacto em redes sociais, epidemiologia e muitas outras áreas. A compreensão do mecanismo de propagação é crítica, por exemplo, para controlar a disseminação de notícias falsas ou controlar uma epidemia. Neste trabalho, seguimos uma perspectiva de otimização e identificamos o menor grupo de usuários que precisam ser convertidos para atingir um certo nível de influência em toda a rede. Portanto, estudamos formalmente o problema de influência de menor custo generalizado, propondo algoritmos de programação matemática para resolver este problema. Introduzimos novos algoritmos de planos de corte e separação, e os incorporamos em um algoritmo de branch-and-cut. Nossos resultados experimentais em instâncias da literatura demonstram a capacidade do método de resolver pequenas e médias instâncias, bem como diminuir o gap da melhor solução conhecida e inclusive encontrando também soluções ótimas para alguns problemas em aberto. / [en] Influence propagation has been the subject of extensive study due to its important role in social networks, epidemiology, and many other areas. Understanding the propagation mechanism is critical, e.g., to control the spread of fake news or to control an epidemic. In this work, we follow an optimization perspective, and attempt to identify the smallest group of users that needs to be converted to achieve an certain influence level over the entire network. We therefore formally study the generalized least cost influence problem, proposing mathematical programming algorithms to solve the challenging problem. We introduce new cutting plane and separation algorithms and embed them into a branch-and-cut algorithm. Our experimental results on classical benchmark instances demonstrates the method ability to solve small-to medium-scale benchmark instances, also finding optimal solutions for some open problems.