Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Please read the abstract (Summary) in the section 00front of this document / Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007. / Electrical, Electronic and Computer Engineering / MEng / Unrestricted

Location-allocation problems can be described generically as follows: Given the location or distribution (perhaps, probabilistic) of a set of customers and their associated demands for a given product or service, determine the optimum location of a number of service facilities and the allocation of products or services from facilities to customers, so as to minimize total (expected) location and transportation costs. This study is concerned with a particular subclass of location-allocation problems involving capacitated facilities and a continuum of demand. Specifically, two minisum, network-based location-allocation problems are analyzed in which facilities having known finite capacities are to be located so as to optimally supply/serve a known continuum of demand. The first problem considered herein, is an absolute p-median problem in which p > l capacitated facilities are to be located on a chain graph having both nodal and link demands, the latter of which are defined by nonnegative, integrable demand functions. In addition, the problem is balanced, in that it is assumed the total demand equals the total supply. An exact solution procedure is developed, wherein the optimality of a certain location-allocation scheme (for any given ordering of the facilities) is used to effect a branch and bound approach by which one can identify an optimal solution to the problem. Results from the chain graph analysis are then used to develop an algorithm with which one can solve a dynamic, sequential location-allocation problem in which a single facility per period is required to be located on the chain. Finally, an exact solution procedure is developed for locating a capacitated, absolute 2-median on a tree graph having both nodal and link demands and for which the total demand is again equal to the total supply. This procedure utilizes an algorithm to construct two subtrees, each of whose ends constitute a set of candidate optimal locations for one of the two elements of an absolute 2-median. Additional localization results are used to further reduce the number of candidate pairs (of ends) that need to be considered, and then a post-localization analysis provides efficient methods of comparing the relative costs of the remaining pairs. / Ph. D.

Not available / text

Orientadores: Edson Moschim, Felipe Rudge Barbosa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T16:46:35Z (GMT). No. of bitstreams: 1 Martins_IndayaraBertoldi_M.pdf: 1239150 bytes, checksum: 785fa753532d04d698ee47a542591430 (MD5) Previous issue date: 2007 / Resumo: Neste trabalho investigamos o desempenho de redes ópticas avançadas, em particular redes de chaveamento de pacotes ópticos (Optical Packet Switching Network-OPSN), constituídos por arquiteturas com topologias em malha e nós ópticos sem armazenador. Utilizou-se distribuição de tráfego uniforme, na qual todos os nós geram a mesma quantidade de tráfego para todos os outros nós. Foram avaliados vários parâmetros de redes OPSN, principalmente número médio de saltos e capacidade efetiva da rede, bem como comparações entre topologias anel e malha, considerando como parâmetros principais vazão e desempenho, e os impactos causados por falhas de enlaces. Demonstrouse também que o aumento do número de nós em OPSNs, não necessariamente aumenta o desempenho ou capacidade / Abstract: In this work we have investigated the performance of advanced optical networks, more specifically optical packet switched networks (OPSN), with architectures comprising fully connected mesh topologies and optical bufferless nodes. We have adopted uniform traffic distribution, in which all nodes generate the same traffic to every other node. Several parameters of the OPSNs have been evaluated, mainly average number of hops and effective network capacity, as well as comparisons between the ring and mesh network topologies, considering as main parameters the network throughput and performance, and the impacts caused by failures of links. We demonstrate that increasing the number of nodes in OSPNs does not necessarily increase performance or capacity / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

by Arjang A. Assad. / Includes bibliographical references. / Supported in part by the U.S. Department of Transportation, Transportation Advanced Research Program (TARP) DOT-TSC-1058

In this thesis we develop integer programming approaches for solving network flow problems with equal-split restrictions. Such problems arise in traffic engineering of internet protocol networks. Equal-split structure is used in protocols like OSPF and IS-IS that allow flow to be split among the multiple shortest paths. Equal-split assumptions also arise in peer-to-peer networks and road optimization problems. All the previous work on this problem has been focused on developing heuristic methods for the specific applications. We are the first ones to study the problem as a general network flow problem and provide a polyhedral study. First we consider a general multi-commodity network flow problem with equal split restrictions. This problem is NP-hard in general. We perform a polyhedral study on mixed integer linear programming formulation for this problem. Valid inequalities are obtained, and are incorporated within a branch-and-cut framework to solve the problem. We provide fast separation schemes for most of the families of valid inequalities. Computational results are presented to show the effectiveness of cutting plane families. Next, we consider the OSPF weight setting problem. We propose an integer programming formulation for this problem. A decomposition based approach to solve the problem is presented next. Valid inequalities, exploiting the structure, are obtained for this problem. We also propose heuristic methods to get good starting solutions for the problem. The proposed cutting planes and heuristic methods are integrated within a branch-and-cut framework to solve the problem. We present computational experiments that demonstrate the effectiveness of our approach to obtain solutions with tight optimality gaps as compared with default CPLEX. Finally, we consider an equal split flow problem on bipartite graphs. We present an integer programming formulation for this problem that models the equal-split in a different way than the multi-commodity network flow problem discussed before. Valid inequalities and heuristic methods for this problem are proposed, and are integrated within the branch-and-cut framework. We present computational experiments demonstrating the effectiveness of our solution strategy. We present an alternate formulation for the problem with some favorable polyhedral properties. Lastly, a computational comparison between the two formulations is presented.

Graphs are a fundamental and widely-used abstraction for representing data. We can analytically study interesting aspects of real-world complex systems such as the Internet, social systems, transportation networks, and biological interaction data by modeling them as graphs. Graph-theoretic and combinatorial problems are also pervasive in scientific computing and engineering applications. In this dissertation, we address the problem of analyzing large-scale complex networks that represent interactions between hundreds of thousands to billions of entities. We present SNAP, a new high-performance computational framework for efficiently processing graph-theoretic queries on massive datasets. Graph analysis is computationally very different from traditional scientific computing, and solving massive graph-theoretic problems on current high performance computing systems is challenging due to several reasons. First, real-world graphs are often characterized by a low diameter and unbalanced degree distributions, and are difficult to partition on parallel systems. Second, parallel algorithms for solving graph-theoretic problems are typically memory intensive, and the memory accesses are fine-grained and highly irregular. The primary contributions of this dissertation are the design and implementation of novel parallel graph algorithms for traversal, shortest paths, and centrality computations, optimized for the small-world network topology, and high-performance multithreaded architectures and multicore servers. SNAP (Small-world Network Analysis and Partitioning) is a modular, open-source framework for the exploratory analysis and partitioning of large-scale networks. With SNAP, we demonstrate the capability to process massive graphs with billions of vertices and edges, and achieve up to two orders of magnitude speedup over state-of-the-art network analysis approaches. We also design a new parallel computing benchmark for characterizing the performance of graph-theoretic problems on high-end systems; study data representations for dynamic graph problems on parallel systems; and apply algorithms in SNAP to solve real-world problems in social network analysis and systems biology.

As cadeias de suprimentos tornaram-se um foco importante para a vantagem competitiva. O desempenho de uma empresa depende cada vez mais da sua capacidade de manter relacionamentos eficazes e eficientes com seus fornecedores e clientes. A empresa estendida, composta de vários parceiros, precisa ser dinamicamente formada, a fim de ser ágil e adaptável. De acordo com o paradigma de produção digital, as empresas têm que ser capazes de compartilhar e divulgar rapidamente informações sobre planejamento, projeto e fabricação de produtos. Além disso, devem responder a todas as determinantes técnicas e de negócios, bem como ser avaliada e certificada para o desempenho garantido. A presente pesquisa tem a intenção de apresentar uma solução para a composição da empresa estendida, dinamicamente formada, para aproveitar as oportunidades do mercado de forma rápida e eficiente. Um modelo de construção foi elaborado. Este modelo de construção consiste em: modelo de informação, modelo de protocolo e modelo de processo. O modelo de informação foi definido com base nos conceitos do Supply Chain Operations Reference Model - SCOR® (Modelo de Referência das Operações na Cadeia de Suprimentos). Neste modelo são definidas as informações para negociar a participação de empresas candidatas no estabelecimento dinâmico de uma rede para responder a uma dada exigência para o desenvolvimento e fabricação de produtos, em sete etapas como a seguir: request for information (solicitação da informação); request for qualification (solicitação da qualificação); alignment of strategy (alinhamento estratégico); request for proposal (solicitação da proposta), request for quotation (solicitação da cotação), compatibility of process (compatibilidade de processo); e compatibility of system (compatibilidade de sistema). O modelo de protocolo foi elaborado inspirado no modelo OSI, este modelo fornece uma estrutura para a ligação entre clientes e fornecedores, indica a ordem dos passos a serem seguidos, a fim de selecionar empresas para tornarem-se fornecedores. O modelo de processo foi implementado por meio de modelagem de processos de acordo com o padrão BPMN. Por sua vez, implementado com um aplicativo baseado na web que executa o processo através das suas várias etapas e utiliza formas de coletar dados. Um exemplo de aplicação no âmbito da indústria do petróleo e gás é usado para demonstrar o conceito da solução. / Supply chains have become an important focus for competitive advantage. The performance of a company increasingly depends on its ability to maintain effective and efficient relationships with its suppliers and customers. The extended enterprise (i.e. composed of several partners) needs to be dynamically formed in order to be agile and adaptable. According to the Digital Manufacturing paradigm, companies have to be able to quickly share and disseminate information regarding planning, designing and manufacturing of products. Additionally, they must be responsive to all technical and business determinants, as well as be assessed and certified for guaranteed performance. The current research intends to present a solution for the dynamic composition of the extended enterprise, formed to take advantage of market opportunities quickly and efficiently. A construction model was developed. This construction model consists of: information model, protocol model and process model. The information model has been defined based on the concepts of Supply Chain Operations Reference model (SCOR®). In this model is defined information for negotiating the participation of candidate companies in the dynamic establishment of a network for responding to a given demand for developing and manufacturing products, in seven steps as follows: request for information; request for qualification; alignment of strategy; request for proposal; request for quotation; compatibility of process; and compatibility of system. The protocol model has been elaborated and inspired in the OSI, this model provides a framework for linking customers and suppliers, indicates a sequence to be followed, in order to selecte companies to become suppliers. The process model has been implemented by means of process modeling according to the BPMN standard and, in turn, implemented as a web-based application that runs the process through its several steps, which uses forms to gather data. An application example in the context of the oil and gas industry is used for demonstrating the solution concept.

As cadeias de suprimentos tornaram-se um foco importante para a vantagem competitiva. O desempenho de uma empresa depende cada vez mais da sua capacidade de manter relacionamentos eficazes e eficientes com seus fornecedores e clientes. A empresa estendida, composta de vários parceiros, precisa ser dinamicamente formada, a fim de ser ágil e adaptável. De acordo com o paradigma de produção digital, as empresas têm que ser capazes de compartilhar e divulgar rapidamente informações sobre planejamento, projeto e fabricação de produtos. Além disso, devem responder a todas as determinantes técnicas e de negócios, bem como ser avaliada e certificada para o desempenho garantido. A presente pesquisa tem a intenção de apresentar uma solução para a composição da empresa estendida, dinamicamente formada, para aproveitar as oportunidades do mercado de forma rápida e eficiente. Um modelo de construção foi elaborado. Este modelo de construção consiste em: modelo de informação, modelo de protocolo e modelo de processo. O modelo de informação foi definido com base nos conceitos do Supply Chain Operations Reference Model - SCOR® (Modelo de Referência das Operações na Cadeia de Suprimentos). Neste modelo são definidas as informações para negociar a participação de empresas candidatas no estabelecimento dinâmico de uma rede para responder a uma dada exigência para o desenvolvimento e fabricação de produtos, em sete etapas como a seguir: request for information (solicitação da informação); request for qualification (solicitação da qualificação); alignment of strategy (alinhamento estratégico); request for proposal (solicitação da proposta), request for quotation (solicitação da cotação), compatibility of process (compatibilidade de processo); e compatibility of system (compatibilidade de sistema). O modelo de protocolo foi elaborado inspirado no modelo OSI, este modelo fornece uma estrutura para a ligação entre clientes e fornecedores, indica a ordem dos passos a serem seguidos, a fim de selecionar empresas para tornarem-se fornecedores. O modelo de processo foi implementado por meio de modelagem de processos de acordo com o padrão BPMN. Por sua vez, implementado com um aplicativo baseado na web que executa o processo através das suas várias etapas e utiliza formas de coletar dados. Um exemplo de aplicação no âmbito da indústria do petróleo e gás é usado para demonstrar o conceito da solução. / Supply chains have become an important focus for competitive advantage. The performance of a company increasingly depends on its ability to maintain effective and efficient relationships with its suppliers and customers. The extended enterprise (i.e. composed of several partners) needs to be dynamically formed in order to be agile and adaptable. According to the Digital Manufacturing paradigm, companies have to be able to quickly share and disseminate information regarding planning, designing and manufacturing of products. Additionally, they must be responsive to all technical and business determinants, as well as be assessed and certified for guaranteed performance. The current research intends to present a solution for the dynamic composition of the extended enterprise, formed to take advantage of market opportunities quickly and efficiently. A construction model was developed. This construction model consists of: information model, protocol model and process model. The information model has been defined based on the concepts of Supply Chain Operations Reference model (SCOR®). In this model is defined information for negotiating the participation of candidate companies in the dynamic establishment of a network for responding to a given demand for developing and manufacturing products, in seven steps as follows: request for information; request for qualification; alignment of strategy; request for proposal; request for quotation; compatibility of process; and compatibility of system. The protocol model has been elaborated and inspired in the OSI, this model provides a framework for linking customers and suppliers, indicates a sequence to be followed, in order to selecte companies to become suppliers. The process model has been implemented by means of process modeling according to the BPMN standard and, in turn, implemented as a web-based application that runs the process through its several steps, which uses forms to gather data. An application example in the context of the oil and gas industry is used for demonstrating the solution concept.